Postgres支持B-tree, hash, GiST, and GIN,也支持用户通过Gist自定义索引方法,比如时空数据库的R-Tree索引。
为了支持索引框架,在创建索引时会查找和操作一系列Catalog元数据,另外为了加速B-Tree索引的构建,会先对待创建索引的数据进行排序,然后再按照B-Tree的页面格式直接写B-Tree的page,避免page的split。
例子
create table t001(id int, i int, j int, k int, msg text); create table t002(id int, i int, j int, k int, msg text); insert into t001 select i, i+1, i+2, i+3, md5(random()::text) from generate_series(1,1000) as i; insert into t002 select i, i+1, i+2, i+3, md5(random()::text) from generate_series(1,1000) as i; create index t001_i_j on t001(i, j);
创建B-Tree索引分成2个部分:
- catalog系统中生成新索引的相关元数据(索引文件也是一个表,因此相关的元数据需要建立和关联起来);
- 对索引列进行排序并生成BTree的page;
校验新索引的Catalog元数据
语法解析
create index t001_i_j on t001 using btree (i, j);
通过parse.y将创建索引的sql解析成IndexStmt结构,其中:
IndexStmt { type = T_IndexStmt idxname = "t001_i_j" accessMethod = "btree" }
校验B-Tree的handler
using btree执行了索引的类型是btree,因此需要校验内核是否支持该类型的索引。
pg_am
tuple = SearchSysCache1(AMNAME, PointerGetDatum("btree"));
在pg_am中查找"btree"对应的handler
postgres=# select oid,* from pg_am; oid | amname | amhandler | amtype ------+--------+-------------+-------- 403 | btree | bthandler | i 405 | hash | hashhandler | i 783 | gist | gisthandler | i 2742 | gin | ginhandler | i 4000 | spgist | spghandler | i 3580 | brin | brinhandler | i (6 行记录)
BTree的handler是bthandler,是一个regproc类型,对应pg_proc一个函数。对于内置的BTree索引,相关的函数是在bootstrap过程中插入(pg_proc.dat文件)。
pg_proc
pg_proc.dat文件(下面代码会被重新格式化成postgres.bki文件,并且在inintdb时被bootstrap.y解析插入):
# Index access method handlers { oid => '330', descr => 'btree index access method handler', proname => 'bthandler', provolatile => 'v', prorettype => 'index_am_handler', proargtypes => 'internal', prosrc => 'bthandler' },
postgres=# select oid,* from pg_proc where proname='bthandler'; -[ RECORD 1 ]---+---------- oid | 330 proname | bthandler pronamespace | 11 proowner | 10 prolang | 12 procost | 1 prorows | 0 provariadic | 0 protransform | - prokind | f prosecdef | f proleakproof | f proisstrict | t proretset | f provolatile | v proparallel | s pronargs | 1 pronargdefaults | 0 prorettype | 325 proargtypes | 2281 proallargtypes | proargmodes | proargnames | proargdefaults | protrftypes | prosrc | bthandler probin | proconfig | proacl |
校验索引列及比较函数
查找pg_attribute,校验create index中指定的索引列是否存在,如果存在记录attno,并且根据atttypid查找对应的比较函数;
校验pg_attribute
postgres=# select a.* from pg_class c, pg_attribute a where c.relname='t001' and c.oid = a.attrelid; -[ RECORD 8 ]-+--------- attrelid | 16384 attname | i atttypid | 23 attstattarget | -1 attlen | 4 attnum | 2 attndims | 0 attcacheoff | -1 atttypmod | -1 attbyval | t attstorage | p attalign | i attnotnull | f atthasdef | f atthasmissing | f attidentity | attisdropped | f attislocal | t attinhcount | 0 attcollation | 0 attacl | attoptions | attfdwoptions | attmissingval | -[ RECORD 9 ]-+--------- attrelid | 16384 attname | j atttypid | 23 attstattarget | -1 attlen | 4 attnum | 3 attndims | 0 attcacheoff | -1 atttypmod | -1 attbyval | t attstorage | p attalign | i attnotnull | f atthasdef | f atthasmissing | f attidentity | attisdropped | f attislocal | t attinhcount | 0 attcollation | 0 attacl | attoptions | attfdwoptions | attmissingval |
查找比较函数
其中403是pg_am中btree的handler的oid
postgres=# select * from pg_opclass where opcmethod = 403 and opcintype = 23; -[ RECORD 1 ]+--------- opcmethod | 403 opcname | int4_ops opcnamespace | 11 opcowner | 10 opcfamily | 1976 opcintype | 23 opcdefault | t opckeytype | 0
在经过上述元数据校验之后,可以开始为新的索引文件生成相关元数据了。
创建新索引的元数据
在文件系统中创建索引文件
生成Oid
DefineIndex -> index_create -> GetNewRelFileNode
为新的索引文件生成唯一oid,过程是:生成一个新的oid,然后查找pg_class的索引,如果不存在就返回这个oid。
跟新本地的relcache
把正在创建的relation添加到relcache系统中
DefineIndex -> index_create -> heap_create -> RelationBuildLocalRelation
创建文件
DefineIndex -> index_create -> heap_create -> RelationCreateStorage
- 文件系统中生成新的文件;
路径: "file-dio:///home/postgres/tmp_datadir_polardb_pg_1100_bld/base/13881/16391"
- 生成wal日志,类型是
XLogInsert(RM_SMGR_ID, XLOG_SMGR_CREATE | XLR_SPECIAL_REL_UPDATE)
创建新索引的Catalog元数据
pg_class
新的索引文件也是一个表文件,因此需要插入到pg_class中:
DefineIndex -> index_create -> InsertPgClassTuple
postgres=# select * from pg_class where relname = 't001_i_j'; -[ RECORD 1 ]-------+--------- relname | t001_i_j relnamespace | 2200 reltype | 0 reloftype | 0 relowner | 10 relam | 403 relfilenode | 16396 reltablespace | 0 relpages | 6 reltuples | 1100 relallvisible | 0 reltoastrelid | 0 relhasindex | f relisshared | f relpersistence | p relkind | i relnatts | 2 relchecks | 0 relhasoids | f relhasrules | f relhastriggers | f relhassubclass | f relrowsecurity | f relforcerowsecurity | f relispopulated | t relreplident | n relispartition | f relrewrite | 0 relfrozenxid | 0 relminmxid | 0 relacl | reloptions |
pg_attribute
把索引文件引用的列插入pg_attr中:
DefineIndex -> index_create -> AppendAttributeTuples
postgres=# select a.* from pg_class c, pg_attribute a where c.relname='t001_i_j' and c.oid = a.attrelid; -[ RECORD 1 ]-+------ attrelid | 16396 attname | i atttypid | 23 attstattarget | -1 attlen | 4 attnum | 1 attndims | 0 attcacheoff | -1 atttypmod | -1 attbyval | t attstorage | p attalign | i attnotnull | f atthasdef | f atthasmissing | f attidentity | attisdropped | f attislocal | t attinhcount | 0 attcollation | 0 attacl | attoptions | attfdwoptions | attmissingval | -[ RECORD 2 ]-+------ attrelid | 16396 attname | j atttypid | 23 attstattarget | -1 attlen | 4 attnum | 2 attndims | 0 attcacheoff | -1 atttypmod | -1 attbyval | t attstorage | p attalign | i attnotnull | f atthasdef | f atthasmissing | f attidentity | attisdropped | f attislocal | t attinhcount | 0 attcollation | 0 attacl | attoptions | attfdwoptions | attmissingval | postgres=#
pg_index
把索引本身相关信息插入pg_index中,如果索引包含了表达式,则把表达式通过nodeToString序列化成字符串:
DefineIndex -> index_create -> UpdateIndexRelation
postgres=# select * from pg_indexes where indexname = 't001_i_j'; -[ RECORD 1 ]------------------------------------------------------- schemaname | public tablename | t001 indexname | t001_i_j tablespace | indexdef | CREATE INDEX t001_i_j ON public.t001 USING btree (i, j) postgres=#
relcache生效
为了使catalog元数据的变更对所有进程生效,把该heap相关的元数据invalid掉,此处仅仅是注册失效函数,在CommandCounterIncrement,开启执行下一个command时才真正执行invalid。
DefineIndex -> index_create -> CacheInvalidateRelcache
pg_depend
记录该索引对heap的依赖,对collations的依赖,对opclass的依赖,
比如: t001_i_j依赖表 t001的i; t001_i_j依赖表 t001的j;
postgres=# select * from pg_depend where objid = 16396; -[ RECORD 1 ]------ classid | 1259 objid | 16396 objsubid | 0 refclassid | 1259 refobjid | 16384 refobjsubid | 2 deptype | a -[ RECORD 2 ]------ classid | 1259 objid | 16396 objsubid | 0 refclassid | 1259 refobjid | 16384 refobjsubid | 3 deptype | a
CommandCounterIncrement
使得新索引文件相关的relcache生效
构建B-Tree索引
create index时通过"btree" ,找到bthandler函数,找到btbuild
DefineIndex -> index_create -> index_build -> btbuild
排序
构建sortkey
通过index的索引列构建排序时需要用到的sortkey:
btbuild -> _bt_spools_heapscan -> tuplesort_begin_index_btree
扫描heap表
在非concurrent模式下create index时,为了扫描所有的tpule,snapshot使用SnapshotAny,
btbuild -> _bt_spools_heapscan -> IndexBuildHeapScan -> IndexBuildHeapRangeScan -> heap_getnext
自下向上构建B-Tree索引page
逐个读取排好序的tuple,填充到B-Tree的叶子节点上,自下向上插入B-Tree,插入叶子节点可能会递归的触发起父节点也插入。
page layout
索引页面的内存布局整体上是遵循堆表的布局:pageheader,行指针数组构成。
不同点是:
1. 页面的尾巴上多了BTree自定义的BTPageOpaqueData结构,和左右邻居页面组织成链表;
2. 每个行指针指向的内容由IndexTupleData和key组成;
填充率
向刚刚创建出来的索引插入新的数据时,为了避免split,在第一次构建索引时,每个页面上都预留了一些空间:
1. 叶子节点90%;
2. 中间节点70%;
自下向上构建
- 填充叶子page:leaf-0;
- 当leaf-0满了,leaf-0落盘前需要把它的邻居和父节点相关指针更新;
- 分配一个paret0,leaf-0插入parent0中;
- 分配一个新的页面leaf-1,leaf-0的右指针指向leaf-1;
- leaft-0可以落盘;
- leaft-1也满了后,过程和2到6一样;
- 当leaf-2满了后,要把leaf-2插入父节点,此时父节点也满了,因此要递归的把父节点落盘,过程和2到6一样;
leaf-0
leaf-0满了
leaf-1满了
leaf-2满了,先递归处理parent0满的情况
leaf-2满了,再处理leaf-2自身满的情况
indextuple和scankey的语义
- 对于叶子节点,indextuple指向heap表的行指针;
- 对于中间节点,indextuple指向大于scankey的页面,是一个左闭右开区间[scankey, );
索引页面中真正存放的是indextuple和scankey的组合,在page这个层面中把这两个当做一个item,长度是两者之和;
在实际查找时,同时linp定位到indextuple,由于indextuple是定长的,只需要再往前移动sizeof(indextuple)就能找到scankey的datum和null区域;
根据index的attribute desc来解析datum和null;
key space
对于-Tree中间节点的任意一层,它的所有的indextuple和scankey并集在一起是[负无穷,正无穷]。
由于一对indextuple和scankey组合表达的是左闭右开区间[scankey, ):
1. 对于最右侧的scankey (k4),它的语义本身就是[scankey,正无穷);
2. 对于最左侧的scankey (k1),这个key本身代表的是负无穷的语义:
使用该层出现的第一个key内容(记录在pagesate->minkey);
indextuple中只记录blkno,使用offset来记录attr为0;
不存储scankey的datum和null;
if (last_off == P_HIKEY) { Assert(state->btps_minkey == NULL); state->btps_minkey = CopyIndexTuple(itup); BTreeTupleSetNAtts(state->btps_minkey, 0); } ... if (!P_ISLEAF(opaque) && itup_off == P_FIRSTKEY) { trunctuple = *itup; trunctuple.t_info = sizeof(IndexTupleData); BTreeTupleSetNAtts(&trunctuple, 0); itup = &trunctuple; itemsize = sizeof(IndexTupleData); //大小仅仅是indextuple,去除了datum和null }
high key和first key
每个非最右侧页面都有highkey,highkey的语义是改页面所有key的上界(不包含),因此最右侧页面没有highkey,它的上界是正无穷。
页面1的highkey是在页面1满了之后,生成页面2时确定下来的:
1. 把页面1的highkey内容拷贝到页面2,做为页面2的FIRSTKEY;
2. 设置页面1的P_HIHEY指向最后一个行指针last_off,并且标记last_off为无效指针;
因此,页面1的highkey是页面2的FIRSTKEY。
未满页面的落盘
当所有的heap表都被插入了之后,还没有达到满的页面需要落盘,在自下向上的过程中,插入父节点时是一个递归的过程,为了维护每次递归的状态信息,每层的页面用一个BTPageState结构来描述:
- 记录level;
- 记录当前层的最右侧的page;
- 记录minkey;
BTPageState结构是一个单向链表,因此在插入了所有heap表之后,只需要遍历这个链表,从叶子节点开始落盘。
注意:过程中会往往父节点插入(indextuple,scankey),可能会触发父节点满了而落盘,因而产生一个新的父节点,所属层的BTPageState会被更新,沿着BTPageState链表会最终把这个新产生的页面也落盘了。
metapage
metapage记录B-Tree:level,root,fastroot等信息。
metapge始终在索引文件的第0个page,root的位置是不固定的。