質問の歴史
ネストされたセットモデルは、1990年代にジョー・セルコによってSQLでの木構造の表現方法として広まりました。このモデルは、各ノードに左(lft)と右(rgt)の整数境界を割り当てることにより、再帰的な結合を使わずに木構造全体のサブツリーを単純な範囲クエリで選択することを可能にします。しかし、標準では間隔の整合性制約が強制されないため、同時に行われるバルク挿入や従来の移行エラーによって、間隔が部分的に重複する破損がしばしば発生し、階層的なセマンティクスが壊れます。この質問は、OLAPキューブや推薦エンジンを稼働させる前に階層を検証しなければならないデータウェアハウジングシナリオで発生します。
問題
有効なネストされたセットでは、任意の2つのノードは、相互に排他的であるか（a.rgt < b.lft）、または厳密な包含関係にある必要があります（a.lft < b.lft AND a.rgt > b.rgt）。部分的な重複が発生すると、a.lft < b.lftだが、a.rgtがb.lftとb.rgtの間に入るため、ノードが兄弟でもあり、子孫でもあるという論理的な不可能性が生じ、サブツリークエリが壊れます。これらの違反を検出するには、すべての間隔のペアを比較して、適切な包含の欠如を示す交差点を見つける必要があり、手続き的に行うと計算コストが高くなります。
解決策
自己結合を使用して、包含なしの交差を特定するために間隔代数を採用します。この述語は、ノードaがノードbの前に開始し、bの範囲内で終了する場合、部分的な重複を示します。
SELECT a.id AS violating_node_a, b.id AS violating_node_b, a.lft AS a_left, a.rgt AS a_right, b.lft AS b_left, b.rgt AS b_right FROM nested_set a JOIN nested_set b ON a.lft < b.lft -- aはbの前に開始する AND a.rgt > b.lft -- aはbの開始後に終了する（交差） AND a.rgt < b.rgt -- しかし、aはbの終了前に終了する（包含なし） WHERE a.id < b.id; -- 対称的な重複を避ける
このクエリは、違法に交差するすべてのノードのペアを返します。読み取り重視の運用環境で実行可能にするため、(lft, rgt)および(rgt, lft)に対する複合インデックスを使用することで、複雑さが**O(n²)の完全テーブルスキャンからO(n log n)**の範囲検索に軽減されます。
従来のIBM DB2システムからPostgreSQLデータウェアハウスへの小売製品の分類のゼロダウンタイム移行中、エンジニアリングチームは分析ダッシュボードのための迅速なカテゴリー集約クエリをサポートするためにネストされたセットモデルを選択しました。ETLパイプラインは、バッチウィンドウ関数を使用してlftおよびrgtの値を計算しましたが、従来のシステムのエクスポートAPIにおける競合条件がオフバイワンエラーを生じ、147の重複するカテゴリー間隔を引き起こしました。これらの重複により、収益レポートで製品が二重計上され、予測売上が12％増加しました。
3つの修正戦略を評価しました。
戦略1: カーソルを使用した手続き的検証。 PL/pgSQL関数は、すべてのノードを反復処理して、各ノードを高いlft値を持つすべてのノードと比較することで重複を再帰的にチェックしました。概念的には簡単でしたが、このアプローチは行レベルのロックを取得し、230万カテゴリーで38分かかり、在庫更新のための厳格な5分の新鮮さSLAに違反しました。受け入れられない競合の低下のため、拒否されました。
戦略2: 再帰的CTEを使用した再構築。 我々は、ネストされたセットモデルを完全に放棄し、隣接リストから新しい正しい間隔を生成するために再帰的CTEを使用してツリーを再構築することを検討しました。これにより破損は修正されましたが、テーブル全体の書き直しとカタログAPIの一時的な停止が必要で、製品検索をオフラインにすることになりました。また、特定の破損したレコードを監査目的で特定するのではなく、症状を処理することになりました。
戦略3: セットベースの間隔代数（ANSI SQL）。 我々は、厳密に標準のSQL述語を使用して自己結合クエリを実装しました。間隔列のB-treeインデックスを活用することで、検証は4.2秒で完了し、147のノードペアが包含ルールに違反していることを正確に特定しました。これにより、影響を受けたサブカテゴリーのみを手動で修正するために隔離し、カタログの他の部分はライブのままにすることができました。
我々は、著作権を損なうことなく手術的な精度を提供する戦略3を選択しました。結果として、間隔の境界が厳密なスーパセットを形成し、参照整合性が回復され、以降のACID準拠の更新によって新たな重複が導入されることができないようになりました。
ジョイン述語を書くとき、どのように有効な親子包含関係と無効な部分的重複を区別しますか？
候補者は、交差と包含を混同しがちです。彼らはa.lft < b.lft AND a.rgt > b.lft（これは交差をチェックするだけです）を書き、この条件が違反を検出することを誤って信じています。重要な詳細は、エンドポイントの排他性です：厳密な包含のためには、親の右境界が子の右境界を超えなければなりません（a.rgt > b.rgt）。部分的な重複は、特にa.lft < b.lft AND a.rgt > b.lft AND a.rgt < b.rgtが成立するときに発生します。初心者はよく3番目の条件を見逃し、有効な親子ペアに対する誤検出を引き起こします。また、自己ペアを除外すること（a.id != b.id）や、対称的な重複を除外すること（a.id < b.idを強制する）が忘れられ、冗長な違反報告を引き起こします。
ノードが重複を持たないように見えながらも、ルートから孤立している場合、どのようにしてこれを検出しますか？セット操作のみを使用して。
孤立したノードは、単一の行がその全間隔（lft、rgt）を含まない場合に存在します。これにより、ルートへのパスがありません。候補者はしばしばLEFT JOINを使ってNULL親を探そうとしますが、これは真の孤立したノード（親を持たないはずのノード）と正当なルートノードを区別できません。正しいアプローチは、グローバルルートを除外してNOT EXISTSを使用します：
SELECT c.id FROM nested_set c WHERE NOT EXISTS ( SELECT 1 FROM nested_set p WHERE p.lft < c.lft AND p.rgt > c.rgt ) AND c.lft != (SELECT MIN(lft) FROM nested_set);
初心者が見逃すエッジケースは、マルチルートシナリオです：テーブルに2つの別々のツリーが誤って含まれている場合、2番目に小さいlftを持つノードは、最小のlftをチェックするだけでは孤立しているように見えるかもしれません。クエリは、単一のルート（最小lft）を明示的に特定し、それを除外しなければなりません。さもなければ、二次ルートが孤立として誤ってフラグされます。
手続き的なウィンドウ関数なしで、ノードが階層的に関連していない2つの異なる先祖に含まれるマルチ親違反をどのように検出しますか？
これは、重複検出とは異なり、2つの先祖が排他的（有効な兄弟）でありながら、同じ子ノードを不適切に包含しています。これにより、ツリーの特性（単一親）に違反しますが、先祖間の間隔の重複は発生しません。候補者はしばしば、すべての先祖に対してGROUP BY child_id HAVING COUNT(*) > 1を試みますが、これは有効な深いノードが自然に多くの先祖（祖父母など）を持つため、失敗します。解決策は、即時の親を特定することです：子のlft値よりも小さい、lftの最大値を持つ先祖です。
SELECT c.id AS child_id FROM nested_set c JOIN nested_set p ON p.lft < c.lft AND p.rgt > c.rgt WHERE NOT EXISTS ( SELECT 1 FROM nested_set p2 WHERE p2.lft > p.lft AND p2.rgt < p.rgt AND p2.lft < c.lft AND p2.rgt > c.rgt ) GROUP BY c.id HAVING COUNT(*) > 1;
サブクエリは、候補と子の間に中間ノードが存在しないことを確認することで、即時の親をフィルタリングします。初心者はこの「最も近い祖先」の論理を見逃すことが多く、代わりにすべての容器をカウントして、深いノードをすべて違反として誤ってフラグを付けることになります。