索引访问方法介绍

支持的索引

1. mydb=# select * from pg_am;
2. oid | amname | amhandler | amtype
3. ------+--------+----------------------+--------
4. 2 | heap | heap_tableam_handler | t
5. 403 | btree | bthandler | i
6. 405 | hash | hashhandler | i
7. 783 | gist | gisthandler | i
8. 2742 | gin | ginhandler | i
9. 4000 | spgist | spghandler | i
10. 3580 | brin | brinhandler | i
11. (7 rows)

索引属性

• 访问方法属性—pg_indexam_has_property
• 特定索引的属性—pg_index_has_property
• 索引中各列的属性—pg_index_column_has_property

访问方法属性中的四种类型

• can_order: 访问方法能够在创建索引时指定值的排序顺序（仅适用于“ btree”）
• can_unique:支持唯一约束和主键，适用于btree
• can_multi_col:可以在多列创建索引
• can_exclude:支持排它约束

1. select a.amname, p.name, pg_indexam_has_property(a.oid,p.name)
2. from pg_am a,
3. unnest(array[‘can_order‘,‘can_unique‘,‘can_multi_col‘,‘can_exclude‘]) p(name)
4. where a.amname = ‘btree‘
5. order by a.amname;
7. amname | name | pg_indexam_has_property
8. --------+---------------+-------------------------
9. btree | can_order | t
10. btree | can_unique | t
11. btree | can_multi_col | t
12. btree | can_exclude | t
13. (4 rows)

特定索引属性

• clusterable:可以根据索引对行进行重新排序（对其进行cluster操作）
• index_scan:支持索引扫描。尽管此属性可能看起来很奇怪，但并非所有索引都能一次返回TID-有些返回结果一次全部返回，并且仅支持位图扫描
• bitmap_scan: 支持位图扫描
• backward_scan：可以按建立索引时指定的相反顺序返回结果

clusterable:可以根据索引对表的行重新排序,直接使用cluster命令，语法如下:

1. mydb=# \h cluster
2. Command: CLUSTER
3. Description: cluster a table according to an index
4. Syntax:
5. CLUSTER [VERBOSE] table_name [ USING index_name ]
6. CLUSTER [VERBOSE]
8. URL: https://www.postgresql.org/docs/13/sql-cluster.html

列属性

• asc，desc，nulls_first，nulls_last，orderable：这些属性与值的排序有关，只有btree索引支持排序
• distance_orderable:可以按照操作确定的排序顺序返回结果（到目前为止仅适用于GiST和RUM索引）
• returnable：在不访问表的情况下使用索引的可能性，即仅索引扫描的支持
• search_array：支持使用表达式搜索多个值。
• search_nulls：通过IS NULL和IS NOT NULL条件进行搜索的可能性。

1. select p.name,
2. pg_index_column_has_property(‘tbl_a_pkey‘::regclass,1,p.name)
3. from unnest(array[
4. ‘asc‘,‘desc‘,‘nulls_first‘,‘nulls_last‘,‘orderable‘,‘distance_orderable‘,‘returnable‘,‘search_array‘,‘search_nulls‘]) p(name);
6. name | pg_index_column_has_property
7. --------------------+------------------------------
8. asc | t
9. desc | f
10. nulls_first | f
11. nulls_last | t
12. orderable | t
13. distance_orderable | f
14. returnable | t
15. search_array | t
16. search_nulls | t
17. (9 rows)

操作符类和操作符族

除了需要知道各种操作方法相关的属性之外，我们还需要知道各种不同的操作方法分别支持哪些数据类型和哪些运算符。pg中提供了操作符类和操作符族的概念。

操作符类包含用于索引的最小运算符集（可能还有辅助函数），以操作某种数据类型。

某些操作符族中包括一个操作符类别。此外，如果一个通用的运算符族具有相同的语义，则它们可以包含多个运算符类。例如，integer_ops系列包括类型bigint，integer和smallint的int8_ops，int4_ops和int2_ops类，它们的大小不同但含义相同

可操作的类型

1. --如整型和日期为例
2. select opfname, opcname, opcintype::regtype
3. from pg_opclass opc, pg_opfamily opf
4. where opf.opfname = ‘integer_ops‘
5. and opc.opcfamily = opf.oid
6. and opf.opfmethod = (
7. select oid from pg_am where amname = ‘btree‘
8. );
9. opfname | opcname | opcintype
10. -------------+----------+-----------
11. integer_ops | int2_ops | smallint
12. integer_ops | int4_ops | integer
13. integer_ops | int8_ops | bigint
14. (3 rows)
16. --datetime_ops系列包含用于操作日期（有时间和无时间）的运算符类：
18. select opfname, opcname, opcintype::regtype
19. from pg_opclass opc, pg_opfamily opf
20. where opf.opfname = ‘datetime_ops‘
21. and opc.opcfamily = opf.oid
22. and opf.opfmethod = (
23. select oid from pg_am where amname = ‘btree‘
24. );
25. opfname | opcname | opcintype
26. --------------+-----------------+-----------------------------
27. datetime_ops | date_ops | date
28. datetime_ops | timestamptz_ops | timestamp with time zone
29. datetime_ops | timestamp_ops | timestamp without time zone
30. (3 rows)

运算符族还可以包括其他运算符，以比较不同类型的值。分组到族中使计划者可以将具有不同类型值的谓词使用索引。一个族还可以包含其他辅助功能。
在大多数情况下，我们不需要了解操作员的族和类。通常，我们只创建索引，默认情况下使用某个运算符类。

但是，我们可以显式指定运算符类。这是当需要显式规范时的一个简单示例：==在排序规则不同于C的数据库中，常规索引不支持LIKE操作：==

1. explain select * from t where b like ‘A%‘;
2. --这种情况我们就可以通过使用操作符类 text_pattern_ops创建索引来克服此限制：
3. create index on t(b text_pattern_ops);

我们可以通过查询这些系统目录解决很多问题，例如：某种访问方法可以操纵哪些数据类型:

btree方法可以操作以下数据类型

1. select opcname, opcintype::regtype
2. from pg_opclass
3. where opcmethod = (select oid from pg_am where amname = ‘btree‘)
4. order by opcintype::regtype::text;
5. opcname | opcintype
6. ---------------------+-----------------------------
7. array_ops | anyarray
8. enum_ops | anyenum
9. range_ops | anyrange
10. int8_ops | bigint
11. bit_ops | bit
12. varbit_ops | bit varying
13. bool_ops | boolean
14. bytea_ops | bytea
15. char_ops | "char"
16. bpchar_pattern_ops | character
17. bpchar_ops | character
18. date_ops | date
19. float8_ops | double precision
20. cidr_ops | inet
21. inet_ops | inet
22. int4_ops | integer
23. interval_ops | interval
24. jsonb_ops | jsonb
25. macaddr_ops | macaddr
26. macaddr8_ops | macaddr8
27. money_ops | money
28. name_ops | name
29. numeric_ops | numeric
30. oid_ops | oid
31. oidvector_ops | oidvector
32. pg_lsn_ops | pg_lsn
33. float4_ops | real
34. record_image_ops | record
35. record_ops | record
36. int2_ops | smallint
37. varchar_pattern_ops | text
38. text_ops | text
39. varchar_ops | text
40. text_pattern_ops | text
41. tid_ops | tid
42. timestamp_ops | timestamp without time zone
43. timestamptz_ops | timestamp with time zone
44. time_ops | time without time zone
45. timetz_ops | time with time zone
46. tsquery_ops | tsquery
47. tsvector_ops | tsvector
48. uuid_ops | uuid
49. xid8_ops | xid8
50. (43 rows)

运算符类包含哪些运算符

1. select amop.amopopr::regoperator
2. from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
3. where opc.opcname = ‘array_ops‘
4. and opf.oid = opc.opcfamily
5. and am.oid = opf.opfmethod
6. and amop.amopfamily = opc.opcfamily
7. and am.amname = ‘btree‘
8. and amop.amoplefttype = opc.opcintype;
9. amopopr
10. -----------------------
11. <(anyarray,anyarray)
12. <=(anyarray,anyarray)
13. =(anyarray,anyarray)
14. >=(anyarray,anyarray)
15. >(anyarray,anyarray)
16. (5 rows)

相关数据字典

索引支持的新数据类型

1. --创建一个新的组合类型
2. create type complex as (re float, im float);
4. --创建表
5. create table t1(x complex);
6. insert into t1 values ((0.0, 10.0)), ((1.0, 3.0)), ((1.0, 1.0));
7. insert into t1 values((1.0,2.0)),((2.0,2.0));

默认情况，对于组合类型排序是分开的，先比较第一个字段再比较第二个，也可以通过其他方式排序。

1. --创建相关函数
2. create function modulus(a complex) returns float as $$
3. select sqrt(a.re*a.re + a.im*a.im);
4. $$ immutable language sql;
6. --定义5种操作符函数：
7. create function complex_lt(a complex, b complex) returns boolean as $$
8. select modulus(a) < modulus(b);
9. $$ immutable language sql;
11. create function complex_le(a complex, b complex) returns boolean as $$
12. select modulus(a) <= modulus(b);
13. $$ immutable language sql;
15. create function complex_eq(a complex, b complex) returns boolean as $$
16. select modulus(a) = modulus(b);
17. $$ immutable language sql;
19. create function complex_ge(a complex, b complex) returns boolean as $$
20. select modulus(a) >= modulus(b);
21. $$ immutable language sql;
23. create function complex_gt(a complex, b complex) returns boolean as $$
24. select modulus(a) > modulus(b);
25. $$ immutable language sql;

创建对应的操作符

1. create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt);
3. create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le);
5. create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq);
7. create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge);
9. create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);
11. --比较数字
12. select (1.0,1.0)::complex #<# (1.0,3.0)::complex;

除了整个5个操作符，还需要定义函数：小于返回-1；等于返回0；大于返回1。其他访问方法可能需要定义其他函数

1. create function complex_cmp(a complex, b complex) returns integer as $$
2. select case when modulus(a) < modulus(b) then -1
3. when modulus(a) > modulus(b) then 1
4. else 0
5. end; $$ language sql;

创建一个操作符类

1. create operator class complex_ops
2. default for type complex
3. using btree as
4. operator 1 #<#,
5. operator 2 #<=#,
6. operator 3 #=#,
7. operator 4 #>=#,
8. operator 5 #>#,
9. function 1 complex_cmp(complex,complex);
11. --查看排序结构
12. mydb=# select * from t1 order by x;
13. x
14. --------
15. (1,1)
16. (1,3)
17. (0,10)
18. (3 rows)
20. --查看可以使用此查询获取支持的函数：
21. select amp.amprocnum,
22. amp.amproc,
23. amp.amproclefttype::regtype,
24. amp.amprocrighttype::regtype
25. from pg_opfamily opf,
26. pg_am am,
27. pg_amproc amp
28. where opf.opfname = ‘complex_ops‘
29. and opf.opfmethod = am.oid
30. and am.amname = ‘btree‘
31. and amp.amprocfamily = opf.oid;
33. amprocnum | amproc | amproclefttype | amprocrighttype
34. -----------+-------------+----------------+-----------------
35. 1 | complex_cmp | complex | complex
36. (1 row)

管理操作符

1. --查看 操作符 和操作符类
2. select * from pg_operator;
3. select * from pg_opclass;
5. --查看操作符类型
6. select o.oid,o.oprname,
7. (select t.typname from pg_type t
8. where o.oprleft=t.oid) as oprleft,
9. (select t.typname from pg_type t
10. where o.oprright=t.oid) as oprright
11. from pg_operator o where o.oprname like ‘#%#‘;
13. --删除操作符
14. drop operator #<# (complex,complex);
15. --删除操作类
16. DROP OPERATOR CLASS complex_ops using btree;
18. --删除函数
19. select * from pg_proc where proname like ‘com%‘;
20. drop function function_name;

参考资料

• 字典参考：https://www.postgresql.org/docs/12/catalogs.html
• 文章参考：https://www.freesion.com/article/9026599468/
• 官方文档：https://www.postgresql.org/docs/13/functions-info.html#FUNCTIONS-INFO-INDEXAM-PROPS

BTREE索引

重要特征

• B树是平衡的
• B树是多分支的，即每个页面（通常为8 KB）包含许多（数百个）ctid。因此，B树的深度很小，对于非常大的表，实际上可以达到4–5的深度。
• 索引中的数据按非递减顺序排序，（在页面之间和每个页面内部），并且同一级别的页面通过双向列表相互连接。因此，我们可以仅通过列表的一个方向或另一个方向获得有序数据集，而不必每次都返回到根。

无论哪种扫描类型(index scan、index only scan、bitmap scan)，使用btree索引都会返回有序的数据。所以，如果在排序列上存在索引，优化器会首先考虑是索引扫描，否则就是先顺序扫描然后排序。

1. create index idx_t1 on t1(c1 desc);
2. --尤其组合索引 ，如果常用排序，可使用如下方法
3. create index idx_t1 on t1(c1 desc,c2 asc);

空值

pg索引可以存储空值，并支持按条件IS NULL和IS NOT NULL进行搜索。

1. explain select * from t1 where c1 is null;

在索引中null值存储在索引的一端，取决于创建索引时指定nulls first还是nulls last。

如果查询包括排序，则这一点很重要：如果SELECT命令在其ORDER BY子句中指定的NULL顺序与构建索引指定的顺序相同（NULLS FIRST或NULLS LAST），则可以使用索引，否则将无法使用索引。

在数据库中null是无法和其它值进行比较的

内部结构

PostgreSQL的btree索引的算法可以参考：src/backend/access/nbtree/README

其中PostgreSQL 的B-Tree索引页分为几种类别，我们可以通过btpo_flags的值去区分.

1. meta page
2. root page # btpo_flags=2
3. branch page # btpo_flags=0
4. leaf page # btpo_flags=1
5. leaf&root page # btpo_flags=3
7. --详情见：src/include/access/nbtree.h
8. /* Bits defined in btpo_flags */
9. #define BTP_LEAF (1 << 0) /* leaf page, i.e. not internal page */
10. #define BTP_ROOT (1 << 1) /* root page (has no parent) */
11. #define BTP_DELETED (1 << 2) /* page has been deleted from tree */
12. #define BTP_META (1 << 3) /* meta-page */
13. #define BTP_HALF_DEAD (1 << 4) /* empty, but still in tree */
14. #define BTP_SPLIT_END (1 << 5) /* rightmost page of split group */
15. #define BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples */
16. #define BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling‘s downlink is missing */

其中meta page和root page是必须有的，meta page需要一个页来存储，表示指向root page的page id。

随着记录数的增加，一个root page可能存不下所有的heap item，就会有leaf page，甚至branch page，甚至多层的branch page。

一共有几层branch 和 leaf，就用btree page元数据的 level 来表示。

可以通过pageinspect插件研究所以你内部结构

• bt_metap(relname text)：返回record，bt_metap用来返回关于一个B树索引元页的信息。
• bt_page_stats(relname text, blkno int)：返回record，bt_page_stats返回有关
  B-树索引单一页面的总计信息
• bt_page_items(relname text, blkno int)：返回record，bt_page_items返回一个
  B-树索引页面上项的所有细节信息

参考文档

• https://www.freesion.com/article/6456622935

HASH索引

哈希表是根据键（Key）而直接访问在内存储存位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做哈希表

索引结构

当插入索引时，让我们计算键的哈希函数。PostgreSQL中的哈希函数总是返回integer类型，其范围为2的32次方≈40亿个值。存储桶的数量最初等于2，然后根据数据大小动态增加。bucket编号可以使用位算法从哈希码中计算出来。这是我们将放置ctid的bucket。

当搜索索引时，我们计算键的哈希函数并获取bucket编号。现在，仍然需要遍历bucket的内容，并仅返回具有适当哈希码的匹配ctid。由于存储的“hash code - ctid”对是有序的，因此可以高效地完成此操作。

哈希索引包含4种页：meta page, primary bucket page, overflow page, bitmap page

• metapage（0号页）,包含了HASH索引的控制信息，指导如何找到其他页面（每个bucket的primary page），以及当前存储概貌。其他索引的0号页基本都是这一个套路。
• primary bucket page，hash index将存储划分为多个bucket（逻辑概念），每个bucket中包含若干page（每个bucket的page数量不需要一致），当插入数据时，根据计算得到的哈希，通过映射算法，映射到某个bucket，也就是说数据首先知道应该插入哪个bucket中，然后插入bucket中的primary
  page，如果primary page空间不足时，会扩展overflow page，数据写入overflow page。在page中，数据是有序存储（TREE），page内支持二分查找(binary search)，而page与page之间是不保证顺序的，所以hash index不支持order by。
• overflow page，是bucket里面的页，当primary page没有足够空间时，扩展的块称为overflow page
• bimap page，记录primary , overflow page是否为空可以被重用

注意bucket, page都没有提供收缩功能，即无法从OS中收缩空间，但是提供了reuse(通过bitmap page跟踪），如果想要减小索引大小的唯一办法就是使用REINDEX或VACUUM FULL命令从头开始重建索引

总结

hash索引介绍：
src/backend/access/hash/README

使用场景：

• 1、等值查询；
• 2、btree索引不支持的大字段类型。

使用限制：

• 1、不支持对null的处理；
• 2、不能使用index only scan；
• 3、不支持多列索引。

【INDEX】Postgresql索引介绍