まだ正規化を避けるべきか?スキーマを持ち、それを検索できるようにする
Do we still have to denormalize? Have your schema and search it too (paradedb.com)
要約
この記事は、リレーショナルデータベースにおけるデータ正規化と検索パフォーマンスのトレードオフについて論じています。従来の検索エンジンでは正規化されたデータを扱うのが難しく、ETLプロセスによる正規化解除(デノーマライズ)か、Postgresのようなデータベースでの低速な検索のどちらかを選択する必要がありました。ParadeDBは、この検索ジョインを高速化し、正規化されたスキーマを維持したまま、パフォーマンスの低下なしに検索を実行できるソリューションを提供すると述べています。
全文翻訳
まだ正規化を避けるべきか?スキーマを持ち、それを検索できるようにする
[画像: Stu Hoodのヘッドショット]
Stu Hood著、2026年10月27日
[画像: まだ正規化を避けるべきか?スキーマを持ち、それを検索できるようにする]
検索とは通常、関連性の高い順(BM25やベクトル類似度など)に結果を返すこと、または結果をファセットに要約することを意味します。データが単一の正規化されていないテーブルに格納されている場合、ParadeDBはすでにこれを高速に処理します。
しかし、リレーショナルデータベースでは、データは通常正規化され、users、posts、commentsのような別々のテーブルに分割されています。複数の結合されたテーブルを横断する検索を検索ジョインと呼び、これらのクエリを高速化することは見た目よりも困難です!
歴史的にこのパターンは、人々を速度を選択して脆弱なETLプロセスを通じてElasticsearch1にデノーマライズするか、シンプルさを選択してPostgres2で数百万行を遅くスコアリングおよび結合して少数の結果を返すことを受け入れるかのどちらかに追いやってきました。
私たちは過去数ヶ月間、ParadeDBで検索ジョインをファーストクラスのエクスペリエンスにするために費やしてきました。これにより、複雑さと低速なクエリの間で選択する必要がなくなりました。StackOverflowベンチマークでは、マルチテーブル検索クエリはバニラPostgresよりも最大1000倍高速です(自然な3テーブルのTop-K検索を2分から100ミリ秒に短縮)。追加のインフラストラクチャの負担なしに。
なぜ検索がデノーマライズを促すのか
検索ジョインが実際にはどのようなものかを見るために、StackOverflowのデータモデルを考えてみましょう。これはリレーショナルジョインと検索の両方を行使します:users(230万行)、posts(2000万行)、comments(2900万行)、badges(2940万行)。これらはすべて、検索ボックスやエージェントから簡単にアクセスできる必要があります。
データベースにこのデータセットを格納する場合、ほとんどは正規化されるべきだと直感的に感じるでしょう。ユーザーを投稿やコメントにデノーマライズし、プロファイルが更新されたときに、彼らが過去に行ったすべての投稿やコメントを更新する必要があるのは避けたいでしょう。誰かが検索するとき、あなたは単一のクエリを書いて、users、posts、comments全体で一致するものを、それらの結合された関連性スコアでソートして見つけたいだけです。
SELECT
users.id AS user_id,
users.display_name,
posts.id AS post_id,
posts.title,
comments.id AS comment_id
FROM
users
JOIN posts ON users.id = posts.owner_user_id
JOIN comments ON comments.post_id = posts.id
WHERE
users.about_me ||| 'ocaml'
OR posts.title ||| 'ocaml'
OR comments.text ||| 'ocaml'
ORDER BY
pdb.score(users.id)
+ pdb.score(posts.id)
+ pdb.score(comments.id) DESC,
comments.id DESC
LIMIT 20;
しかし、従来の検索エンジンは、このように記述できないと教えてくれます。Elasticにエクスポートしようとすると、「ネストされたフィールドタイプ」、「エンリッチプロセッサ」、「termsルックアップクエリ」、「runtimeフィールド」、「10,000行バッチサーキットブレーカーを備えたLOOKUP JOIN」、「クライアントサイド_update_by_query」、そして「joinフィールド」(インデックスごとに1つのみ!)をさまようことになります。それでも、ユーザーまたはバッジのいずれかをすべての投稿とコメントにデノーマライズすることを選択する必要があることに気づくでしょう。そして、デノーマライズすると、パワーローの偏りにより、書き込みとスペースの増幅が平均行サイズが示唆するものよりもはるかに悪化します。3 2つのデータベースに書き込むだけでなく、デノーマライズされたコピーはレプリケーション後最大3倍のストレージを消費します。
Postgresで検索ジョインが遅い理由
外部検索エンジンをスキップして、そのクエリをバニラPostgresで直接実行したらどうなるでしょうか? B-Tree + GINスキーマ(8方向並列)では、約2分(118,000ミリ秒)かかります。
「Just Use Postgres」は魅力的なシンプルな答えです。しかし、最小限の妥協でそれを可能にするには、Postgresがインデックス付けとクエリ実行の両方をどのように行うかを再考する必要があります。以前にParadeDBのインデックスがトランザクション整合性をどのように維持するかや、単一テーブルのTop-Kで組み込みインデックスをどのように上回るかについて議論しましたが、ジョインは個々のインデックスの上にあり、Postgresのクエリ実行エンジン内にあります。
検索ジョインを高速に実行するには、Top-Kまたはジョインの上にある集計がユーザーに表示できる量にそのボリュームを減らす前に、可能な限り少ないデータ(ローカリティに優しい方法で)にアクセスする必要があります。この場合、制限された出力(小さなLIMITまたはGROUP BY)は問題の重要な部分です。
[画像: バニラPostgresで検索ジョインが難しい理由]
created_atのような単一の列でソートする場合、PostgresはB-Treeインデックスをウォークし、20個の適合する行が見つかったら終了できます。ORで結合されたテーブルの関連性スコアの合計でソートする場合、どのテーブルもその結合スコアで事前にソートされていません。コメントが'ocaml'を含んでいなくても、その投稿またはユーザーを通じて一致する可能性があるため、Postgresはテーブルを結合する前にテーブルをフィルタリングすることさえできません。すべての2850万行を結合し、すべてのトリプルのスコアを合計し、それからソートして上位20を取得する必要があります。
これらの行すべてを処理するのはコストがかかります。なぜなら、Postgresの行ごとの実行エンジンは、結合するためにテーブルストレージ(ヒープ)からタプルを取得する必要があるからです。そのタプルを取得するとき、そのコストは十分に高いため、Postgresはクエリに必要な可能性のあるすべての列(display_name、titleなど)を常に取得します。たとえその行が後でLIMIT 20によって削除される可能性が非常に高い場合でもです。
集計クエリの場合、Postgresのベクトル化の欠如とヒープから単一の列を選択する必要性は、同様にパフォーマンスを低下させます。カバードB-Treeインデックス(通常は実行する必要がある特定の集計に特化)は役立ちますが、累積するにつれて書き込みスループットが低下し、ランダム書き込みを挿入パスに導入する可能性があります。また、カラムストアの集計パフォーマンスに近づくことはできません。
特殊なクエリ書き換え(例えば、CTEで個別のテーブルごとのクエリの84行のUNION ALLとしてORを書き換える)は、より近い結果を得ることができます。まれな検索語に対しては約2分から1.2秒に短縮されますが、メンテナンスするコードははるかに多くなり、一般的な用語では実行時間が14秒に膨れ上がります。
元の自然なSQLクエリを単一コアで100ミリ秒(84行のUNION ALL書き換えよりも12倍から50倍高速で、完全にデノーマライズされたデータセットの範囲内)まで短縮するには、ジョインと検索インデックスがどのように相互作用するかを再考する必要がありました。
検索ジョインのための実行エンジンの構築
ParadeDBのインデックスは、カラム型ストレージとBM25およびベクトル検索を統合し、クエリされたテーブル全体にわたってジョインキーと投影された列をインデックス内に直接格納します。
Postgresのヒープに対してタプルごとにではなく、そのカラム型データ上で直接ジョインを実行するために、Postgresの実行エンジンを使用することは選択肢ではありませんでした。代わりに、検索ジョインを認識すると、Postgresのクエリプランナーフックを介してクエリプランをインターセプトし、マルチテーブルのJOINとLIMIT / GROUP BY(およびDISTINCT、OVER、FILTERなど)クエリ全体を、Apache DataFusionで構築されたカラム型実行エンジンにプッシュするクエリパスを提案します。検索クエリ以外のすべてのクエリは、変更なしにPostgresの標準プランナーと実行エンジンを引き続き使用します。そして、加速するクエリについては、Postgresと同等であることを保証するために広範なプロパティテストを実施しています。
DataFusionは、現在利用可能な最も高速なOLAPクエリエンジンの1つです。これはベクトル化された実行を中心に構築されており、その共有されないモデルはPostgresのプロセスモデルに最適です。4
しかし、DataFusionのParadeDBにとって最も重要な機能の1つはその拡張性です。分析エンジンをPostgres内の低遅延、トランザクション実行エンジンに変えるために、DataFusionを拡張し、コンパクトな内部ドキュメントIDとジョインキーのみがジョインを通過するようにしました(選択的遅延マテリアライゼーション56を通じて、適切なタイミングまで列のフェッチを遅延させます)。また、Postgres MVCCの可視性チェックがジョインが行を絞り込んだ後まで遅延されるようにしました(ヒープに触れる前にPostgresのインメモリ可視性マップをチェックします)。
今日、この実行エンジンは、検索ワークロードで遭遇するジョイン形状全体で、バニラPostgresよりも大幅に高速です。7 以下では、ほぼすべての検索ページを支える2つのクエリ形状のベンチマークと内部メカニクスを見ていきます。
- 関連性による結合とソート(Top-K):
ORで結合されたテーブル全体で結合スコアによってランク付けされた上位20件の結果を見つけます。これは、0.26.4で導入されたRank Joinと呼ばれる新しい演算子によって実現されます。 - ファセットへの結合とグループ化(集計):ヒープに触れることなく、
ORで結合されたテーブル全体の一致するカテゴリをカウントします。これはタプルタグ付け、インデックス共同パーティショニング、および遅延マテリアライゼーションによって実現されます。
関連性による結合とソート(Top-K)
前述のように、元の3テーブルORクエリは、バニラPostgresにすべての2850万行を結合してからフィルタリングする(約118,000ミリ秒)、または84行のUNION ALL書き換えを維持する(一般的な用語でジョインを3回実行するのに相当し、1.2秒から14秒)ことを強制します。
ParadeDB 0.26.4は、Rank Joinを使用して、すべての選択性レベルで、元の自然なSQLを100〜600ミリ秒で単一コアで実行します。
インタラクティブベンチマークチャート
上記のPostgresプランは最大8ワーカーで並列実行されます。ParadeDBのRank Joinは現在単一コアで実行されます(ベンチマークハーネスを参照)。
仕組み:Rank Joins
結合されたテーブル全体で上位20の結合スコアを、2850万行すべてを結合する前に見つけるにはどうすればよいでしょうか?テーブルを完全に結合して最後にソートするのではなく、Rank Joinは入力(スコアの高い順)をストリームし、候補結果セットを構築しながら進みます。各ストリームで見た最低スコアは、そのSAフロアです。ユーザーのストリームが4.0のSAに達した場合、まだ見ていないユーザーは4.0を超えるスコアを持つことはできません。著者スコアよりも6.0のスコアを持つ投稿は、最大10.0の結合スコアを持つことができます。これにより、実行エンジンは、残りの組み合わせが現在のトップ20の結果を上回ることが証明できると、早期に停止できます。
[画像: ユーザーと投稿間のSorted Access Rank Join]
usersとpostsをusers.id = posts.owner_user_idで結合するだけの場合を考えます。最も基本的な形式9では、Rank JoinはSorted Access(SA)を使用して、各テーブルのスコアソート済みイテレータからトップスコアのusersとpostsをハッシュテーブルと候補ヒープにプルします(usersからu1: 5.0およびu3: 4.0。postsからp2: 6.0およびp1: 4.0)。
ペアの両側が見られた場合、例えば(u1、p1)の場合、ヒープはその正確な結合スコア(5.0 + 4.0 = 9.0)を知っています。
片側のみが見られた場合、例えば投稿p2と著者u2((u2、p2))の場合、ヒープはそれを部分候補として追跡し、usersストリームで見た最低スコア(4.0)をu2のスコアの上限として使用します(? + 6.0 ≤ 10.0)。
十分な行がプルされ、部分的なまたはまだ見ていないペアの上限(閾値)がヒープ内の最高の完全なペア(閾値達成)を上回ることができないと証明されると、次の最高スコアの結合タプルとして(u1、p1)を発行しても安全です。
この基本的な形式の問題は、スコアがゆっくり減少する場合、またはp2(スコア6.0)のような高スコアの投稿が検索用語にまったく一致しなかったユーザーu2(スコア0.0、したがってusers SAストリームに表示されない)の著者であった場合、u2のスコアの上限(≤ 2.5)を下げるためにSA順で数千行をプルする必要があることです。これにより、(u2、p2)が9.0を上回ることができないことが証明されます。
[画像: Rank Joinがランダムアクセスポイントルックアップを送信]
これを修正するために、さらなる研究10により、SAプルと閾値チェックの間にランダムアクセス(RA)が追加されました。ヒープ内の最高の部分候補は、結合キー(users.id = u2)によって反対側のテーブルのインデックスへの直接ポイントルックアップをトリガーし、そのパートナーの正確なスコア(一致しない場合は0.0)を取得します。
RAを使用して(u2、p2)を早期に解決する(0.0 + 6.0 = 6.0)と、9.0を超える唯一の可能性のあるスコアが排除され、閾値達成(4.0 + 4.0 = 8.0 < 9.0)が満たされ、SAストリームがまだトップにある間に(u1、p1)が発行されます。
[画像: 完全な3フェーズRank Joinアニメーション]
DataFusionにストリーミングバイナリジョイン演算子を実装しました。これにより、下流の演算子はストリームが終了するまで結合タプルをプルできます。LIMIT 20で20行後に早期終了する場合でも、3テーブル階層を満たすために必要なだけ消費する2番目のスタックRank Join((users JOIN posts)JOIN comments)を駆動する場合でもです。将来のバージョンでは、さらに実行時間を短縮するために、この演算子をワーカー間で並列化および共同パーティショニングすることをサポートします。
ParadeDB 0.26.4では、結果として完全に透過的なバイナリジョイン演算子が得られ、最も明白で保守しやすいクエリで、100ミリ秒の3テーブルOR Top-Kクエリ(users.display_nameやposts.titleのような投影された列は、最終的な20行に対してのみマテリアライズされます)が可能になります。
ファセットへの結合とグループ化(集計)
検索ページのもう半分は集計(しばしば「ファセット」と呼ばれる)であり、一致した全セットをカテゴリカウントに要約します。例:eコマースサイドバーのブランド、色、サイズの内訳。
Top-Kクエリと同様に、ファセットクエリは、画面上部に表示される小さな結果を返します。集計とは異なり、集計は上位20件で停止するのではなく、すべての一致する行をカウントする必要があります。これは、Rank Joinが集計には適さないことを意味します。
StackOverflowの検索エクスペリエンスでは、Top-20検索結果のすぐ隣に、一致するposts全体の上位10のtagsのサイドバーを表示したいと考えています。ここで、投稿は、'python'が著者about_meまたは投稿のtitleのいずれかに現れる場合に一致します(2000万投稿と230万ユーザーのうち854,000件の一致投稿):
SELECT
posts.tags,
COUNT(*) AS post_count
FROM
users
JOIN posts ON posts.owner_user_id = users.id
WHERE
users.about_me ||| 'python'
OR posts.title ||| 'python'
GROUP BY
posts.tags
ORDER BY
post_count DESC
LIMIT 10;
集計は20行で停止するのではなく、854,000件のすべての一致をカウントする必要があるため、PostgresとParadeDBの両方が、ORフィルターを適用する前に2000万件の投稿と230万人のユーザー全体で並列ハッシュジョインを実行します。Postgresでは、標準SQL JOINはヒープをスキャンして35.3秒かかりますが、手動のUNION書き換え(二重カウントを避けるためにposts.idの重複排除が必要)は、1.0秒まで短縮され、233万バッファを使用します。
ParadeDBでは、自然なSQLクエリはカラム型インデックス内で422ミリ秒で実行され、48倍少ないバッファにヒットします12:
インタラクティブベンチマークチャート
上記のすべてのプランは最大8ワーカーで並列実行されます(ベンチマークハーネスを参照)。
仕組み:タプルタグ付け、共同パーティショニング、および遅延マテリアライゼーション
私たちの実行エンジンにおける3つの技術が組み合わさって、ヒープに触れることなくこのハッシュジョインと集計を高速化します。
- タプルタグ付け13は
ORフィルターを処理します。各テーブルのインデックススキャン中に、各行は'python'に一致したかどうかを示す1ビットフラグでタグ付けされます。そのため、投稿ジョインフィルター(tag_users OR tag_posts)は単純なインメモリビットマップチェックになります。 -
partition_byによるインデックス共同パーティショニングは、ハッシュジョイン自体を高速化します。両方のインデックスがジョインキーでパーティショニングされている場合(注:テーブルではなくインデックスをパーティショニングします。詳細は今後の投稿で)、各並列ワーカーは、競合なしにローカルで結合するためのジョインキーのバランスの取れた範囲を割り当てられます(実行時間を935ミリ秒から422ミリ秒に短縮)。 - 遅延マテリアライゼーションの選択は、ジョインの上にある
GROUP BYを高速化します。ParadeDBは、tag_users OR tag_postsが2000万件の投稿を854,000件の一致に絞り込んだ後、posts.tagsのフェッチを遅延させ、コンパクトな8バイト辞書序数でローカルに集計し、勝ったタグ文字列のみをデコードします。そして、ParadeDBのインデックスはLSMツリーベースであるため、インデックスに追加のファセット列を追加しても(32列以上でも問題ありません!)、ランダムな書き込みトラフィックは増加しません。
スキーマを持ち、それを検索できるようにする
私たちは検索ジョインを改善することに着手しました。なぜなら、ParadeDBに興味のあるほとんどすべてのユーザーが最初にそれについて尋ねるからです。「正規化されたスキーマを持ち、それを検索することもできますか?」私たちは、その質問に「はい」と答える頻度を大幅にシフトさせたと信じており、ユーザーが「Just Use Postgres」できるように支援しています。
正規化されたデータモデルは、アプリケーションにとって正しい選択かもしれません。しかし、デノーマライズが必要だと判断した場合、ParadeDBは最も高速な単一テーブル検索ソリューションの1つでもあり、汎用的でトランザクション的に一貫性のあるデータベースが、物事を複製するのに最適な場所です!
私たちは、正規化されたデータに対する低遅延検索および分析クエリのパフォーマンスを引き続き推進していきます。ご自身のデータでこれらのクエリをテストしたい場合は、ParadeDB Cloudを試すか、ParadeDBをローカルで実行するか、今後の情報にご期待ください!
注釈
- Elasticsearchのような検索エンジンは高速ですが、苦痛なデノーマライズのハードルが必要です。それらは歴史的にジョインやクエリ最適化を避けてきました。なぜなら、それらの不変のLSMツリーのようなアーキテクチャは、デノーマライズされたデータを更新するために必要な巨大なバッチ書き込みを、シーケンシャルセグメント書き込みとして吸収できる一方で、低遅延の読み取りを提供できるからです。 ↩
- Postgresのようなリレーショナルデータベースは、正規化されたスキーマとジョインをネイティブにサポートしますが、関連性スコアリングがジョインに関与する場合に苦労します。Postgresは歴史的に、より多くのデータセットをRAMに収容し、B-Tree(ランダム書き込みを嫌う)上でのトランザクションサイズを削減するために正規化を奨励してきましたが、そのインデックスと実行エンジンは、すべてを結合してスコアリングする前に、マルチテーブル検索のトップ結果を見つける方法がありません。 ↩
- 多作なStackOverflowの著者は、平均的な著者に比べて5倍長い
about_meの紹介文と、投稿あたりのバッジ数が16倍多いです。 ↩ - Postgresのバックグラウンドワーカー全体でのマルチワーカー実行は、datafusion-distributedコントリビューションプロジェクトによってサポートされています。 ↩
- Liu et al. 2024(「現代分析データベースにおける選択的遅延マテリアライゼーション」)。 ↩
ANDで結合されたジョインでは、動的なジョインフィルターもビルド側からプローブ側のインデックススキャンにプッシュされ、行がインデックスから離れる前にそれらをプルーニングします。 ↩- 関連性スコアではなく静的列でソートされたTop-Kジョイン(PostgresがネストループジョインでB-Treeインデックスを使用できる場合)であっても、インデックスバックのネストループジョインのようにRank Joinを使用すると、ParadeDBはネイティブB-Treeネストループの1桁以内に収まります。これは、列ごとのインデックスのランダム書き込みなしで実現されます。 ↩
- フロンティアLLMに単一のSQLクエリを特定の検索語に対してB-TreeおよびGINインデックスの上にハイパー最適化させる場合、それは134行の階層結合された7マッチステートの
LATERALワンダーを生成します。そして、その正確なクエリではより高速(34ミリ秒)ですが、他の選択性レベルでは16.6秒に膨れ上がります。誰もそれを本番環境で保守しないため、チャートからは除外しました。 ↩ - Fagin, Lotem, & Naor 2001(「ミドルウェアのための最適な集計アルゴリズム」)。 ↩
- Bruno, Gravano, & Marian 2002(「Webアクセス可能なデータベース上のTop-kクエリの評価」);Chang & Hwang 2002(「Top-kクエリのための最小プロービング:高価な述語のサポート」);Ilyas, Aref, & Elmagarmid 2004(「リレーショナルデータベースにおけるTop-kジョインクエリのサポート」)。 ↩
- これは、チャート上の逆直感的な結果を説明してもいます。一般的な用語'code'(合計470万件の一致、274ミリ秒)は、'python'(150万件の一致、603ミリ秒)よりも2倍以上高速に実行されます。'code'は非常に頻繁であるため、3つのテーブルすべてで一致するトリプルは各SAストリームの上位に密集して表示され、Top-Kヒープ閾値を迅速に引き上げます。'code'は、3つのテーブル全体で約9,000行をスコアリングした後に収束しますが、'python'は、まだ見ていない組み合わせがトップ20を上回ることができないことを証明するために約18,000行をスコアリングする必要があります。 ↩
ANDまたは単一テーブルのフィルター付きジョインであっても、Postgresがジョイン前にインデックスを使用できる場合(例:170,900件の'python'投稿全体で上位10件のbadgesをカウントし、80倍に広がって1370万件のバッジ行になる場合)、ParadeDBはファセット集計をPostgresの2,225ミリ秒に対して422ミリ秒で実行します(専用のカバードbadges(user_id, name)B-Treeを作成した場合の664ミリ秒。それでもParadeDBよりも122倍多くのバッファにヒットします)。 ↩- Kim & Maden 2024;Candea, Polyzotis, & Vingralek 2009(「高同時実行データウェアハウスのためのスケーラブルで予測可能なジョイン演算子」)。 ↩