PostgreSql索引相关知识总结

postgres简称为pg

相关阅读 :

postgresql-12-US.pdf 

Relationale Datenbanken - Von den theoretischen Grundlagen zu Anwendungen mit PostgreSQL (2019).pdf

https://www.bilibili.com/video/BV1FM4y1V7V7/?spm_id_from=333.788.recommend_more_video.1

https://www.postgresql.org/docs/current/pageinspect.html#id-1.11.7.32.6

https://cloud.tencent.com/developer/article/1671374

https://www.youtube.com/watch?v=HubezKbFL7E
1
2
3
4
5
6
7
8
9
10
11

postgres中的btree索引结构

在pg中的btree特性

postgresql-12-US.pdf 中 421 页

11.2. Index Types
PostgreSQL provides several index types: B-tree, Hash, GiST, SP-GiST, GIN and BRIN. Each index type
uses a different algorithm that is best suited to different types of queries. By default, the CREATE INDEX
command creates B-tree indexes, which fit the most common situations.
 B-trees can handle equality and range queries on data that can be sorted into some ordering. In particular,
the PostgreSQL query planner will consider using a B-tree index whenever an indexed column is involved
in a comparison using one of these operators:
<
<=
=
>=
>
#上句话翻译成中文为: B 树可以处理对可按某种顺序排序的数据的相等和范围查询。特别PostgreSQL 查询规划器将考虑在涉及索引列时使用 B 树索引在使用以下运算符之一的比较中：

Constructs equivalent to combinations of these operators, such as BETWEEN and IN, can also be implemented with a B-tree index search. Also, an IS NULL or IS NOT NULL condition on an index column
can be used with a B-tree index.
#上句话翻译成中文为: 等效于这些运算符组合的构造，例如 BETWEEN 和 IN，也可以通过 B-tree 索引搜索来实现 。此外，索引列上的 IS NULL 或 IS NOT NULL 条件可以与 B 树索引一起使用。

The optimizer can also use a B-tree index for queries involving the pattern matching operators LIKE and ~
if the pattern is a constant and is anchored to the beginning of the string — for example, col LIKE 'foo
%' or col ~ '^foo', but not col LIKE '%bar'. However, if your database does not use the C locale
you will need to create the index with a special operator class to support indexing of pattern-matching
queries; see Section 11.10 below. It is also possible to use B-tree indexes for ILIKE and ~*, but only
if the pattern starts with non-alphabetic characters, i.e., characters that are not affected by upper/lower
case conversion.
#上句话翻译成中文为: 优化器还可以对涉及模式匹配运算符 LIKE 和 ~ 的查询使用 B-tree 索引如果模式是一个常量并且锚定到字符串的开头——例如，col LIKE 'foo%' 或 col ~ '^foo'，但不是 col LIKE '%bar'。但是，如果您的数据库不使用 C 语言环境您将需要使用特殊的运算符类创建索引以支持模式匹配的索引查询；见下文第 11.10 节。也可以对 ILIKE 和 ~* 使用 B-tree 索引，但仅限如果模式以非字母字符开头，即不受大写/小写影响的字符大小写转换。

B-tree indexes can also be used to retrieve data in sorted order. This is not always faster than a simple
scan and sort, but it is often helpful.
#上句话翻译成中文为: B 树索引还可用于按排序顺序检索数据。这并不总是快于简单的扫描和排序，但它通常很有帮助。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

pg中的btree结构 (有待考究)

btree 还是 b+tree ? (有待考究)

在我搜到的技术博客中 , 这些博客只是说了使用了btree , 但是并没有说明是 btree 还是 b+tree , 于是我翻阅了书籍以及官方文档

Relationale Datenbanken - Von den theoretischen Grundlagen zu Anwendungen mit PostgreSQL (2019).pdf 中 128 页

图中可以看出 , 叶子结点有指针 , 说明是 b+tree , 但是叶子结点储存的是什么呢 , 是数据还是物理地址? 真的是像图中所演示的那样 , 是数据吗 ?

叶子结点储存是数据还是物理地址?

• 如何查看索引

使用pg自带的插件 pageinspect

相关阅读链接 : https://www.bilibili.com/video/BV1FM4y1V7V7/?spm_id_from=333.788.recommend_more_video.1

相关阅读链接 : https://www.postgresql.org/docs/current/pageinspect.html#id-1.11.7.32.6

SELECT * FROM bt_metap('"IDX_userpoolId_leaderUserId"'); #返回有关 B 树索引的元页的信息。

SELECT * FROM bt_page_stats('"IDX_userpoolId_leaderUserId"',161); #返回有关 B 树索引的单页的摘要信息。

SELECT * FROM bt_page_items('"IDX_userpoolId_leaderUserId"',3); #返回有关 B 树索引页上所有项目的详细信息。

SELECT * FROM nodes WHERE ctid='(115,1)'; #返回元素内容。
1
2
3
4
5
6
7

• 索引分析 , 模拟数据查找

我们首先要知道一些特定名词 , 图中有解释

这里我们用nodes表做演示 , 60w数据量 , 使用 IDX_userpoolId_leaderUserId 索引做示范

SELECT * FROM bt_metap('"IDX_userpoolId_leaderUserId"');
1

上图所示 根块 为 161 , btree层数为 3 层 (level+1)

继续搜索 , 显示根结点摘要

SELECT * FROM bt_page_stats('"IDX_userpoolId_leaderUserId"',161);
1

上图所示 btpo_level 为 2 , btpo_flags 为 2 , 则说明我们现在的看到的btree索引为三层(level+1) , 看的是根结点

继续搜索 , 查看该根块的孩子节点信息

SELECT * FROM bt_page_items('"IDX_userpoolId_leaderUserId"',161);
1

上图所示 我们查到了根块的枝块指向 . 该节点中每行的孩子节点中的 data 为16进制码 , 表示索引中数据的最小值 (比如我们这里的索引是靠 userpool_id 键排序的) , 转换成10进制就可以看出来 , 他是从小到大的排序

继续分析枝块 , 我们可以通过 SELECT * FROM bt_page_items(‘“IDX_userpoolId_leaderUserId”’,x); 命令与 ctid(x,y) 的 x 相对应 , 继续查看该孩子节点中的索引指向

SELECT * FROM bt_page_items('"IDX_userpoolId_leaderUserId"',6591);
1

上图所示 我们查到了枝块的叶子块指向 (因为树有3层 , 查了2次 , 所以现在所表示的为叶子结点)

继续分析叶子块

SELECT * FROM bt_page_stats('"IDX_userpoolId_leaderUserId"',7870);
1

上图所示 我们查到了叶子块的数据块 , 此时可以根据 ctid 找到数据了

根据 ctid 找数据

SELECT * FROM nodes WHERE ctid='(29183,13)'; 
1

上图所示 我们找到了数据

但是 , 叶子结点储存的是数据还是物理地址呢 ?

我们已经做了刚才的测试 , 我也找到了相应的文献 : postgresql-12-US.pdf 中 75 页

其中 ctid 表示行版本在其表中的物理位置。请注意，尽管 ctid 可用于非常快速地找到行版本，如果通过 VACUUM 更新或移动行，则行的 ctid 将发生变化满。因此，ctid 作为长期行标识符是无用的。主键应用于标识逻辑行

于是我们可以得出结论 , 叶子结点储存的是物理地址 , 和传统的 b+tree 不太一样

优化器 (mysql中的 , pg可参考)

相关阅读 : https://cloud.tencent.com/developer/article/1671374

优化器优化时会考虑的因素

• 扫描行数
• 是否使用临时表
• 是否需要排序 话外音：涉及到这个点，都要考虑你的index 是否生效。

扫描行数是怎么判断的

MySQL 在真正开始执行语句之前，并不能精确地知道满足这个条件的记录有多少条，而只能根据统计信息来估算记录数。这个统计信息就是索引的“区分度”。显然，一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。

那么，MySQL 是怎样得到索引的基数的呢？这里，我给你简单介绍一下 MySQL 采样统计的方法。为什么要采样统计呢？因为把整张表取出来一行行统计，虽然可以得到精确的结果，但是代价太高了，所以只能选择“采样统计”。采样统计的时候，InnoDB 默认会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。而数据表是会持续更新的，索引统计信息也不会固定不变。所以，当变更的数据行数超过 1/M 的时候，会自动触发重新做一次索引统计。

为何突然出现异常慢查询

问：这个查询语句已经在线上稳定运行了非常长的时间，为何这次突然出现了慢查询？

答：以前的语句查询条件返回结果都不为空，limit1很快就能找到那条数据，返回结果。而这次代码中查询条件实际结果为空，导致了扫描了全部的主键索引。

解决方案

知道了MySQL为何选择这个索引的原因后，我们就可以根据上面的思路来列举出解决办法了。

主要有两个大方向：

1. 强制指定索引
2. 干涉优化器选择

缺点也很明显：

• 高耦合，这种语句写在代码里，会变得难以维护，如果索引名变化了，或者没有这个索引了，代码就要反复修改。属于硬编码。
• 很多代码用框架封装了SQL，force index()并不容易加进去。

pg中优化器选择索引与人为干涉索引

相关阅读 : https://www.youtube.com/watch?v=HubezKbFL7E

视频中 25:25 描述了优化器优化的效率以及最终的结果比我们人为的干涉要好很多

TIPS : 两条索引选择(roles)

表中有一个 userpool_id的索引 和 一个主键索引

当用 IN 等函数操作时 , 优化器大部分情况下会优先选择另一个索引 , 或者使用拦截 Filter

EXPLAIN ANALYSE SELECT * FROM roles WHERE "id"='1233165' AND "userpool_id" IN ('123123213','414656747')
//Index Scan using "PK_c1433d71a4838793a49dcad46ab" on roles  (cost=0.42..8.45 rows=1 width=185) (actual time=0.141..0.142 rows=0 loops=1)
//  Index Cond: ((id)::text = '1233165'::text)
//  Filter: ((userpool_id)::text = ANY ('{123123213,414656747}'::text[]))
//Planning Time: 0.326 ms
//Execution Time: 0.215 ms


EXPLAIN ANALYSE SELECT * FROM roles WHERE "userpool_id"='12fd32312' AND "id" IN ('123123213','414656747')
//Index Scan using "IDX_userpoolId_namespaceId_code1" on roles  (cost=0.55..8.57 rows=1 width=185) (actual time=0.270..0.271 rows=0 loops=1)
//  Index Cond: ((userpool_id)::text = '12fd32312'::text)
//  Filter: ((id)::text = ANY ('{123123213,414656747}'::text[]))
//Planning Time: 0.451 ms
//Execution Time: 0.385 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14