X

Big Data、Data Integration、Data Lakeに関するテクノロジー、製品・サービス情報、セミナー情報などをお届けします

Big Data SQL - JOIN性能を向上するBloom Filter(ブルーム・フィルター)

Big Data SQLはOracle Databaseから素晴らしい機能を継承しています。ひとつはBloom Filter(ブルーム・フィルター)の活用です。この機能はOracle10g以降で利用可能で、JOIN性能の向上に使われます。具体例を示す前に、Bloom Filterとは何かを説明しましょう。

Bloom Filter 概要 1). Input

Bloom Filterは「要素Xは集合Yに存在するか?」というシンプルな問いに答える事ができるデータ構造です。答えは「絶対に違う」もしくは「存在するかもしれない」のどちらかになります。

Bloom Filterはビット配列であり、Bloom Filter の「配列の長さ」と、「複数のハッシュ関数(値に対し、配列の長さに準じた値を返す、例えば配列長が12なら1~12のどれかを返す)」が定義されています。

これから、集合Y("oracle",  "database", "filter"の3つの要素からなる)に、ある要素(例:"bytes")は、存在するか?について、調べていきます。

Input:
  1. データセット ※このデータセット(=集合Y)に対して、Bloom Filterを作成していきます。
    集合Y ["oracle",  "database", "filter"]

  2. Bloom Filterの長さ。ここではBloom Filterの配列の長さを12とします。

  3. ハッシュ関数のセット。ここでは次の3つのハッシュ関数:h1, h2, h3 があり、それぞれは1~12の数値を返します。(なぜなら配列の長さを12と決めたから)

Bloom Filter 概要 2). Bloom Filter の作成

Bloom Filterを作成するには、

  • それぞれのハッシュ関数を、集合Yのそれぞれの要素に適用する
  • 上で得られた結果でBloom Filterにマーキングする

これらを以下に図示します。例えば、h1("oracle")=1、つまり、ハッシュ関数 h1 に "oracle"をかけた結果は1なので、ビット配列であるBloom Filterの1番目にマークをつけます。

 

 

実際には、Bloom Filter配列内の各要素に、いくつのチェックがついているかは気にしないので、このFilterをBooleanでマークし直します。(1つ以上のマークがついたかどうかをTRUE or FALSEで示します。)

 

 

集合Y("oracle", "database", "filter")に対するBloom Filterの作成が完了し、利用する準備ができました。

Bloom Filter 概要 3). Bloom Filter を使用

さあ、Bloom Filterを使いましょう。今ここに集合Y("oracle", "database", "filter")があり、この配列にある要素が存在するか否かをチェックしなければなりません。

まず、要素="oracle"の存在をチェックしたいとします。ここで必要なのは、全てのハッシュ関数を"oracle"に適用した結果を計算し、Bloom Filterとの適合をチェックすることです。

 

"oracle"は、Bloom Filterの全ての埋められた要素と一致するので、答えは「この要素は集合Yに含まれるかもしれない」。しかしなぜ「かもしれない」なのでしょうか?他の例を挙げて考えてみましょう。

次に、"Alex"という要素がこの集合Yに存在するかどうかをチェックしたいです。

Bloom Filterの1番目, 2番目, 7番目のマークを確認してみると、

  • Bloom Filterの要素1はTRUEとマークされている、なぜならh1("oracle")=1
  • Bloom Filterの要素2はTRUEとマークされている、なぜならh1("database")=2
  • Bloom Filterの要素7はTRUEとマークされている、なぜならh2("filter")=7

従って、要素"Alex"に対するハッシュ関数の結果は、Bloom Filterに合致します。つまり、要素"Alex"は、Bloom Filterのマーク済み要素と全て一致するので、答えは「"Alex"は集合Yに含まれるかもしれない」です。


では、Bloom Filterの利点は何でしょうか?それは「絶対違う」といえる場合です。次の例として、要素 "byte"の存在を確認してみましょう。

h2("byte")が6を返すがこれはFALSEです。つまり、要素"byte"は、集合Yの中に絶対に含まれません。

このように、「絶対違う」場合に、何かをしなくてよい(Oracle DatabaseのBloom Filter を使ったJOINでの例でいうと、データをJOIN対象としなくてよい)ことが、Bloom Filterを使うメリットになります。

実行計画でBloom Filterを確認しよう

Oracle DatabaseでBloom Filterを使うのに、2つのステップが必要です。小さいテーブルに対しBloom Filterを作成し、それを大きなテーブルに適用することです。これらのステップは実行計画では"JOIN FILTER CREATE"と"JOIN FILTER USE"として現れます。

 

Bloom Filter と Big Data SQL: テーブルが全てHadoopにある場合

実際のケースに適用してみましょう。巨大なファクト表と、小さなディメンション表を用意します。どちらもHadoop上に格納されています。

SQL> SELECT COUNT(1) FROM store_sales_orc;
6385178703
SQL> SELECT COUNT(1) FROM  date_dim_orc;  
109573

 

テスト目的でクエリを準備します。TPCDSベンチマークテストから選びました。実行計画を読みやすくするために、NOPARALLELヒントを使用しました。

SQL> SELECT *  FROM
(SELECT /*+ NOPARALLEL*/ dt.d_year, SUM(ss_ext_sales_price) sum_agg  
FROM date_dim_orc dt, store_sales_orc
WHERE
dt.d_date_sk = store_sales_orc.ss_sold_date_sk
AND dt.d_moy = 12
GROUP BY dt.d_year        
ORDER BY dt.d_year,
     sum_agg DESC)
WHERE rownum <= 100;

実行計画は以下です。

実行計画などから、次のことが分かります。

  • 小さい表(DATA_DIM_ORC)に対しBloom Filterが作成される(“JOIN FILTER CREATE” ステップ)。軽い処理。
  • 大きい表(STORE_SALES_ORC)に対し Bloom Filterが適用される(“JOIN FILTER USE”ステップ)。重い処理。
  • Bloom Filterは91%のデータを除去した。(Actual Rows列より598M行と表示されているが、これはSTORES_SALES_ORC表の行数の9%である)。Bloom Filterの効果は、テーブルの実際行で割ることで計算できるだろう
  • これらの全てのステップはHadoop側で行われている(Database側ではない)
  • Databaseは最終的なJOINを行う

ではどのくらいの量のデータがデータベースに転送されたか見てみましょう。2つの統計に注目します。

  • "cell XT granule bytes requested for predicate offload" スキャンすべきデータサイズ(ディスク上にどれくらいのデータがあるか)
  • "cell interconnect bytes returned by XT smart scan" データベースに転送されたサイズ

SQL> SELECT n.name,
round(s.value/1024/1024/1024)
FROM v$mystat s, v$statname n
WHERE  s.statistic# IN (462,463)
AND s.statistic# = n.statistic#; 

cell XT granule bytes requested for predicate offload 229
cell interconnect bytes returned by XT smart scan     10

上記より、Databaseに転送されたのは10GBです。悪くないですね。

Bloom Filter と Big Data SQL: テーブルがDatabaseとHadoopにある場合

2つ目のテストケースを説明しましょう。巨大なファクト表はHadoopにあり、小さなディメンジョン表はDatabaseに格納されています。これは、極めて一般的な例です。なぜならディメンジョン表は頻繁に更新されるかもしれず(Database向き)、ファクト表は通常更新されない(Hadoop向き)からです。

同じテストを、テーブル名だけを変更して実行します。

SQL> SELECT *  FROM
(SELECT /*+ NOPARALLEL*/ dt.d_year, SUM(ss_ext_sales_price) sum_agg  
FROM date_dim_db dt, store_sales_orc
        WHERE
dt.d_date_sk = store_sales_orc.ss_sold_date_sk
AND dt.d_moy = 12
GROUP BY dt.d_year        
ORDER BY dt.d_year,
     sum_agg DESC)
WHERE rownum <= 100;

実行計画は同じです。

同じアプローチが使われていますが、1点だけ異なります。Bloom FilterはDatabase側で作成され(軽い処理)、それをHadoop(Cell)側に転送し、大きな表に対し適用しています。統計もよく似ています。

SQL> SELECT n.name,
round(s.value/1024/1024/1024)
FROM v$mystat s, v$statname n
WHERE  s.statistic# IN (462,463)
AND s.statistic# = n.statistic#; 

cell XT granule bytes requested for predicate offload 229
cell interconnect bytes returned by XT smart scan     8

性能の観点からはこれらのクエリはよく似ており、同じ実行時間を要します。(なぜならクエリの大部分の時間はBloom FilterをSTORE_SALES_ORC表に適用するところだからです)

まとめ

  • Bloom Filterは「要素Xは集合Yに存在するか?」というシンプルな問いに、「絶対に違う」もしくは「存在するかもしれない」で答えることができるもの
  • Oracle Databaseの機能で、Bloom Filterを使ってJOINする機能がある
    これは、JOIN前にファクト表の行数をBloom Filterで削減することで、高速化が期待できる
  • Big Data SQLでも、このOracle Databaseの機能を継承しており、Hadoop上にある大きなファクト表から「絶対に違う」データを除去するのに使用される

本投稿はBig Data SQL Quick Start. Joins. Bloom Filter and other features - Part5.を元に投稿しています。

 

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.