パフォーマンスの背後にある最適化

Apache Dorisの初期バージョンはオンライン分析処理（OLAP）に焦点を当て、主にレポートと集計ワークロード（典型的なクエリは複数テーブルのJOINとGROUP BY）を対象としていました。2.xでは、Dorisは転置インデックスによるテキスト検索を追加し、効率的なJSON処理のためのVariant型を導入しました。3.xでは、ストレージ・コンピュート分離により、オブジェクトストレージを活用してストレージコストを大幅に削減できるようになりました。4.xでは、Dorisはベクトルインデックスとハイブリッド検索（ベクトル + テキスト）を導入してAI時代に参入し、Dorisを企業向けAI分析プラットフォームとして位置づけています。本文書では、Dorisが4.xでベクトルインデックスを実装する方法と、最先端のパフォーマンスを達成するために行われたエンジニアリング努力について説明します。

ベクトルインデックスを2つの段階に分けます：インデックス作成とクエリです。インデックス作成段階は、1）データシャーディング、2）高品質インデックスの効率的な構築、3）インデックス管理に焦点を当てます。クエリ段階には単一の目標があります：クエリパフォーマンスの向上—冗長な計算と不要なIOを排除し、並行性を最適化することです。

インデックス作成段階

インデックス作成のパフォーマンスは、インデックスのハイパーパラメータと強く関連しています：通常、インデックス品質が高いほど構築時間が長くなります。取り込みパスの最適化により、Dorisは取り込みスループットを向上させながら高いインデックス品質を維持できます。

768D 10Mデータセットにおいて、Apache Dorisは業界最高水準の取り込みパフォーマンスを実現しています。

alt text

マルチレベルシャーディング

Apache Dorisの内部テーブルは本質的に分散されています。クエリと取り込みの際、ユーザーは単一の論理テーブルと対話し、Dorisカーネルはテーブル定義に基づいて必要な数の物理タブレットを作成します。取り込み時には、データはパーティションとバケットキーによって適切なBEタブレットにルーティングされます。複数のタブレットが組み合わさって、ユーザーに見える論理テーブルを形成します。各取り込みリクエストはトランザクションを形成し、対応するタブレット上にrowset（バージョニング単位）を作成します。各rowsetにはいくつかのセグメントが含まれ、セグメントが実際のデータキャリアです；ANNインデックスはセグメントの粒度で動作します。

Hierarchy from table to shards

ベクトルインデックス（例：HNSW）は、インデックス品質とクエリパフォーマンスを直接決定する主要なハイパーパラメータに依存し、通常は特定のデータスケールに対してチューニングされます。Apache Dorisのマルチレベルシャーディングは「インデックスパラメータ」と「全テーブルデータスケール」を分離します：ユーザーは総データ量の増加に伴ってインデックスを再構築する必要はなく、バッチごとの取り込みサイズに基づいてパラメータをチューニングするだけで済みます。テストから、異なるバッチサイズでのHNSW推奨パラメータは以下の通りです：

batch_size	max_degree	ef_construction	ef_search	recall@100
250000	100	200	50	89%
250000	100	200	100	93%
250000	100	200	150	95%
250000	100	200	200	98%
500000	120	240	50	91%
500000	120	240	100	94%
500000	120	240	150	96%
500000	120	240	200	99%
1000000	150	300	50	90%
1000000	150	300	100	93%
1000000	150	300	150	96%
1000000	150	300	200	98%

要するに、「バッチごとの取り込みサイズ」に注目し、品質と安定したクエリ動作を維持するために適切なインデックスパラメータを選択してください。

高性能インデックス構築

並列・高品質インデックス構築

Dorisは2レベルの並列性でインデックス構築を高速化します：BEノード間のクラスターレベル並列性と、グループ化されたバッチデータでのノード内マルチスレッド距離計算です。速度を超えて、Dorisはインメモリバッチングによりインデックス品質を向上させます：総ベクトル数が固定されているがバッチングが細かすぎる場合（頻繁な増分構築）、グラフ構造はよりスパースになりリコールが低下します。例えば、768D10Mにおいて、10バッチで構築すると約99%のリコールに達する可能性がありますが、100バッチでは約95%に低下する可能性があります。インメモリバッチングは、同じハイパーパラメータの下でメモリ使用量とグラフ品質のバランスを取り、過度なバッチングによる品質劣化を回避します。

SIMD

ANNインデックス構築における中核コストは大規模な距離計算です—これはCPUバウンドなワークロードです。DorisはこのワークをBEノードに集約し、C++で実装し、Faissの自動および手動ベクトル化最適化を活用します。L2距離については、Faissはコンパイラプラグマを使用して自動ベクトル化をトリガーします：

FAISS_PRAGMA_IMPRECISE_FUNCTION_BEGIN
float fvec_L2sqr(const float* x, const float* y, size_t d) {
    size_t i; float res = 0;
    FAISS_PRAGMA_IMPRECISE_LOOP
    for (i = 0; i < d; i++) {
        const float tmp = x[i] - y[i];
        res += tmp * tmp;
    }
    return res;
}
FAISS_PRAGMA_IMPRECISE_FUNCTION_END

FAISS_PRAGMA_IMPRECISE_*を使用することで、コンパイラは自動ベクトル化を行います：

#define FAISS_PRAGMA_IMPRECISE_LOOP \
    _Pragma("clang loop vectorize(enable) interleave(enable)")

Faissは#ifdef SSE3/AVX2/AVX512Fブロック内で_mm*/_mm256*/_mm512*を使用してSIMDを明示的に適用し、ElementOpL2/ElementOpIPおよび次元特化されたfvec_op_ny_D{1,2,4,8,12}と組み合わせて以下を行います：

イテレーションごとに複数のサンプルを処理し（例：8/16）、レジスタレベルの転置を実行してメモリアクセスの局所性を向上させる
FMA（例：_mm512_fmadd_ps）を使用して乗算-加算を融合し、命令数を削減する
水平和を実行してスカラを効率的に生成する
整列されていないサイズに対してマスク読み取りによりテール要素を処理するこれらの最適化により命令とメモリのコストが削減され、インデックス作成のスループットが大幅に向上します。

クエリステージ

検索はレイテンシに敏感です。数千万件のレコードで高い同時実行性を持つ場合、P99レイテンシは通常500ms未満である必要があり、オプティマイザ、実行エンジン、およびインデックス実装のハードルを上げています。標準テストでは、DorisはメインストリームのベクトルDB専用データベースと同等のパフォーマンスを達成しています。以下のチャートは、Performance768D10MでのDorisと他のシステムとの比較を示しています。ピアデータはZillizのオープンソースVectorDBBenchから取得しています。

alt text

注：このチャートには標準結果の一部が含まれています。OpenSearchとElastic Cloudは、インデックスファイル数を最適化することでクエリパフォーマンスを向上させることができます。

Prepare Statement

従来のパスでは、DorisはすべてのSQLに対してフル最適化（構文解析、意味解析、RBO、CBO）を実行します。一般的なOLAPには不可欠ですが、シンプルで高度に反復的な検索クエリにはオーバーヘッドが追加されます。Doris 4.0では、Prepare Statementをポイントルックアップを超えてベクトル検索を含むすべてのSQLタイプに拡張しています：

コンパイルと実行の分離
- Prepareは構文解析、意味解析、最適化を一度実行し、再利用可能なLogical Planを生成します。
- Executeは実行時にパラメータをバインドし、事前構築されたプランを実行してオプティマイザを完全にスキップします。
プランキャッシュ
- 再利用はSQLフィンガープリント（正規化されたSQL + スキーマバージョン）によって決定されます。
- 同じ構造で異なるパラメータ値を持つクエリはキャッシュされたプランを再利用し、再最適化を回避します。
スキーマバージョンチェック
- 実行時にスキーマバージョンを検証して正確性を保証します。
- 変更なし → 再利用、変更あり → 無効化して再準備。
オプティマイザをスキップすることによる高速化
- ExecuteはRBO/CBOを実行しなくなり、オプティマイザ時間がほぼ排除されます。
- テンプレート多用のベクトルクエリは、エンドツーエンドレイテンシの大幅な低減により恩恵を受けます。

Index Only Scan

Dorisはベクトルインデックスを外部（プラガブル）インデックスとして実装しており、これによりマネジメントが簡素化され非同期ビルドがサポートされますが、冗長な計算とIOの回避などのパフォーマンス課題が導入されます。ANNインデックスは行IDに加えて距離を返すことができます。Dorisは、Scanオペレータ内で「仮想カラム」を介して距離式をショートサーキットすることでこれを活用し、Ann Index Only Scanは距離関連の読み取りIOを完全に排除します。ナイーブなフローでは、Scanが述語をインデックスにプッシュし、インデックスが行IDを返し、その後Scanがデータページを読み取り式を計算してからN行を上流に返します。

alt text

Index Only Scanが適用されると、フローは以下のようになります：

alt text

例えば、SELECT l2_distance_approximate(embedding, [...]) AS dist FROM tbl ORDER BY dist LIMIT 100;はデータファイルに触れることなく実行されます。

Ann TopN Search以外に、Range SearchとCompound Searchも同様の最適化を採用しています。Range Searchはより微妙です：インデックスがdistを返すかどうかは比較演算子に依存します。以下に、Ann Index Only Scanに関連するクエリタイプとIndex Scanが適用されるかどうかを列挙します：

-- Sql1: Range + proj
-- Index returns dist; no need to recompute dist
-- Virtual column for CSE avoids dist recomputation in proj
-- IndexScan: True
select id, dist(embedding, [...]) from tbl where dist <= 10;

-- Sql2: Range + no-proj
-- Index returns dist; no need to recompute
-- IndexScan: True
select id from tbl where dist <= 10 order by id limit N;

-- Sql3: Range + proj + no-dist-from index
-- Index cannot return dist (only updates rowid map)
-- proj requires dist → embedding must be reread
-- IndexScan: False
select id, dist(embedding, [...]) from tbl where dist > 10;

-- Sql4: Range + proj + no-dist-from index
-- Index cannot return dist, but proj does not need dist → embedding not reread
-- IndexScan: True
select id from tbl where dist > 10;

-- Sql5: TopN
-- Index returns dist; virtual slot for CSE uploads dist to proj
-- embedding column not read
-- IndexScan: True
select id[, dist(embedding, [...])] from tbl order by dist(embedding, [...]) asc limit N;

-- Sql6: TopN + IndexFilter
-- 1) comment not read (inverted index already optimizes this)
-- 2) embedding not read (same reason as Sql5)
-- IndexScan: True
select id[, dist(embedding, [...])] from tbl where comment match_any 'olap' ORDER BY dist(embedding, [...]) LIMIT N;

-- Sql7: TopN + Range
-- IndexScan: True (combination of Sql1 and Sql5)
select id[, dist(embedding, [...])] from tbl where dist(embedding, [...]) > 10 order by dist(embedding, [...]) limit N;

-- Sql8: TopN + Range + IndexFilter
-- IndexScan: True (combination of Sql7 and Sql6)
select id[, dist(embedding, [...])] from tbl where comment match_any 'olap' and dist(embedding, [...]) > 10 ORDER BY dist(embedding, [...]) LIMIT N;

-- Sql9: TopN + Range + CommonFilter
-- Key points: 1) dist < 10 (not > 10); 2) common filter reads dist, not embedding
-- Index returns dist; virtual slot for CSE ensures all reads refer to the same column
-- In theory embedding need not materialize; in practice it still does due to residual predicates on the column
-- IndexScan: False
select id[, dist(embedding, [...])] from tbl where comment match_any 'olap' and dist(embedding, [...]) < 10 AND abs(dist(embedding) + 10) > 10 ORDER BY dist(embedding, [...]) LIMIT N;

-- Sql10: Variant of Sql9, dist < 10 → dist > 10
-- Index cannot return embedding; to compute abs(dist(embedding,...)) embedding must materialize
-- IndexScan: False
select id[, dist(embedding, [...])] from tbl where comment match_any 'olap' and dist(embedding, [...]) > 10 AND abs(dist(embedding) + 10) > 10 ORDER BY dist(embedding, [...]) LIMIT N;

-- Sql11: Variant of Sql9, abs(dist(...)+10) > 10 → array_size(embedding) > 10
-- array_size requires embedding materialization
-- IndexScan: False
select id[, dist(embedding, [...])] from tbl where comment match_any 'olap' and dist(embedding, [...]) < 10 AND array_size(embedding) > 10 ORDER BY dist(embedding, [...]) LIMIT N;

CSE用の仮想列

Index Only Scanは主にIO（埋め込みのランダム読み取り）を排除します。冗長な計算をさらに削除するため、Dorisはインデックスが返すdistを式エンジンに列として渡す仮想列を導入します。設計のハイライト：

式ノードVirtualSlotRef
列イテレータVirtualColumnIterator

VirtualSlotRefは計算時に生成される列です：一つの式によって具現化され、多くによって再利用可能で、初回使用時に一度だけ計算されることで、ProjectionとpredicateにわたるCSEを排除します。VirtualColumnIteratorはインデックスが返す距離を式に具現化し、反復する距離計算を回避します。当初はANNクエリCSE排除のために構築されましたが、メカニズムはProjection + Scan + Filterに汎化されました。 ClickBenchデータセットを使用して、以下のクエリはGoogleクリック数によるトップ20のWebサイトをカウントします：

set experimental_enable_virtual_slot_for_cse=true;

SELECT counterid,
       COUNT(*)               AS hit_count,
       COUNT(DISTINCT userid) AS unique_users
FROM   hits
WHERE  ( UPPER(regexp_extract(referer, '^https?://([^/]+)', 1)) = 'GOOGLE.COM'
         OR UPPER(regexp_extract(referer, '^https?://([^/]+)', 1)) = 'GOOGLE.RU'
         OR UPPER(regexp_extract(referer, '^https?://([^/]+)', 1)) LIKE '%GOOGLE%' )
       AND ( LENGTH(regexp_extract(referer, '^https?://([^/]+)', 1)) > 3
              OR regexp_extract(referer, '^https?://([^/]+)', 1) != ''
              OR regexp_extract(referer, '^https?://([^/]+)', 1) IS NOT NULL )
       AND eventdate = '2013-07-15'
GROUP  BY counterid
HAVING hit_count > 100
ORDER  BY hit_count DESC
LIMIT  20;

コア式regexp_extract(referer, '^https?://([^/]+)', 1)はCPU集約的であり、述語間で再利用されます。仮想列を有効にした場合（set experimental_enable_virtual_slot_for_cse=true;）：

有効：0.57秒
無効：1.50秒

エンドツーエンドのパフォーマンスは約3倍向上します。

Scan並列処理の最適化

DorisはAnn TopN検索のScan並列処理を刷新しました。元のポリシーは行数によって並列処理を設定していました（デフォルト：Scanタスクあたり2,097,152行）。セグメントはサイズベースであるため、高次元ベクトル列はセグメントあたりの行数がはるかに少なくなり、1つのScanタスク内で複数のセグメントが順次スキャンされることになります。Dorisは「セグメントあたり1つのScanタスク」に切り替え、インデックススキャンでの並列処理を向上させました。Ann TopNの高いフィルタ率（N行のみが返される）を考慮すると、back-to-tableフェーズはパフォーマンスを損なうことなくシングルスレッドのままでも問題ありません。SIFT 1Mにおいて： set optimize_index_scan_parallelism=true; TopNシングルスレッドクエリのレイテンシは230msから50msに低下します。さらに、4.0では動的並列処理を導入しています：各スケジューリングラウンドの前に、Dorisはスレッドプールの圧迫に基づいて投入するScanタスク数を調整します—高負荷時にはタスクを減らし、アイドル時には増やす—これにより、逐次および並行ワークロード全体でリソース使用とスケジューリングオーバーヘッドのバランスを取ります。

Global TopN遅延マテリアライゼーション

典型的なAnn TopNクエリは2段階で実行されます：

Scanがインデックス経由でセグメントごとのTopN距離を取得
Global sortがセグメントごとのTopNをマージして最終的なTopNを生成

プロジェクションが多くの列や大きな型（例：String）を返す場合、ステージ1で各セグメントからN行を読み取ると重いIOが発生する可能性があり、多くの行がステージ2のglobal sort中に破棄されます。Dorisはglobal TopN遅延マテリアライゼーションによってステージ1のIOを最小化します。 SELECT id, l2_distance_approximate(embedding, [...]) AS dist FROM tbl ORDER BY dist LIMIT 100;の場合：ステージ1はAnn Index Only Scan + 仮想列を通じて、セグメントあたり100個のdist値とrowidのみを出力します。Mセグメントの場合、ステージ2は100 * M個のdist値をグローバルにソートして最終的なTopNとrowidを取得し、その後Materializeオペレータが対応するtablet/rowset/segmentからrowidによって必要な列を取得します。

インデックス作成段階​

マルチレベルシャーディング​

高性能インデックス構築​

並列・高品質インデックス構築​

SIMD​

クエリステージ​

Prepare Statement​

Index Only Scan​

CSE用の仮想列​

Scan並列処理の最適化​

Global TopN遅延マテリアライゼーション​

インデックス作成段階

マルチレベルシャーディング

高性能インデックス構築

並列・高品質インデックス構築

SIMD

クエリステージ

Prepare Statement

Index Only Scan

CSE用の仮想列

Scan並列処理の最適化

Global TopN遅延マテリアライゼーション