65.1. B-树索引 #
65.1.1. 简介 #
PostgreSQL 包含标准 B-树(btree,即多路平衡树)索引数据结构的一种实现。凡是能够排成定义明确的线性顺序的数据类型,都可以使用 B-树索引。唯一的限制是,索引项在经过 TOAST 压缩(如果适用)后,大小也不能超过一个页面的大约三分之一。
由于每个 B-树操作符类都会为其数据类型施加一种排序顺序,B-树操作符类(更准确地说,是操作符族)已经成为 PostgreSQL 用来统一表示和理解排序语义的方式。因此,它们具备了一些超出单纯支持 B-树索引所需范围的特性,系统中某些与 B-树 AM 相距甚远的部分也会利用它们。
65.1.2. B-树操作符类的行为 #
正如表 36.3 所示,B-树操作符类必须提供五个比较操作符,<、<=、=、>= 和
>。人们可能会以为 <> 也应当属于操作符类的一部分,但事实并非如此,因为在索引搜索中使用
<> 的 WHERE 子句几乎毫无用处。(出于某些目的,规划器会把 <> 视为与 B-树操作符类相关联;但规划器是通过 = 操作符的求反器链接找到该操作符,而不是从
pg_amop 中找到它。)
当多种数据类型共享几乎相同的排序语义时,可以将它们的操作符类归入同一个操作符族。这样做的好处是,规划器就能够对跨类型比较作出推理。族中的每个操作符类都应当包含对应其输入数据类型的单类型操作符(以及相关支持函数),而跨类型比较操作符及其支持函数则作为该族中的“松散”成员存在。建议在族中包含一套完整的跨类型操作符,从而确保规划器能够表示它根据传递性推导出来的任意比较条件。
B-树操作符族必须满足一些基本假设:
=操作符必须是一种等价关系;也就是说,对于该数据类型的所有非 null 值A、B、C:A=A为真(自反律)如果
A=B,则B=A(对称律)如果
A=B且B=C,则A=C(传递律)
<操作符必须是一种强排序关系;也就是说,对于所有非 null 值A、B、C:A<A为假(非自反律)如果
A<B且B<C,则A<C(传递律)
此外,该顺序还是全序的;也就是说,对于所有非 null 值
A、B:A<B、A=B以及B<A中恰有一个为真(三分律)
(三分律当然也正是定义比较支持函数的依据。)
另外三个操作符都可以用 = 和
< 以显而易见的方式定义,并且必须与它们保持一致。
对于支持多种数据类型的操作符族,当 A、B、C
取自该族中的任意数据类型时,上述定律都必须成立。传递律最难保证,因为在跨类型情况下,它要求两种或三种不同操作符的行为彼此一致。举例来说,不能把
float8 和 numeric
放进同一个操作符族,至少在当前这种语义下不行:会先将
numeric 值转换为 float8,以便与
float8 比较。由于
float8 精度有限,这意味着会存在不同的
numeric 值都与同一个 float8
值比较为相等,于是传递律就会失效。
对于多数据类型操作符族,另一个要求是:在族内数据类型之间定义的任何隐式或二进制强制转换,都不得改变相应的排序顺序。
很容易理解为什么 B-树索引要求这些定律在单一数据类型内部成立:没有这些定律,就不存在可用于排列键的顺序。此外,使用不同数据类型比较键的索引搜索,也要求跨两种数据类型的比较行为合理一致。把这些要求扩展到一个族内的三种或更多数据类型,虽然并非 B-树索引机制本身的严格要求,但规划器会出于优化目的依赖它们。
65.1.3. B-树支持函数 #
如表 36.9 所示,B-树定义了一个必需和五个可选的支持函数。六个用户定义的方法如下:
order对于 B-树操作符族为其提供比较操作符的每一种数据类型组合,都必须提供一个比较支持函数。该函数在
pg_amproc中注册,支持函数编号为 1,并且amproclefttype/amprocrighttype要等于该比较的左右数据类型(也就是与匹配操作符在pg_amop中注册时相同的数据类型)。比较函数必须接受两个非 null 值A和B,并返回一个int32值,其值为<0、0或>0,分别对应A<B、A=B或A>B。不允许返回 null:该数据类型的所有值都必须可比较。示例见src/backend/access/nbtree/nbtcompare.c。如果参与比较的值属于支持排序规则的数据类型,则会通过标准的
PG_GET_COLLATION()机制,把适当的排序规则 OID 传递给比较支持函数。sortsupport可选地,B-树操作符族可以提供排序支持函数,注册为支持函数编号 2。这些函数允许以比朴素地直接调用比较支持函数更高效的方式,实现用于排序的比较。相关 API 定义在
src/include/utils/sortsupport.h中。in_range可选地,B-树操作符族可以提供 in_range 支持函数,注册为支持函数编号 3。这些函数不会在 B-树索引操作期间使用;相反,它们会扩展操作符族的语义,使其能够支持包含
RANGEoffsetPRECEDING和RANGEoffsetFOLLOWING这两种帧边界类型的窗口子句(见第 4.2.8 节)。本质上,它额外提供的信息是:如何以与该族数据排序兼容的方式,对offset值进行加减。in_range函数必须具有如下签名:in_range(
valtype1,basetype1,offsettype2,subbool,lessbool) returns boolval和base必须具有相同类型,并且该类型必须是操作符族支持的类型之一(也就是该族为其提供排序的一种类型)。不过,offset可以是另一种类型,而该类型甚至可能不被该族以其他方式支持。例如,内置的time_ops族就提供了一个in_range函数,其offset的类型为interval。一个族可以提供in_range函数,分别对应其支持的任意类型以及一个或多个offset类型。每个in_range函数都应在pg_amproc中登记,其中amproclefttype等于type1,而amprocrighttype等于type2。in_range函数的核心语义取决于这两个布尔标志参数。它应当先对base与offset做加法或减法,再把val与结果比较,具体如下:如果
!sub且!less,返回val>=(base+offset)如果
!sub且less,返回val<=(base+offset)如果
sub且!less,返回val>=(base-offset)如果
sub且less,返回val<=(base-offset)
在此之前,函数应检查
offset的符号:如果它小于零,就引发错误ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE(22013),错误文本类似于“invalid preceding or following size in window function”。(这是 SQL 标准的要求,尽管非标准操作符族或许会选择忽略这一限制,因为从语义上看似乎并没有太大必要。)把这个要求委托给in_range函数,是为了让核心代码无需理解对于某个特定数据类型来说“小于零”究竟意味着什么。另外还希望
in_range函数在可行时避免因为base+offset或base-offset会溢出而抛出错误。即便该值会超出该数据类型的取值范围,仍然可以判定正确的比较结果。注意,如果该数据类型包含诸如“infinity”或“NaN”之类的概念,就可能需要格外小心,以确保in_range的结果与该操作符族的正常排序顺序一致。in_range函数的结果必须与操作符族施加的排序顺序保持一致。更精确地说,给定任意固定的offset和sub值,则:如果
in_range在less= true 时,对某个val1和base返回真,那么对于每一个val2<=val1,只要其base相同,它也必须返回真。如果
in_range在less= true 时,对某个val1和base返回假,那么对于每一个val2>=val1,只要其base相同,它也必须返回假。如果
in_range在less= true 时,对某个val和base1返回真,那么对于每一个base2>=base1,只要其val相同,它也必须返回真。如果
in_range在less= true 时,对某个val和base1返回假,那么对于每一个base2<=base1,只要其val相同,它也必须返回假。
当
less= false 时,也有条件相反的对应陈述成立。如果被排序的类型(
type1)属于支持排序规则的数据类型,则会通过标准的 PG_GET_COLLATION() 机制,把适当的排序规则 OID 传递给in_range函数。in_range函数不必处理 NULL 输入,并且通常会被标记为 strict。equalimage可选地,B-树操作符族可以提供
equalimage(“相等蕴含映像相等”)支持函数,注册为支持函数编号 4。这些函数允许核心代码判断何时可以安全地应用 B-树去重优化。目前,equalimage函数只会在构建或重建索引时被调用。equalimage函数必须具有如下签名:equalimage(
opcintypeoid) returns bool返回值是关于某个操作符类及其排序规则的静态信息。返回
true表示可以保证:该操作符类的order函数只有在其A和B参数也能够互换而不损失任何语义信息时,才会返回0(“参数相等”)。如果未注册equalimage函数,或其返回false,就表示不能假定该条件成立。opcintype参数是该操作符类所索引数据类型的。这只是为了方便在不同操作符类之间复用同一个底层pg_type.oidequalimage函数。如果opcintype是支持排序规则的数据类型,则会通过标准的PG_GET_COLLATION()机制,把适当的排序规则 OID 传递给equalimage函数。就操作符类本身而言,返回
true表示可以安全去重(或者更准确地说,对于传递给其equalimage函数的那个排序规则来说可以安全去重)。但是,只有当每个被索引列都使用注册了equalimage函数的操作符类,并且各函数在调用时实际都返回true时,核心代码才会认为某个索引可以安全地去重。映像相等与简单的按位相等几乎是同一个条件。两者有一个细微差别:当 varlena 数据类型建立索引时,由于输入时应用 TOAST 压缩可能不一致,两个映像相等的 datum 的磁盘表示未必按位相等。形式化地说,当某个操作符类的
equalimage函数返回true时,就可以安全地假定datum_image_eq()C 函数将始终与该操作符类的order函数保持一致(前提是向equalimage和order函数传入的是同一个排序规则 OID)。核心代码本质上无法仅根据同一多数据类型族中其他操作符类的细节,推断出某个操作符类的“相等蕴含映像相等”状态。此外,操作符族注册跨类型的
equalimage函数并不合理,尝试这样做会导致错误。原因在于,“相等蕴含映像相等”状态并不只依赖于排序/相等语义,而这些语义大致是在操作符族层面定义的。一般来说,某个具体数据类型所实现的语义必须单独考虑。核心 PostgreSQL 发行版中包含的操作符类遵循的惯例是:注册一个现成的通用
equalimage函数。大多数操作符类注册btequalimage(),这表示去重在无条件下都是安全的。像text这样支持排序规则的数据类型的操作符类会注册btvarstrequalimage(),这表示在确定性排序规则下去重是安全的。第三方扩展的最佳实践则是注册它们自己的自定义函数,以保留控制权。options可选地,B-树操作符族可以提供
options(“操作符类特定选项”)支持函数,注册为支持函数编号 5。这些函数定义一组用户可见的参数,用于控制操作符类行为。options支持函数必须具有如下签名:options(
reloptslocal_relopts *) returns void该函数会接收一个指向
local_relopts结构体的指针,必须在其中填入一组操作符类特定选项。其他支持函数可以使用PG_HAS_OPCLASS_OPTIONS()和PG_GET_OPCLASS_OPTIONS()宏来访问这些选项。目前还没有任何 B-树操作符类带有
options支持函数。B-树不像 GiST、SP-GiST、GIN 和 BRIN 那样允许键具有灵活的表示方式。因此,options在当前的 B-树索引访问方法中大概没有太多用途。尽管如此,为了统一性,这个支持函数还是被加入到了 B-树中,并且很可能会在 PostgreSQL 中 B-树的进一步演进过程中派上用场。skipsupport可选地,B-树操作符族可以提供跳过支持函数,注册为支持函数编号 6。这些函数为 B-树代码提供了一种按键空间顺序遍历某个操作符类底层输入类型所能表示的全部可能值的方法。当核心代码应用跳过扫描优化时,就会用到它。相关 API 定义在
src/include/utils/skipsupport.h中。没有提供跳过支持函数的操作符类,仍然可以使用跳过扫描。核心代码仍可采用其后备策略,尽管对于某些离散类型来说,这种策略可能并非最优。对于连续类型上的操作符类,提供跳过支持函数通常没有意义(甚至可能不可行)。
操作符族注册跨类型的
skipsupport函数并不合理,尝试这样做会导致错误。因为要确定下一个可被索引的值,必须通过递增一个从索引元组复制出来的值来完成。所生成的值都必须属于同一种底层数据类型(也就是被“跳过”的索引列的操作符类输入类型)。
65.1.4. 实现 #
本节介绍一些可能对高级用户有用的 B-树索引实现细节。若要查看更详细、更加侧重内部机制的 B-树实现说明,请参见源码发布包中的
src/backend/access/nbtree/README。
65.1.4.1. B-树结构 #
PostgreSQL 的 B-树索引是多层树结构,其中树的每一层都可以用作页的双向链表。索引的第一个段文件起始处的固定位置保存着一个元页。其余页面要么是叶页,要么是内部页。叶页位于树的最低层,其余各层都由内部页组成。每个叶页都包含指向表中行的元组。每个内部页都包含指向树中下一层的元组。通常,超过 99% 的页面都是叶页。内部页和叶页都使用第 66.6 节中描述的标准页格式。
当现有叶页无法容纳一个新传入的元组时,B-树索引就会增加新的叶页。一次页拆分操作会把原本属于溢出页的一部分项移动到新页中,从而为这些项腾出空间。页拆分还必须在父页中插入一个指向新页的下行链接,这又可能导致父页继续拆分。页拆分会以递归的方式“向上级联”。当根页最终也容纳不下新的下行链接时,就会发生一次根页拆分操作。它通过创建一个位于原始根页之上的新根页,为树结构增加一个新的层级。
65.1.4.2. 自底向上索引删除 #
B-树索引并不直接知道,在 MVCC
下同一个逻辑表行可能存在多个现存版本;对索引来说,每个元组都是一个独立对象,都需要自己的索引项。“版本频繁更替”元组有时会积累起来,并对查询延迟和吞吐量造成不利影响。这通常发生在以
UPDATE 为主的工作负载中,因为其中大多数单次更新都无法应用
HOT 优化。在一次 UPDATE
中,如果哪怕只修改了某一个被某个索引覆盖的列的值,总是都需要生成一组新的索引元组,也就是表上每一个索引都要有一个。要特别注意,这也包括那些没有被“逻辑修改”、但仍会受到 UPDATE 影响的索引。所有索引都需要一个新的后继物理索引元组,指向表中的最新版本。每个索引中的新元组通常都需要在一小段时间内与原始的“被更新”元组共存(通常直到
UPDATE 事务提交后不久)。
B-树索引会通过执行自底向上索引删除轮次,增量地删除这类版本频繁更替产生的索引元组。每一轮删除都是因预期中的“版本频繁更替页拆分”而触发的。这只会发生在那些没有被
UPDATE 语句逻辑修改的索引上;如果不执行这类删除,过时版本就会集中积累在某些特定页面中。通常可以避免页拆分,不过也可能出现某些实现层面的启发式规则甚至一个垃圾索引元组都识别不出来、删不掉的情况(这时就要靠页拆分或一次去重轮次来解决新元组放不进叶页的问题)。任何一次索引扫描在单个逻辑行上必须穿越的最坏版本数,是影响整个系统响应能力和吞吐量的重要因素。一次自底向上索引删除轮次会基于涉及逻辑行与版本的定性区别,针对单个叶页中疑似垃圾的元组。这与自动清理工作进程执行的“自顶向下”索引清理不同,后者是在超出某些定量的表级阈值时触发的(见第 24.1.6 节)。
注意
在 B-树索引内部执行的删除操作,并不全都是自底向上删除。索引元组删除还有另一类独立类别:简单索引元组删除。这是一种延迟维护操作,用来删除那些已知可以安全删除的索引元组(即其项标识符的
LP_DEAD
位已经被设置的元组)。和自底向上索引删除一样,简单索引删除也发生在预期将要进行页拆分的时候,以此避免拆分。
简单删除具有机会性,因为它只能发生在最近的索引扫描顺便设置了受影响项的
LP_DEAD 位时。在
PostgreSQL 14 之前,B-树删除的唯一类别就是简单删除。它与自底向上删除的主要区别在于:只有前者会由经过的索引扫描活动机会性地驱动,而只有后者专门针对那些不会逻辑修改已索引列的
UPDATE 所造成的版本频繁更替。
对于某些工作负载下的特定索引,自底向上索引删除承担了绝大多数垃圾索引元组清理工作。任何一个
B-树索引,只要它遭受了来自
UPDATE 的显著版本频繁更替,而这些更新又很少或从不逻辑修改该索引覆盖的列,通常都会出现这种情况。仅通过有针对性的增量删除轮次,就能把每个逻辑行的平均版本数和最坏版本数都控制在较低水平。尽管持续不断的
UPDATE 会持续造成版本频繁更替,某些索引的磁盘大小也完全有可能连一个页面/块都不会增加。即便如此,最终仍然需要一次彻底的“全面清扫”,由
VACUUM 操作(通常运行在自动清理工作进程中)执行,作为表及其各个索引整体清理的一部分。
与 VACUUM 不同,自底向上索引删除并不会对最老垃圾索引元组的年龄给出任何强保证。不允许任何索引保留那些在表及其所有索引共同遵守的保守截断点之前就已经死亡的“浮动垃圾”索引元组。这个基本的表级不变量使得回收表
TID 成为安全操作。也正因如此,不同的逻辑行才有可能随着时间推移重用同一个表
TID(当然,这绝不可能发生在生命周期跨越同一个
VACUUM 周期的两个逻辑行之间)。
65.1.4.3. 去重 #
重复项是这样一种叶页元组(即指向表中行的元组):其中所有被索引的键列值,都与同一索引中至少另一个叶页元组对应列的值相匹配。重复元组在实践中相当常见。当启用一种可选技术时,B-树索引可以为重复项采用一种特殊且节省空间的表示形式:去重。
去重通过周期性地把一组组重复元组合并起来,为每一组形成一个倒排列表元组。在这种表示中,列键值只出现一次,后面跟着一个排好序的 TID 数组,指向表中的各行。这能显著减小那些每个值(或每一种不同列值组合)平均会出现多次的索引的存储大小。查询延迟可能显著降低,整体查询吞吐量也可能显著提升,例行索引清理的开销同样可能显著减少。
注意
即使“重复项”中包含 NULL 值,B-树去重同样有效,尽管根据任何 B-树操作符类的
= 成员,NULL
值彼此永远不相等。对于实现中任何理解磁盘上 B-树结构的部分来说,NULL 只是索引值域中的另一个值而已。
去重过程是惰性发生的:当插入一个放不进现有叶页的新项时,只有在索引元组删除也无法为该新项释放足够空间的情况下,才会进行去重(通常只会短暂考虑删除,然后就跳过)。与 GIN 的倒排列表元组不同,B-树的倒排列表元组不需要在每次插入新的重复项时都扩展;它们只是叶页原始逻辑内容的一种替代物理表示。这种设计优先考虑混合读写工作负载下的稳定性能。大多数客户端应用至少都能从去重中获得适度的性能收益。去重默认启用。
CREATE INDEX 和 REINDEX
都会应用去重来创建倒排列表元组,不过它们采用的策略与上述过程略有不同。对于从表中取出的已排序输入中遇到的每一组普通重复元组,都会在被加入当前待写入叶页之前先合并成一个倒排列表元组。每个倒排列表元组都会尽量容纳更多的
TID。叶页按通常方式写出,不需要额外独立的去重过程。由于
CREATE INDEX 和
REINDEX 都是一次性的批处理操作,这种策略非常适合它们。
如果某个写密集型工作负载由于索引中的重复值很少甚至没有,而无法从去重中获益,那么它会承担很小且固定的性能损耗(除非显式禁用去重)。deduplicate_items
存储参数可用于在单个索引内禁用去重。而只读工作负载绝不会因此遭受性能损失,因为读取倒排列表元组至少与读取标准元组表示一样高效。禁用去重通常并没有帮助。
有时唯一索引(以及唯一约束)也可以使用去重。这允许叶页临时“吸收”因版本频繁更替产生的额外重复项。唯一索引中的去重能够增强自底向上索引删除,特别是在长事务持有阻塞垃圾回收的快照时。其目标是为自底向上索引删除策略再次发挥作用争取时间。把页拆分推迟到某个单独的长事务自然结束之后,可能使一次自底向上删除轮次在较早一次失败的地方获得成功。
提示
系统会应用一种特殊的启发式规则,来判定唯一索引中是否应当执行一次去重轮次。它往往可以直接跳到拆分叶页,从而避免把处理器周期浪费在无益的去重过程中而造成性能损耗。如果你担心去重的开销,可以考虑有选择地设置
deduplicate_items = off。在唯一索引中保持去重启用,坏处很小。
由于实现层面的限制,并非所有情况下都能使用去重。去重是否安全,是在运行
CREATE INDEX 或
REINDEX 时确定的。
请注意,在下列情况下,相等的 datum 之间存在语义上重要的差异,因此去重被视为不安全且不可使用:
text、varchar和char在使用非确定性排序规则时,不能使用去重。必须保留相等的 datum 之间的大小写和重音差异。numeric不能使用去重。必须保留相等的 datum 之间的显示小数位数。jsonb不能使用去重,因为jsonb的 B-树操作符类在内部使用了numeric。float4和float8不能使用去重。这些类型对-0和0有不同的表示形式,但它们仍然被视为相等,这种差异必须保留。
还有一个实现层面的限制,未来版本的 PostgreSQL 也许会取消它:
容器类型(例如复合类型、数组或范围类型)不能使用去重。
还有一个实现层面的限制,无论使用何种操作符类或排序规则都适用:
INCLUDE索引永远不能使用去重。