HyperLogLogを使ったカーディナリティの推測（補足）
少し、こちらのフォローアップ記事となります。
ブログ公開後、何件かコメントをいただきました。
PG-StromでCOUNT(distinct KEY) にHyperLogLogを使うお話。専用の関数を使うのかと思ったら、パラメータのon/offでCOUNT自体の計算方法（実行計画）を変えるのか。
— こば - as a DB Engineer - (@tzkb) 2021年9月25日
Citusにも同様の仕組みがあって、そちらはerror_rateを指定するのかな。 https://t.co/Z4JCh8EoHQ
ありがとうございます。個人的にはhll_count(KEY) が好みです。古い人間なので、COUNTは正確な結果だと思い込みがちです。
— こば - as a DB Engineer - (@tzkb) 2021年9月25日
ちなみに図中にあるHLL Registersは、sketchと言われるものなのでしょうか。
なるほど確かに、GUCパラメータの値に応じてCOUNT(distinct KEY)を置き換える構造だと、そのつもりがないのに、HyperLogLogを使ったカーディナリティの推計を行ってしまう・・・という事故が発生してしまうかもしれぬ。
という事で、前回の記事で説明したpg_strom.enable_hll_countは廃止し、代わりに、ユーザが明示的にHyperLogLogを使用する事を教えるために、hll_count(KEY)という集約関数を追加しています。
使用法としてはこんな感じ。
=# select hll_count(lo_custkey) from lineorder ; hll_count ----------- 2005437 (1 row)
さらにもう一点、hll_count(KEY)はHyperLogLogを使って作成したHLL Sketch（前回記事でHLL Registersと呼んでいたもの。用語を統一。）を元に推計値を出す関数ですが、推計値を出すのではなく、そのままHLL Sketchをbytea型で保存できるようにしました。
こちらは、hll_sketch(KEY)という集約関数になり、あとで保存しておいたHLL Sketchをhll_merge(SKETCH)に食わせて、改めて推計値を出力できるようになります。
使い方としては、例えば、予め週次や月次のデータで HLL Sketch を作成しておけば、あとで必要な範囲だけの HLL Sketch をマージしてカーディナリティの推計値を出力するといった使い方が考えられます。
使用法としてはこんな感じ。
--- 年単位で HLL Sketch を出力する
=# select lo_orderdate / 10000 as year, hll_sketch(lo_custkey) as sketch
into pg_temp.annual
from lineorder group by 1;
SELECT 7
--- HLL Sketchをヒストグラムにして出力する
=# select year, hll_sketch_histogram(sketch) from pg_temp.annual order by year;
year | hll_sketch_histogram
------+-------------------------------------------------------
1992 | {0,0,0,0,0,0,0,0,0,22,73,132,118,82,39,26,12,2,4,2}
1993 | {0,0,0,0,0,0,0,0,0,9,59,118,125,96,50,30,15,2,6,2}
1994 | {0,0,0,0,0,0,0,0,0,4,33,111,133,113,53,36,17,4,6,2}
1995 | {0,0,0,0,0,0,0,0,0,2,21,99,131,121,62,42,18,5,7,3,1}
1996 | {0,0,0,0,0,0,0,0,0,1,17,84,119,131,73,50,20,5,7,4,1}
1997 | {0,0,0,0,0,0,0,0,0,0,14,71,118,128,82,53,23,10,7,4,2}
1998 | {0,0,0,0,0,0,0,0,0,0,13,64,114,126,86,61,23,11,8,4,2}
(7 rows)
--- 累積値で lo_custkey のカーディナリティを推測
=# select max_y, (select hll_merge(sketch) from pg_temp.annual where year < max_y)
from generate_series(1993,1999) max_y;
max_y | hll_merge
-------+-----------
1993 | 854093
1994 | 1052429
1995 | 1299916
1996 | 1514915
1997 | 1700274
1998 | 1889527
1999 | 2005437
(7 rows)例えば、ユニークユーザ数の集計を日次・週次で集計する時など、毎回 COUNT(distinct KEY)でやっていては遅くてたまらない、みたいな状況であれば、利用価値のある手法かもしれません。
本日、PostgreSQL Unconference (online) にてこの辺のトピックについて話しますので、お時間ある方はぜひご覧ください。
pgunconf.connpass.com
