sql – 使用int8range连接2个大的postgres表不能很好地缩放

MsSQL 前端之家
前端之家收集整理的这篇文章主要介绍了sql – 使用int8range连接2个大的postgres表不能很好地缩放，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
我想加入IP路由表信息给IP whois信息.我正在使用Amazon的RDS,这意味着我不能使用Postgres ip4r扩展,所以我反而使用 int8range类型来表示IP地址范围,具有 gist索引.

我的表格如下所示：

=> \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表包含的行数不到600K,netblock_details包含大约8.25M行.在两个表中都有重叠的范围,但是对于routing_details表中的每个范围,我想从netblock_details表中获得最佳(最小)的匹配.

我想出了两个不同的查询,我认为会返回准确的数据,一个使用窗口函数,一个使用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,((upper(n.range) - lower(n.range)))
   ->  Sort  (cost=118452809778.47..118464988052.34 rows=4871309551 width=91)
         Output: r.asn,((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,(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.range
               ->  Materialize  (cost=0.00..277082.12 rows=8221675 width=48)
                     Output: n.range,n.country
                     ->  Seq Scan on public.netblock_details n  (cost=0.00..163712.75 rows=8221675 width=48)
                           Output: n.range,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.rank
         Filter: (a.rank = 1)
         ->  WindowAgg  (cost=118416274956.83..118550235969.49 rows=4871309551 width=91)
               Output: r.asn,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.asn,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)),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.range
                           ->  Materialize  (cost=0.00..277082.12 rows=8221675 width=48)
                                 Output: n.range,n.country
                                 ->  Seq Scan on public.netblock_details n  (cost=0.00..163712.75 rows=8221675 width=48)
                                       Output: n.range,n.country
(20 rows)

DISTINCT ON看起来效率稍高,所以我进行了一次.当我针对完整数据集运行查询时,在大约24小时的等待之后,我会发现磁盘空间错误.我创建了一个routing_details_small表,其中包含完整routing_details表的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)

对于600k行的全表,大约24小时后查询失败,出现磁盘空间不足的错误,这可能是由外部合并步骤引起的.所以这个查询使用一个小的routing_details表非常快速地工作,但是扩展性非常差.

关于如何改进我的查询的建议,或者甚至可以改变模式,以便这个查询可以在完整的数据集上有效地工作？

解决方法

我正在考虑其他建议方法(例如,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表中找到扫描的起始点 – 最小n.ip_min小于r.ip_min,或最小n.ip_max大于r.ip_max.但是,您必须扫描/读取索引/表的其余部分,并且对于每一行执行检查的第二部分并过滤出大部分行.

换句话说,此索引有助于快速找到满足第一搜索条件的起始行：n.ip_min <= r.ip_min,但是您将继续阅读满足此条件的所有行,并且对于每个此类行执行第二行检查n.ip_max> = r.ip_max.平均(如果数据均匀分布),您必须读取netblock_details表的一半行.优化器可以选择使用索引首先搜索n.ip_max> = r.ip_max,然后应用第二个过滤器n.ip_min< = r.ip_min,但不能使用此索引将两个过滤器应用于一起. 最终结果：
对于route_details中的每一行,我们将从netblock_details读取一半行. 600K * 4M = 2,400,000,000行.
是笛卡尔乘积的2倍.您可以在问题中的EXPLAIN ANALYZE的输出中看到这个数字(笛卡尔乘积).

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

难怪在尝试实现和排序时,您的查询耗尽磁盘空间.

总体高层次的过程得到最终结果：

>连接两个表(没有找到最好的匹配).在最糟糕的情况下,它是笛卡尔乘积,在最好的情况下,它覆盖范围从netblock_details每个范围从routing_details.你说在routing_details中的每个条目的netblock_details中有多个条目,从3到大约10,所以这个连接的结果可能有〜6M行(不是太多)
>通过routing_details范围对连接的结果进行排序/分区,对于每个这样的范围,从netblock_details找到最佳(最小)的覆盖范围.

我的想法是反转查询.而不是从较小的routing_details表中找到每一行的更大netblock_details的所有覆盖范围,我建议从较大的netblock_details中的每一行的较小的routing_details中找到所有较小的范围.

两步过程

对于每个来自较大netblock_details的行,可以从netblock范围内的routing_details中找到所有范围.

我将在查询中使用以下模式.我已经在两个表中添加了主键ID.

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

CREATE TABLE netblock_details (
ID        int,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

我们需要在route_details上的索引(ip_min,ip_max).这里的主要内容是ip_min的索引.索引中的第二列有助于消除对ip_max的值进行查找的需要;它在树搜索中没有帮助.

请注意,横向子查询没有限制.这不是最后的结果.此查询应返回〜6M行.将此结果保存在临时表中.
在(r_ID,n_length,n_ID)上添加临时表的索引. n_ID也只是为了删除额外的查找.我们需要一个索引,避免为每个r_ID排序数据.

最后一步

对于route_details的每一行,找到n_length最小的n_ID.现在我们可以用“正确”的顺序使用横向连接.这里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,所以你将在6M行临时表中找到600K的索引.

原来的答案(我会保留它的范围图)：

你可以“欺骗”吗

如果我正确地理解你的查询,对于每个routing_details.range
你想要找到一个最小的netblock_details.range,其覆盖/大于routing_details.range.

给定以下示例,其中r是路由范围,n1,…,n8是netblock范围,正确的答案是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显示索引扫描需要6ms,但按范围长度排序需要80ms.

通过这种搜索,数据没有简单的一维排序.你和n.end一起使用n.start和n.length.但是,也许您的数据不是通用的,或者返回一个有些不同的结果是可行的.

例如,如果结果返回n6是可行的,它可以工作得更快. n6是起始最大的覆盖范围：

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

或者,你可以去n7,最小的结局：

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

这种搜索将使用n.start(或n.end)上的简单索引,无需额外排序.

第二个完全不同的方法.范围有多大/长？如果它们相对较短(少数),那么可以尝试将它们存储为显式的整数列表,而不是一个范围.例如,范围[5-8]将被存储为4行：(5,6,7,8).使用这种存储模型,可能会更容易找到范围的交集.

猜你在找的MsSQL相关文章

SQL Server2012高可用之日志传送测试
（一）日志传送架构 （1.1）相关服务器 主服务器 ：用于生产的服务器，上面运行这生产SQL ...
SQL server事物复制报错：要复制的 LOB 数据的长度(xxxxx)超出了配置的最大值 65536
(一)事故背景 最近在SQL Server 2012生产数据库上配置完事物复制（发布订阅）后，生产数据...
SQL Server2012高可用之事物复制(发布订阅)测试
（一）测试目的 目前公司使用的SQL SERVER 2012高可用环境为主备模式，其中主库可执行读写...
使用zabbix监控sql server的发布订阅
（一）背景个人在使用sql server时，用到了sql server的发布订阅来做主从同步，类似MySQL的...
SQL学习（四）集合运算
UNION和OR谓词 找出 product 和 product2 中售价高于 500 的商品的基本信息. select * fro...
SQL学习（五） 高级处理
5.1 请说出针对本章中使用的 product（商品）表执行如下 SELECT 语句所能得到的结果。 SEL...
SQL学习(一）初识数据库
datawhale组队学习SQL task01
SQL学习(二）基础查询与排序
datawhale数据库组队学习第二天打卡
SQL Server 2005 返回修改后的数据
今天在公司看到同事写了个SQL2005的新特性的文章，觉得很实用，在这里和大家分享下。原著作...
SQL Server 数据库最小宕机迁移方案
一、目的 在做SQL Server数据库维护的时候，当上司要求我们把几十G的数据文件搬动到其它服...
MySQLMsSQLOracleSqlitePostgre SQLMariadbMongoDBNoSQLHBaseJDBC
undo日志persistent-cmysql-error-postal-codesql-match-almysql-5.6mysql-8.0database-tri安装路径系统错误data_dir丢失文件主从同步sql_mode数据库目录匿名用户character_seID归零数据库位置查询表重复字段查询字段截断日志SUSPECT7391Remote ServeLinked Serve玄学问题登录不上开启远程访问