PostgreSQL 数据库多列复合索引的字段顺序选择原理

标签

PostgreSQL , 多列索引 , 复合索引 , 驱动列 , 顺序 , 等值查询 , 范围扫描 , 离散值 , 连续值 , 单列索引 , bitmap index scan

背景

《深入浅出PostgreSQL B-Tree索引结构》

create index idx on tbl using btree (udf(c1) desc, c2 , c3 desc nulls last);


举个例子

postgres=# create unlogged table tab1 (id int, c1 int, c2 int);
CREATE TABLE
postgres=# insert into tab1 select id, random()*9, 1 from generate_series(1,1000000) t(id);
INSERT 0 1000000
postgres=# insert into tab1 select id, random()*9, 3 from generate_series(1,1000000) t(id);
INSERT 0 1000000
postgres=# insert into tab1 values (1,1,2);
INSERT 0 1
postgres=# insert into tab1 select id, 1, 3 from generate_series(1,1000000) t(id);
INSERT 0 1000000
postgres=# insert into tab1 select id, 1, 1 from generate_series(1,1000000) t(id);
INSERT 0 1000000


c1=1, c2=2的记录只有一条

1、搜索c1=1, c2=2，只需要扫描4个BLOCK

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1=1 and c2=2;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1 on public.tab1  (cost=0.43..2.38 rows=1 width=12) (actual time=0.017..0.018 rows=1 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c1 = 1) AND (tab1.c2 = 2))
Buffers: shared hit=4  （4个BLOCK，包括 root page, branch page, leaf page, HEAP PAGE）
Planning time: 0.214 ms
Execution time: 0.042 ms
(6 rows)


2、搜索其他的，需要扫描很多BLOCK。

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1=1 and c2=3;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1 on public.tab1  (cost=0.43..46108.77 rows=1109400 width=12) (actual time=0.026..237.712 rows=1111519 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c1 = 1) AND (tab1.c2 = 3))
Buffers: shared hit=22593 read=303   (包括heap page)
Planning time: 0.089 ms
Execution time: 328.249 ms
(6 rows)

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1=1 and c2=1;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1 on public.tab1  (cost=0.43..46108.77 rows=1109400 width=12) (actual time=0.022..238.399 rows=1110527 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c1 = 1) AND (tab1.c2 = 1))
Buffers: shared hit=22582 read=299   (包括heap page)
Planning time: 0.094 ms
Execution time: 329.331 ms
(6 rows)


postgres=# create extension pageinspect ;
CREATE EXTENSION


查看索引内部结构，看看如何通过复合索引快速定位一条记录

postgres=# SELECT * FROM bt_metap('idx_tab1');
magic  | version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
340322 |       2 |  290 |     2 |      290 |         2
(1 row)


postgres=# SELECT * FROM bt_page_items('idx_tab1', 290);
itemoffset |   ctid    | itemlen | nulls | vars |          data
------------+-----------+---------+-------+------+-------------------------
1 | (3,1)     |       8 | f     | f    |
2 | (289,1)   |      16 | f     | f    | 00 00 00 00 03 00 00 00
3 | (12341,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
4 | (12124,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
5 | (11907,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
6 | (11690,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
7 | (11473,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
8 | (11256,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
9 | (11039,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
10 | (10822,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
11 | (10605,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
12 | (10388,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
13 | (10171,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
14 | (9954,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
15 | (9737,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
16 | (9520,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
17 | (9303,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
18 | (9086,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
19 | (575,1)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
20 | (8866,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
21 | (8649,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
22 | (8432,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
23 | (8215,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
24 | (7998,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
25 | (7781,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
26 | (7564,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
27 | (7347,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
28 | (7130,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
29 | (6913,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
30 | (6696,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
31 | (6479,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
32 | (6262,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
33 | (6045,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
34 | (5828,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
35 | (5611,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
36 | (860,1)   |      16 | f     | f    | 01 00 00 00 03 00 00 00
37 | (1145,1)  |      16 | f     | f    | 02 00 00 00 01 00 00 00
38 | (1430,1)  |      16 | f     | f    | 02 00 00 00 03 00 00 00
39 | (1715,1)  |      16 | f     | f    | 03 00 00 00 01 00 00 00
40 | (2000,1)  |      16 | f     | f    | 03 00 00 00 03 00 00 00
41 | (2285,1)  |      16 | f     | f    | 04 00 00 00 01 00 00 00
42 | (2570,1)  |      16 | f     | f    | 04 00 00 00 03 00 00 00
43 | (2855,1)  |      16 | f     | f    | 05 00 00 00 01 00 00 00
44 | (3140,1)  |      16 | f     | f    | 05 00 00 00 03 00 00 00
45 | (3425,1)  |      16 | f     | f    | 06 00 00 00 01 00 00 00
46 | (3710,1)  |      16 | f     | f    | 06 00 00 00 03 00 00 00
47 | (3995,1)  |      16 | f     | f    | 07 00 00 00 01 00 00 00
48 | (4280,1)  |      16 | f     | f    | 07 00 00 00 03 00 00 00
49 | (4565,1)  |      16 | f     | f    | 07 00 00 00 03 00 00 00
50 | (4850,1)  |      16 | f     | f    | 08 00 00 00 01 00 00 00
51 | (5135,1)  |      16 | f     | f    | 08 00 00 00 03 00 00 00
52 | (5420,1)  |      16 | f     | f    | 09 00 00 00 03 00 00 00
(52 rows)


         19 | (575,1)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
20 | (8866,1)  |      16 | f     | f    | 01 00 00 00 03 00 00 00


postgres=# SELECT * FROM bt_page_items('idx_tab1', 575);
itemoffset |   ctid   | itemlen | nulls | vars |          data
------------+----------+---------+-------+------+-------------------------
1 | (8712,1) |      16 | f     | f    | 01 00 00 00 03 00 00 00
2 | (572,1)  |       8 | f     | f    |
3 | (573,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
4 | (574,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
5 | (576,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
6 | (577,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
7 | (578,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
8 | (579,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
9 | (580,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
10 | (581,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
11 | (582,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
12 | (583,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
13 | (584,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
14 | (585,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
15 | (586,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
16 | (587,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
17 | (588,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
18 | (589,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
19 | (590,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
20 | (591,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
21 | (592,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
22 | (593,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
23 | (594,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
24 | (595,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
25 | (596,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
26 | (597,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
27 | (598,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
28 | (599,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
29 | (600,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
30 | (601,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
31 | (602,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
32 | (603,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
33 | (604,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
34 | (605,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
35 | (606,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
36 | (607,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
37 | (608,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
38 | (609,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
39 | (610,1)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
40 | (5488,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
41 | (8961,1) |      16 | f     | f    | 01 00 00 00 03 00 00 00
42 | (8960,1) |      16 | f     | f    | 01 00 00 00 03 00 00 00
。。。。。。。。。。。。。。


         40 | (5488,1) |      16 | f     | f    | 01 00 00 00 01 00 00 00
41 | (8961,1) |      16 | f     | f    | 01 00 00 00 03 00 00 00


postgres=# SELECT * FROM bt_page_items('idx_tab1', 5488);
itemoffset |    ctid     | itemlen | nulls | vars |          data
------------+-------------+---------+-------+------+-------------------------
1 | (16215,25)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
2 | (5398,127)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
3 | (5398,137)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
4 | (5398,156)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
5 | (5398,172)  |      16 | f     | f    | 01 00 00 00 01 00 00 00
.....

130 | (5405,10)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
131 | (5405,15)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
132 | (5405,17)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
133 | (5405,35)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
134 | (5405,59)   |      16 | f     | f    | 01 00 00 00 01 00 00 00
135 | (10810,151) |      16 | f     | f    | 01 00 00 00 02 00 00 00
136 | (16216,41)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
137 | (16216,40)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
138 | (16216,39)  |      16 | f     | f    | 01 00 00 00 03 00 00 00
...


HEAP PAGE

        135 | (10810,151) |      16 | f     | f    | 01 00 00 00 02 00 00 00


postgres=# select * from tab1 where ctid='(10810,151)';
id | c1 | c2
----+----+----
1 |  1 |  2
(1 row)


例子 - 范围+等值查询

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1 between 1 and 9 and c2=2;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1 on public.tab1  (cost=0.43..60757.38 rows=1 width=12) (actual time=0.027..106.362 rows=1 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c1 >= 1) AND (tab1.c1 <= 9) AND (tab1.c2 = 2))
Buffers: shared hit=8321
Planning time: 0.099 ms
Execution time: 106.422 ms
(6 rows)


优化

postgres=# create index idx_tab1_2 on tab1 using btree (c2,c1);
CREATE INDEX


postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1 between 1 and 9 and c2=2;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1_2 on public.tab1  (cost=0.43..2.35 rows=1 width=12) (actual time=0.017..0.018 rows=1 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c2 = 2) AND (tab1.c1 >= 1) AND (tab1.c1 <= 9))
Buffers: shared hit=4
Planning time: 0.095 ms
Execution time: 0.040 ms
(6 rows)


例子 - 多值+等值查询

PostgreSQL针对离散多值查询，有一定的优化，仅仅扫描了多个离散值的索引ITEM

drop index idx_tab1_2;

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1 in (1,2,3,4,5,6,7,8,9) and c2=2;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1 on public.tab1  (cost=0.43..13.90 rows=1 width=12) (actual time=0.024..0.186 rows=1 loops=1)
Output: id, c1, c2
Index Cond: ((tab1.c1 = ANY ('{1,2,3,4,5,6,7,8,9}'::integer[])) AND (tab1.c2 = 2))
Planning time: 0.114 ms
Execution time: 0.208 ms
(6 rows)


postgres=# create index idx_tab1_2 on tab1 using btree (c2,c1);
CREATE INDEX

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tab1 where c1 in (1,2,3,4,5,6,7,8,9) and c2=2;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_tab1_2 on public.tab1  (cost=0.43..2.35 rows=1 width=12) (actual time=0.027..0.027 rows=1 loops=1)
Output: id, c1, c2
Index Cond: (tab1.c2 = 2)
Filter: (tab1.c1 = ANY ('{1,2,3,4,5,6,7,8,9}'::integer[]))
Buffers: shared hit=4
Planning time: 0.107 ms
Execution time: 0.047 ms
(7 rows)


小结

PostgreSQL目前还不支持非连续性的索引扫描，所以当驱动列（第一列）使用了范围扫描后，即使复合索引有第二列，并且第二列是个等值查询，那么也要扫描第一列范围覆盖的所有索引。

1、离散查询条件（例如 等值）的列放在最前面，如果一个复合查询中有多个等值查询的列，尽量将选择性好（count(distinct) 值多的）的放在前面。

2、离散查询条件（例如 多值）的列放在后面，如果一个复合查询中有多个多值查询的列，尽量将选择性好（count(distinct) 值多的）的放在前面。

3、连续查询条件（例如 范围查询）的列放在最后面，如果一个复合查询中有多个多值查询的列，尽量将输入范围条件返回结果集少的列放前面，提高筛选效率（同时也减少索引扫描的范围）。

4、如果返回的结果集非常大（或者说条件命中率很高），并且属于流式返回（或需要高效率优先返回前面几条记录），同时有排序输出的需求。建议按排序键建立索引。

参考

《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》

《深入浅出PostgreSQL B-Tree索引结构》

https://www.postgresql.org/docs/devel/static/pageinspect.html

+ 订阅