懒人促进社会进步 - 5种索引的原理和优化Case (btree,hash,gin,gist,brin)-阿里云开发者社区

开发者社区> 阿里云数据库> 正文

懒人促进社会进步 - 5种索引的原理和优化Case (btree,hash,gin,gist,brin)

简介:

标签

PostgreSQL , 多列聚合 , gin , btree , n_distinct , 选择性 , 如何选择索引方法(hash,btree,gin,gist,brin) , 如何优化索引 , 相关性


背景

在广告行业,精准营销是一个较热的话题,之前写过一个案例,如何使用PostgreSQL的array类型和GIN索引实时圈人的场景。

《万亿级营销(圈人)迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》

使用以上方法,程序需要作出一些调整(当然,如果用户原本就是PostgreSQL技术栈,改动量会很少),改动量举例

假设用户使用了多个列来表示不同的属性,每个属性对应一些TAG取值空间。

create table user_tags(uid int8 primary key, lab1 int, lab2 text, lab3 timestamp, lab4 text, lab5 interval, lab6 json);  

用户原有的圈人、维度统计查询可能是这样的

select * from user_tags where lab1 ? xxx and lab2 ? xxx or lab4 ? xxx;  
  
select xx, count(*) from user_tags where lab1 ? xxx and lab2 ? xxx or lab4 ? xxx group by xxx;  

由于属性取值空间可能连续,使用《万亿级营销(圈人)迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》提到的方法,需要建立标签库,将数据阶梯化,查询也要进行转换。

例如between and这种连续查询需要转换为in的散列查询。使得程序设计更加复杂,(虽然这样也许可以将性能最大化)。

那么PostgreSQL有没有什么折中的办法呢?

当然有,一切办法都是为懒人准备的,懒人推动了社会的进步。

如果你阅读一下这些文档,你会发现PG里面办法还是蛮多的。

1、使用bitmapand, bitmapor+任意索引,解决圈人问题。

《多字段,任意组合条件查询(0建模) - 毫秒级实时圈人 最佳实践》

2、使用varbitx插件,解决圈人问题。

《阿里云RDS for PostgreSQL varbitx插件与实时画像应用场景介绍》

接下来针对有连续查询,等值查询多种组合查询的圈人场景,我们来看看如何解决。

建模和测试

构建一张TAG表

postgres=# create table tbl_label(uid int primary key, c1 int, c2 text, c3 numeric, c4 timestamp, c5 interval, c6 int);  
CREATE TABLE  
Time: 31.145 ms  

插入一批数据

postgres=# insert into tbl_label select id,   
random()*10000, md5(random()::text),   
10000*random(), clock_timestamp(),   
(random()*1000::int||' hour')::interval,   
random()*99999   
from generate_series(1,10000000) t(id);  
INSERT 0 10000000  

数据样式

postgres=# select * from tbl_label limit 10;  
 uid |  c1  |                c2                |        c3        |             c4             |        c5        |  c6     
-----+------+----------------------------------+------------------+----------------------------+------------------+-------  
   1 | 1692 | 505662aa4a6b33e1775cea660063ba58 | 9761.26249413937 | 2017-06-12 18:38:57.515097 | 322:06:55.266882 | 67699  
   2 | 8611 | a60d564b7f4d58029dfd5e16f0457305 | 1003.07232700288 | 2017-06-12 18:38:57.515282 | 780:59:39.081975 | 89283  
   3 |  290 | f226358e08372d4b79c8ecdd27172244 | 8240.20517989993 | 2017-06-12 18:38:57.515296 | 261:29:59.658099 | 87975  
   4 | 7829 | 32bc5d97731ddaf2c1630218e43d1e85 | 9061.87939457595 | 2017-06-12 18:38:57.515303 | 760:47:18.267513 | 76409  
   5 | 7735 | 3813b4bcdaadc21a55da143f6aceeac9 | 6651.74870751798 | 2017-06-12 18:38:57.515309 | 512:45:50.116217 | 11252  
   6 | 9945 | ff72917169cdea9225e429e438f22586 | 2114.50539063662 | 2017-06-12 18:38:57.515316 | 63:30:34.15014   | 33288  
   7 | 9144 | 7cf4067f22c5edbb1fc4e08ecee7242c | 5662.74457611144 | 2017-06-12 18:38:57.515322 | 890:30:28.360096 | 55484  
   8 | 2433 | 8ac9732bec2b1c175483c16e82467653 | 9184.17258188128 | 2017-06-12 18:38:57.515328 | 343:34:40.88581  | 53265  
   9 | 8113 | 2dd724e82dc7c2a15dfda45f6a41cd53 | 5094.92502082139 | 2017-06-12 18:38:57.515334 | 635:16:39.096908 | 63410  
  10 | 3893 | b8abdb00228f09efb04c1e2a8a022c22 | 6397.02362008393 | 2017-06-12 18:38:57.51534  | 295:26:24.752753 | 17894  
(10 rows)  

分析表的统计信息

postgres=# analyze tbl_label ;  
ANALYZE  

查看每列的散列程度

n_distinct解释  
  
-1表示唯一,也就是说这个列的每一行都不一样.  
  
>=1时,表示这个列有多少唯一值.  
  
<1时,表示这个列的  唯一值数量/总数.    
  
correlation解释  
表示该列与数据堆存储的线性相关性, 1表示正向完全相关。越接近0表示数据分布越离散。<0表示反向相关。  
  
uid是自增的, c4是时间递增的,所以都是1,完全相关。  
  
postgres=# select tablename,attname,n_distinct,correlation from pg_stats where tablename='tbl_label';  
 tablename | attname | n_distinct | correlation   
-----------+---------+------------+-------------  
 tbl_label | uid     |         -1 |           1  
 tbl_label | c1      |      10018 |  0.00431651  
 tbl_label | c2      |  -0.957505 | -0.00796595  
 tbl_label | c3      |         -1 |  0.00308372  
 tbl_label | c4      |         -1 |           1  
 tbl_label | c5      |         -1 | 0.000382809  
 tbl_label | c6      |     100688 |  0.00156045  
(7 rows)  

针对以上统计信息,对于唯一列,建立btree索引,对于松散列,建立gin索引(倒排),以达到最好的效果。

为了让普通类型支持gin,需要创建btree_gin插件

postgres=# create extension btree_gin;  
CREATE EXTENSION  

创建c1,c6的gin复合索引

postgres=# set maintenance_work_mem ='32GB';  
SET  
Time: 0.168 ms  
postgres=# create index idx_tbl_label_1 on tbl_label using gin(c1,c6);  
CREATE INDEX  
Time: 1504.542 ms (00:01.505)  

查询测试,查询c1,c6的任意组合,效果非常棒。

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where c1 between 1 and 100;  
                                                            QUERY PLAN                                                               
-----------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.tbl_label  (cost=125.76..8759.97 rows=10074 width=80) (actual time=40.856..50.480 rows=9922 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Recheck Cond: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100))  
   Heap Blocks: exact=7222  
   Buffers: shared hit=7982  
   ->  Bitmap Index Scan on idx_tbl_label_1  (cost=0.00..123.24 rows=10074 width=0) (actual time=39.773..39.773 rows=9922 loops=1)  
         Index Cond: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100))  
         Buffers: shared hit=760  
 Planning time: 0.105 ms  
 Execution time: 51.043 ms  
(10 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where c1 between 1 and 100 or c6=100;  
                                                               QUERY PLAN                                                                  
-----------------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.tbl_label  (cost=134.36..8799.70 rows=10085 width=80) (actual time=41.133..50.187 rows=9932 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Recheck Cond: (((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100)) OR (tbl_label.c6 = 100))  
   Heap Blocks: exact=7228  
   Buffers: shared hit=7992  
   ->  BitmapOr  (cost=134.36..134.36 rows=10085 width=0) (actual time=40.045..40.045 rows=0 loops=1)  
         Buffers: shared hit=764  
         ->  Bitmap Index Scan on idx_tbl_label_1  (cost=0.00..123.24 rows=10074 width=0) (actual time=40.031..40.031 rows=9922 loops=1)  
               Index Cond: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100))  
               Buffers: shared hit=760  
         ->  Bitmap Index Scan on idx_tbl_label_1  (cost=0.00..6.08 rows=11 width=0) (actual time=0.012..0.012 rows=10 loops=1)  
               Index Cond: (tbl_label.c6 = 100)  
               Buffers: shared hit=4  
 Planning time: 0.125 ms  
 Execution time: 50.758 ms  
(15 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where c1 between 1 and 100 and c6=100;  
                                                        QUERY PLAN                                                           
---------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.tbl_label  (cost=22.50..24.02 rows=1 width=80) (actual time=36.193..36.193 rows=0 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Recheck Cond: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100) AND (tbl_label.c6 = 100))  
   Buffers: shared hit=763  
   ->  Bitmap Index Scan on idx_tbl_label_1  (cost=0.00..22.50 rows=1 width=0) (actual time=36.190..36.190 rows=0 loops=1)  
         Index Cond: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100) AND (tbl_label.c6 = 100))  
         Buffers: shared hit=763  
 Planning time: 0.115 ms  
 Execution time: 36.226 ms  
(9 rows)  

创建其他列的btree索引,因为其他列的n_distinct表明这些列基本唯一,所以我们建立btree索引,可以精准的进行定位。

对于线性相关性好的列,创建brin索引。后面会讲到索引的原理和选择。

postgres=# create index idx_tbl_label2 on tbl_label using btree(c2);  
CREATE INDEX  
Time: 1388.756 ms (00:01.389)  
  
postgres=# create index idx_tbl_label3 on tbl_label using btree(c3);  
CREATE INDEX  
Time: 1028.865 ms (00:01.029)  

多列组合查询,效果非常好

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where c1 between 1 and 100 and c6=100 and c2='abc';  
                                                            QUERY PLAN                                                              
----------------------------------------------------------------------------------------------------------------------------------  
 Index Scan using idx_tbl_label2 on public.tbl_label  (cost=0.42..3.45 rows=1 width=80) (actual time=0.032..0.032 rows=0 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Index Cond: (tbl_label.c2 = 'abc'::text)  
   Filter: ((tbl_label.c1 >= 1) AND (tbl_label.c1 <= 100) AND (tbl_label.c6 = 100))  
   Buffers: shared read=3  
 Planning time: 0.248 ms  
 Execution time: 0.056 ms  
(7 rows)  

多个索引通过bitmapAnd, bitmapOr对数据进行过滤,大幅提升任意条件查询的性能。原理如下

《多字段,任意组合条件查询(0建模) - 毫秒级实时圈人 最佳实践》

那么应该如何选择索引呢?后面会讲到。

赠送彩蛋

实际上前面用到的是GIN多列复合索引,还有一种方法,将多列转换为数组,然后建立数组索引(PostgreSQL 表达式索引。)。

1、如何将多列转换为数组?

postgres=# create or replace function to_array(VARIADIC anyarray) returns anyarray as $$  
  select $1;                        
$$ language sql strict immutable;  
CREATE FUNCTION  

例子

postgres=# select to_array('a'::text,'b','c');  
 to_array   
----------  
 {a,b,c}  
(1 row)  
  
postgres=# select to_array(now(),clock_timestamp());  
                             to_array                                
-------------------------------------------------------------------  
 {"2017-06-12 17:50:47.992274+08","2017-06-12 17:50:47.992489+08"}  
(1 row)  
  
postgres=# select to_array(1,2,3);  
 to_array   
----------  
 {1,2,3}  
(1 row)  

2、数组表达式索引

例子

create index idx_tbl_label_combin on tbl_label using gin (to_array(c1,c6));   
  
当列的类型不一致时,可以转换为一致的,然后建立表达式索引,类型转换可能需要使用immutable函数,如果没有则需要自建immutable转换函数,也很简单  
  
postgres=# create index idx_tbl_label_combin1 on tbl_label using gin (to_array('c1:'||c1,'c6:'||c6));   

3、如何命中数组表达式索引

查询条件与索引中的表达式一致,即可命中。

例子

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where to_array(c1,c6) && array[1,2];  
                                                              QUERY PLAN                                                                
--------------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.tbl_label  (cost=840.56..86397.30 rows=99750 width=80) (actual time=0.777..4.030 rows=2254 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Recheck Cond: (ARRAY[tbl_label.c1, tbl_label.c6] && '{1,2}'::integer[])  
   Heap Blocks: exact=2242  
   Buffers: shared hit=2251  
   ->  Bitmap Index Scan on idx_tbl_label_combin  (cost=0.00..815.62 rows=99750 width=0) (actual time=0.465..0.465 rows=2254 loops=1)  
         Index Cond: (ARRAY[tbl_label.c1, tbl_label.c6] && '{1,2}'::integer[])  
         Buffers: shared hit=9  
 Planning time: 0.361 ms  
 Execution time: 4.176 ms  
(10 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_label where to_array('c1:'||c1,'c6:'||c6) && array['c1:1'];  
                                                              QUERY PLAN                                                                 
---------------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.tbl_label  (cost=422.00..54015.43 rows=50000 width=80) (actual time=0.331..1.888 rows=1021 loops=1)  
   Output: uid, c1, c2, c3, c4, c5, c6  
   Recheck Cond: (ARRAY[('c1:'::text || (tbl_label.c1)::text), ('c6:'::text || (tbl_label.c6)::text)] && '{c1:1}'::text[])  
   Heap Blocks: exact=1019  
   Buffers: shared hit=1024  
   ->  Bitmap Index Scan on idx_tbl_label_combin1  (cost=0.00..409.50 rows=50000 width=0) (actual time=0.195..0.195 rows=1021 loops=1)  
         Index Cond: (ARRAY[('c1:'::text || (tbl_label.c1)::text), ('c6:'::text || (tbl_label.c6)::text)] && '{c1:1}'::text[])  
         Buffers: shared hit=5  
 Planning time: 0.173 ms  
 Execution time: 1.972 ms  
(10 rows)  

小结

1、什么时候选择btree

btree索引适合选择性好的列(n_distinct很大,或者=-1),唯一值比例越高越适合btree。

2、什么时候选择gin

与btree相反,选择性越差,采用GIN索引效率越高。

另外GIN的倒排特性,还特别适合多值类型的元素组合查询,例如数组、全文检索类型、TOKEN类型、等等。

同时GIN索引接口是开放的,用户可以根据数据特征,自定义GIN索引。支持更多的数据类型,例如图像特征值相似查询,文本的相似度查询等。

3、什么时候选择gist

GIST是PG的一种通用索引接口,适合各种数据类型,特别适合异构的类型,例如几何类型,空间类型,范围类型等。

GIST索引的原理可参考

《从难缠的模糊查询聊开 - PostgreSQL独门绝招之一 GIN , GiST , SP-GiST , RUM 索引原理与技术背景》

4、什么时候选择hash

如何用好只有等值查询,并且被索引的列长度很长,可能超过数据库block的1/3时,建议使用hash索引。 PG 10 hash索引会产生WAL,确保了可靠性,同时支持流复制。

PG 10 以前的版本,不建议使用hash index,crash后需要rebuild,不支持流复制。

5、什么时候选择brin

当数据与堆存储线性相关性很好时,可以采用BRIN索引。

BRIN是块级索引,存储每个(或者每一段连续的)数据块的原子信息(最大值,最小值,平均值,空值比例,COUNT等)。

特别适合范围扫描。

不同的索引方法支持什么类型的查询?

1、btree

适合排序、>=, <=, =, in, >, < 等查询。

2、HASH

适合=查询。

3、GIN

不同的数据类型,适应不同的查询需求。

例如数组类型,适合 相交,包含等。

4、GIST

不同的数据类型,适应不同的查询需求。

例如空间类型,适合,距离排序,KNN,包含,相交,左,右等。

5、BRIN

适合范围查询,=查询。

如何优化索引效率

前面的方法告诉你应该如何选择索引,但是没有提索引本身的优化,实际上数据分布会影响索引的效率。

例如

《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法 - PostgreSQL index scan enlarge heap page scans when index and column correlation small.》

因此,根据索引的扫描特点,对数据进行重分布,可以大幅度优化索引查询的效率。

例如bitmap index scan(按BLOCK ID顺序读取)就是PostgreSQL用于减少离散IO的手段。

1、btree数据分布优化

线性相关越好,扫描或返回多条数据的效率越高。

2、hash数据分布优化

线性相关越好,扫描或返回多条数据的效率越高。

3、gin数据分布优化

如果是普通类型,则线性相关越好,扫描或返回多条数据的效率越高。

如果是多值类型(如数组、全文检索、TOKENs),则元素越集中(元素聚类分析,横坐标为行号,纵坐标为元素值,数据分布越集中),效率越高。

元素集中通常不好实现,但是我们可以有集中方法来聚集数据,1. 根据元素的出现频率进行排序重组,当用户搜索高频词时,扫描的块更少,减少IO放大。2. 根据(被搜索元素的次数*命中条数)的值进行排序,按排在最前的元素进行聚集,逐级聚集。

(以上方法可能比较烧脑,下次发一篇文档专门讲GIN的数据重组优化)

《索引扫描优化之 - GIN数据重组优化(按元素聚合) 想象在玩多阶魔方》

4、gist数据分布优化

如果是普通类型,则线性相关越好,扫描或返回多条数据的效率越高。

如果是空间类型,则元素越集中(例如数据按geohash连续分布),效率越高。

5、brin数据分布优化

线性相关越好,扫描或返回多条数据的效率越高。

6、多列复合索引数据分布优化

对于多列符合索引,则看索引的类型,要求与前面一样。

增加一个,多个列的线性相关性越好,性能越好。

多列线性相关性计算方法如下

《PostgreSQL 计算 任意类型 字段之间的线性相关性》

数据分布还有一个好处,对于列存储,可以大幅提升压缩比

《一个简单算法可以帮助物联网,金融 用户 节约98%的数据存储成本 (PostgreSQL,Greenplum帮你做到)》

参考

《阿里云RDS for PostgreSQL varbitx插件与实时画像应用场景介绍》

《多字段,任意组合条件查询(0建模) - 毫秒级实时圈人 最佳实践》

《PostgreSQL GIN 单列聚集索引 应用》

《宝剑赠英雄 - 任意组合字段等效查询, 探探PostgreSQL多列展开式B树 (GIN)》

《PostgreSQL GIN索引实现原理》

《从难缠的模糊查询聊开 - PostgreSQL独门绝招之一 GIN , GiST , SP-GiST , RUM 索引原理与技术背景》

《PostgreSQL 9.3 pg_trgm imporve support multi-bytes char and gist,gin index for reg-exp search》

《万亿级营销(圈人)迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》

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

分享:
阿里云数据库
使用钉钉扫一扫加入圈子
+ 订阅

帮用户承担一切数据库风险,给您何止是安心!

官方博客
链接