主页 / dba / 问题 / 317886
Accepted
Vladimir Baranov
Asked: 2022-10-06 22:30:11 +0800 CST

Postgres 可以向后扫描索引吗？

  • 772

我们使用 Amazon RDS 实例

x86_64-pc-linux-gnu 上的 PostgreSQL 11.13，由 gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12) 编译，64 位

我有一个简单的经典 top-1-per-group 查询。我需要为每个creativeScheduleId.

这是一个表和索引定义：

CREATE TABLE IF NOT EXISTS public.creative_schedule_status_histories (
  id serial PRIMARY KEY,
  "creativeScheduleId" text NOT NULL,
  -- other columns
);

CREATE UNIQUE INDEX IF NOT EXISTS idx_creativescheduleid_id
  ON public.creative_schedule_status_histories ("creativeScheduleId" ASC, id ASC);

当id ASC引擎的查询命令只读取索引而不做任何额外的排序时：

EXPLAIN (ANALYZE) 
SELECT history.id, history."creativeScheduleId"
FROM  (
    SELECT cssh.id, cssh."creativeScheduleId"
         , ROW_NUMBER() OVER (PARTITION BY cssh."creativeScheduleId"
                              ORDER BY cssh.id ASC) AS rn  -- !
    FROM creative_schedule_status_histories as cssh
    ) AS history
WHERE history.rn = 1;

"Subquery Scan on history  (cost=0.56..511808.63 rows=26377 width=41) (actual time=0.047..4539.058 rows=709030 loops=1)"
"  Filter: (history.rn = 1)"
"  Rows Removed by Filter: 4579766"
"  ->  WindowAgg  (cost=0.56..445866.24 rows=5275391 width=49) (actual time=0.046..4165.835 rows=5288796 loops=1)"
"        ->  Index Only Scan using idx_creativescheduleid_id on creative_schedule_status_histories cssh  (cost=0.56..353546.90 rows=5275391 width=41) (actual time=0.037..1447.490 rows=5288796 loops=1)"
"              Heap Fetches: 2372"
"Planning Time: 0.072 ms"
"Execution Time: 4568.235 ms"

当我订购时，我希望看到完全相同的查询计划id DESC，但是计划中有一个明确的排序溢出到磁盘，显然一切都变慢了。

EXPLAIN (ANALYZE) 
SELECT history.id, history."creativeScheduleId"
FROM  (
    SELECT cssh.id, cssh."creativeScheduleId"
         , ROW_NUMBER() OVER (PARTITION BY cssh."creativeScheduleId"
                              ORDER BY cssh.id DESC) AS rn  -- !
    FROM creative_schedule_status_histories as cssh
    ) AS history
WHERE history.rn = 1;

"Subquery Scan on history  (cost=1267132.63..1438582.84 rows=26377 width=41) (actual time=11974.827..15840.338 rows=709046 loops=1)"
"  Filter: (history.rn = 1)"
"  Rows Removed by Filter: 4579802"
"  ->  WindowAgg  (cost=1267132.63..1372640.45 rows=5275391 width=49) (actual time=11974.825..15529.679 rows=5288848 loops=1)"
"        ->  Sort  (cost=1267132.63..1280321.11 rows=5275391 width=41) (actual time=11974.814..13547.038 rows=5288848 loops=1)"
"              Sort Key: cssh.""creativeScheduleId"", cssh.id DESC"
"              Sort Method: external merge  Disk: 263992kB"
"              ->  Index Only Scan using idx_creativescheduleid_id on creative_schedule_status_histories cssh  (cost=0.56..353550.90 rows=5275391 width=41) (actual time=0.015..1386.310 rows=5288848 loops=1)"
"                    Heap Fetches: 2508"
"Planning Time: 0.078 ms"
"Execution Time: 15949.877 ms"

我希望给定的索引在查询的两个变体中同样有用。
Postgres 不能在这里向后扫描索引？
我在这里想念什么？

当我对特定的给定进行查询时creativeScheduleId，Postgres 对索引ASC和DESC排序顺序都同样有效。在任何变体中都没有明确的排序：

EXPLAIN (ANALYZE) 
SELECT id, "creativeScheduleId"
FROM   creative_schedule_status_histories AS cssh
WHERE  "creativeScheduleId" = '24238370-a64c-4b30-ac8e-27eb2b693aca'
ORDER  BY id DESC  -- or ASC, no sort
LIMIT  1

"Limit  (cost=0.56..0.71 rows=1 width=41) (actual time=0.022..0.022 rows=1 loops=1)"
"  ->  Index Only Scan Backward using idx_creativescheduleid_id on creative_schedule_status_histories cssh  (cost=0.56..14.06 rows=86 width=41) (actual time=0.021..0.021 rows=1 loops=1)"
"        Index Cond: (""creativeScheduleId"" = '24238370-a64c-4b30-ac8e-27eb2b693aca'::text)"
"        Heap Fetches: 0"
"Planning Time: 0.064 ms"
"Execution Time: 0.033 ms"

在这里我们实际上看到Index Only Scan Backward了，所以 Postgres 能够做到。但不适用于整张桌子。

任何想法如何鼓励引擎为读取整个表的第一个查询向后扫描整个索引？

postgresql

3 个回答

  1. 由于所讨论的限制，我们不能让 Postgres 向后扫描特定用例的索引。然而 ...

    清洁测试用例

    我从测试用例中去除了噪音：

    CREATE TABLE tbl (
  id   int PRIMARY KEY
, part int NOT NULL
, ballast text  -- possibly big column(s)?
);

CREATE UNIQUE INDEX tbl_part_id_idx ON tbl (part, id);

    摆脱昂贵的排序步骤

    在 Postgres 14 或更高版本中，我Incremental Sort在Index Only Scan.
    在 Postgres 11 或更高版本中，额外的排序随着这个解决方法而消失：

    SELECT id, part
FROM  (
   SELECT *
        , CASE WHEN part = lead(part) OVER (ORDER BY part, id ROWS UNBOUNDED PRECEDING)
               THEN false 
               ELSE true END AS qualified
   FROM   tbl
   ) sub
WHERE  qualified;

    Subquery Scan on sub (cost=0.42..10293.58 rows=89880 width=8) (actual time=1.759..115.799 rows=67 loops=1)
  Filter: sub.qualified
  Rows Removed by Filter: 179692
  -> WindowAgg (cost=0.42..8495.99 rows=179759 width=41) (actual time=0.022..106.609 rows=179759 loops=1)
        -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4900.81 rows=179759 width=8) (actual time=0.017..29.208 rows=179759 loops=1)
              Heap Fetches: 0
Planning Time: 0.114 ms
Execution Time: 115.850 ms

    那是基于Paul 的查询。它比我的第一个想法要好于比较每个分区的行数和计数。我适应了id每个组的最佳表现，简化并切换到ROWS模式以获得更好的性能。看：

    它向前扫描索引。要查看实际Index Scan backwards：

    ...
          CASE WHEN part = lag(part) OVER (ORDER BY part DESC, id DESC ROWS UNBOUNDED PRECEDING)
               THEN false 
               ELSE true END AS qualified
...

    第一个变体只是稍微短一些，速度更快。

    当您被原始查询卡住时，您至少可以在 RAM 中进行排序。您的查询计划说Disk: 263992kB。增加work_mem300 MB（如果你负担得起的话）以实现这一目标。可能只是在您的会话中进行大查询。看：

    你真正想要的

    您当前的查询永远不会赢得任何竞争。
    为了使您的查询快速（即使没有额外的索引）：

    对于每组几行（并且足够work_mem），使用DISTINCT ON. 匹配索引是最快的，甚至可能没有：

    SELECT DISTINCT ON (part) id, part
FROM   tbl
ORDER  BY part, id DESC;

    Unique (cost=33480.91..34380.55 rows=67 width=8) (actual time=96.726..131.735 rows=67 loops=1)
  -> Sort (cost=33480.91..33930.73 rows=179929 width=8) (actual time=96.724..118.292 rows=179929 loops=1)
        Sort Key: part, id DESC
        Sort Method: external merge Disk: 3184kB
        -> Index Only Scan using tbl_part_id_idx on tbl (cost=0.42..4903.35 rows=179929 width=8) (actual time=0.019..25.871 rows=179929 loops=1)
              Heap Fetches: 0
Planning Time: 0.102 ms
Execution Time: 132.208 ms

    对于每组的许多行（如在此测试中），DISTINCT ON这并不理想，但通常也没有那么糟糕。

    对于每组超过几行，我们需要索引跳过扫描。已经做出了相当大的努力，但不幸的是，这并没有进入 Postgres 15。我们仍然可以使用递归 CTE 来模拟该技术以达到很好的效果：

    EXPLAIN ANALYZE
WITH RECURSIVE cte AS (
   (
   SELECT part, id
   FROM   tbl
   ORDER  BY part DESC, id DESC
   LIMIT  1
   )
   
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT t.part, t.id
      FROM   tbl t
      WHERE  t.part < c.part
      ORDER  BY t.part DESC, t.id DESC
      LIMIT  1
      ) l
   )
TABLE  cte;

    'CTE Scan on cte  (cost=40.74..42.76 rows=101 width=8) (actual time=0.013..0.304 rows=34 loops=1)'
'  CTE cte'
'    ->  Recursive Union  (cost=0.29..40.74 rows=101 width=8) (actual time=0.012..0.297 rows=34 loops=1)'
'          ->  Limit  (cost=0.29..0.33 rows=1 width=8) (actual time=0.011..0.012 rows=1 loops=1)'
'                ->  Index Only Scan Backward using tbl_part_id_idx on tbl  (cost=0.29..3410.28 rows=100000 width=8) (actual time=0.010..0.011 rows=1 loops=1)'
'                      Heap Fetches: 1'
'          ->  Nested Loop  (cost=0.29..3.84 rows=10 width=8) (actual time=0.008..0.008 rows=1 loops=34)'
'                ->  WorkTable Scan on cte c  (cost=0.00..0.20 rows=10 width=4) (actual time=0.000..0.000 rows=1 loops=34)'
'                ->  Limit  (cost=0.29..0.34 rows=1 width=8) (actual time=0.008..0.008 rows=1 loops=34)'
'                      ->  Index Only Scan Backward using tbl_part_id_idx on tbl t  (cost=0.29..1714.08 rows=33333 width=8) (actual time=0.007..0.007 rows=1 loops=34)'
'                            Index Cond: (part < c.part)'
'                            Heap Fetches: 33'
'Planning Time: 0.115 ms'
'Execution Time: 0.324 ms'  -- !!!

    一个或另一个通常比您的原始查询快得多。

    为 Postgres 15提供小提琴，每组 3000
    行为 Postgres 11提供
    小提琴，为 Postgres 11提供每组 8 行（〜您的分布）和足够work_mem
    的用于 Postgres 11 的小提琴，每组 2 行和足够work_mem

    看：

    • 3
  2. Best Answer

    作为一种解决方法，请考虑按索引降序排序的行：

    ID creativeScheduleId
    10 d
    9 C
    8 C
    7 b
    6 b
    5 b
    4 一个
    3 一个
    2 一个
    1 一个

    您想要的行（粗体）是前一行没有“creativeScheduleId”匹配值的行：

    EXPLAIN (ANALYZE) 
SELECT 
    q1.id, 
    q1."creativeScheduleId" 
FROM 
(
    SELECT
        cssh.*,
        CASE
            WHEN cssh."creativeScheduleId" = 
                LAST_VALUE(cssh."creativeScheduleId") OVER (
                    ORDER BY cssh."creativeScheduleId" DESC, cssh.id DESC
                        ROWS BETWEEN 1 PRECEDING AND 1 PRECEDING)
            THEN 0
            ELSE 1
    END AS qualified
    FROM public.creative_schedule_status_histories AS cssh
) AS q1
WHERE
    q1.qualified = 1;

    Subquery Scan on q1 (cost=0.15..104.48 rows=6 width=36) (actual time=0.014..0.014 rows=0 loops=1)
  Filter: (q1.qualified = 1)
  -> WindowAgg (cost=0.15..88.60 rows=1270 width=40) (actual time=0.013..0.014 rows=0 loops=1)
        -> Index Only Scan Backward using idx_creativescheduleid_id on creative_schedule_status_histories cssh (cost=0.15..63.20 rows=1270 width=36) (actual time=0.011..0.011 rows=0 loops=1)
              Heap Fetches: 0
Planning Time: 0.415 ms
Execution Time: 0.076 ms

    db<>小提琴

    在评论中，您表达了对 SQL Server 如何处理此问题的兴趣。

    它可以使用索引向后扫描，但需要一点帮助：

    SELECT
    Q1.id, 
    Q1.creativeScheduleId
FROM 
(
    SELECT 
        CSSH.id, 
        CSSH.creativeScheduleId,
        rn = ROW_NUMBER() OVER (
            PARTITION BY CSSH.creativeScheduleId
            ORDER BY CSSH.id DESC)
    FROM dbo.creative_schedule_status_histories AS CSSH
) AS Q1
WHERE
    Q1.rn = 1
-- Encourage optimizer
ORDER BY
    Q1.creativeScheduleId DESC,
    Q1.id DESC;

     |--Filter(WHERE:([Expr1001]=(1)))
       |--Sequence Project(DEFINE:([Expr1001]=row_number))
            |--Segment
                 |--Index Scan([idx_creativescheduleid_id]), ORDERED BACKWARD)

    索引后向扫描； 没有排序

    db<>小提琴

    • 3

  3. 虽然 PostgreSQL 通常知道如何向后读取索引，但有些情况超出了它的掌握范围，这个具有分区和排序的窗口函数就是其中之一。

    您还可以想象使用哈希表而不是任何类型的排序/排序（在特定情况下rn=1）来解决此查询，但这也没有实现。

    • 2

相关问题