使用 int8range 连接 2 个大的 postgres 表不能很好地扩展
Joining 2 large postgres tables using int8range not scaling well
我想将 IP 路由 table 信息加入到 IP whois 信息中。我正在使用 Amazon 的 RDS，这意味着我不能使用 Postgres ip4r extension, and so I am instead using int8range types to represent the IP address ranges, with gist 索引。
我的 table 看起来像这样：
=> \d routing_details
Table "public.routing_details"
Column | Type | Modifiers
----------+-----------+-----------
asn | text |
netblock | text |
range | int8range |
Indexes:
"idx_routing_details_netblock" btree (netblock)
"idx_routing_details_range" gist (range)
=> \d netblock_details
Table "public.netblock_details"
Column | Type | Modifiers
------------+-----------+-----------
range | int8range |
name | text |
country | text |
source | text |
Indexes:
"idx_netblock_details_range" gist (range)
完整的 routing_details table 包含不到 60 万行，netblock_details 包含大约 825 万行。两个 table 中都有重叠范围，但是对于 routing_details table 中的每个范围，我想从 netblock_details [=46 中获得单个最佳（最小）匹配=].
我提出了 2 个不同的查询，我认为 return 会得到准确的数据，一个使用 window 函数，一个使用 DISTINCT ON:
EXPLAIN SELECT DISTINCT ON (r.netblock) *
FROM routing_details r JOIN netblock_details n ON r.range <@ n.range
ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Unique (cost=118452809778.47..118477166326.22 rows=581300 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, ((upper(n.range) - lower(n.range)))
-> Sort (cost=118452809778.47..118464988052.34 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, ((upper(n.range) - lower(n.range)))
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
-> Nested Loop (cost=0.00..115920727265.53 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, (upper(n.range) - lower(n.range))
Join Filter: (r.range <@ n.range)
-> Seq Scan on public.routing_details r (cost=0.00..11458.96 rows=592496 width=43)
Output: r.asn, r.netblock, r.range
-> Materialize (cost=0.00..277082.12 rows=8221675 width=48)
Output: n.range, n.name, n.country
-> Seq Scan on public.netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
Output: n.range, n.name, n.country
(14 rows) -> Seq Scan on netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
EXPLAIN VERBOSE SELECT * FROM (
SELECT *, ROW_NUMBER() OVER (PARTITION BY r.range ORDER BY UPPER(n.range) - LOWER(n.range)) AS rank
FROM routing_details r JOIN netblock_details n ON r.range <@ n.range
) a WHERE rank = 1 ORDER BY netblock;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=118620775630.16..118620836521.53 rows=24356548 width=99)
Output: a.asn, a.netblock, a.range, a.range_1, a.name, a.country, a.rank
Sort Key: a.netblock
-> Subquery Scan on a (cost=118416274956.83..118611127338.87 rows=24356548 width=99)
Output: a.asn, a.netblock, a.range, a.range_1, a.name, a.country, a.rank
Filter: (a.rank = 1)
-> WindowAgg (cost=118416274956.83..118550235969.49 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, row_number() OVER (?), ((upper(n.range) - lower(n.range))), r.range
-> Sort (cost=118416274956.83..118428453230.71 rows=4871309551 width=91)
Output: ((upper(n.range) - lower(n.range))), r.range, r.asn, r.netblock, n.range, n.name, n.country
Sort Key: r.range, ((upper(n.range) - lower(n.range)))
-> Nested Loop (cost=0.00..115884192443.90 rows=4871309551 width=91)
Output: (upper(n.range) - lower(n.range)), r.range, r.asn, r.netblock, n.range, n.name, n.country
Join Filter: (r.range <@ n.range)
-> Seq Scan on public.routing_details r (cost=0.00..11458.96 rows=592496 width=43)
Output: r.asn, r.netblock, r.range
-> Materialize (cost=0.00..277082.12 rows=8221675 width=48)
Output: n.range, n.name, n.country
-> Seq Scan on public.netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
Output: n.range, n.name, n.country
(20 rows)
DISTINCT ON 似乎更有效一些，所以我继续使用它。当我 运行 针对完整数据集的查询时，我在等待大约 24 小时后收到磁盘不足 space 错误。我创建了一个 routing_details_small table，其中包含完整 routing_details table 的 N 行的子集，以尝试了解发生了什么。
N=1000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=4411888.68..4453012.20 rows=999 width=90) (actual time=124.094..133.720 rows=999 loops=1)
-> Sort (cost=4411888.68..4432450.44 rows=8224705 width=90) (actual time=124.091..128.560 rows=4172 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external sort Disk: 608kB
-> Nested Loop (cost=0.41..1780498.29 rows=8224705 width=90) (actual time=0.080..101.518 rows=4172 loops=1)
-> Seq Scan on routing_details_small r (cost=0.00..20.00 rows=1000 width=42) (actual time=0.007..1.037 rows=1000 loops=1)
-> Index Scan using idx_netblock_details_range on netblock_details n (cost=0.41..1307.55 rows=41124 width=48) (actual time=0.063..0.089 rows=4 loops=1000)
Index Cond: (r.range <@ range)
Total runtime: 134.999 ms
(9 rows)
N=100000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=654922588.98..659034941.48 rows=200 width=144) (actual time=28252.677..29487.380 rows=98992 loops=1)
-> Sort (cost=654922588.98..656978765.23 rows=822470500 width=144) (actual time=28252.673..28926.703 rows=454856 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external merge Disk: 64488kB
-> Nested Loop (cost=0.41..119890431.75 rows=822470500 width=144) (actual time=0.079..24951.038 rows=454856 loops=1)
-> Seq Scan on routing_details_small r (cost=0.00..1935.00 rows=100000 width=96) (actual time=0.007..110.457 rows=100000 loops=1)
-> Index Scan using idx_netblock_details_range on netblock_details n (cost=0.41..725.96 rows=41124 width=48) (actual time=0.067..0.235 rows=5 loops=100000)
Index Cond: (r.range <@ range)
Total runtime: 29596.667 ms
(9 rows)
N=250000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=1651822953.55..1662103834.80 rows=200 width=144) (actual time=185835.443..190143.266 rows=247655 loops=1)
-> Sort (cost=1651822953.55..1656963394.18 rows=2056176250 width=144) (actual time=185835.439..188779.279 rows=1103850 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external merge Disk: 155288kB
-> Nested Loop (cost=0.28..300651962.46 rows=2056176250 width=144) (actual time=19.325..177403.913 rows=1103850 loops=1)
-> Seq Scan on netblock_details n (cost=0.00..163743.05 rows=8224705 width=48) (actual time=0.007..8160.346 rows=8224705 loops=1)
-> Index Scan using idx_routing_details_small_range on routing_details_small r (cost=0.28..22.16 rows=1250 width=96) (actual time=0.018..0.018 rows=0 loops=8224705)
Index Cond: (range <@ n.range)
Total runtime: 190413.912 ms
(9 rows)
针对具有 60 万行的完整 table，查询在大约 24 小时后失败，并出现有关 运行 磁盘不足 space 的错误，这可能是由外部合并步骤引起的.因此，此查询在 routing_details table 的情况下运行良好且速度非常快，但扩展性非常差。
关于如何改进我的查询的建议，或者甚至是我可以进行的架构更改，以便此查询能够在完整数据集上高效工作的建议？
我没有很好的答案给你，因为我不熟悉 gist 索引，但我有点感兴趣所以我看了一下你的解释计划。有几件事很突出：
1) 即使在 250K 示例中，您的计划也使用了嵌套循环连接。它是 seq 扫描较大的 table，并在较小的 table 上进行查找。这意味着它在较小的 table 上执行 800 万次索引查找，占用超过 148 秒。令我感到奇怪的是，随着 routing_details_small table 大小的增加，速度会显着降低。就像我说的，我不熟悉要点索引，但我会尝试 set enable_nestloop to false; 看看你是否可以让它进行某种排序的 merge/hash 连接。
2) 最后执行distinct。它只需要一小部分时间（约 11 秒），但这也意味着您可能需要做一些额外的工作。看起来 distinct 使生成的记录数从超过 100 万条减少到 250K，所以我会尝试更早地尝试它。我不确定您是否收到重复项，因为 routing_details_small table 中有多个条目用于 netblock，或者 netblock_details table 有多个匹配给定的网络块。如果是前者，您可以加入只有唯一路由详细信息的子查询。如果是后者，请尝试我要提到的事情：
3) 结合前两个观察结果，您可以尝试从 routing_details_small 上的序列扫描进行部分连接（在子查询上连接）。这应该只会导致 600K 索引扫描。类似的东西（假设是 postgres 9.4）：
SELECT * FROM routing_details_small r,
LATERAL (SELECT * FROM netblock_details n WHERE r.range <@ n.range LIMIT 1) nb;
我最初考虑的是其他建议方法中的横向连接（例如，Erwin Brandstetter 的最后一个查询，他使用简单的 int8 数据类型和简单的索引），但不想把它写在答案中，因为我认为它不是很有效。当您尝试查找涵盖给定范围的所有 netblock 个范围时，索引帮不上什么忙。
我将在这里重复 Erwin Brandstetter 的查询：
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 table 中找到扫描的起点 - 小于 [= 的最大值 n.ip_min 23=]，或大于 r.ip_max 的最小值 n.ip_max。但是然后你必须 scan/read index/table 的其余部分，并对每一行进行检查的第二部分并过滤掉大多数行。
换句话说，此索引有助于快速找到满足第一个搜索条件的起始行：n.ip_min <= r.ip_min，但随后您将继续阅读满足此条件的所有行，并对每个此类行执行第二次检查 n.ip_max >= r.ip_max。平均而言（如果数据分布均匀），您必须读取 netblock_details table 的一半行。优化器可能会选择先使用索引搜索 n.ip_max >= r.ip_max，然后应用第二个过滤器 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
难怪您在尝试具体化和排序时查询 运行 磁盘 space。
获得最终结果的总体高级过程：
加入两个 table（尚未找到最佳匹配）。在最坏的情况下它是笛卡尔积，在最好的情况下它全部覆盖从 netblock_details 开始的每个范围 routing_details。您说 routing_details 中的每个条目在 netblock_details 中有多个条目，从 3 到 10 左右不等。因此，此连接的结果可能有 ~6M 行（不是太多）
order/partition routing_details 范围的连接结果，并为每个这样的范围找到最佳（最小）覆盖范围 netblock_details.
我的想法是逆向查询。而不是从较小的 routing_details table 中的每一行找到较大的 netblock_details 的所有覆盖范围我建议从较大的 [=21] 中的每一行从较小的 routing_details 中找到所有较小的范围=].
两步过程
对于较大的 netblock_details 中的每一行，找到 routing_details 中 netblock 范围内的所有范围。
我会在查询中使用以下架构。我已经将主键 ID 添加到两个 tables.
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
我们需要 (ip_min, ip_max) 上 routing_details 的索引。这里最主要的是 ip_min 上的索引。在索引中有第二列有助于消除查找 ip_max 值的需要；它对树搜索没有帮助。
注意横向子查询没有LIMIT。目前还不是最终结果。此查询应 return ~6M 行。将此结果保存在临时 table 中。
在 (r_ID, n_length, n_ID) 上为临时 table 添加索引。 n_ID 再次只是为了删除额外的查找。我们需要一个索引来避免对每个 r_ID.
的数据进行排序
最后一步
对于 routing_details 中的每一行，找到具有最小 n_length 的 n_ID。现在我们可以使用 "proper" 顺序的横向连接。这里 temp table 是上一步的结果 和索引 .
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，优化器应该足够聪明，只执行查找和 return 第一个找到的结果，因此您将在 6M 行温度 table.[=80 中进行 600K 索引查找=]
原始答案（我将保留它只是为了范围图）：
你能"cheat"吗？
如果我正确理解了您的查询，对于每个 routing_details.range
你想找到一个比 routing_details.range.
大 covers/is 的最小 netblock_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
您的 query that took 14 hours 显示索引扫描用了 6 毫秒，但按范围长度排序用了 80 毫秒。
这种搜索没有简单的一维数据排序。您正在使用 n.start 和 n.end 以及 n.length。但是，也许您的数据不是那么通用，或者可以 return 稍微不同的结果。
例如，如果结果 return 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）上使用简单索引，无需额外排序。
第二种，完全不同的方法。 big/long 范围如何？如果它们相对较短（数字很少），那么您可以尝试将它们存储为一个明确的整数列表，而不是一个范围。
例如，范围 [5-8] 将存储为 4 行：(5, 6, 7, 8)。使用此存储模型，可能更容易找到范围的交集。
我不知道这是否适用于真实数据。 candidate selection 被挤进了内循环，这对我来说似乎很好。在测试时，它给出了两次索引扫描（加上一次用于反连接），避免了最后的 sort/unique。它似乎确实给出了相同的结果。
-- EXPLAIN ANALYZE
SELECT *
FROM routing_details r
JOIN netblock_details n ON r.range <@ n.range
-- We want the smallest overlapping range
-- Use "Not exists" to suppress overlapping ranges
-- that are larger than n
-- (this should cause an antijoin)
WHERE NOT EXISTS(
SELECT * FROM netblock_details nx
WHERE r.range <@ nx.range -- should enclose r
AND n.range <> nx.range -- but differ from n
AND (nx.range <@ n.range -- and overlap n, or be larger
OR upper(nx.range) - lower(nx.range) < upper(n.range) - lower(n.range)
OR (upper(nx.range) - lower(nx.range) = upper(n.range) - lower(n.range) AND lower(nx.range) > lower(n.range) )
)
)
ORDER BY r.netblock
-- not needed any more
-- , upper(n.range) - lower(n.range)
;
更新：（FWIW）作为奖励，我的测试数据集
CREATE Table routing_details
( asn text
, netblock text
, range int8range
);
-- Indexes:
CREATE INDEX idx_routing_details_netblock ON routing_details (netblock);
CREATE INDEX idx_routing_details_range ON routing_details USING gist(range) ;
CREATE Table netblock_details
( range int8range
, name text
, country text
, source text
);
-- Indexes:
CREATE INDEX idx_netblock_details_range ON netblock_details USING gist(range);
-- the smaller table
INSERT INTO routing_details(range,netblock)
SELECT int8range(gs, gs+13), 'block_' || gs::text
FROM generate_series(0,1000000, 11) gs
;
-- the larger table
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+17), 'name_' || gs::text
FROM generate_series(0,1000000, 17) gs
;
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+19), 'name_' || gs::text
FROM generate_series(0,1000000, 19) gs
;
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+23), 'name_' || gs::text
FROM generate_series(0,1000000, 23) gs
;
VACUUM ANALYZE routing_details;
VACUUM ANALYZE netblock_details;
使用 LATERAL join（在 routing_details 中查找每行的最小匹配）：
当前的数据库设计
这些查询的唯一相关索引是：
"idx_netblock_details_range" gist (range)
其他指标与此处无关
查询
SELECT * -- only select columns you need to make it faster
FROM routing_details r
, LATERAL (
SELECT *
FROM netblock_details n
WHERE n.range @> r.range
ORDER BY upper(n.range) - lower(n.range)
LIMIT 1
) n
SQL Fiddle具有更真实的测试数据。
与您的原始查询一样，routing_details 中没有 netblock_details 中任何匹配项的行将从结果中删除。
性能取决于数据分布。这在许多比赛中应该更胜一筹。 DISTINCT ON 可能在 routing_details 中每行只有很少的比赛获胜 - 但它需要 很多 的 work_mem 来进行大排序。为大查询设置大约 200 MB。在同一事务中使用 SET LOCAL：
- Configuration parameter work_mem in PostgreSQL on Linux
这个查询将不需要那么多的排序内存。与 DISTINCT ON 不同，您不应该看到 Postgres 交换到磁盘以使用 work_mem 的中等设置进行排序。所以在 EXPLAIN ANALYZE 输出中没有这样的行：
Sort Method: external merge Disk: 155288kB
更简单的数据库设计
再看一遍，我测试了一个简化的设计，它使用简单的 int8 列作为下限和上限，而不是范围类型和一个简单的 btree 索引：
CREATE TABLE routing_details ( -- SMALL table
ip_min int8
, ip_max int8
, asn text
, netblock text
);
CREATE TABLE netblock_details ( -- BIG table
ip_min int8
, ip_max int8
, name text
, country text
, source text
);
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
对第二个索引列进行排序 DESC NULLS LAST 是必不可少的！
查询
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;
相同的基本技术。在我的测试中，这比第一种方法快 3 倍。但对于数百万行来说仍然不够快。
技术详解（以b-tree索引为例，但查询原理与GiST索引类似）：
- Optimize GROUP BY query to retrieve latest record per user
对于 DISTINCT ON 变体：
- Select first row in each GROUP BY group?
高级解决方案
以上解决方案与 routing_details 中的行数成线性比例关系，但随着 netblock_details 中的匹配数而恶化。它终于回到了我的身边：我们已经 在 之前 dba.SE 上解决了这个问题，使用更复杂的方法产生了更好的性能：
链接答案中的 frequency 在此处扮演 ip_max - n.ip_min / upper(range) - lower(range) 的角色。
我想将 IP 路由 table 信息加入到 IP whois 信息中。我正在使用 Amazon 的 RDS，这意味着我不能使用 Postgres ip4r extension, and so I am instead using int8range types to represent the IP address ranges, with gist 索引。
我的 table 看起来像这样：
=> \d routing_details
Table "public.routing_details"
Column | Type | Modifiers
----------+-----------+-----------
asn | text |
netblock | text |
range | int8range |
Indexes:
"idx_routing_details_netblock" btree (netblock)
"idx_routing_details_range" gist (range)
=> \d netblock_details
Table "public.netblock_details"
Column | Type | Modifiers
------------+-----------+-----------
range | int8range |
name | text |
country | text |
source | text |
Indexes:
"idx_netblock_details_range" gist (range)
完整的 routing_details table 包含不到 60 万行，netblock_details 包含大约 825 万行。两个 table 中都有重叠范围，但是对于 routing_details table 中的每个范围，我想从 netblock_details [=46 中获得单个最佳（最小）匹配=].
我提出了 2 个不同的查询，我认为 return 会得到准确的数据，一个使用 window 函数，一个使用 DISTINCT ON:
EXPLAIN SELECT DISTINCT ON (r.netblock) *
FROM routing_details r JOIN netblock_details n ON r.range <@ n.range
ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Unique (cost=118452809778.47..118477166326.22 rows=581300 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, ((upper(n.range) - lower(n.range)))
-> Sort (cost=118452809778.47..118464988052.34 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, ((upper(n.range) - lower(n.range)))
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
-> Nested Loop (cost=0.00..115920727265.53 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, r.netblock, (upper(n.range) - lower(n.range))
Join Filter: (r.range <@ n.range)
-> Seq Scan on public.routing_details r (cost=0.00..11458.96 rows=592496 width=43)
Output: r.asn, r.netblock, r.range
-> Materialize (cost=0.00..277082.12 rows=8221675 width=48)
Output: n.range, n.name, n.country
-> Seq Scan on public.netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
Output: n.range, n.name, n.country
(14 rows) -> Seq Scan on netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
EXPLAIN VERBOSE SELECT * FROM (
SELECT *, ROW_NUMBER() OVER (PARTITION BY r.range ORDER BY UPPER(n.range) - LOWER(n.range)) AS rank
FROM routing_details r JOIN netblock_details n ON r.range <@ n.range
) a WHERE rank = 1 ORDER BY netblock;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=118620775630.16..118620836521.53 rows=24356548 width=99)
Output: a.asn, a.netblock, a.range, a.range_1, a.name, a.country, a.rank
Sort Key: a.netblock
-> Subquery Scan on a (cost=118416274956.83..118611127338.87 rows=24356548 width=99)
Output: a.asn, a.netblock, a.range, a.range_1, a.name, a.country, a.rank
Filter: (a.rank = 1)
-> WindowAgg (cost=118416274956.83..118550235969.49 rows=4871309551 width=91)
Output: r.asn, r.netblock, r.range, n.range, n.name, n.country, row_number() OVER (?), ((upper(n.range) - lower(n.range))), r.range
-> Sort (cost=118416274956.83..118428453230.71 rows=4871309551 width=91)
Output: ((upper(n.range) - lower(n.range))), r.range, r.asn, r.netblock, n.range, n.name, n.country
Sort Key: r.range, ((upper(n.range) - lower(n.range)))
-> Nested Loop (cost=0.00..115884192443.90 rows=4871309551 width=91)
Output: (upper(n.range) - lower(n.range)), r.range, r.asn, r.netblock, n.range, n.name, n.country
Join Filter: (r.range <@ n.range)
-> Seq Scan on public.routing_details r (cost=0.00..11458.96 rows=592496 width=43)
Output: r.asn, r.netblock, r.range
-> Materialize (cost=0.00..277082.12 rows=8221675 width=48)
Output: n.range, n.name, n.country
-> Seq Scan on public.netblock_details n (cost=0.00..163712.75 rows=8221675 width=48)
Output: n.range, n.name, n.country
(20 rows)
DISTINCT ON 似乎更有效一些，所以我继续使用它。当我 运行 针对完整数据集的查询时，我在等待大约 24 小时后收到磁盘不足 space 错误。我创建了一个 routing_details_small table，其中包含完整 routing_details table 的 N 行的子集，以尝试了解发生了什么。
N=1000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=4411888.68..4453012.20 rows=999 width=90) (actual time=124.094..133.720 rows=999 loops=1)
-> Sort (cost=4411888.68..4432450.44 rows=8224705 width=90) (actual time=124.091..128.560 rows=4172 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external sort Disk: 608kB
-> Nested Loop (cost=0.41..1780498.29 rows=8224705 width=90) (actual time=0.080..101.518 rows=4172 loops=1)
-> Seq Scan on routing_details_small r (cost=0.00..20.00 rows=1000 width=42) (actual time=0.007..1.037 rows=1000 loops=1)
-> Index Scan using idx_netblock_details_range on netblock_details n (cost=0.41..1307.55 rows=41124 width=48) (actual time=0.063..0.089 rows=4 loops=1000)
Index Cond: (r.range <@ range)
Total runtime: 134.999 ms
(9 rows)
N=100000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=654922588.98..659034941.48 rows=200 width=144) (actual time=28252.677..29487.380 rows=98992 loops=1)
-> Sort (cost=654922588.98..656978765.23 rows=822470500 width=144) (actual time=28252.673..28926.703 rows=454856 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external merge Disk: 64488kB
-> Nested Loop (cost=0.41..119890431.75 rows=822470500 width=144) (actual time=0.079..24951.038 rows=454856 loops=1)
-> Seq Scan on routing_details_small r (cost=0.00..1935.00 rows=100000 width=96) (actual time=0.007..110.457 rows=100000 loops=1)
-> Index Scan using idx_netblock_details_range on netblock_details n (cost=0.41..725.96 rows=41124 width=48) (actual time=0.067..0.235 rows=5 loops=100000)
Index Cond: (r.range <@ range)
Total runtime: 29596.667 ms
(9 rows)
N=250000
=> EXPLAIN ANALYZE SELECT DISTINCT ON (r.netblock) *
-> FROM routing_details_small r JOIN netblock_details n ON r.range <@ n.range
-> ORDER BY r.netblock, upper(n.range) - lower(n.range);
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Unique (cost=1651822953.55..1662103834.80 rows=200 width=144) (actual time=185835.443..190143.266 rows=247655 loops=1)
-> Sort (cost=1651822953.55..1656963394.18 rows=2056176250 width=144) (actual time=185835.439..188779.279 rows=1103850 loops=1)
Sort Key: r.netblock, ((upper(n.range) - lower(n.range)))
Sort Method: external merge Disk: 155288kB
-> Nested Loop (cost=0.28..300651962.46 rows=2056176250 width=144) (actual time=19.325..177403.913 rows=1103850 loops=1)
-> Seq Scan on netblock_details n (cost=0.00..163743.05 rows=8224705 width=48) (actual time=0.007..8160.346 rows=8224705 loops=1)
-> Index Scan using idx_routing_details_small_range on routing_details_small r (cost=0.28..22.16 rows=1250 width=96) (actual time=0.018..0.018 rows=0 loops=8224705)
Index Cond: (range <@ n.range)
Total runtime: 190413.912 ms
(9 rows)
针对具有 60 万行的完整 table，查询在大约 24 小时后失败，并出现有关 运行 磁盘不足 space 的错误，这可能是由外部合并步骤引起的.因此，此查询在 routing_details table 的情况下运行良好且速度非常快，但扩展性非常差。
关于如何改进我的查询的建议，或者甚至是我可以进行的架构更改，以便此查询能够在完整数据集上高效工作的建议？
我没有很好的答案给你，因为我不熟悉 gist 索引，但我有点感兴趣所以我看了一下你的解释计划。有几件事很突出：
1) 即使在 250K 示例中，您的计划也使用了嵌套循环连接。它是 seq 扫描较大的 table，并在较小的 table 上进行查找。这意味着它在较小的 table 上执行 800 万次索引查找，占用超过 148 秒。令我感到奇怪的是，随着 routing_details_small table 大小的增加，速度会显着降低。就像我说的，我不熟悉要点索引，但我会尝试 set enable_nestloop to false; 看看你是否可以让它进行某种排序的 merge/hash 连接。
2) 最后执行distinct。它只需要一小部分时间（约 11 秒），但这也意味着您可能需要做一些额外的工作。看起来 distinct 使生成的记录数从超过 100 万条减少到 250K，所以我会尝试更早地尝试它。我不确定您是否收到重复项，因为 routing_details_small table 中有多个条目用于 netblock，或者 netblock_details table 有多个匹配给定的网络块。如果是前者，您可以加入只有唯一路由详细信息的子查询。如果是后者，请尝试我要提到的事情：
3) 结合前两个观察结果，您可以尝试从 routing_details_small 上的序列扫描进行部分连接（在子查询上连接）。这应该只会导致 600K 索引扫描。类似的东西（假设是 postgres 9.4）：
SELECT * FROM routing_details_small r,
LATERAL (SELECT * FROM netblock_details n WHERE r.range <@ n.range LIMIT 1) nb;
我最初考虑的是其他建议方法中的横向连接（例如，Erwin Brandstetter 的最后一个查询，他使用简单的 int8 数据类型和简单的索引），但不想把它写在答案中，因为我认为它不是很有效。当您尝试查找涵盖给定范围的所有 netblock 个范围时，索引帮不上什么忙。
我将在这里重复 Erwin Brandstetter 的查询：
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 table 中找到扫描的起点 - 小于 [= 的最大值 n.ip_min 23=]，或大于 r.ip_max 的最小值 n.ip_max。但是然后你必须 scan/read index/table 的其余部分，并对每一行进行检查的第二部分并过滤掉大多数行。
换句话说，此索引有助于快速找到满足第一个搜索条件的起始行：n.ip_min <= r.ip_min，但随后您将继续阅读满足此条件的所有行，并对每个此类行执行第二次检查 n.ip_max >= r.ip_max。平均而言（如果数据分布均匀），您必须读取 netblock_details table 的一半行。优化器可能会选择先使用索引搜索 n.ip_max >= r.ip_max，然后应用第二个过滤器 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
难怪您在尝试具体化和排序时查询 运行 磁盘 space。
获得最终结果的总体高级过程：
加入两个 table（尚未找到最佳匹配）。在最坏的情况下它是笛卡尔积，在最好的情况下它全部覆盖从
netblock_details开始的每个范围routing_details。您说routing_details中的每个条目在netblock_details中有多个条目，从 3 到 10 左右不等。因此，此连接的结果可能有 ~6M 行（不是太多）order/partition
routing_details范围的连接结果，并为每个这样的范围找到最佳（最小）覆盖范围netblock_details.
我的想法是逆向查询。而不是从较小的 routing_details table 中的每一行找到较大的 netblock_details 的所有覆盖范围我建议从较大的 [=21] 中的每一行从较小的 routing_details 中找到所有较小的范围=].
两步过程
对于较大的 netblock_details 中的每一行，找到 routing_details 中 netblock 范围内的所有范围。
我会在查询中使用以下架构。我已经将主键 ID 添加到两个 tables.
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
我们需要 (ip_min, ip_max) 上 routing_details 的索引。这里最主要的是 ip_min 上的索引。在索引中有第二列有助于消除查找 ip_max 值的需要；它对树搜索没有帮助。
注意横向子查询没有LIMIT。目前还不是最终结果。此查询应 return ~6M 行。将此结果保存在临时 table 中。
在 (r_ID, n_length, n_ID) 上为临时 table 添加索引。 n_ID 再次只是为了删除额外的查找。我们需要一个索引来避免对每个 r_ID.
最后一步
对于 routing_details 中的每一行，找到具有最小 n_length 的 n_ID。现在我们可以使用 "proper" 顺序的横向连接。这里 temp table 是上一步的结果 和索引 .
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，优化器应该足够聪明，只执行查找和 return 第一个找到的结果，因此您将在 6M 行温度 table.[=80 中进行 600K 索引查找=]
原始答案（我将保留它只是为了范围图）：
你能"cheat"吗？
如果我正确理解了您的查询，对于每个 routing_details.range
你想找到一个比 routing_details.range.
netblock_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
您的 query that took 14 hours 显示索引扫描用了 6 毫秒，但按范围长度排序用了 80 毫秒。
这种搜索没有简单的一维数据排序。您正在使用 n.start 和 n.end 以及 n.length。但是，也许您的数据不是那么通用，或者可以 return 稍微不同的结果。
例如，如果结果 return 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）上使用简单索引，无需额外排序。
第二种，完全不同的方法。 big/long 范围如何？如果它们相对较短（数字很少），那么您可以尝试将它们存储为一个明确的整数列表，而不是一个范围。
例如，范围 [5-8] 将存储为 4 行：(5, 6, 7, 8)。使用此存储模型，可能更容易找到范围的交集。
我不知道这是否适用于真实数据。 candidate selection 被挤进了内循环，这对我来说似乎很好。在测试时，它给出了两次索引扫描（加上一次用于反连接），避免了最后的 sort/unique。它似乎确实给出了相同的结果。
-- EXPLAIN ANALYZE
SELECT *
FROM routing_details r
JOIN netblock_details n ON r.range <@ n.range
-- We want the smallest overlapping range
-- Use "Not exists" to suppress overlapping ranges
-- that are larger than n
-- (this should cause an antijoin)
WHERE NOT EXISTS(
SELECT * FROM netblock_details nx
WHERE r.range <@ nx.range -- should enclose r
AND n.range <> nx.range -- but differ from n
AND (nx.range <@ n.range -- and overlap n, or be larger
OR upper(nx.range) - lower(nx.range) < upper(n.range) - lower(n.range)
OR (upper(nx.range) - lower(nx.range) = upper(n.range) - lower(n.range) AND lower(nx.range) > lower(n.range) )
)
)
ORDER BY r.netblock
-- not needed any more
-- , upper(n.range) - lower(n.range)
;
更新：（FWIW）作为奖励，我的测试数据集
CREATE Table routing_details
( asn text
, netblock text
, range int8range
);
-- Indexes:
CREATE INDEX idx_routing_details_netblock ON routing_details (netblock);
CREATE INDEX idx_routing_details_range ON routing_details USING gist(range) ;
CREATE Table netblock_details
( range int8range
, name text
, country text
, source text
);
-- Indexes:
CREATE INDEX idx_netblock_details_range ON netblock_details USING gist(range);
-- the smaller table
INSERT INTO routing_details(range,netblock)
SELECT int8range(gs, gs+13), 'block_' || gs::text
FROM generate_series(0,1000000, 11) gs
;
-- the larger table
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+17), 'name_' || gs::text
FROM generate_series(0,1000000, 17) gs
;
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+19), 'name_' || gs::text
FROM generate_series(0,1000000, 19) gs
;
INSERT INTO netblock_details(range,name)
SELECT int8range(gs, gs+23), 'name_' || gs::text
FROM generate_series(0,1000000, 23) gs
;
VACUUM ANALYZE routing_details;
VACUUM ANALYZE netblock_details;
使用 LATERAL join（在 routing_details 中查找每行的最小匹配）：
当前的数据库设计
这些查询的唯一相关索引是：
"idx_netblock_details_range" gist (range)
其他指标与此处无关
查询
SELECT * -- only select columns you need to make it faster
FROM routing_details r
, LATERAL (
SELECT *
FROM netblock_details n
WHERE n.range @> r.range
ORDER BY upper(n.range) - lower(n.range)
LIMIT 1
) n
SQL Fiddle具有更真实的测试数据。
与您的原始查询一样，routing_details 中没有 netblock_details 中任何匹配项的行将从结果中删除。
性能取决于数据分布。这在许多比赛中应该更胜一筹。 DISTINCT ON 可能在 routing_details 中每行只有很少的比赛获胜 - 但它需要 很多 的 work_mem 来进行大排序。为大查询设置大约 200 MB。在同一事务中使用 SET LOCAL：
- Configuration parameter work_mem in PostgreSQL on Linux
这个查询将不需要那么多的排序内存。与 DISTINCT ON 不同，您不应该看到 Postgres 交换到磁盘以使用 work_mem 的中等设置进行排序。所以在 EXPLAIN ANALYZE 输出中没有这样的行：
Sort Method: external merge Disk: 155288kB
更简单的数据库设计
再看一遍，我测试了一个简化的设计，它使用简单的 int8 列作为下限和上限，而不是范围类型和一个简单的 btree 索引：
CREATE TABLE routing_details ( -- SMALL table
ip_min int8
, ip_max int8
, asn text
, netblock text
);
CREATE TABLE netblock_details ( -- BIG table
ip_min int8
, ip_max int8
, name text
, country text
, source text
);
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
对第二个索引列进行排序 DESC NULLS LAST 是必不可少的！
查询
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;
相同的基本技术。在我的测试中，这比第一种方法快 3 倍。但对于数百万行来说仍然不够快。
技术详解（以b-tree索引为例，但查询原理与GiST索引类似）：
- Optimize GROUP BY query to retrieve latest record per user
对于 DISTINCT ON 变体：
- Select first row in each GROUP BY group?
高级解决方案
以上解决方案与 routing_details 中的行数成线性比例关系，但随着 netblock_details 中的匹配数而恶化。它终于回到了我的身边：我们已经 在 之前 dba.SE 上解决了这个问题，使用更复杂的方法产生了更好的性能：
frequency 在此处扮演 ip_max - n.ip_min / upper(range) - lower(range) 的角色。