PostgreSQL 10.0 preview 优化器改进 - 驱动索引+quicksort支持更多sort场景

本文涉及的产品
云原生数据库 PolarDB 分布式版,标准版 2核8GB
RDS PostgreSQL Serverless,0.5-4RCU 50GB 3个月
推荐场景:
对影评进行热评分析
云数据库 RDS SQL Server,基础系列 2核4GB
简介:

标签

PostgreSQL , 10.0 , 排序 , 不完整索引排序


背景

当我们在使用数据库时,排序是一个比较常见的需求,排序有几种方法,使用索引,或者访问堆表然后显示的排序。

当使用索引排序时,索引必须包含排序列,同时必须是驱动列包含排序列。

例如

order by a,b,c,那么可使用索引(a,b,c,*)  

但是order by a,b,c能使用索引(a,b)或者(a)吗?  

实际上使用不完整索引,复合排序时,我们可以分为两个阶段,一个节点是按索引扫描,当扫描到一样的索引数据时,再从HEAP读取其他需要排序的列,然后使用quicksort或者其他排序手段对剩余字段进行排序。

这样原本需要再创建一个复合索引来支持复合排序就不必了。

Hackers!  

Currently when we need to get ordered result from table we have to choose  
one of two approaches: get results from index in exact order we need or do  
sort of tuples. However, it could be useful to mix both methods: get  
results from index in order which partially meets our requirements and do  
rest of work from heap.  

Two attached patches are proof of concept for this approach.  

*partial-sort-1.patch*  

This patch allows to use index for order-by if order-by clause and index  
has non-empty common prefix. So, index gives right ordering for first n  
order-by columns. In order to provide right order for rest m columns, sort  
node is inserted. This sort node sorts groups of tuples where values of  
first n order-by columns are equal.  

See an example.  

create table test as (select id, (random()*10000)::int as v1, random() as  
v2 from generate_series(1,1000000) id);  
create index test_v1_idx on test (v1);  

We've index by v1 column, but we can get results ordered by v1, v2.  

postgres=# select * from test order by v1, v2 limit 10;  
   id   | v1 |         v2  
--------+----+--------------------  
 390371 |  0 | 0.0284479795955122  
 674617 |  0 | 0.0322008323855698  
 881905 |  0 |  0.042586590629071  
 972877 |  0 | 0.0531588457524776  
 364903 |  0 | 0.0594307743012905  
  82333 |  0 | 0.0666455538012087  
 266488 |  0 |  0.072808934841305  
 892215 |  0 | 0.0744258034974337  
  13805 |  0 | 0.0794667331501842  
 338435 |  0 |  0.171817752998322  
(10 rows)  

And it's fast using following plan.  

                                                                QUERY PLAN  

------------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=69214.06..69214.08 rows=10 width=16) (actual  
time=0.097..0.099 rows=10 loops=1)  
   ->  Sort  (cost=69214.06..71714.06 rows=1000000 width=16) (actual  
time=0.096..0.097 rows=10 loops=1)  
         Sort Key: v1, v2  
         Sort Method: top-N heapsort  Memory: 25kB  
         ->  Index Scan using test_v1_idx on test  (cost=0.42..47604.42  
rows=1000000 width=16) (actual time=0.017..0.066 rows=56 loops=1)  
 Total runtime: 0.125 ms  
(6 rows)  

For sure, this approach is effective only when first n order-by columns we  
selected provides enough count of unique values (so, sorted groups are  
small). Patch is only PoC because it doesn't contains any try to estimate  
right cost of using partial sort.  


*partial-knn-1.patch*  

KNN-GiST provides ability to get ordered results from index, but this order  
is based only on index information. For instance, GiST index contains  
bounding rectangles for polygons, and we can't get exact distance to  
polygon from index (similar situation is in PostGIS). In attached patch,  
GiST distance method can set recheck flag (similar to consistent method).  
This flag means that distance method returned lower bound of distance and  
we should recheck it from heap.  

See an example.  

create table test as (select id, polygon(3+(random()*10)::int,  
circle(point(random(), random()), 0.0003 + random()*0.001)) as p from  
generate_series(1,1000000) id);  
create index test_idx on test using gist (p);  

We can get results ordered by distance from polygon to point.  

postgres=# select id, p <-> point(0.5,0.5) from test order by p <->  
point(0.5,0.5) limit 10;  
   id   |       ?column?  
--------+----------------------  
 755611 | 0.000405855808916853  
 807562 | 0.000464123777564343  
 437778 | 0.000738524708741959  
 947860 |  0.00076250998760724  
 389843 | 0.000886362723569568  
  17586 | 0.000981960100555216  
 411329 |  0.00145338112316853  
 894191 |  0.00149399559703506  
 391907 |   0.0016647896049741  
 235381 |  0.00167554614889509  
(10 rows)  

It's fast using just index scan.  

                                                            QUERY PLAN  

----------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=0.29..1.86 rows=10 width=36) (actual time=0.180..0.230  
rows=10 loops=1)  
   ->  Index Scan using test_idx on test  (cost=0.29..157672.29  
rows=1000000 width=36) (actual time=0.179..0.228 rows=10 loops=1)  
         Order By: (p <-> '(0.5,0.5)'::point)  
 Total runtime: 0.305 ms  
(4 rows)  

This patch is also only PoC because of following:  
1) It's probably wrong at all to get heap tuple from index scan node. This  
work should be done from another node.  
2) Assumption that order-by operator returns float8 comparable with GiST  
distance method result in general case is wrong.  

------  
With best regards,  
Alexander Korotkov.  

这个patch的讨论,详见邮件组,本文末尾URL。

PostgreSQL社区的作风非常严谨,一个patch可能在邮件组中讨论几个月甚至几年,根据大家的意见反复的修正,patch合并到master已经非常成熟,所以PostgreSQL的稳定性也是远近闻名的。

参考

https://commitfest.postgresql.org/13/1011/

https://www.postgresql.org/message-id/flat/CAPpHfdscOX5an71nHd8WSUH6GNOCf=V7wgDaTXdDd9=goN-gfA@mail.gmail.com#CAPpHfdscOX5an71nHd8WSUH6GNOCf=V7wgDaTXdDd9=goN-gfA@mail.gmail.com

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
目录
相关文章
|
21天前
|
关系型数据库 Go 网络安全
go语言中PostgreSQL驱动安装
【11月更文挑战第2天】
60 5
|
4月前
|
监控 关系型数据库 数据库
PostgreSQL的索引优化策略?
【8月更文挑战第26天】PostgreSQL的索引优化策略?
100 1
|
4月前
|
SQL 关系型数据库 MySQL
SQL Server、MySQL、PostgreSQL:主流数据库SQL语法异同比较——深入探讨数据类型、分页查询、表创建与数据插入、函数和索引等关键语法差异,为跨数据库开发提供实用指导
【8月更文挑战第31天】SQL Server、MySQL和PostgreSQL是当今最流行的关系型数据库管理系统,均使用SQL作为查询语言,但在语法和功能实现上存在差异。本文将比较它们在数据类型、分页查询、创建和插入数据以及函数和索引等方面的异同,帮助开发者更好地理解和使用这些数据库。尽管它们共用SQL语言,但每个系统都有独特的语法规则,了解这些差异有助于提升开发效率和项目成功率。
418 0
|
4月前
|
关系型数据库 数据库 PostgreSQL
PostgreSQL索引维护看完这篇就够了
PostgreSQL索引维护看完这篇就够了
303 0
|
6月前
|
关系型数据库 分布式数据库 数据库
PolarDB产品使用合集之优化器对索引的阈值一般是多少
PolarDB是阿里云推出的一种云原生数据库服务,专为云设计,提供兼容MySQL、PostgreSQL的高性能、低成本、弹性可扩展的数据库解决方案,可以有效地管理和优化PolarDB实例,确保数据库服务的稳定、高效运行。以下是使用PolarDB产品的一些建议和最佳实践合集。
|
7月前
|
监控 关系型数据库 Java
SpringBoot【集成 01】Druid+Dynamic+Greenplum(实际上用的是PostgreSQL的驱动)及 dbType not support 问题处理(附hikari相关配置)
SpringBoot【集成 01】Druid+Dynamic+Greenplum(实际上用的是PostgreSQL的驱动)及 dbType not support 问题处理(附hikari相关配置)
329 0
|
存储 关系型数据库 数据库
PostgreSQL技术大讲堂 - 第28讲:索引内部结构
从零开始学PostgreSQL技术大讲堂 - 第28讲:索引内部结构
759 2
|
关系型数据库 Go 数据库
《提高查询速度:PostgreSQL索引实用指南》
《提高查询速度:PostgreSQL索引实用指南》
592 0
|
存储 自然语言处理 关系型数据库
MySQL学习笔记-优化器选索引的因素
MySQL学习笔记-优化器选索引的因素
159 0
|
关系型数据库 分布式数据库 数据库
PolarDB for PostgreSQL 14:全局索引
PolarDB for PostgreSQL 14 相较于 PostgreSQL 14,提供了更多企业级数据库的特性。本实验将体验其中的全局索引功能。

相关产品

  • 云原生数据库 PolarDB
  • 云数据库 RDS PostgreSQL 版