過去の記事では、PostgreSQLのインデックス作成メカニズムとアクセス方法のインターフェース、およびハッシュインデックス、 Bツリー、 GiST 、 SP-GiST 、 GIN 、 RUM、およびBRINについて見てきました。ブルームインデックスを見るだけです。

ブルーム

一般的な考え方

クラシックブルームフィルターは、要素がセットに属しているかどうかをすばやく確認できるデータ構造です。フィルターは非常にコンパクトですが、誤検知を許可します：間違いを犯して要素をセットに属すると見なす権利（誤検知）がありますが、要素が実際にセットに存在する場合はセットに含まれていないと言う権利はありません（誤検知）。

フィルターは、長さがmビットのビットマップ（署名とも呼ばれます）であり、最初はゼロで埋められています。セットの任意の要素を署名のkビットにマッピングするK個の異なるハッシュ関数が選択されます。セットに要素を追加するには、署名でこれらの各ビットを1に設定する必要があります。したがって、要素に対応するすべてのビットが1に設定されている場合、要素はセットに存在する可能性があります。少なくとも1ビットがゼロの場合、要素は間違いなく欠落しています。

DBMSインデックスの場合、実際には各インデックス行に対してN個の個別のフィルターが構築されています。通常、インデックスにはいくつかのフィールドが含まれます。これらのフィールドの値は、各行の要素のセットを構成します。

署名サイズmを選択することにより、インデックスの量と誤検知の確率との間で妥協点を見つけることができます。ブルームインデックスの範囲は大きく、かなり「幅の広い」テーブルで、クエリはどのフィールドでもフィルタリングを使用できます。 BRINのようなこのアクセス方法は、シーケンシャルスキャンのアクセラレータと見なすことができます。インデックスによって検出されたすべての一致は、テーブルに従ってダブルチェックする必要がありますが、行の重要な部分をまったく考慮しない可能性があります。

装置

GiSTアクセス方法のコンテキストで署名ツリーについて既に説明しました。これらの木とは異なり、ブルームインデックスはフラットな構造です。メタページとそれに続くインデックス行のある通常のページで構成されます。図に模式的に示すように、各インデックス行には署名とテーブル行へのリンク（TID）が含まれています。

パラメーター値の作成と選択

ブルームインデックスを作成する場合、ストレージパラメータは、シグネチャの合計サイズ（長さ）と、インデックスに含まれる各フィールドに個別に設定されたビット数（col1 — col32）を示します。

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...);

ビット数を示す方法は奇妙に見えます。これらの数値はインデックスのパラメータではなく、演算子のクラスである必要があります。現在、演算子クラスはパラメータ化できませんが、これは現在進行中です。

適切な値を選択する方法は？理論では、偽フィルタの確率pを設定すると、署名の最適なビット数は次のように推定できると言われています。

m = −n log ₂ （p）/ ln（2）。ここで、 nはインデックス内のフィールドの数であり、設定されるビット数はk = −log ₂ （p）です。

インデックス内では、署名は2バイト整数の配列として格納されるため、 mの値は安全に16に切り上げられます。

確率pを選択するときは、インデックスのサイズを考慮する必要があります。これは、ほぼ

（m / 8 + 6）N。Nはテーブル内の行数、6はバイト単位のTIDポインターのサイズです。

いくつかのポイント：

偽陽性pの確率は、1つのフィルターを指します。テーブルをスキャンするときに、 Npの誤検出が発生することが予想されます（もちろん、いくつかの行を返すクエリの場合）。たとえば、100万行と平均0.01の確率を持つテーブルの場合、クエリ「インデックス再チェックによって削除された行：10000」に関して期待できます。
ブルームフィルターは確率構造です。非常に多くの値を平均化することによってのみ特定の数値について話すことは理にかなっており、それぞれの場合に必要なものを取得できます。
上記の推定値は、理想的な数学的モデルといくつかの仮定に基づいています。実際には、結果はほとんどの場合悪化します。したがって、式は冷静にとるべきです。これは、さらなる実験のために初期値を選択するための単なる方法です。
アクセス方法では、各フィールドに個別に設定するビット数を選択できます。実際、最適な数は列の値の分布に依存するという合理的な仮定があります。混乱したい場合は、たとえば、この記事を参照してください（他の研究へのリンクに感謝します）。しかし、最初に前の段落を読み直してください。

更新する

新しい行がテーブルに挿入されると、署名が形成されます。すべてのインデックス付きフィールドの値について、それらに対応するすべてのビットが単一に設定されます。古典的には、 k個の異なるハッシュ関数が必要です。実際には、それらは単一のハッシュ関数を使用して毎回選択されるシード要素である擬似乱数ジェネレーターによってバイパスされます。

通常のブルームフィルターは要素の削除をサポートしていませんが、これはブルームインデックスには必須ではありません。テーブルから行を削除すると、インデックス行とともに署名全体が削除されます。

通常の変更は、古いバージョンの行を削除して新しいバージョンを挿入することです（署名が再計算されます）。

スキャン

ブルームフィルターでできるのは要素がセットに属していることを確認することだけなので、ブルームインデックスでサポートされる唯一の操作は（ハッシュインデックスのように）等価性チェックです。

前述したように、ブルームインデックスはフラットであるため、インデックスアクセスでは常に行全体が読み取られます。読み取りプロセスでは、ビットマップが構築され、テーブルにアクセスするために使用されます。

従来のインデックスアクセスでは、いくつかのインデックスページを読み取る必要があると想定されており、さらにすぐに再び必要になる場合があります。したがって、それらはバッファキャッシュに格納されます。ブルームインデックスの読み取りは、実際には順次スキャンです。有用な情報がキャッシュから押し出されるのを防ぐために、テーブルを順番にスキャンするときのように、小さなバッファリングを介して読み取りが行われます。

ブルームインデックスのサイズが大きいほど、プランナーにとって魅力的ではないように見えることに注意してください。この依存関係は、ツリーインデックスとは対照的に線形です。

例

テーブル

例として前回の記事の大規模なflights_biテーブルを使用してブルームインデックスを見てみましょう。このテーブルのサイズは4 GBで、約3,000万行あることに注意してください。テーブル定義：

demo=# \d flights_bi 
      

        
        
        
      

     Table "bookings.flights_bi" 
      

        
        
        
      

     Column      |          Type          | Collation | Nullable | Default 
      

        
        
        
      

     --------------------+--------------------------+-----------+----------+--------- 
      

        
        
        
      

     airport_code      | character(3)            |          |          | 
      

        
        
        
      

     airport_coord      | point                    |          |          | 
      

        
        
        
      

     airport_utc_offset | interval                |          |          | 
      

        
        
        
      

     flight_no          | character(6)            |          |          | 
      

        
        
        
      

     flight_type        | text                    |          |          | 
      

        
        
        
      

     scheduled_time    | timestamp with time zone |          |          | 
      

        
        
        
      

     actual_time        | timestamp with time zone |          |          | 
      

        
        
        
      

     aircraft_code      | character(3)            |          |          | 
      

        
        
        
      

     seat_no            | character varying(4)    |          |          | 
      

        
        
        
      

     fare_conditions    | character varying(10)    |          |          | 
      

        
        
        
      

     passenger_id      | character varying(20)    |          |          | 
      

        
        
        
      

     passenger_name    | text                    |          |          |

拡張機能の作成から始めましょう-ブルームインデックスは、バージョン9.6以降の標準パッケージに含まれていますが、デフォルトでは使用できません。

demo=# create extension bloom; 
      

        
        
        
      

     CREATE EXTENSION

前回、BRINを使用して、3つのフィールド（scheduled_time、actual_time、airport_utc_offset）のインデックスを作成できました。ブルームインデックスは、データの物理的な場所に依存しないため、インデックス内のテーブルのほとんどすべてのフィールドを含めてみましょう。ただし、時間（scheduled_timeおよびactual_time）を除外します-このメソッドは等値比較のみをサポートしますが、正確な時間クエリは誰にとっても興味深いものではありません（式によってインデックスを構築し、時刻を1日に丸めることができますが、これは行いません）。また、空港の座標（airport_coord）を除外する必要があります-将来的には、ポイントタイプはサポートされていません。

パラメーターの値を選択するために、0.01の誤検知の確率を使用します（実際にはさらに多くなることがわかります）。 n = 9およびN = 30,000,000の上記の式は、96ビットの署名サイズを与え、要素ごとに7ビットを設定することを提案します。インデックスの推定サイズは515 MB（表の約8分の1）です。

（最小署名サイズが16ビットの場合、式は半分の低いインデックスを約束しますが、0.5の確率しか期待できません。これは本当に悪いです。）

演算子クラス

そのため、インデックスを作成しようとします。

demo=# create index flights_bi_bloom on flights_bi 
      

        
        
        
      

     using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) 
      

        
        
        
      

     with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 
      

        
        
        
      

     ERROR: data type character has no default operator class for access method "bloom" 
      

        
        
        
      

     HINT: You must specify an operator class for the index or define a default operator class for the data type.

悲しみ：拡張では、2つのクラスの演算子のみが与えられます。

demo=# select opcname, opcintype::regtype 
      

        
        
        
      

     from pg_opclass 
      

        
        
        
      

     where opcmethod = (select oid from pg_am where amname = 'bloom') 
      

        
        
        
      

     order by opcintype::regtype::text; 
      

        
        
        
      

     opcname  | opcintype 
      

        
        
        
      

     ----------+----------- 
      

        
        
        
      

     int4_ops | integer 
      

        
        
        
      

     text_ops | text 
      

        
        
        
      

     (2 rows)

幸いなことに、他のデータ型に対して同様のクラスを簡単に作成できます。 bloomメソッドの演算子クラスには、厳密に1つの演算子-等価-と厳密に1つの補助関数-ハッシュを含める必要があります。任意の型に必要な演算子と関数を見つける最も簡単な方法は、システムディレクトリのハッシュメソッド演算子クラスを調べることです。

demo=# select distinct 
      

        
        
        
      

     opc.opcintype::regtype::text, 
      

        
        
        
      

     amop.amopopr::regoperator, 
      

        
        
        
      

     ampr.amproc 
      

        
        
        
      

     from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr 
      

        
        
        
      

     where am.amname = 'hash' 
      

        
        
        
      

     and opc.opcmethod = am.oid 
      

        
        
        
      

     and amop.amopfamily = opc.opcfamily 
      

        
        
        
      

     and amop.amoplefttype = opc.opcintype 
      

        
        
        
      

     and amop.amoprighttype = opc.opcintype 
      

        
        
        
      

     and ampr.amprocfamily = opc.opcfamily 
      

        
        
        
      

     and ampr.amproclefttype = opc.opcintype 
      

        
        
        
      

     order by opc.opcintype::regtype::text; 
      

        
        
        
      

     opcintype |      amopopr        |    amproc 
      

        
        
        
      

     -----------+----------------------+-------------- 
      

        
        
        
      

     abstime  | =(abstime,abstime)  | hashint4 
      

        
        
        
      

     aclitem  | =(aclitem,aclitem)  | hash_aclitem 
      

        
        
        
      

     anyarray  | =(anyarray,anyarray) | hash_array 
      

        
        
        
      

     anyenum  | =(anyenum,anyenum)  | hashenum 
      

        
        
        
      

     anyrange  | =(anyrange,anyrange) | hash_range 
      

        
        
        
      

     ...

この情報を取得して、不足している2つのクラスを作成します。

demo=# CREATE OPERATOR CLASS character_ops 
      

        
        
        
      

     DEFAULT FOR TYPE character USING bloom AS 
      

        
        
        
      

     OPERATOR  1  =(character,character), 
      

        
        
        
      

     FUNCTION  1  hashbpchar; 
      

        
        
        
      

     CREATE OPERATOR CLASS 
      

        
        
        
      

     
      

        
        
        
      

     demo=# CREATE OPERATOR CLASS interval_ops 
      

        
        
        
      

     DEFAULT FOR TYPE interval USING bloom AS 
      

        
        
        
      

     OPERATOR  1  =(interval,interval), 
      

        
        
        
      

     FUNCTION  1  interval_hash; 
      

        
        
        
      

     CREATE OPERATOR CLASS

ポイント（ポイントタイプ）の場合、ハッシュ関数は定義されていません。そのため、このようなフィールドにブルームインデックスを作成することはできません（このタイプのフィールドでハッシュ結合を実行できないのと同じ方法で）。

再試行してください：

demo=# create index flights_bi_bloom on flights_bi 
      

        
        
        
      

     using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) 
      

        
        
        
      

     with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 
      

        
        
        
      

     CREATE INDEX

インデックスのサイズは526 MBです。これは、式では各ブロックのサービス情報のオーバーヘッドコストを考慮していないため、計算されたサイズよりわずかに大きくなっています。

demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 
      

        
        
        
      

     pg_size_pretty 
      

        
        
        
      

     ---------------- 
      

        
        
        
      

     526 MB 
      

        
        
        
      

     (1 row)

お問い合わせ

これで、さまざまな基準を使用して検索を実行でき、インデックスによってサポートされます。

前述したように、ブルームフィルターは確率的な構造であるため、それぞれの場合の効率は異なる場合があります。たとえば、Miroslav Sidorovという2人の乗客に関連するエントリを見てみましょう。

demo=# explain(costs off,analyze) 
      

        
        
        
      

     select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 
      

        
        
        
      

     QUERY PLAN 
      

        
        
        
      

     -------------------------------------------------------------------------------------------------- 
      

        
        
        
      

     Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) 
      

        
        
        
      

     Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) 
      

        
        
        
      

     Rows Removed by Index Recheck: 38562 
      

        
        
        
      

     Heap Blocks: exact=21726 
      

        
        
        
      

     ->  Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) 
      

        
        
        
      

     Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) 
      

        
        
        
      

     Planning time: 0.109 ms 
      

        
        
        
      

     Execution time: 3010.736 ms

そして、Marfa Solovieva：

demo=# explain(costs off,analyze) 
      

        
        
        
      

     select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 
      

        
        
        
      

     QUERY PLAN 
      

        
        
        
      

     --------------------------------------------------------------------------------------------------- 
      

        
        
        
      

     Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) 
      

        
        
        
      

     Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) 
      

        
        
        
      

     Rows Removed by Index Recheck: 3950168 
      

        
        
        
      

     Heap Blocks: exact=45757 lossy=67332 
      

        
        
        
      

     ->  Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) 
      

        
        
        
      

     Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) 
      

        
        
        
      

     Planning time: 0.157 ms 
      

        
        
        
      

     Execution time: 10142.730 ms

あるケースでは、フィルターは4万件の誤検知しか許可しませんでした。したがって、クエリの実行時間は異なります。

次に、名前ではなくドキュメント番号を使用して、同じ行を検索した結果を示します。ミロスラフ：

demo=# explain(costs off,analyze) 
      

        
        
        
      

     demo-# select * from flights_bi where passenger_id='5864 006033'; 
      

        
        
        
      

     QUERY PLAN 
      

        
        
        
      

     ------------------------------------------------------------------------------------------------- 
      

        
        
        
      

     Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) 
      

        
        
        
      

     Recheck Cond: ((passenger_id)::text = '5864 006033'::text) 
      

        
        
        
      

     Rows Removed by Index Recheck: 9620258 
      

        
        
        
      

     Heap Blocks: exact=50510 lossy=165722 
      

        
        
        
      

     ->  Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) 
      

        
        
        
      

     Index Cond: ((passenger_id)::text = '5864 006033'::text) 
      

        
        
        
      

     Planning time: 0.110 ms 
      

        
        
        
      

     Execution time: 16907.423 ms

そしてマーサ：

demo=# explain(costs off,analyze) 
      

        
        
        
      

     select * from flights_bi where passenger_id='2461 559238'; 
      

        
        
        
      

     QUERY PLAN 
      

        
        
        
      

     -------------------------------------------------------------------------------------------------- 
      

        
        
        
      

     Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) 
      

        
        
        
      

     Recheck Cond: ((passenger_id)::text = '2461 559238'::text) 
      

        
        
        
      

     Rows Removed by Index Recheck: 30669 
      

        
        
        
      

     Heap Blocks: exact= 27513 
      

        
        
        
      

     ->  Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) 
      

        
        
        
      

     Index Cond: ((passenger_id)::text = '2461 559238'::text) 
      

        
        
        
      

     Planning time: 0.120 ms 
      

        
        
        
      

     Execution time: 3934.517 ms

効率もまた非常に異なります。今回はマーサはより幸運でした。

偽陽性pの確率はp ^2に変わるため、2つのフィールドで同時に検索を行うと、はるかに効率的に実行されることに注意してください。

demo=# explain(costs off,analyze) 
      

        
        
        
      

     select * from flights_bi 
      

        
        
        
      

     where passenger_name='MIROSLAV SIDOROV' 
      

        
        
        
      

     and passenger_id='5864 006033'; 
      

        
        
        
      

     QUERY PLAN 
      

        
        
        
      

     -------------------------------------------------------------------------------------------------------------------- 
      

        
        
        
      

     Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) 
      

        
        
        
      

     Recheck Cond: (((passenger_id)::text = '5864 006033'::text) 
      

        
        
        
      

     AND (passenger_name = 'MIROSLAV SIDOROV'::text)) 
      

        
        
        
      

     Rows Removed by Index Recheck: 357 
      

        
        
        
      

     Heap Blocks: exact=356 
      

        
        
        
      

     ->  Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) 
      

        
        
        
      

     Index Cond: (((passenger_id)::text = '5864 006033'::text) 
      

        
        
        
      

     AND (passenger_name = 'MIROSLAV SIDOROV'::text)) 
      

        
        
        
      

     Planning time: 0.524 ms 
      

        
        
        
      

     Execution time: 877.967 ms

ただし、論理「or」の条件はまったくサポートされていません。これは、このアクセス方法ではなく、スケジューラの制限です。もちろん、インデックスを2回読み取り、2つのビットマップを構築し、それらを結合するオプションは残りますが、そのようなプランを選択するにはコストが高すぎる可能性があります。

BRINおよびHashとの比較

ブルームインデックスとBRINインデックスの適用分野は明らかに重複しています。これらは大きなテーブルであり、異なるフィールドで検索を提供することが望ましいため、コンパクトにするために検索の精度が犠牲になります。

BRINインデックスはよりコンパクトで（この例では最大10メガバイト）、範囲検索をサポートできますが、ファイル内のデータの物理的な場所に関連する非常に強力な制限があります。ブルームインデックスはより多く（数百メガバイト）取得されますが、適切なハッシュ関数が存在することを除いて、制限はありません。

ブルームインデックスと同様に、ハッシュインデックスは単一の等価チェック操作をサポートします。ハッシュインデックスは、Bloomに到達できない検索精度を提供しますが、そのサイズは非常に大きくなります（この例では、1つのフィールドのみでギガバイトであり、複数のフィールドでハッシュインデックスを作成することはできません）。

プロパティ

伝統的に、プロパティを見てみましょう（クエリは以前に与えられました）。

メソッドのプロパティ：

amname |    name      | pg_indexam_has_property 
      

        
        
        
      

     --------+---------------+------------------------- 
      

        
        
        
      

     bloom  | can_order    | f 
      

        
        
        
      

     bloom  | can_unique    | f 
      

        
        
        
      

     bloom  | can_multi_col | t 
      

        
        
        
      

     bloom  | can_exclude  | f

明らかに、アクセス方法を使用すると、複数の列にインデックスを作成できます。1つの列にあるブルームインデックスはほとんど意味がありません。

インデックスのプロパティ：

name      | pg_index_has_property 
      

        
        
        
      

     ---------------+----------------------- 
      

        
        
        
      

     clusterable  | f 
      

        
        
        
      

     index_scan    | f 
      

        
        
        
      

     bitmap_scan  | t 
      

        
        
        
      

     backward_scan | f

スキャンできる唯一の方法はビットマップです。インデックスは常に全体としてスキャンされるため、TIDが1つずつ返される通常のインデックスアクセスを実装する意味はありません。

name        | pg_index_column_has_property 
      

        
        
        
      

     --------------------+------------------------------ 
      

        
        
        
      

     asc                | f 
      

        
        
        
      

     desc              | f 
      

        
        
        
      

     nulls_first        | f 
      

        
        
        
      

     nulls_last        | f 
      

        
        
        
      

     orderable          | f 
      

        
        
        
      

     distance_orderable | f 
      

        
        
        
      

     returnable        | f 
      

        
        
        
      

     search_array      | f 
      

        
        
        
      

     search_nulls      | f

ここにすべての「ダッシュ」があり、未定義の値であっても、このアクセス方法は方法を知りません。

そして最後に

このシリーズの記事が、新しい興味深い種類のインデックスの出現とともに今後も続くことを除外していませんが、今はやめましょう。

下書きやコメントを読んでくれたPostgres Professionalの同僚（議論した多くのアクセス方法の作者の一部）に感謝したいと思います。そして、もちろん、 あなたの忍耐と貴重なコメントに感謝します。あなたの注意がこの点に到達する力を与えてくれました。よろしくお願いします！

PostgreSQLインデックス-10