int8rangeを使用して2つの大きなpostgresテーブルを結合するとスケーリングがうまくいかない

私はもともと、他の提案されたアプローチと同様に、横方向の結合について考えていました（たとえば、Erwin Brandstetterによる最後のクエリでは、単純なint8を使用しています。データ型と単純なインデックス）ですが、あまり効率的ではないと思ったので、答えには書きたくありませんでした。すべてのnetblockを見つけようとしたとき指定された範囲をカバーする範囲では、インデックスはあまり役に立ちません。

ここでErwinBrandstetterのクエリを繰り返します：

SELECT *  -- only select columns you need to make it faster
FROM   routing_details r
     , LATERAL (
   SELECT *
   FROM   netblock_details n
   WHERE  n.ip_min <= r.ip_min
   AND    n.ip_max >= r.ip_max
   ORDER  BY n.ip_max - n.ip_min
   LIMIT  1
   ) n;

次のように、netblock_detailsにインデックスがある場合：

CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details 
(ip_min, ip_max DESC NULLS LAST);

すばやく実行できます（O(logN) ）netblock_detailsでスキャンの開始点を見つけますテーブル-最大n.ip_minのいずれか r.ip_min未満です、または最小のn.ip_max それはr.ip_max以上です。ただし、インデックス/テーブルの残りの部分をスキャン/読み取り、各行についてチェックの2番目の部分を実行し、ほとんどの行を除外する必要があります。

つまり、このインデックスは、最初の検索条件を満たす開始行をすばやく見つけるのに役立ちます。n.ip_min <= r.ip_min 、ただし、この条件を満たすすべての行の読み取りを続行し、そのような行ごとに2番目のチェックn.ip_max >= r.ip_maxを実行します。。平均して（データが均等に分布している場合）、netblock_detailsの行の半分を読み取る必要があります。テーブル。オプティマイザーは、インデックスを使用してn.ip_max >= r.ip_maxを検索することを選択できます。最初に2番目のフィルターを適用しますn.ip_min <= r.ip_min 、ただし、このインデックスを使用して両方のフィルターを一緒に適用することはできません。

最終結果：routing_detailsの各行 netblock_detailsから行の半分を読み取ります。 600K * 4M=2,400,000,000,000行。デカルト積の2倍優れています。この番号（デカルト積）は、EXPLAIN ANALYZEの出力で確認できます。質問で。

592,496 * 8,221,675 = 4,871,309,550,800

これを具体化して並べ替えようとすると、クエリのディスク容量が不足するのも不思議ではありません。

最終結果に到達するための全体的な高レベルのプロセス：

2つのテーブルを結合します（まだ最適なものを見つけることなく）。最悪の場合はデカルト積であり、最良の場合はすべてnetblock_detailsの範囲をカバーしています。 routing_detailsからの各範囲。 netblock_detailsに複数のエントリがあるとおっしゃいました routing_detailsのエントリごとに、3から約10までのいずれかです。したがって、この結合の結果は、最大600万行（多すぎない）になる可能性があります
routing_detailsによる結合の結果を順序付け/分割します範囲とそのような範囲ごとに、netblock_detailsから最適な（最小の）カバー範囲を見つけます。

私の考えは、クエリを逆にすることです。より大きなnetblock_detailsからすべてのカバー範囲を見つける代わりに小さいrouting_detailsの各行表小さいrouting_detailsからすべての小さい範囲を見つけることをお勧めしますより大きなnetblock_detailsからの各行に対して。

2ステップのプロセス

より大きなnetblock_detailsの各行 routing_detailsからすべての範囲を検索します netblock内にあります範囲。

クエリでは次のスキーマを使用します。主キーIDを追加しました両方のテーブルに。

CREATE TABLE routing_details (
ID        int
,ip_min   int8
,ip_max   int8
,asn      text
,netblock text
);

CREATE TABLE netblock_details (
ID        int
,ip_min   int8
,ip_max   int8
,name     text
,country  text
,source   text
);

SELECT
    netblock_details.ID AS n_ID
    ,netblock_details.ip_max - netblock_details.ip_min AS n_length
    ,r.ID AS r_ID
FROM
    netblock_details
    INNER JOIN LATERAL
    (
        SELECT routing_details.ID
        FROM routing_details
        WHERE
            routing_details.ip_min >= netblock_details.ip_min
            AND routing_details.ip_min <= netblock_details.ip_max
            -- note how routing_details.ip_min is limited from both sides
            -- this would make it possible to scan only (hopefully) small
            -- portion of the table instead of full or half table
            AND routing_details.ip_max <= netblock_details.ip_max
            -- this clause ensures that the whole routing range
            -- is inside the netblock range
    ) AS r ON true

routing_detailsのインデックスが必要です (ip_min, ip_max)で。ここで重要なのは、ip_minのインデックスです。。インデックスに2番目の列があると、ip_maxの値を検索する必要がなくなります。;ツリー検索には役立ちません。

ラテラルサブクエリにはLIMITがないことに注意してください。まだ最終結果ではありません。このクエリは最大600万行を返す必要があります。この結果を一時テーブルに保存します。(r_ID, n_length, n_ID)の一時テーブルにインデックスを追加します。。 n_ID 余分なルックアップを削除するだけです。 r_IDごとにデータを並べ替えないようにインデックスが必要です。

最終ステップ

routing_detailsの各行 n_IDを見つけます最小のn_length 。これで、横方向の結合を「適切な」順序で使用できます。ここでtemp 表は、インデックスを使用した前の手順の結果です。。

SELECT
    routing_details.*
    ,t.n_ID
    ,netblock_details.*
FROM
    routing_details
    INNER JOIN LATERAL
    (
        SELECT temp.n_ID
        FROM temp
        WHERE temp.r_ID = routing_details.ID
        ORDER BY temp.n_length
        LIMIT 1
    ) AS t ON true
    INNER JOIN netblock_details ON netblock_details.ID = t.n_ID

ここで、サブクエリはスキャンではなく、インデックスのシークである必要があります。オプティマイザーは、LIMIT 1のため、シークだけを実行して最初に見つかった結果を返すのに十分スマートである必要があります、したがって、600万行の一時テーブルに600Kのインデックスシークがあります。

元の回答（範囲の図のためだけに保持します）：

「ごまかす」ことはできますか？

routing_details.rangeごとに、クエリを正しく理解した場合最小のnetblock_details.rangeを見つけたいそれはrouting_details.rangeをカバー/より大きい。

次の例を考えます。ここで、r はルーティング範囲であり、n1, ..., n8 ネットブロック範囲である場合、正解はn5です。。

   |---|
   n1

     |------------------|
     n2

                           |---------------|
                           n3

                                          |-----|
                                          n4

                  |------------------|
                  n5

                     |--------------------------------------|
                     n6

        |---------------------------|
        n7

                      |-----|
                      n8

                      |------------|
                      r
                     start       end

n.start <= r.start AND n.end >= r.end
order by n.length
limit 1

14時間かかったクエリは、インデックススキャンに6ミリ秒かかったことを示していますが、範囲の長さによる並べ替えには80ミリ秒かかりました。

この種の検索では、データの単純な1D順序付けはありません。 n.startを使用しています n.endと一緒にそしてn.lengthと一緒に。ただし、データがそれほど一般的ではない場合や、多少異なる結果を返しても問題ない場合があります。

たとえば、n6を返しても問題がない場合結果として、それははるかに速く動作する可能性があります。 n6 startが最大のカバー範囲です：

n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1

または、n7を選択することもできます、最小のend ：

n.start <= r.start AND n.end >= r.end
order by n.end
limit 1

この種の検索では、n.startの単純なインデックスを使用します（またはn.end ）追加の並べ替えなし。

2番目の完全に異なるアプローチ。範囲はどのくらいの大きさ/長さですか？それらが比較的短い（数が少ない）場合は、範囲ではなく整数の明示的なリストとして格納することを試みることができます。たとえば、range [5-8] 4行として保存されます：(5, 6, 7, 8) 。このストレージモデルを使用すると、範囲の共通部分を見つけやすくなる場合があります。