阅读顺序
《Postgresql源码(30)Postgresql索引基础B-linked-tree》
《Postgresql源码(31)Btree索引相关系统表和整体结构》
《Postgresql源码(32)Btree索引分裂前后结构差异对比》
《Postgresql源码(33)Btree索引读——整体流程&_bt_first》
《Postgresql源码(34)Btree索引读——_bt_first搜索部分分析》
《Postgresql源码(36)Btree索引读——_bt_next搜索部分分析》
继续上一篇https://cloud.tencent.com/developer/article/2000739
本篇重点关注双key场景拼scankey的特点 和 _first_key的搜索部分的流程和加锁特点。
场景构造:双key索引跨页搜索
当前索引形态
代码语言:javascript复制root: 412
branch: 3, 115, 227, 338, 449, 560, 671, 782, 893, 1004
/ /
leaf: 1 2 4 5 6 ... 111 112 113 114 ...
表结构:
代码语言:javascript复制create table t81(id int, info text);
create index idx_t81_id_info on t81(id,info);
postgres=# select * from bt_metap('idx_t81_id_info');
magic | version | root | level | fastroot | fastlevel
-------- --------- ------ ------- ---------- -----------
340322 | 2 | 116 | 2 | 116 | 2
select itemoffset,ctid,itemlen,nulls,vars from bt_page_items('idx_t81_id_info', 116);
itemoffset | ctid | itemlen | nulls | vars
------------ ---------- --------- ------- ------
1 | (3,1) | 8 | f | f
2 | (115,1) | 48 | f | t
3 | (227,1) | 48 | f | t
4 | (338,1) | 48 | f | t
5 | (449,1) | 48 | f | t
6 | (560,1) | 48 | f | t
7 | (671,1) | 48 | f | t
8 | (782,1) | 48 | f | t
9 | (893,1) | 48 | f | t
10 | (1004,1) | 48 | f | t
select itemoffset,ctid,itemlen,nulls,vars from bt_page_items('idx_t81_id_info', 2) limit 10;
itemoffset | ctid | itemlen | nulls | vars
------------ -------- --------- ------- ------
1 | (2,41) | 48 | f | t
2 | (1,21) | 48 | f | t
3 | (1,22) | 48 | f | t
4 | (1,23) | 48 | f | t
5 | (1,24) | 48 | f | t
6 | (1,25) | 48 | f | t
7 | (1,26) | 48 | f | t
8 | (1,27) | 48 | f | t
9 | (1,28) | 48 | f | t
10 | (1,29) | 48 | f | t
select itemoffset,ctid,itemlen,nulls,vars from bt_page_items('idx_t81_id_info', 5) limit 10;
itemoffset | ctid | itemlen | nulls | vars
------------ -------- --------- ------- ------
1 | (4,81) | 48 | f | t
2 | (3,61) | 48 | f | t
3 | (3,62) | 48 | f | t
4 | (3,63) | 48 | f | t
5 | (3,64) | 48 | f | t
6 | (3,65) | 48 | f | t
7 | (3,66) | 48 | f | t
8 | (3,67) | 48 | f | t
9 | (3,68) | 48 | f | t
10 | (3,69) | 48 | f | t
select * from t81 where ctid='(1,23)';
id | info
----- ----------------------------------
143 | 8a5f7d9783b38755e1df35c7ff7456c6
select * from t81 where ctid='(3,63)';
id | info
----- ----------------------------------
423 | c985618de291db89879d2c8589e39449
用于分析的SQL
预期1:索引会扫过1、2、4、5四个leaf页面、访问3号branch页面、访问116号root页面
预期2:搜索条件会缩减成4个,用于定位起始搜索点的条件是id>143 and info>‘8a’
代码语言:javascript复制select * from t81
where id>143 and info>'8a' and id<423 and info<'9f' -- 正常条件
and id>100 and id<500 and info>'00' and info<'ff'; -- 冗余条件
结果
代码语言:javascript复制 id | info
----- ----------------------------------
149 | 950ff540153cef9af64b53ca17fa3d1e
162 | 99980baf92019a558251089685444d7f
175 | 9e70997ba78c8458bfa8f78439fa6664
178 | 8bc6444cc5e80a6c29407ae55053bcfc
193 | 9a6fe7fcfe2191134424f1471e44287d
208 | 9a598f8859cd3b48fb691f1a1b61b4eb
209 | 91e1f34f0594ea1df35efae36e385e1f
238 | 9a1242106efdc75be7c4f19975509052
243 | 8e5ba26c5dfa9127756d3224cdb4397b
248 | 98dd36696506d990fcf3e6e9e39181d6
255 | 8de35b6524b7780c155c6dfd51baa4fb
268 | 9d2c8bee035881f0944ea596ad080cef
275 | 8c0c22ec820d248e574fbde6441da2fc
295 | 8c855108642c6be76bff4f451de41404
300 | 998dfbe7f18a86d3fe8d6965ce836cfc
327 | 8da63af1288433da429d272f5087096c
328 | 8b649f2659d1a049f62f6b77fdd553e9
335 | 9bd93e5a2033e24926305cc1f5fd7aec
338 | 91b271b1e4011ecd07e8e3d1105db64d
350 | 9106fa32fc398321e8dff200ce4f2aef
356 | 9e154f50faa64931d34fe86639e7c986
358 | 8daf29713228d27188949d2092ba8498
360 | 9b003ad7b5169a20d4d21f084749ee84
395 | 99060b7ae0af3fb48aae1770fb98a844
413 | 961c6e221306ee733559773bd6bb522f
415 | 930235728f96601ab13e0d1726669e7a
420 | 93b764104fbcb1d2bdd23e378c9222ce
计划
代码语言:javascript复制explain analyze select * from t81
where id>143 and info>'8a' and id<423 and info<'9f' -- 正常条件
and id>100 and id<500 and info>'00' and info<'ff'; -- 冗余条件
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using idx_t81_id_info on t81 (cost=0.42..62.35 rows=23 width=37) (actual time=0.028..0.062 rows=27 loops=1)
Index Cond: ((id > 143) AND (id < 423) AND (id > 100) AND (id < 500) AND (info > '8a'::text) AND (info < '9f'::text) AND (info > '00'::text) AND (info < 'ff'::text))
Heap Fetches: 27
Planning time: 0.195 ms
Execution time: 0.091 ms
下面开始分析
_first_key
直奔主题_first_key。ps. 避免断到其他堆栈里:break _bt_first if scan->numberOfKeys==8
按上一篇的流程来看:
第一步:_bt_preprocess_keys开始处理冗余key,结果记录到so中
第二步:开始构造startKeys(ScanKey数组)(找到能用的scankey)
第三步:比较函数转换为通用的row comparisons
第四步:确定临界值判断规则
第五步:scankeys&边界规则准备完毕,开始扫描
第一步:_bt_preprocess_keys开始处理冗余key,结果记录到so中
预处理 _bt_preprocess_keys(scan)前后对比,冗余key被合并。
输入:scan->keyData
输出: ((BTScanOpaque)scan->opaque)->keyData
执行前:scan->numberOfKeys
8
执行后:p ((BTScanOpaque)scan->opaque)->numberOfKeys
4
--
执行前:sk_argument(sk_func): 143(int4gt) 423(int4lt) 100(int4gt) 500(int4lt) 25572760(text_gt) 25573760(text_lt) 25575200(text_gt) 25575760(text_lt)
执行后:sk_argument(sk_func): 143(int4gt) 423(int4lt) 25572760(text_gt) 25573760(text_lt)
-- command
p scan->keyData[0] ... scan->keyData[7]
p ((BTScanOpaque)scan->opaque)->numberOfKeys
p ((BTScanOpaque)scan->opaque)->keyData[0]
第二步:开始构造startKeys(ScanKey数组)(找到能用的scankey)
代码语言:javascript复制select * from t81
where id>143 and info>'8a' and id<423 and info<'9f' -- 正常条件
and id>100 and id<500 and info>'00' and info<'ff'; -- 冗余条件
找起始点所需的所有key保存在startKeys中。
输入:so->keyData
输出:startKeys数组(根据规则选择ScanKey chosen,然后保存到startKeys中)
代码语言:javascript复制遍历so->keyData
第一轮循环:(id>143)大于号走BTGreaterStrategyNumber分支,chosen = cur
第二轮循环:(id<423)小于号不能当做定位起点,do nothing
第三轮循环:(info>'8a')新一列会触发startKeys保存chosen,并且已经找到 > 直接跳出循环。
for (cur = so->keyData, i = 0;; cur , i )
if (i >= so->numberOfKeys || cur->sk_attno != curattr) // 已经到下一列了,可以保存上一轮的结果
结果:startKeys保存了一条id>143
代码语言:javascript复制(gdb) p *startKeys[0]
$34 = {sk_flags = 131072, sk_attno = 1, sk_strategy = 5, sk_subtype = 23, sk_collation = 0, sk_func = {fn_addr = 0x8f65ac <int4gt>,
fn_oid = 147, fn_nargs = 2, fn_strict = 1 '