PostgreSQL 11 preview - Incremental Sort(排序优化)

标签

PostgreSQL , 增量排序

背景

当我们需要对数据进行排序时，通常加速的方法是建索引，走索引就快了对吧。

PostgreSQL排序的能力还是很强大的：

《PostgreSQL 11 preview - 并行排序、并行索引 (性能线性暴增) 单实例100亿TOP-K仅40秒》

通常情况下，如果要让排序用上索引，那么索引必须与排序字段一致才行。

那么这种情况能不能用到索引呢？

create index idx on tbl(a1,a2);  
  
select * from tbl order by a1,a2,a3,a4;  

PostgreSQL增加了一种排序方法Incremental Sort，即使索引只包含了一部分，也能用它来排序，只要包含的部分是排序键的前序列即可。

换句话说说a1,a2已经在索引中有序了，只是a3,a4需要排，所以可以根据索引顺序取出，然后对A3，A4来排序。

更加适合A1，A2较少唯一值的场景。

patch中提到的执行计划如下

https://www.postgresql.org/message-id/flat/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com#CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com

SELECT * FROM s_1 ORDER BY a, b  
                                                                   QUERY  
PLAN  
-------------------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=1588080.84..1588080.84 rows=1 width=20) (actualtime=5874.527..5874.527 rows=0 loops=1)  
   ->  Incremental Sort  (cost=119371.51..1488081.45 rows=9999939 width=20) (actual time=202.842..5653.224 rows=10000000 loops=1)  
         Sort Key: s_1.a, s_1.b  
         Presorted Key: s_1.a  
         Sort Method: external merge  Disk: 29408kB  
         Sort Groups: 11  
         ->  Index Scan using s_1_a_idx on s_1  (cost=0.43..323385.52rows=9999939 width=20) (actual time=0.051..1494.105 rows=10000000 loops=1)  
 Planning time: 0.269 ms  
 Execution time: 5877.367 ms  
(9 rows)  

非驱动列索引优化其他例子

《PostgreSQL Oracle 兼容性之 - INDEX SKIP SCAN (递归查询变态优化) 非驱动列索引扫描优化》

参考

https://www.postgresql.org/message-id/flat/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com#CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com