PostgreSQL Oracle 兼容性之 - INDEX SKIP SCAN (递归查询变态优化) 非驱动列索引扫描优化-阿里云开发者社区

开发者社区> 德哥> 正文

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

简介:
+关注继续查看

标签

PostgreSQL , Oracle , index skip scan , 非驱动列条件 , 递归查询 , 子树


背景

对于输入条件在复合索引中为非驱动列的,如何高效的利用索引扫描?

在Oracle中可以使用index skip scan来实现这类CASE的高效扫描:

INDEX跳跃扫描一般用在WHERE条件里面没有使用到引导列,但是用到了引导列以外的其他列,并且引导列的DISTINCT值较少的情况。

在这种情况下,数据库把这个复合索引逻辑上拆散为多个子索引,依次搜索子索引中非引导列的WHERE条件里面的值。

使用方法如下:

/*+ INDEX_SS ( [ @ qb_name ] tablespec [ indexspec [ indexspec ]... ] ) */  

The INDEX_SS hint instructs the optimizer to perform an index skip scan for the specified table. If the statement uses an index range scan, then Oracle scans the index entries in ascending order of their indexed values. In a partitioned index, the results are in ascending order within each partition.Each parameter serves the same purpose as in "INDEX Hint". For example:

SELECT /*+ INDEX_SS(e emp_name_ix) */ last_name FROM employees e WHERE first_name = 'Steven';  

下面是来自ORACLE PERFORMANCE TUNING里的原文:

Index skip scans improve index scans by nonprefix columns. Often, scanning index blocks is faster than scanning table data blocks.

Skip scanning lets a composite index be split logically into smaller subindexes. In skip scanning, the initial column of the composite index is not specified in the query. In other words, it is skipped.

The number of logical subindexes is determined by the number of distinct values in the initial column. Skip scanning is advantageous if there are few distinct values in the leading column of the composite index and many distinct values in the nonleading key of the index.

Example 13-5 Index Skip Scan

Consider, for example, a table

employees(  
sex,   
employee_id,  
address  
)   

with a composite index on

(sex, employee_id).   

Splitting this composite index would result in two logical subindexes, one for M and one for F.

For this example, suppose you have the following index data:

('F',98)('F',100)('F',102)('F',104)('M',101)('M',103)('M',105)  

The index is split logically into the following two subindexes:

The first subindex has the keys with the value F.

The second subindex has the keys with the value M

pic

The column sex is skipped in the following query:

SELECT * FROM employeesWHERE employee_id = 101;  

A complete scan of the index is not performed, but the subindex with the value F is searched first, followed by a search of the subindex with the value M.

PostgreSQL 非skip scan

PostgreSQL支持非驱动列的索引扫描,但是需要扫描整个索引。

例子

1、创建测试表

postgres=# create table t(id int, c1 int);  
CREATE TABLE  

2、写入1000万测试数据

postgres=# insert into t select random()*1 , id from generate_series(1,10000000) id;  
INSERT 0 10000000  

3、创建多列索引

postgres=# create index idx_t on t(id,c1);  
CREATE INDEX  

4、非驱动列查询测试如下

index only scan

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t where c1=1;  
                                                                QUERY PLAN                                                                   
-------------------------------------------------------------------------------------------------------------------------------------------  
 Index Only Scan using idx_t on public.t  (cost=10000000000.43..10000105164.89 rows=1 width=8) (actual time=0.043..152.288 rows=1 loops=1)  
   Output: id, c1  
   Index Cond: (t.c1 = 1)  
   Heap Fetches: 0  
   Buffers: shared hit=27326  
 Execution time: 152.328 ms  
(6 rows)  

index scan

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t where c1=1;  
                                                      QUERY PLAN                                                         
-----------------------------------------------------------------------------------------------------------------------  
 Index Scan using idx_t on public.t  (cost=0.43..105165.99 rows=1 width=8) (actual time=0.022..151.845 rows=1 loops=1)  
   Output: id, c1  
   Index Cond: (t.c1 = 1)  
   Buffers: shared hit=27326  
 Execution time: 151.881 ms  
(5 rows)  

bitmap scan

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t where c1=1;  
                                                       QUERY PLAN                                                         
------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t  (cost=105164.88..105166.00 rows=1 width=8) (actual time=151.731..151.732 rows=1 loops=1)  
   Output: id, c1  
   Recheck Cond: (t.c1 = 1)  
   Heap Blocks: exact=1  
   Buffers: shared hit=27326  
   ->  Bitmap Index Scan on idx_t  (cost=0.00..105164.88 rows=1 width=0) (actual time=151.721..151.721 rows=1 loops=1)  
         Index Cond: (t.c1 = 1)  
         Buffers: shared hit=27325  
 Execution time: 151.777 ms  
(9 rows)  

seq scan(全表扫描)

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t where c1=1;  
                                               QUERY PLAN                                                  
---------------------------------------------------------------------------------------------------------  
 Seq Scan on public.t  (cost=0.00..169248.41 rows=1 width=8) (actual time=0.014..594.535 rows=1 loops=1)  
   Output: id, c1  
   Filter: (t.c1 = 1)  
   Rows Removed by Filter: 9999999  
   Buffers: shared hit=44248  
 Execution time: 594.568 ms  
(6 rows)  

使用索引扫,因为不需要FILTER,同时扫描的BLOCK更少,所以性能比全表扫略好。但是还是扫了整个索引的PAGE,所以并不能算skip scan。

那么如何让PostgreSQL支持index skip scan呢?

PostgreSQL skip scan

实际上原理和Oracle类似,可以输入驱动列条件,然后按多个条件扫描,这样就能达到SKIP SCAN的效果。(即多颗子树扫描)。

同样也更加适合于驱动列DISTINCT值较少的情况。

用PostgreSQL的递归查询语法可以实现这样的加速效果。这种方法也被用于获取count(distinct), distinct值等。

《distinct xx和count(distinct xx)的变态递归优化方法 - 索引收敛(skip scan)扫描》

例如,我们通过这个方法,可以快速的得到驱动列的唯一值

with recursive skip as (    
  (    
    select min(t.id) as id from t where t.id is not null    
  )    
  union all    
  (    
    select (select min(t.id) as id from t where t.id > s.id and t.id is not null)     
      from skip s where s.id is not null    
  )  -- 这里的where s.id is not null 一定要加,否则就死循环了.    
)     
select id from skip ;  

然后封装到如下SQL,实现skip scan的效果

explain (analyze,verbose,timing,costs,buffers) select * from t where id in  
(  
with recursive skip as (    
  (    
    select min(t.id) as id from t where t.id is not null    
  )    
  union all    
  (    
    select (select min(t.id) as id from t where t.id > s.id and t.id is not null)     
      from skip s where s.id is not null    
  )  -- 这里的where s.id is not null 一定要加,否则就死循环了.    
)     
select id from skip   
) and c1=1  
union all   
select * from t where id is null and c1=1;  

或者

explain (analyze,verbose,timing,costs,buffers) select * from t where id = any(array  
(  
with recursive skip as (    
  (    
    select min(t.id) as id from t where t.id is not null    
  )    
  union all    
  (    
    select (select min(t.id) as id from t where t.id > s.id and t.id is not null)     
      from skip s where s.id is not null    
  )  -- 这里的where s.id is not null 一定要加,否则就死循环了.    
)     
select id from skip   
)) and c1=1  
union all   
select * from t where id is null and c1=1;  

看执行计划:

效果好多了

  
                                                                                       QUERY PLAN                                                                                          
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 Append  (cost=55.00..215.22 rows=2 width=8) (actual time=0.127..0.138 rows=1 loops=1)  
   Buffers: shared hit=21  
   ->  Nested Loop  (cost=55.00..213.64 rows=1 width=8) (actual time=0.126..0.127 rows=1 loops=1)  
         Output: t.id, t.c1  
         Buffers: shared hit=18  
         ->  HashAggregate  (cost=54.57..55.58 rows=101 width=4) (actual time=0.108..0.109 rows=3 loops=1)  
               Output: skip.id  
               Group Key: skip.id  
               Buffers: shared hit=11  
               ->  CTE Scan on skip  (cost=51.29..53.31 rows=101 width=4) (actual time=0.052..0.102 rows=3 loops=1)  
                     Output: skip.id  
                     Buffers: shared hit=11  
                     CTE skip  
                       ->  Recursive Union  (cost=0.46..51.29 rows=101 width=4) (actual time=0.050..0.099 rows=3 loops=1)  
                             Buffers: shared hit=11  
                             ->  Result  (cost=0.46..0.47 rows=1 width=4) (actual time=0.049..0.049 rows=1 loops=1)  
                                   Output: $1  
                                   Buffers: shared hit=4  
                                   InitPlan 3 (returns $1)  
                                     ->  Limit  (cost=0.43..0.46 rows=1 width=4) (actual time=0.045..0.046 rows=1 loops=1)  
                                           Output: t_3.id  
                                           Buffers: shared hit=4  
                                           ->  Index Only Scan using idx_t on public.t t_3  (cost=0.43..205165.21 rows=10000033 width=4) (actual time=0.045..0.045 rows=1 loops=1)  
                                                 Output: t_3.id  
                                                 Index Cond: (t_3.id IS NOT NULL)  
                                                 Heap Fetches: 0  
                                                 Buffers: shared hit=4  
                             ->  WorkTable Scan on skip s  (cost=0.00..4.88 rows=10 width=4) (actual time=0.015..0.015 rows=1 loops=3)  
                                   Output: (SubPlan 2)  
                                   Filter: (s.id IS NOT NULL)  
                                   Rows Removed by Filter: 0  
                                   Buffers: shared hit=7  
                                   SubPlan 2  
                                     ->  Result  (cost=0.46..0.47 rows=1 width=4) (actual time=0.018..0.019 rows=1 loops=2)  
                                           Output: $3  
                                           Buffers: shared hit=7  
                                           InitPlan 1 (returns $3)  
                                             ->  Limit  (cost=0.43..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=0 loops=2)  
                                                   Output: t_2.id  
                                                   Buffers: shared hit=7  
                                                   ->  Index Only Scan using idx_t on public.t t_2  (cost=0.43..76722.42 rows=3333344 width=4) (actual time=0.017..0.017 rows=0 loops=2)  
                                                         Output: t_2.id  
                                                         Index Cond: ((t_2.id > s.id) AND (t_2.id IS NOT NULL))  
                                                         Heap Fetches: 0  
                                                         Buffers: shared hit=7  
         ->  Index Only Scan using idx_t on public.t  (cost=0.43..1.56 rows=1 width=8) (actual time=0.005..0.005 rows=0 loops=3)  
               Output: t.id, t.c1  
               Index Cond: ((t.id = skip.id) AND (t.c1 = 1))  
               Heap Fetches: 0  
               Buffers: shared hit=7  
   ->  Index Only Scan using idx_t on public.t t_1  (cost=0.43..1.56 rows=1 width=8) (actual time=0.010..0.010 rows=0 loops=1)  
         Output: t_1.id, t_1.c1  
         Index Cond: ((t_1.id IS NULL) AND (t_1.c1 = 1))  
         Heap Fetches: 0  
         Buffers: shared hit=3  
 Execution time: 0.256 ms  
(56 rows)  

从150多毫秒,降低到了0.256毫秒

内核层面优化

与Oracle做法类似,或者说与递归的做法类似。

使用这种方法来改进优化器,可以达到index skip scan的效果,而且不用改写SQL。

参考

《distinct xx和count(distinct xx)的变态递归优化方法 - 索引收敛(skip scan)扫描》

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
hbase源码系列(十五)终结篇&Scan续集-->如何查询出来下一个KeyValue
这是这个系列的最后一篇了,实在没精力写了,本来还想写一下hbck的,这个东西很常用,当hbase的Meta表出现错误的时候,它能够帮助我们进行修复,无奈看到3000多行的代码时,退却了,原谅我这点自私的想法吧。
3135 0
PostgreSQL 10.1 手册_部分 IV. 客户端接口_第 33 章 libpq - C 库_33.6. 取消进行中的查询
33.6. 取消进行中的查询 一个客户端应用可以使用本节描述的函数请求取消一个仍在被服务器处理的命令。 PQgetCancel 创建一个数据结构,这个数据结构包含取消一个通过特定数据库连接发出的命令所需要的信息。
992 0
Oracle-动态SQL
动态SQL语法与使用
1229 0
MySQL索引优化案例
开发同学或多或少会遇到系统响应慢的问题,除了业务系统本身的问题外,常常会遇到SQL查询慢的问题,这篇文章结合实际案例分析MySQL InnoDB存储引擎的索引优化,这篇文章不会介绍B+树的知识点,如果需要了解聚集索引和辅助索引特点的同学可以参考这篇文章,这篇文章主要会介绍三星索引和ICP优化.
993 0
PostgreSQL 11 内核优化 - 降低vacuum cleanup阶段index scan概率 ( vacuum_cleanup_index_scale_factor , skip index vacuum cleanup stage)
PostgreSQL 11 内核优化 - 降低vacuum cleanup阶段index scan概率 ( vacuum_cleanup_index_scale_factor , skip index vacuum cleanup stage)
594 0
PostgreSQL Oracle 兼容性 - Oracle 19c 新特性在PostgreSQL中的使用
PostgreSQL Oracle 兼容性 - Oracle 19c 新特性在PostgreSQL中的使用
1413 0
Redis命令:scan实现模糊查询
Redis命令:scan实现模糊查询
2241 0
+关注
德哥
公益是一辈子的事, I'm digoal, just do it.
2153
文章
245
问答
来源圈子
更多
阿里云数据库:帮用户承担一切数据库风险,给您何止是安心!支持关系型数据库:MySQL、SQL Server、PostgreSQL、PPAS(完美兼容Oracle)、自研PB级数据存储的分布式数据库Petadata、自研金融级云数据库OceanBase支持NoSQL数据库:MongoDB、Redis、Memcache更有褚霸、丁奇、德哥、彭立勋、玄惭、叶翔等顶尖数据库专家服务。
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载