Instacartでは、主要業績評価指標（KPI）レポート作成、KPIトレンド分析、主要ディメンションにわたる当社のコアメトリックにおけるドロップまたはスパイクの決定にTableauを使用します。チームが日常業務においてより効率的かつデータ駆動になるよう支援するために、我々は高度なデータ探索のためのキュレーション抽出物を提供することにより、democratize our data（データの民主化）するためにTableauを使用します。 柔軟性とパフォーマンスのトレードオフにおいて、集約されたデータソースを構築するのではなく、きめ細かなデータ抽出を作成することを選択しました。

集約されたデータソースはパフォーマンスがはるかに高いものの、分析可能な多様性を制限しています。

私たちのデータ量は予測よりもはるかに速いため、このトレードオフは最近、多くのダッシュボードの負荷時間を（フィルタが適用されるたびに数秒から20〜30秒程度まで）低下させ始めました。

我々は、このスローダウンの根本原因の1つが、別個のカウントを含むメトリクスを学びました。 これらのメトリックは、集約されていないデータソースに必要とされるため、Tableauのパフォーマンスを向上させるための選択肢を検討し始めました。 InstacartのTableauライセンスは、現在そのような機能を提供していません。

Tableauでデータ抽出を行うために、確率的な計数アルゴリズムであるHyperLogLogを実装しました。 この記事では、Redshiftクラスタ（他のデータウェアハウスも同様に動作する）からデータソースを作成する方法と、TableauでHyperLogLogを実装するための関連するメジャー定義について説明します。

HyperLogLog Algorithm　（アルゴリズム）

HyperLogLogは、約1.6％の精度（4096個のレジスタを使用する）でデータセット内の別個のエレメントの数を推定するアルゴリズムです。 アルゴリズムは多くの場所で詳細に記述されており、かなり簡単なので、ここでは最も高いレベルでのみ説明します（アルゴリズムの詳細な説明はここ、ここには対応するシミュレーションです）。

HyperLogLogでは、セットの要素が最初にハッシュされてランダム性が確保され、バイナリに変換されてレジスタに追加されます。 レジスタは、先行ゼロの最長連続カウントを観察することによって、セット内で観測される最も起こりそうなイベントを格納します。 レジスタの最大値に基づいて、別個の要素のおおよその数を計算することができます。

以下の表は、合計セット内の要素のバイナリ表現（簡略化のために8ビットに制限されている）を考慮して、レジスタ内の所定数の先行ゼロを観察する可能性を示しています：

╔════════════════╦═══════════════╦═════════════════════════════════╗
║  Binary Hash   ║  Observation  ║   Distinct Elements             ║
║                ║  Probability  ║   1/Observation Probability     ║
╠════════════════╬═══════════════╬═════════════════════════════════╣
║  1XXXXXXX      ║  0.5          ║  2                              ║
║  01XXXXXX      ║  0.25         ║  4                              ║
║  001XXXXX      ║  0.125        ║  8                              ║
║  0001XXXX      ║  0.0625       ║  16                             ║
║  00001XXX      ║  0.03125      ║  32                             ║
║  000001XX      ║  0.015625     ║  64                             ║
║  0000001X      ║  0.0078125    ║  128                            ║
║  00000001      ║  0.00390625   ║  256                            ║
║  00000000      ║  0.001953125  ║  512                            ║
╚════════════════╩═══════════════╩═════════════════════════════════╝

たとえば、最長ランのゼロが4であった場合、32個の要素が推定されます。

この推定は、無作為にゼロの長いランを得ることによって大きく影響を受けることがあるので、要素の総数を多数のレジスタに分割し、平均化して別個の要素の総数を推定する。

我々のデータが2つのレジスタに分割され、最初のものが最大4つの先行ゼロを持ち、2つ目の先行ゼロが3つしかない場合、（32 + 16）/ 2 = 24の基数が見積もられます。 ハッシュの衝突の可能性を考慮する必要があります。 この調整係数はFlajolet et al.が元のHyperLogLog論文[10.1.1.76.4286]には次のように書かれています：

ハッシュ衝突調整係数

mはレジスタの総数です。 さらに、外れ値の影響を最小限に抑えるために、HyperLogLogは標準平均の代わりに調波平均(harmonic mean)を使用します。これにより、次の定式が得られます。

HyperLogLogカーディナリティ数式

M [j]は、レジスタmの最初の非ゼロ値の位置です。

RedshiftでのHyperLogLogの実装

Tableauのデータ抽出を準備する課題は、Tableauでこれらの非標準操作の一部を再作成し、結果レジスタをTableauに格納して、それらを組み合わせて多くの次元にわたる別個のカウントを決定することにあります。

このコード全体はここで見つけることができますが、繰り返しテキストを最小限に抑えるために、[PREVIOUS QUERYからのRESULTS]を使用して前のステップを参照して段階的に構築します。 まず、個体数とそれに関連する次元を取得する要素を選択します。 たとえば、所定の期間内にInstacartによって販売される個別の商品数を計算するには、次のようにします。

SELECT
date as dimension,
product_id as element
FROM sales

次に、product_id列をハッシュする必要があります。 Redshiftにはいくつかのハッシュ関数があります。 この例では、FUNC_SHA1関数で定義されたSHA-1実装を使用します。 結果として得られる16進数は、私たちが必要とするよりもはるかに高い精度を提供します（数値のRedshiftデータ型に格納することができます）。したがって、ハッシュとして14右端の文字のみを使用し、レジスタ番号として3左端の文字を使用します。

HyperLogLogの計算で使用されるハッシュの部分

要素はハッシュされているため、最初の3文字で表されるレジスタに疑似ランダム（pseudo-randomly）に割り当てられます。 同じ（数）値が常に同じレジスタに追加されます。 STRTOL関数を使用して、レジスタとハッシュの両方が16進数から10進数に変換されます。

SELECT
dimension,
element,
STRTOL(LEFT(FUNC_SHA1(element),3),16) register_number,
STRTOL(RIGHT(FUNC_SHA1(element),14),16) as hash
FROM (
[RESULTS from PREVIOUS QUERY]
)

次に、ハッシュをバイナリに変換する必要がありますが、Redshiftにはこれを実現する標準機能がありません。 UDFの書き込みがない場合、この操作はビットシフトによって実行できます（可読性と効率性の面でUDFが適していますが、適切な権限が必要です）。

SELECT
dimension,
element,
register_number,
((sha1>>0)%2)::varchar+
((sha1>>1)%2)::varchar+
…
((sha1>>54)%2)::varchar+
((sha1>>55)%2)::varchar as binary_hash
FROM (
[RESULTS from PREVIOUS QUERY]
)

要素の最初の非ゼロビットを決めるために、正規表現（Regular Expression）の部分文字列式を使うことができます：

SELECT
dimension,
element,
register_number,
LENGTH(NVL(REGEXP_SUBSTR(
binary_binary,’0*’),’’))+1 as first_non_zero
FROM (
[RESULTS from PREVIOUS QUERY]
)

最後に、ディメンションごとにグループ化（グループ）して、指定したグループの最長ランを見つける必要があります。

SELECT
dimension,
register,
MAX(first_non_zero) as first_non_zero
FROM (
[RESULTS from PREVIOUS QUERY]
)
GROUP BY
dimension,
register

最終的なクエリは、必要なレジスタを生成します。これは、別個のカウントを計算するためにTableauで組み合わせることができます。

TableauでのHyperLogLogの実装

ビジュアライゼーションを構築するために、私たちが上記で書いたクエリをとり、Tableauでそこからデータソースを作成します。 Tableauでは、要素の個数を計算するために2つの計算を実行する必要があります。 まず、特定のグループ内のレジスタごとに、最大で非ゼロの要素数を見つけなければなりません。 これは、以下に示す詳細レベルの計算で実行できます。

この計算された尺度が与えられると、定式を適用して基数推定を決定することができます。

基数推定のためのTableau計算
HyperLogLogの推定を、等価な個別のカウント操作と比較する方法を見てみましょう。

HyperLogLogの推定と実際の個別の推定の比較
些細な違いがありますが、実際のカウントが非常によく反映されており、HyperLogLogのバージョンが大幅に改善されていることがわかります。

パフォーマンス向上の測定

だから、この例でHyperLogLogがどれくらい助けてくれたのでしょうか？ Tableauの新しいバージョンでは、ダッシュボードをレンダリングする際に各操作に必要な時間を正確に測定することができます。 この機能を使って、この特定の例では、HyperLogLogアルゴリズムが異なるカウントを決定する際に〜50倍高速に実行されることがわかります。

HyperLogLogの個別カウントと、集約されていないデータソースからの同等の操作とのパフォーマンス比較。

さらに重要なのは、HyperLogLogアルゴリズムの計算コストが、データ量で線形にスケーリングするのではなく、データセットの次元数に比例するようになったことです。 その結果、私たちがTableauサーバー上でますます多くのデータを表示し続けるにつれて、それは潰すしません。

結論

多くの場合、Tableauは簡単な分析とトレンドツールとして使用されます。 このような場合、大きなデータセットを集約として実装した場合の1.6％のエラーは完全に受け入れられ、HyperLogLogアルゴリズムを使用すると、集約されていないデータセットの個別のカウントと比較してパフォーマンスが大幅に向上します。 最終的に、このテクニックは、チームにメトリックにすばやくアクセスし、重要な傾向を判断し、さらにデータ駆動型になるための別のツールを提供します。

Jon HsiehとMuffy Barkocyに感謝します。

タイトル：Implementing HyperLogLog in Redshift and Tableau

作者：Oliver Gothe

原文URL:https://tech.instacart.com/implementing-hyperloglog-in-redshift-and-tableau-a62081c98e1c