概要
Citus Dataの許諾を得て翻訳・公開いたします。
- 英語記事: TopN for your Postgres database
- 原文公開日: 2018/03/27
- 著者: Furkan Sahin
- サイト: Citus Data -- PostgreSQLのクラウドスケーリングサービスを得意とするデータベース企業です。
PostgreSQLデータベースで「トップN」集計をうまく扱うTopN extension（翻訳）
人間は人気の高いものを愛するようです。開発者も含めた私たちの多くも、やはりそうだと思います。Spotifyが「2017年版あなたのトップソング」をリリースしたときに、私のように興奮のあまりリストの曲を片っ端から聞きまくった人もいますよね（ちなみに私のリストはこちら）？アカデミー賞発表の季節になれば、候補者や受賞者をチェックしまくりますし、冬季オリンピックでは誰がメダルを取ったかとか得点上位のホッケーチームが気になります。
あるリストの上位を検索する問題は「トップK問題」（Top K problem）または「トップN問題」（Top "N" problem）と呼ばれることがあります。総売上の上位にランクインしたかどうかとか、Webサイトで訪問者数の多いページの上位かどうかなど、それをトップKと呼ぶかトップNと呼ぶかはさておき、私たちの多くはたいてい「トップN位」を知りたがるものです。
「トップN」を知るのは簡単ではない
一般的に、頻度の高い上位項目を検索するには全レコードを通しでカウントする必要があります。Webアプリのクリック数をカウントしたり、曲の再生数をカウントしたり、プロジェクトのダウンロード数をカウントしたりなど、これらはいずれもカウントに関連します。PostgreSQLでのカウントやソート、リストの絞り込みの方法は至極簡単ですし、データセットが比較的小さい場合はとてもうまくいきます。イベント数が数千件になったとしても、今どきのコンピュータはかなり高速なのでさほど問題にはなりません。数百万件になってもこなせます。しかしさすがに数十億件ともなるとちょっと待たされるかもしれません。
しかし、種類の異なるさまざまな項目ごとに個数をデータベースから得てそれらをソートし、そのトップNを得ようとすると、規模が大きくなったときに難易度が相当高くなります。
さらに、トップNの結果をマテリアライズしてもっと小さなデータセットを恒常的に使えるようにし、クエリをいくつか組み合わせてさらなる分析を行おうとしたらどうなるでしょうか。ここから本当の問題が始まるのです。トップNの算出は困難になることがあります。これこそが、Citus Data社（PostgreSQLで水平スケールするためのCitus extensionを開発しています）の我がチームがこのたびPostgreSQL用TopN extensionをオープンソースとしてリリースした理由です。
訳注: マテリアライズドビューについてはこちらもどうぞ。
TopN extension開発のきっかけは、Citus Data社のある顧客のところで、PostgreSQLデータベースをスケールするCitus extensionと協調できるTopN的な機能を使う必要が生じたことでした。TopN機能の設計では、これをPostgreSQL拡張として実装することと、TopNをC言語で記述することを決定しました。TopN extensionの出力はJSONBオブジェクトなのでさまざまなユースケースで柔軟に利用でき、JSONBを入力として受け取って結合できる集計関数も含まれています。
TopN extensionは、あるカラムで最も頻度の高い値を算出でき、「スケッチアルゴリズム」と呼ばれる「確率的個別アルゴリズム（probabilistic distinct algorithms）」のクラスに属します。それでは、TopN extensionがPostgreSQLで実際に動くしくみをもう少し詳しく見ていきましょう。
訳注: probabilistic distinctの定訳が見当たらないため仮訳としています。
カウントごとに要素をマップする
TopN extensionはサイズ固定のハッシュマップ構造で、データをマップに集約します。サイズはtopn.number_of_countersと呼ばれるGUC（Grand Unified Configuration）で設定できます。この変数は基本的に、私たちが関心を持っている1つの集合の個別の要素数を定義します。より正確に言うと、ハッシュマップのサイズは1回の集約でnumber_of_countersの3倍まで拡大できるようにしています。個別データのカウントの数がこの個数を超えると、参照頻度が少ない方の半分を捨てて集約を続行します。
TopN extensionはテキスト値を扱う
TopN extensionは入力としてテキストデータ型を取ります。TopN extensionを非テキストカラムにも使いたい場合は、既存のデータ型をテキストにキャストできます。オブジェクトをどうしてもテキストにキャストする必要がある場合、結果のTopNリストも結果のテキスト型になります。
結果をJSONで得る
データの取り込みが完了して「トップN」要素数がハッシュマップに保存されると、要素とその頻度を含むこのハッシュマップがJSONBオブジェクトに含まれて返されます。集計したカウントをデータベースに保存したことのある方もいらっしゃるでしょう。そうしたデータをTopN extensionが生成したJSONBと併用することもできます。それぞれの結果を組み合わせて、集約された結合関数で詳細な分析を行えます。GINインデックスを作成して、カウント済みのオブジェクトをリアルタイムでスキャンすることもできます。
TopNのマテリアライズと継続的分析
Citus Dataでは、Citus distributed databaseのある顧客向けに同様のユースケースを提供するために、2018年の最初の週にgithub_eventsデータセットを取り出しました。以下を実行してダウンロードすると、同じテストを行うことができます。
wget http://data.githubarchive.org/2018-01-{01..07}-{0..23}.json.gz
データを取り込んで、日付がnullのバケットの一部を除去した後のデータサイズは次のようになりました。
# select pg_size_pretty(pg_total_relation_size('github_events'));
pg_size_pretty
----------------
7906 MB
(1 row)
このデータセットには7日分のイベントが含まれています。仮に、私たちがユーザー向けのダッシュボードを提供していて、ユーザーがそこでリポジトリの動きを日ごとに分析できるようになっているとしましょう。日別のTopN要素を集約して保存するには、次のようにします。
# create table aggregated_topns (day date, topn jsonb);
CREATE TABLE
Time: 9.593 ms
# insert into aggregated_topns select date_trunc('day', created_at), topn_add_agg((repo::json)->> 'name') as topn from github_events group by 1;
INSERT 0 7
Time: 34904.259 ms (00:34.904)
ここでは日別のトップ1000リポジトリを算出し、結果を私たちの集約テーブルにINSERTしています。
ユーザーが新年の2日目や3日目のトップテン要素を知りたいのであれば、2つのTopN JSONBを結合するだけでできます。
postgres=# select (topn(topn_union_agg(topn), 10)).* from aggregated_topns where day IN ('2018-01-02', '2018-01-03');
item | frequency
------------------------------------------------+-----------
dipper-github-fra-sin-syd-nrt/test-ruby-sample | 12489
wangshub/wechat_jump_game | 6402
shenzhouzd/update | 6170
SCons/scons | 4593
TheDimPause/thedimpause.github.io | 3964
nicopeters/sigrhtest | 3740
curtclifton/curtclifton.github.io | 3345
CreatorB/hackerdroid | 3206
dipper-github-icn-bom-cdg/test-ruby-sample | 3126
dotclear/dotclear | 2992
(10 rows)
Time: 7.750 ms
ユーザーが最初の3日間の日別のトップ2を知りたい場合も、かなり簡単にできます。
postgres=# select day, (topn(topn, 2)).* from aggregated_topns where day IN ('2018-01-01', '2018-01-02', '2018-01-03');
day | item | frequency
------------+------------------------------------------------+-----------
2018-01-01 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 9179
2018-01-01 | shenzhouzd/update | 4543
2018-01-02 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 7151
2018-01-02 | SCons/scons | 4593
2018-01-03 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 5338
2018-01-03 | CreatorB/hackerdroid | 3206
(6 rows)
Time: 4.037 ms
新しいTopN extensionを今すぐPostgreSQLでお試しください
TopNやHyperLogLogのようなスケッチアルゴリズムは、価値ある情報をより簡単に算出する大きな力をもたらします。Citus Dataは、PostgreSQL向けのTopN extensionを開発し、PostgreSQLコミュニティのユーザーや開発者の皆さまにお使いいただけるようになったことを嬉しく思います。
トップN位を今日にでも算出して保存したいとお思いの方は、ぜひこちらにてTopN extensionをお試しください。
お楽しみいただけましたでしょうか？
弊社チームの技術記事をもっとお読みになりたい方は、元記事末尾の弊社の月刊ニュースレターにサインインいただければ最新情報をメールで直接配信いたします。
社内Slackより
TopNを全件データから流すのは大抵辛くなるから、仕様段階で条件付けることも多いかなあ。
良くあるのはバッチで計算しておくとか: 条件を柔軟に変えられない代わりに、安定はする。
あとよく見るのはRedis使ってランキングデータカウントするみたいなやつ: RDBMSで集計用のテーブル作って…とかやり始めると、大体とても辛くなる（データ整合性を保つためにメンテナンスするのがとても重くなったりする。
最近ならElasticSearchに全部突っ込むとか、AWS RedShiftみたいな列指向DBを使ったりとかも。