PolarDB:IMCIを使用したデータのフィルタリング

背景情報と効果

ハイブリッドトランザクション /分析処理 (HTAP) シナリオでは、PolarDBのIMCI機能は、列指向のヒープテーブルをストレージアーキテクチャとして使用して、リアルタイムの更新をサポートします。 SQL ServerとOracleの列ストアインデックスは同じストレージアーキテクチャを使用します。 ただし、ヒープテーブルを使用するストレージアーキテクチャでは、クエリ中にスキャンするデータ量は削減されません。 ほとんどの場合、フルテーブルスキャンが必要です。 スキャンするデータ量を最小限に抑え、テーブル全体のスキャンを減らすために、SQL ServerはMIN() 関数、MAX() 関数、パーティション、およびクラスタ化インデックスを使用しますが、OracleはMIN() 関数、MAX() 関数、およびメモリ内列ストアインデックスに基づくメタデータディクショナリを使用します。 PolarDBのIMCI機能は、列指向テーブルを使用し、データストレージをサポートして、テーブル全体のスキャンを最適化するためのより多様な方法を提供します。

PolarDBのIMCI機能は、行グループごとにデータを整理します。 各行グループは約64,000行を含む。 各列の列インデックスは、追加書き込みモードに基づいて特定の順序なしに格納されます。 したがって、IMCIは、InnoDBの順序付けられたインデックスほど正確にクエリ条件に基づいてデータをフィルタリングできません。 IMCIがデータパックを読み取ると、IMCIはデータパックをディスクからメモリにロードし、データパックを解凍し、データパック内のすべてのデータレコードをトラバースしてから、クエリ条件を満たすデータレコードを見つけます。 大きなテーブルをスキャンすると、テーブル全体のスキャンが非効率的になり、LRU (least recently used) キャッシュが影響を受け、全体的なクエリの待ち時間が増加し、1秒あたりのクエリ数 (QPS) が減少します。

フルテーブルスキャンを減らすために、PolarDBのIMCI機能ではプルーニングメソッドが用意されています。 IMCIはプルーニングを使用して、事前にアクセスしたくないデータパックを除外します。 これにより、クエリするデータ量が減り、クエリ効率が向上します。 これを実装するために、IMCIはプルーニングメソッドを使用してパーティションまたは統計にアクセスし、指定された条件を満たさないデータをプルーニングしてからデータを照会します。 これにより、保存されたデータのスキャン数と、データ転送とコンピューティングに消費されるリソースの量が削減されます。 プルーニングは、単一のテーブルおよび複数のテーブルからのデータクエリに適用でき、PolarDB IMCIのクエリパフォーマンスを向上させることができます。

基本原則と使用方法

パーティションの剪定

IMCIのパーティションプルーニング方法は、クエリが実行されるときにパーティションキーに基づいてクエリする必要のないパーティションを除外するために使用されます。 これにより、クエリするデータ量が減り、クエリ効率が向上します。 IMCIは、RANGE、LIST、およびHASHの分割方法をサポートしています。 RANGEまたはLIST分割方法は、テーブルを複数の範囲またはリストに分割します。 HASH分割方法は、データを異なるパーティションにハッシュする。 パーティションプルーニング方法を使用する場合、パーティション条件を満たすクエリ文を使用し、パーティションキーに基づいてクエリ条件を指定する必要があります。

たとえば、注文という名前のテーブルは、注文日に基づいて12のパーティションに分割されます。 次のステートメントを実行して、特定の日に注文を照会できます。

SELECT * FROM注文WHERE order_date = '2022-01-01 ';

IMCIがクエリを実行すると、IMCIは注文日に基づいてクエリ条件を満たすパーティションを見つけ、パーティションのデータのみをクエリします。 これにより、クエリするデータ量が減り、クエリ効率が向上します。 IMCIは、結合された列間の同値関係に基づく推論もサポートしており、完全なパーティションプルーニングを実行します。 たとえば、Table RとTable Sのパーティションキーはaで、次のクエリ文を実行します。select count(1) from R,Sここで、R.a = S.a and R.a > 10。 R.a = S.aおよびR.a > 10という条件に基づいて、S.a > 10であると推論することができ、これは表5の分割枝刈りに使用することができる。

次のリストでは、さまざまなタイプのパーティションのプルーニングアルゴリズムについて説明します。

• RANGEパーティション分割方法を使用して生成されたパーティションでは、さまざまなパーティションの境界点が順番に配列に格納されます。 したがって、バイナリ検索方法を使用してパーティションを検索できます。

• LISTパーティション分割方法を使用して生成されたパーティションの場合、各パーティションのリスト値とパーティションIDは、<value, part_id> 形式のタプルを形成します。 タプルは、リスト値によって順に格納される。 バイナリ検索方法を使用してパーティションを検索することもできます。

• HASH分割方法を使用して生成されたパーティションについては、可能な値がハッシュのために列挙され、ハッシュ値が計算されて、それらがどのパーティションに入るかが決定される。 このプルーニングアルゴリズムは、少数の値を列挙する必要がある場合に整数フィールドに対してのみ使用できます。

次の図は、パーティションの剪定アルゴリズムを示しています。

実際の使用では、最適なクエリパフォーマンスを実現するために、データボリュームとクエリ要件に基づいて適切なパーティションタイプとパーティションキーを選択する必要があります。

統計剪定

IMCIは、データパックの統計を使用して、照会する必要のないデータパックを除外します。 これは、ClickHouseおよびInfobrightのKnowledge Gridのインデックスをスキップするデータに似ています。 IMCIでは、プルーナーはクエリのパフォーマンスを最適化します。 クエリが実行されると、IMCIプルーナは統計とクエリ条件を使用してデータをプルーニングし、データパックをスキャンする必要があるかどうかを判断します。 統計は少量のメモリを占有するので、それらはメモリ内に常駐することができる。 データがプルーニングされると、I/O動作の数および条件に基づく判断の数が低減される。 このようにして、クエリのパフォーマンスが向上します。

データパックは、データパックがIMCIプルーナによってフィルタリングされた後、以下の状態、すなわち、AcceptまたはAC、RejectまたはRE、およびPartial AcceptまたはPAのうちの1つにあり得る。 データパックがAccept状態の場合、IMCIはデータパック内の各データレコードをスキャンする必要がないため、コンピューティングオーバーヘッドが削減されます。 データパックが拒否状態にある場合、IMCIはデータパックをメモリにロードする必要はありません。これにより、I/O操作およびコンピューティングオーバーヘッドの数が減少し、LRUキャッシュが影響を受けるのを防ぎます。 データパックがパーシャルアクセプト状態にある場合、IMCIは、データパック内の各データレコードをさらにスキャンして、クエリ条件を満たすデータレコードを見つける必要があります。

IMCIには、minmaxインデックスとBloomフィルターの2種類のプルーナーがあり、これらはさまざまなシナリオに適しています。 さらに、IMCIは、ヌル可能な列のクエリを最適化します。 IMCIプルーナーは、クエリ中にnull値を含むデータパックを除外して、クエリをさらに高速化できます。

Minmaxインデックス

Minmaxインデックスは、大規模なデータセットの拡張インデックス技術として使用されます。 Minmaxインデックスは、各データパックの最小値と最大値をインデックスデータセットに格納することにより、高速で効率的なデータ取得を提供します。 Minmaxインデックスは、タイムスタンプや実数値などの連続値を持つデータセット内のデータに適しています。 minmaxインデックスは、データセットをデータパックに分割し、各データパックの最小値と最大値を計算し、インデックスに格納します。 データがクエリされると、minmaxインデックスはクエリ範囲の最小値と最大値に基づいてクエリ対象のデータパックをすばやく見つけることができるため、無関係なデータへのアクセスが削減されます。 以下の図は一例です。 この例では、列Aと列Bの両方が3つのデータパックを含む。 A > 15およびB < 10のおよびminmaxインデックスの条件に基づいて、行グループ2および行グループ3をスキップすることができ、行グループ1のみにアクセスする必要がある。 これにより、スキャン作業負荷が3分の2削減されます。

minmaxインデックスは、短時間で大きなデータセットを処理できます。 クエリ範囲に関連するデータパックのみを処理する必要があるため、クエリ中にスキャンするデータ量を減らすことができます。 さらに、minmaxインデックスは、すべてのデータのインデックスではなく、各データパックの最小値と最大値のみを格納する必要があるため、インデックスの格納に必要なスペースを削減できます。

ブルームフィルター

ブルームフィルタは、要素がセットのメンバーであるかどうかをチェックするために使用される確率的データ構造です。 ビットの配列とハッシュ関数のセットを使用して、要素を格納および検索します。 要素がブルームフィルタでセットに追加されると、ハッシュ関数は要素をビット配列のいくつかのビットにマップし、対応するビットを1に設定します。 要素がセットのメンバーであるかどうかをチェックするためにブルームフィルタが使用されると、ハッシュ関数が再び要素に適用されます。 すべての対応するビットが1である場合、要素はセット内にあり得る。 しかし、対応するビットの1つが0である場合、要素はセット内にない。 ブルームフィルタは、空間および時間効率の高いデータ構造である。 しかしながら、偽陽性が生じることがある。 この場合、セットに存在しない要素を照会すると、その要素がセットに存在することをBloomフィルターが誤って報告することがあります。

Aブルームフィルタは、空間効率および時間効率が高く、スケーラブルであり、誤判定率において制御可能である。 これらの機能により、ブルームフィルターは、大きなデータセットに要素が存在するかどうかを確認するための有用なデータ構造になります。

ブルームフィルタとminmaxインデックスを一緒に使用できます。 IMCIは、一緒に使用された後に生成された結果に基づいて、データパックをスキップするかどうかを決定します。

ヌル可能な列に対するクエリの最適化

null値の特殊な処理ロジックのため、ほとんどの場合、データベースインデックスはnull値を持つ列を完全にはサポートしません。 異なるデータベースは、異なる方法でヌル可能な列を処理します。

PolarDBのIMCI機能は、ヌル可能な列のクエリを最適化します。 これにより、クエリのパフォーマンスに対するnull値の影響が軽減されます。 PolarDBを使用する場合、null値を含む列が頻繁に使用されます。 デフォルト値を使用してnull値を置き換える場合は、DDL操作を実行してテーブルスキーマを変更する必要があります。また、ビジネスデータを照会するために既存のSQL文を変更する必要がある場合もあります。 PolarDBのIMCI機能を使用すると、null値を持つ列のminmaxインデックスとBloomフィルターを作成して、IS Null、IS NOT Null、> 、<、=などの述語を含むクエリをサポートできます。

データパックにnull値が含まれている場合、プルーナーの作成時に値はスキップされます。 たとえば、データパックには、1、2、3、およびnullの4つのデータエントリが含まれます。 最小値は1、最大値は3です。 データパックのクエリ中に、null値を無視してクエリが処理され、データパックにnull値が含まれているかどうかに基づいて処理結果が変換されます。 上の図は例を示しています。 この例では、Pack A1にはnull値のみが含まれます。 パックA2とパックA3の両方が部分的にヌル値を含む。 A > 15の条件に基づいて、ヌル値を考慮せずに結果として [PA, AC, RE] が得られる。 Pack A1にはnull値のみが含まれているため、フィルタリングできません。 次に、各データパックがヌル値を含むという事実に基づいて、結果が [RE, PA, RE] に変換される。 最後に、パックA1およびパックA3を剪定することができる。 これにより、クエリのパフォーマンスが向上します。

ランタイムフィルター

クエリの最適化には、ランタイムフィルターが使用されます。 クエリ中に動的に生成されます。 クエリ中に、ランタイムフィルターは、スキャンされたデータ値やその他の情報に基づいて、指定された条件を満たさないデータを除外できます。 これにより、クエリするデータ量が減り、クエリのパフォーマンスが向上します。 IMCIは、ブルームフィルターとminmaxフィルターの2つの一般的なタイプのランタイムフィルターを提供します。 JOIN、GROUP BY、ORDER BYなどのさまざまなクエリに適用できます。

たとえば、PolarDBのIMCI機能は、ORDER BY列LIMIT構文を使用するTopKクエリを最適化します。 TopK演算子によって構築されたセルフシャープニング入力フィルターと、ストレージ層のデータパックに作成されたminmaxインデックスを使用して、プルーニングを実行できます。 これにより、TopKクエリが高速化されます。 詳細については、「IMCIでのTopK演算子の実装」トピックのComputing pushdownセクションを参照してください。

さらに、ランタイムフィルターを使用してハッシュ結合を高速化できます。 たとえば、SELECT * FROM sales JOIN items ON sales.item_id = items.id WHERE items.price > 1000ステートメントを実行します。 このステートメントでは、売上テーブルはファクトテーブルであり、アイテムテーブルはディメンションテーブルです。 アイテムテーブルは小さいです。 返されるデータレコードの数は、次の条件に基づいてさらに減らすことができます。価格> 1000。 salesテーブルとitemsテーブルが結合されると、指定された条件を満たすitem_id結果セットに基づいてランタイムフィルターを構築できます。 最小値が1であり、最大値が100である場合、id > 1およびid < 100フィルタ式またはin(id1,id2,id3 ...) 式を生成することができる。 ランタイムフィルターは左のテーブルに渡されます。 左側のテーブルのデータレコードをスキャンしてプローブを探す場合、ランタイムフィルターで指定された条件を満たさないデータレコードを事前に除外して、プローブの数を減らすことができます。 STRING型のデータについては、右のテーブルの結果セットに対してBloomフィルターを作成して、STRING型のデータを事前にフィルター処理できます。 ブルームフィルタはリソースのオーバーヘッドを増加させ、大きな結果セットには適していません。 プルーナーが左側のテーブルの列に存在する場合、プルーナーはランタイムフィルタに基づいてデータレコードをフィルタリングして、スキャンするデータパックを減らすことができます。 大規模並列処理 (MPP) シナリオでは、Runtimeフィルターを使用すると、シャッフルするデータ量を減らすことができます。

ビットマップ索引

ビットマップインデックスは、行指向ストレージでも使用されます。 たとえば、Oracleは、低濃度の列に適したビットマップ・インデックスを提供しています。 ビットマップインデックスでは、列内の各個別の値に、テーブルの各行の値の有無を表すビットが割り当てられます。 クエリ中にデータがフィルタリングされると、列の値に基づいてビットマップ情報を取得して行を見つけることができます。 これは、複数の列のANDやorなどの述語を含むクエリに特に適しています。 ほとんどの場合、データレコードのフィルタリングと検索に役立つBツリーインデックスは、高濃度の列に適しています。 B-treeインデックスはビットマップインデックスを補完します。 B-treeインデックスは、検索モードが固定されているシナリオに適しています。 ビットマップインデックスは、これらのシナリオでも使用できます。 ただし、Bツリーインデックスは、OR述語を含むクエリと完全に互換性がありません。

ビットマップインデックスは、低濃度列のBツリーインデックスよりも少ないストレージスペースを占有します。 以下の図は一例です。 この例では、テーブルのGENDER列とRANK列にビットマップインデックスが作成されます。 テーブルには5行しか含まれていません。 1つの列値に対応するビットマップは、5ビットのみを必要とする。 従来のBツリーインデックスと比較して、ビットマップインデックスは必要なストレージスペースが少なく、必要なストレージスペースは行のカーディナリティと総数に依存します。 グローバルビットマップインデックスの場合、ビットマップインデックスの特性により、テーブルの行を変更する場合は、ビットマップインデックスを維持し、テーブル全体をロックする必要があります。 したがって、グローバルビットマップインデックスは、読み出されるデータの量が書き込まれるデータの量よりも多いシナリオに適しています。

PolarDBのIMCI機能は、データパックのビットマップインデックスをサポートします。 必要なデータの行番号は、ビットマップインデックスに基づいて直接返すことができます。 これにより、データパックへのアクセスが減少します。

利点とシナリオ

PolarDBのIMCI機能は、互いに補完的な複数のプルーニングメソッドをサポートします。 データ特性とクエリシナリオに基づいたメソッドを使用できます。 PolarDB IMCIでサポートされているプルーニング方法を使用する場合は、データが配布されていることを確認してください。 データがより多く分散されるほど、剪定効果はより良くなる。 しかしながら、データは、実際のシナリオにおいて期待されるように配信されない。 この場合、データの配布を慎重に計画する必要があります。

• パーティションプルーニング: この方法を使用するには、適切なパーティションキーを選択してパーティションテーブルを作成する必要があります。 データは、パーティションキーに基づいて事前に配布されます。 ほとんどの場合、無関係なデータは予想通りに除外されます。 指定するクエリ条件のほとんどにパーティションキーが含まれており、パーティションごとにデータライフサイクルを管理する場合は、ビジネス要件に基づいて、パーティションテーブルをプルーニングし、レベル1またはレベル2のパーティションを作成できます。

• Minmaxインデックス: このプルーナーを使用するには、列内のデータを適切に分散し、範囲クエリをサポートする必要があります。 例えば、TIMESTAMPタイプのデータは、順番にテーブルに挿入される。 TIMESTAMP型の列に作成されるminmaxインデックスは、データのフィルタリングを容易にします。

• Bloomフィルタ: ブルームフィルタは、同等の条件およびIN条件のフィルタリング性能を改善するために使用することができる。 同等の条件に基づいて予想されるフィルタリング結果を提供し、良好なフィルタリングパフォーマンスを実現します。 たとえば、ランダムに生成されたさまざまなIDにBloomフィルターを使用できます。 ほとんどの場合、単一のIDは少数のデータレコードにのみ対応します。 そのようなIDを含む等価フィルタ条件は、条件を満たさないデータを剪定することができる。

• ビットマップインデックス: ビットマップインデックスは、単一のフィルター条件または複数の強力なフィルター条件を含むクエリ、またはマテリアライズドデータを必要としないクエリに適しています。select count(*) from t where xxx.

制限と解決策

IMCIのさまざまな剪定方法には独自の限界があります。 実際のシナリオでは、データプルーニング機能を改善するために複数の方法と組み合わせる必要があります。

• パーティションプルーニング: 既存のデータに対してDDL操作を実行すると、コストが高くなります。 さらに、クエリ条件にはパーティションキーを含める必要があります。 オフピーク時に既存のデータに対してDDL操作を実行できます。 複数のクエリ条件にパーティションキーが含まれていない場合は、別の方法を使用してクエリを最適化することを推奨します。

• Statisticsプルーニング: 統計は特定の順序なしでソートされます。 したがって、データが均等に分散および分散されているシナリオでは、統計の効果は低くなります。 次のいずれかの最適化ソリューションを使用できます。

  • データパックのサイズを縮小します。 minmaxインデックスとBloomフィルターの場合、データパックのサイズが小さいほど、インデックスが細かく、ほとんどの場合、プルーニング効果が優れていることを示します。 IMCIを使用すると、テーブルのデータパックサイズを変更できます。 しかしながら、データパックサイズが低減される場合、データパックは、より多くのメモリリソースを占有し得る。

  • データの並べ替え データがランダムに分散されている場合は、PolarDB IMCIのソートキー機能を使用して統計プルーニングを実行できます。

  • プルーナーを無効にします。 統計のプルーニングはクエリの最適化には役立たない場合がありますが、コンピューティングとメモリのオーバーヘッドが発生します。 ブルームフィルタはまた、I/Oオーバーヘッドを増加させる。 この場合、クエリ中にプルーナーを無効にできます。

パフォーマンステスト

このセクションでは、PolarDB HTAPシナリオにおけるプルーナーとビットマップインデックスのパフォーマンスをテストします。 プルーナーには、minmaxインデックスとBloomフィルターが含まれます。 テストデータセットは100 GBのTPC-Hデータを使用します。 点クエリおよび範囲クエリを含むいくつかの典型的なクエリがテストされる。 データ型には、NUMERIC型とSTRING型が含まれます。

テストSQL文

軽量インデックスの有効性は、データの分布とクエリの種類によって異なります。 軽量インデックスの有効性は、次の方法でテストされます。スキャン演算子に基づいて構築されたいくつかのSQLステートメントを使用して、プルーナーとビットマップインデックスが使用される前後のアクセラレーション効果を比較します。 テスト環境はメモリ内ストレージを使用し、同時実行性は1に設定されます。 I/Oが関与するシナリオでは、インデックスのアクセラレーション効果が優れています。

Q1: ps_suppkey = 41164であるpartsuppからcount(*) を選択します。Q2: ps_suppkeyが (41164,58321) にあるpartsuppからcount(*) を選択します。Q3: 40000と50000の間のps_suppkeyがあるpartsuppからカウント (*) を選択します。Q4: o_clerk = 'Clerk#000068170 'の注文からカウント (*) を選択します。Q5: o_clerkが ('Clerk#000068170 '、'Clerk#000087784') の注文からカウント (*) を選択します。Q6: c_mktsegment = 'AUTOMOBILE' の顧客からカウント (*) を選択します。Q7: c_mktsegmentが ('AUTOMOBILE' 、'FURNITURE' 、'BUILDING') の顧客からカウント (*) を選択します。Q8: c_mktsegment = 'AUTOMOBILE' またはc_phone = '18-338-906-3675 'の顧客からカウント (*) を選択します。Q9: c_mktsegment = 'AUTOMOBILE' およびc_phone = '18-338-906-3675 'である顧客からカウント (*) を選択します。

テスト結果

• Q1からQ5はプルーナーの加速効果を確認します。 partsuppテーブルのps_suppkey列のクエリはminmaxインデックスを使用して高速化でき、注文テーブルのo_clerk列のクエリはBloomフィルターを使用して高速化できます。 加速比は、フィルタリングされたデータパックの数に比例する。

  • 次の表は、クエリの継続時間を比較しています。

    SQLクエリ	クエリ期間 (秒)
    	SQLクエリ期間 (秒)	プルーナーを使用したSQLクエリ期間 (秒)
    Q1	0.11	5.80
    Q2	0.14	15.00
    Q3	0.13	6.90
    Q4	0.89	0.43
    Q5	1.85	1.35

  • 次の図は、クエリの期間を比較しています。

    

• Q6〜Q9は、ビットマップインデックスのアクセラレーション効果を検証します。 顧客テーブルのc_mktsegment列の値は、各データパックに均等に分散されます。 したがって、プルーナーだけではSQL文の実行を加速できません。 SQL文の実行は、プルーナーとビットマップインデックスを一緒に使用することで高速化できます。

  • 次の表は、クエリの継続時間を比較しています。

    SQLクエリ	クエリ期間 (秒)
    	SQLクエリ期間 (秒)	プルーナーを使用したSQLクエリ期間 (秒)	プルーナーとビットマップインデックスを使用したSQLクエリ期間 (秒)
    Q6	1.43	1.43	0.03
    Q7	3.49	3.49	15.00
    Q8	2.48	2.48	1.09
    Q9	1.25	5.80	5.80

  • 次の図は、クエリの期間を比較しています。