オンライン集約

オンライン集計は、高価な分析クエリを処理するデータベースシステムの対話型動作を改善するための手法です。ほぼすべてのデータベース操作はバッチモードで実行されます。つまり、ユーザーはクエリを発行し、データベースがクエリ全体の処理を完了するまで待機します。一方、オンライン集計を使用すると、ユーザーはクエリが発行されるとすぐに集計クエリの推定値をオンラインで取得します。たとえば、最終的な答えが 1000 の場合、k 秒後に、ユーザーは 95% の確率で [990, 1020] のような信頼区間の形式で推定値を取得します。この信頼度は、システムが取得するサンプルが増えるにつれて低下し続けます。

オンライン集約は、1997 年に Hellerstein、Haas、Wang ^[1]によって、単一テーブルに対するグループ化集約クエリ用に提案されました。その後、著者らは結合をオンラインで評価する方法を示しました。^[2] 2007 年に Jermaine らは、複数のテーブルに対するグループ化集約クエリをオンラインで、さらに重要なことにスケーラブルな方法で計算する Database-Online (または DBO) と呼ばれるプロトタイプデータベースシステムを設計および実装しました。^[3]オンライン集約のすべてのアプローチではランダムサンプリングが使用されますが、これは更新報酬理論の検査パラドックスのため、分散環境では簡単ではありません。2011 年に Pansare らは、検査パラドックスに対処するベイジアンモデルを提案し、 MapReduceのような環境向けにオンライン集約を実装しました。^[4]

参考文献

^ ヘラースタイン、ジョセフM.ピーター・J・ハース;ワン、ヘレン J. (1997 年 6 月)。「オンラインアグリゲーション」。SIGMOD Rec . 26 (2): 171–182。土井: 10.1145/253262.253291。
^ Haas, Peter ; Hellerstein, Joseph M. (1999 年 6 月). 「Ripple がオンライン集約に参加」SIGMOD Rec . 28 (2): 287–298. doi :10.1145/304181.304208.
^ Jermaine, Chris; Arumugam, Subramanian; Pol, Abhijit; Dobra, Alin (2007). 「DBO エンジンによるスケーラブルな近似クエリ処理」。2007 ACM SIGMOD 国際データ管理会議議事録。pp . 725–736。doi : 10.1145/1247480.1247560。ISBN 9781595936868. S2CID 13040670。
^ Pansare, Niketan; Borkar , Vinayak; Jermaine, Chris; Condie, Tyson (2011 年 8 月)。「大規模な MapReduce ジョブのオンライン集約」(PDF) 。VLDB。

[OLA-Hellerstein-1] ヘラースタイン、ジョセフM.ピーター・J・ハース;ワン、ヘレン J. (1997 年 6 月)。「オンラインアグリゲーション」。SIGMOD Rec . 26 (2): 171–182。土井: 10.1145/253262.253291。

[RippleJoin-2] Haas, Peter ; Hellerstein, Joseph M. (1999 年 6 月). 「Ripple がオンライン集約に参加」SIGMOD Rec . 28 (2): 287–298. doi :10.1145/304181.304208.

[DBO-3] Jermaine, Chris; Arumugam, Subramanian; Pol, Abhijit; Dobra, Alin (2007). 「DBO エンジンによるスケーラブルな近似クエリ処理」。2007 ACM SIGMOD 国際データ管理会議議事録。pp . 725–736。doi : 10.1145/1247480.1247560。ISBN 9781595936868. S2CID 13040670。

[OLA-MapReduce-4] ^ Pansare, Niketan; Borkar , Vinayak; Jermaine, Chris; Condie, Tyson (2011 年 8 月)。「大規模な MapReduce ジョブのオンライン集約」(PDF) 。VLDB。