加入使用int8range不结垢以及2个大型的Postgres表 [英] Joining 2 large postgres tables using int8range not scaling well
问题描述
我想加入IP路由表信息，IP whois信息。我使用的是亚马逊的RDS这意味着我不能用Postgres ip4r 的延伸，所以我不是使用的int8range 的类型来重新present的IP地址范围，与要点指标。
我的表是这样的：
=＆GT; \ D routing_details
表public.routing_details
专栏|类型|修饰符
---------- + ----------- ----------- +
ASN |文|
网络块|文|
范围| int8range |
索引：
idx_routing_details_netblockB树（网络块）
idx_routing_details_range要点（范围）
=＆GT; \ D netblock_details
表public.netblock_details
专栏|类型|修饰符
------------ + ----------- ----------- +
范围| int8range |
名称|文|
国家|文|
来源|文|
索引：
idx_netblock_details_range要点（范围）
全routing_details表包含刚下600K行，netblock_details含有约8.25M行。有两个表中重叠的范围，但在routing_details表中的每个范围我想获得最好的一个（最小的）从netblock_details表匹配。
我想出了2，我认为将回到使用DISTINCT ON准确的数据，一个使用窗口函数和一个不同的查询：
EXPLAIN SELECT DISTINCT ON（r.netblock）*
从routing_details R连接netblock_details N于r.range＆LT; @ n.range
ORDER BY r.netblock，上（n.range） - 下（n.range）;
查询计划
查询计划
-----------------------------------------------------------------------------------------------------------------------------
独特的（成本= 118452809778.47..118477166326.22行数= 581300宽= 91）
输出：r.asn，r.netblock，r.range，n.range，n.name，n.country，r.netblock，（（上（n.range） - 下（n.range）））
- ＆GT;排序（成本= 118452809778.47..118464988052.34行= 4871309551宽= 91）
输出：r.asn，r.netblock，r.range，n.range，n.name，n.country，r.netblock，（（上（n.range） - 下（n.range）））
排序键：r.netblock，（（上（n.range） - 下（n.range）））
- ＆GT;嵌套循环（成本= 0.00..115920727265.53行= 4871309551宽= 91）
输出：r.asn，r.netblock，r.range，n.range，n.name，n.country，r.netblock，（上（n.range） - 下（n.range））
加入过滤器：（r.range＆LT; @ n.range）
- ＆GT;序列扫描就public.routing_details R（成本= 0.00..11458.96行数= 592496宽= 43）
输出：r.asn，r.netblock，r.range
- ＆GT;物化（成本= 0.00..277082.12行= 8221675宽= 48）
输出：n.range，n.name，n.country
- ＆GT;序列扫描就public.netblock_details N（成本= 0.00..163712.75行= 8221675宽= 48）
输出：n.range，n.name，n.country
（14行） - ＆GT;序列扫描就netblock_details N（成本= 0.00..163712.75行= 8221675宽= 48）
EXPLAIN VERBOSE SELECT * FROM（
SELECT *，ROW_NUMBER（）OVER（PARTITION BY r.range ORDER BY UPPER（n.range） - 下（n.range））AS排名
从routing_details R连接netblock_details N于r.range＆LT; @ n.range
）一个WHERE排名= 1 ORDER BY网络块;
查询计划
---------------------------------------------------------------------------------------------------------------------------------------------------
排序（成本= 118620775630.16..118620836521.53行= 24356548宽= 99）
输出：a.asn，a.netblock，a.range，a.range_1，a.name，a.country，a.rank
排序关键字：a.netblock
- ＆GT;子查询扫描上（成本= 118416274956.83..118611127338.87行= 24356548宽= 99）
输出：a.asn，a.netblock，a.range，a.range_1，a.name，a.country，a.rank
筛选：（a.rank = 1）
- ＆GT; WindowAgg（成本= 118416274956.83..118550235969.49行= 4871309551宽= 91）
输出：（？）r.asn，r.netblock，r.range，n.range，n.name，n.country，ROW_NUMBER（）OVER（（上（n.range） - 下（n.range）） ），r.range
- ＆GT;排序（成本= 118416274956.83..118428453230.71行= 4871309551宽= 91）
输出：（（上（n.range） - 下（n.range））），r.range，r.asn，r.netblock，n.range，n.name，n.country
排序键：r.range，（（上（n.range） - 下（n.range）））
- ＆GT;嵌套循环（成本= 0.00..115884192443.90行= 4871309551宽= 91）
输出：（上（n.range） - 下（n.range）），r.range，r.asn，r.netblock，n.range，n.name，n.country
加入过滤器：（r.range＆LT; @ n.range）
- ＆GT;序列扫描就public.routing_details R（成本= 0.00..11458.96行数= 592496宽= 43）
输出：r.asn，r.netblock，r.range
- ＆GT;物化（成本= 0.00..277082.12行= 8221675宽= 48）
输出：n.range，n.name，n.country
- ＆GT;序列扫描就public.netblock_details N（成本= 0.00..163712.75行= 8221675宽= 48）
输出：n.range，n.name，n.country
（20行）
该DISTINCT ON似乎会更有效，所以我继续用那一个。当我运行对全部数据的查询，我得到一个磁盘空间错误后，围绕24小时的等待。我创建了一个routing_details_small表N行全routing_details表的子集，试图了解发生了什么事情。
使用N = 1000
=＆GT; EXPLAIN ANALYZE SELECT DISTINCT ON（r.netblock）*
- ＆GT;从routing_details_small R连接netblock_details N于r.range＆LT; @ n.range
- ＆GT; ORDER BY r.netblock，上（n.range） - 下（n.range）;
查询计划
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
独特的（成本= 4411888.68..4453012.20行= 999宽度= 90）（实际时间= 124.094..133.720行= 999循环= 1）
- ＆GT;排序（成本= 4411888.68..4432450.44行= 8224705宽= 90）（实际时间= 124.091..128.560行= 4172循环= 1）
排序键：r.netblock，（（上（n.range） - 下（n.range）））
排序方式：外部排序盘：608KB
- ＆GT;嵌套循环（成本= 0.41..1780498.29行= 8224705宽= 90）（实际时间= 0.080..101.518行= 4172循环= 1）
- ＆GT;序列扫描就routing_details_small R（成本= 0.00..20.00行= 1000的宽度= 42）（实际时间= 0.007..1.037行= 1000循环= 1）
- ＆GT;使用idx_netblock_details_range上netblock_details索引扫描N（成本= 0.41..1307.55行数= 41124宽度= 48）（实际时间= 0.063..0.089行= 4圈= 1000）
指数电导率：（r.range＆LT; @范围内）
总运行时间：134.999毫秒
（9行）
使用N = 100000
=＆GT; EXPLAIN ANALYZE SELECT DISTINCT ON（r.netblock）*
- ＆GT;从routing_details_small R连接netblock_details N于r.range＆LT; @ n.range
- ＆GT; ORDER BY r.netblock，上（n.range） - 下（n.range）;
查询计划
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
独特的（成本= 654922588.98..659034941.48行= 200宽度= 144）（实际时间= 28252.677..29487.380行数= 98992循环= 1）
- ＆GT;排序（成本= 654922588.98..656978765.23行= 822470500宽度= 144）（实际时间= 28252.673..28926.703行数= 454856循环= 1）
排序键：r.netblock，（（上（n.range） - 下（n.range）））
排序方式：外部合并磁盘：64488kB
- ＆GT;嵌套循环（成本= 0.41..119890431.75行= 822470500宽度= 144）（实际时间= 0.079..24951.038行数= 454856循环= 1）
- ＆GT;序列扫描就routing_details_small R（成本= 0.00..1935.00行数= 100000宽= 96）（实际时间= 0.007..110.457行数= 100000循环= 1）
- ＆GT;使用idx_netblock_details_range上netblock_details索引扫描N（成本= 0.41..725.96行数= 41124宽度= 48）（实际时间= 0.067..0.235行= 5圈= 100000）
指数电导率：（r.range＆LT; @范围内）
总运行时间：29596.667毫秒
（9行）
使用N = 250000
=＆GT; EXPLAIN ANALYZE SELECT DISTINCT ON（r.netblock）*
- ＆GT;从routing_details_small R连接netblock_details N于r.range＆LT; @ n.range
- ＆GT; ORDER BY r.netblock，上（n.range） - 下（n.range）;
查询计划
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
独特的（成本= 1651822953.55..1662103834.80行= 200宽度= 144）（实际时间= 185835.443..190143.266行数= 247655循环= 1）
- ＆GT;排序（成本= 1651822953.55..1656963394.18行= 2056176250宽= 144）（实际时间= 185835.439..188779.279行= 1103850循环= 1）
排序键：r.netblock，（（上（n.range） - 下（n.range）））
排序方式：外部合并磁盘：155288kB
- ＆GT;嵌套循环（成本= 0.28..300651962.46行= 2056176250宽= 144）（实际时间= 19.325..177403.913行= 1103850循环= 1）
- ＆GT;序列扫描就netblock_details N（成本= 0.00..163743.05行= 8224705宽= 48）（实际时间= 0.007..8160.346行= 8224705循环= 1）
- ＆GT;使用idx_routing_details_small_range上routing_details_smallř索引扫描（成本= 0.28..22.16行= 1250的宽度= 96）（实际时间= 0.018..0.018行= 0循环= 8224705）
指数电导率：（范围＆LT; @ n.range）
总运行时间：190413.912毫秒
（9行）
针对全表600K行查询各地24小时有关运行的磁盘空间不足，这是presumably通过外部合并步骤导致错误后失败。因此，这个查询运作良好，并很快与一小routing_details表，但扩展很差。
建议如何提高我的查询，或甚至架构更改，我可以赚那么这个查询将工作效率上的全部数据？
我在想的横向最初加入作为其他建议的方法（例如，通过欧文Brandstetter修改，在那里，他用简单的网络块的范围，涵盖了给定的范围内，指数并没有多大帮助。
我会在这里重复欧文Brandstetter修改的查询：
SELECT * - 只选择你需要使它更快列
从routing_detailsř
， 侧 （
选择 *
从netblock_detailsñ
WHERE n.ip_min＆LT; = r.ip_min
与n.ip_max＆GT; = 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 。但你必须扫描/读取索引/表的其余部分，并为每一行做检查的第二部分，过滤掉大部分的行。
在换句话说，该指数有助于快速找到起始行，满足第一搜索条件： n.ip_min＆LT; = r.ip_min ，但你会继续阅读满足此条件的所有行，并为每个这样的行进行第二次检查 n.ip_max＆GT; = r.ip_max 。平均而言（如果数据有均匀分布），你就必须读了一半的 netblock_details 表中的行。优化器可以选择使用索引来搜索 n.ip_max＆GT; = r.ip_max ，然后再申请第二个过滤器 n.ip_min＆LT; = R。 ip_min ，但你不能用这个指数来两个过滤器适用在一起。
最终结果：
从 routing_details每行我们将从 netblock_details 仔细阅读半行。 600K * 4M = 2,400,000,000,000行。
它比笛卡儿积2次为宜。你可以看到这个数字（笛卡尔乘积）的的输出EXPLAIN ANALYZE 中的问题。
592496 * 8221675 = 4,871,309,550,800
难怪你的查询试图兑现和排序这个当用完磁盘空间。
整体高水平过程中获得最终结果：
-
连接两个表（没有找到最佳的比赛还没有）。在最坏的情况下，它是笛卡尔乘积，在最好的情况下，它是从
netblock_details所有覆盖范围的每个范围routing_details。你说，在netblock_details的多个项routing_details的每个条目，从3什么10左右。因此，这种连接的结果可以有〜6M行（不要太多） -
订单/分区的结果通过了
routing_details的范围加入，并为每个这样的范围内找到最好的（最小的），涵盖范围从netblock_details。
我的想法是反向查询。与其寻找所有覆盖范围从大 netblock_details 从较小的 routing_details 表的每一行，我建议找到所有较小范围小 routing_details 从各行大 netblock_details 。
两步法
有关从大 netblock_details 找到从 routing_details 所有范围是里面的每一行网络块系列。
我会用下面的架构中查询。我已经添加主键 ID 这两个表。
CREATE TABLE routing_details（
ID INT
，ip_min INT8
，ip_max INT8
，ASN文
，网络块文本
）;
CREATE TABLE netblock_details（
ID INT
，ip_min INT8
，ip_max INT8
，名文
，国家文
，原文
）;
选择
netblock_details.ID AS N_ID
，netblock_details.ip_max - netblock_details.ip_min AS n_length
，r.ID AS R_ID
从
netblock_details
INNER JOIN侧向
（
选择routing_details.ID
从routing_details
哪里
routing_details.ip_min＆GT; = netblock_details.ip_min
与routing_details.ip_min＆LT; = netblock_details.ip_max
- 请注意如何routing_details.ip_min从两侧限制
- 这将使得有可能仅扫描（希望）小
- 部分全或半表的表，而不是
与routing_details.ip_max＆LT; = netblock_details.ip_max
- 这一条款保证了整个路由范围
- 里面的网络块范围
）为R ON真
我们需要对指数。这里最主要的是指数 routing_details （ip_min，ip_max） ip_min 。有第二列的索引可以帮助消除了需要做的查找，值 ip_max ;它不会在树中寻找帮助。
请注意，该横向子查询不具有限制。它不是最后的结果尚未。该查询应该返回〜6M行。在临时表中保存这个结果。
添加一个索引到临时表（R_ID，n_length，N_ID）。 N_ID 又是只删除多余的查找。我们需要一个指数都避免对数据进行排序每个 R_ID 。
最后一步
对于每一行从 routing_details 找到 N_ID 用最小 n_length 。现在，我们可以使用横向参加正确的顺序。在这里，温度 table是previous步随着指数
SELECT
routing_details。*
，t.n_ID
，netblock_details。*
从
routing_details
INNER JOIN侧向
（
选择temp.n_ID
从温度
WHERE temp.r_ID = routing_details.ID
ORDER BY temp.n_length
LIMIT 1
）为t ON真
INNER JOIN netblock_details ON netblock_details.ID = t.n_ID
下面的子查询应该是一个寻求指数的，而不是扫描。优化应该是足够聪明，只是做的寻找和返回，因为 LIMIT 1 ，所以你必须600K寻求指数在600万行的临时表。<第一次发现结果/ P>
原来的答复（我会保持它只是为范围的示意图）：
您可以欺骗？
如果我理解正确的查询，对每个 routing_details.range
你想找到一个最小的 netblock_details.range 覆盖/比 routing_details.range 大。
对于以下示例，其中研究是路由范围和 N1，...，N8 是网络块范围，正确答案是 N5 。
| - |
N1
| ------------------ |
N2
| --------------- |
N3
| ----- |
N4
| ------------------ |
N5
| -------------------------------------- |
N6
| --------------------------- |
N7
| ----- |
N8
| ------------ |
ř
开始结束
n.start＆LT; = r.start和n.end＆GT; = r.end
为了通过n.length
限制1
您说了14小时查询显示，索引扫描了6ms的，但排序通过一系列长了80毫秒。
通过这种搜索有数据没有简单的一维排序。您正在使用 n.start 与 n.end 和 n.length <在一起/ code>。但是，也许你的数据是不是通用的，或者是确定返回略有不同的结果。
例如，如果它是确定返回 N6 作为一个结果，它可以工作得更快。 N6 是具有最大的覆盖范围启动：
n.start＆LT; = r.start和n.end＆GT; = r.end
为了通过n.start降序
限制1
或者，你可以去为 N7 ，其中有最小的结束：
n.start＆LT; = r.start和n.end＆GT; = r.end
为了通过n.end
限制1
本的搜索会使用简单的指数 n.start （或 n.end ），无需额外的排序
第二，完全不同的方法。如何大/长的范围？如果它们是相对较短（几号），那么你可以尝试将它们存储，而不是一个范围内的整数的显式列表。
例如，范围 [5-8] 将被存储为4行：（5，6，7，8）。与此存储模型可能更容易找到范围的交点。
I'd like to join IP routing table information to IP whois information. I'm using Amazon's RDS which means I can't use the Postgres ip4r extension, and so I am instead using int8range types to represent the IP address ranges, with gist indexes.
My tables look like this:
=> \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)
The full routing_details table contains just under 600K rows, and netblock_details contains around 8.25M rows. There are overlapping ranges in both tables, but for each range in the routing_details table I want to get the single best (smallest) match from the netblock_details table.
I came up with 2 different queries that I think will return the accurate data, one using window functions and one using 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)
The DISTINCT ON seems slightly more efficient, so I've proceeded with that one. When I run the query against the full dataset I get an out of disk space error after around a 24h wait. I've created a routing_details_small table with a subset of N rows of the full routing_details table to try and understand what's going on.
With 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)
With 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)
With 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)
Against the full table with 600k rows the query fails after around 24h with an error about running out of disk space, which is presumably caused by the external merge step. So this query is working well and very quickly with a small routing_details table, but is scaling very poorly.
Suggestions for how to improve my query, or perhaps even schema changes I could make so that this query will work efficiently on the full dataset?
I was thinking originally of a lateral join as in other suggested approaches (for example, the last query by Erwin Brandstetter, where he uses simple int8 datatype and simple indexes), but didn't want to write it in the answer, because I thought that it is not really efficient. When you try to find all netblock ranges that cover the given range, an index doesn't help much.
I'll repeat the Erwin Brandstetter's query here:
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;
When you have an index on netblock_details, like this:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
you can quickly (in O(logN)) find the starting point of the scan in the netblock_details table - either the maximum n.ip_min that is less than r.ip_min, or the minimum n.ip_max that is more than r.ip_max. But then you have to scan/read the rest of the index/table and for each row do the second part of the check and filter out most rows.
In other words, this index helps to quickly find the starting row that satisfies first search criteria: n.ip_min <= r.ip_min, but then you'll continue reading all rows that satisfy this criteria and for each such row perform the second check n.ip_max >= r.ip_max. On average (if data has even distribution) you'll have to read half of the rows of the netblock_details table. Optimizer may choose to use index to search n.ip_max >= r.ip_max first and then apply second filter n.ip_min <= r.ip_min, but you can't use this index to apply both filters together.
End result:
for each row from routing_details we'll read through half of rows from netblock_details. 600K * 4M = 2,400,000,000,000 rows.
It is 2 times better than Cartesian product. You can see this number (Cartesian product) in the output of EXPLAIN ANALYZE in the question.
592,496 * 8,221,675 = 4,871,309,550,800
No wonder your queries run out of disk space when trying to materialize and sort this.
The overall high level process to get to the final result:
join two tables (without finding the best match yet). In the worst case it is Cartesian product, in the best case it is all covering ranges from
netblock_detailsfor each range fromrouting_details. You said that there are multiple entries innetblock_detailsfor each entry inrouting_details, anything from 3 to around 10. So, result of this join could have ~6M rows (not too much)order/partition the result of the join by the
routing_detailsranges and for each such range find the best (smallest) covering range fromnetblock_details.
My idea is to reverse the query. Instead of finding all covering ranges from larger netblock_details for each row from smaller routing_details table I suggest to find all smaller ranges from smaller routing_details for each row from larger netblock_details.
Two step process
For each row from larger netblock_details find all ranges from routing_details that are inside the netblock range.
I would use the following schema in the queries. I've added primary key ID to both 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
We need index on routing_details on (ip_min, ip_max). The main thing here is index on ip_min. Having second column in the index helps by eliminating the need to do the lookup for the value of ip_max; it doesn't help in the tree search.
Note that the lateral subquery doesn't have LIMIT. It is not the final result yet. This query should return ~6M rows. Save this result in a temporary table.
Add an index to the temporary table on (r_ID, n_length, n_ID). n_ID is again just to remove extra lookups. We need an index do avoid sorting the data for each r_ID.
Final step
For each row from routing_details find the n_ID with the smallest n_length. Now we can use the lateral join in "proper" order. Here temp table is result of the previous step with the index.
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
Here subquery should be a seek of the index, not scan. Optimizer should be smart enough to do just the seek and return the first found result because of LIMIT 1, so you'll have 600K seeks of index in 6M row temp table.
Original answer (I'll keep it just for the diagram of ranges):
Can you "cheat"?
If I understood your query correctly, for each routing_details.range
you want to find a smallest netblock_details.range that covers/is larger than routing_details.range.
Given the following example, where r is routing range and n1, ..., n8 are netblock ranges, the correct answer is 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
Your query that took 14 hours shows that index scan took 6ms, but sorting by range length took 80ms.
With this kind of search there is no simple 1D ordering of the data. You are using n.start together with n.end and together with n.length. But, maybe your data is not that generic, or it is OK to return a somewhat different result.
For example, if it was OK to return n6 as a result, it could work much faster. n6 is the covering range that has largest start:
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Or, you could go for n7, which has smallest end:
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
This kind of search would use simple index on n.start (or n.end) without extra sorting.
A second, completely different approach. How big/long are the ranges? If they are relatively short (few numbers), then you could try to store them as an explicit list of integers, instead of a range.
For example, range [5-8] would be stored as 4 rows: (5, 6, 7, 8). With this storage model it may be easier to find intersections of ranges.
这篇关于加入使用int8range不结垢以及2个大型的Postgres表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
