| 1 |
<!-- doc/src/sgml/btree.sgml --> |
| 2 |
|
| 3 |
<sect1 id="btree"> |
| 4 |
<title>B-Tree Indexes</title> |
| 5 |
|
| 6 |
<indexterm> |
| 7 |
<primary>index</primary> |
| 8 |
<secondary>B-Tree</secondary> |
| 9 |
</indexterm> |
| 10 |
|
| 11 |
<sect2 id="btree-intro"> |
| 12 |
<title>Introduction</title> |
| 13 |
|
| 14 |
<para> |
| 15 |
<productname>PostgreSQL</productname> includes an implementation of the |
| 16 |
standard <acronym>btree</acronym> (multi-way balanced tree) index data |
| 17 |
structure. Any data type that can be sorted into a well-defined linear |
| 18 |
order can be indexed by a btree index. The only limitation is that an |
| 19 |
index entry cannot exceed approximately one-third of a page (after TOAST |
| 20 |
compression, if applicable). |
| 21 |
</para> |
| 22 |
|
| 23 |
<para> |
| 24 |
Because each btree operator class imposes a sort order on its data type, |
| 25 |
btree operator classes (or, really, operator families) have come to be |
| 26 |
used as <productname>PostgreSQL</productname>'s general representation |
| 27 |
and understanding of sorting semantics. Therefore, they've acquired |
| 28 |
some features that go beyond what would be needed just to support btree |
| 29 |
indexes, and parts of the system that are quite distant from the |
| 30 |
btree <acronym>AM</acronym> make use of them. |
| 31 |
</para> |
| 32 |
|
| 33 |
</sect2> |
| 34 |
|
| 35 |
<sect2 id="btree-behavior"> |
| 36 |
<title>Behavior of B-Tree Operator Classes</title> |
| 37 |
|
| 38 |
<para> |
| 39 |
As shown in <xref linkend="xindex-btree-strat-table"/>, a btree operator |
| 40 |
class must provide five comparison operators, |
| 41 |
<literal><</literal>, |
| 42 |
<literal><=</literal>, |
| 43 |
<literal>=</literal>, |
| 44 |
<literal>>=</literal> and |
| 45 |
<literal>></literal>. |
| 46 |
One might expect that <literal><></literal> should also be part of |
| 47 |
the operator class, but it is not, because it would almost never be |
| 48 |
useful to use a <literal><></literal> WHERE clause in an index |
| 49 |
search. (For some purposes, the planner treats <literal><></literal> |
| 50 |
as associated with a btree operator class; but it finds that operator via |
| 51 |
the <literal>=</literal> operator's negator link, rather than |
| 52 |
from <structname>pg_amop</structname>.) |
| 53 |
</para> |
| 54 |
|
| 55 |
<para> |
| 56 |
When several data types share near-identical sorting semantics, their |
| 57 |
operator classes can be grouped into an operator family. Doing so is |
| 58 |
advantageous because it allows the planner to make deductions about |
| 59 |
cross-type comparisons. Each operator class within the family should |
| 60 |
contain the single-type operators (and associated support functions) |
| 61 |
for its input data type, while cross-type comparison operators and |
| 62 |
support functions are <quote>loose</quote> in the family. It is |
| 63 |
recommendable that a complete set of cross-type operators be included |
| 64 |
in the family, thus ensuring that the planner can represent any |
| 65 |
comparison conditions that it deduces from transitivity. |
| 66 |
</para> |
| 67 |
|
| 68 |
<para> |
| 69 |
There are some basic assumptions that a btree operator family must |
| 70 |
satisfy: |
| 71 |
</para> |
| 72 |
|
| 73 |
<itemizedlist> |
| 74 |
<listitem> |
| 75 |
<para> |
| 76 |
An <literal>=</literal> operator must be an equivalence relation; that |
| 77 |
is, for all non-null values <replaceable>A</replaceable>, |
| 78 |
<replaceable>B</replaceable>, <replaceable>C</replaceable> of the |
| 79 |
data type: |
| 80 |
|
| 81 |
<itemizedlist> |
| 82 |
<listitem> |
| 83 |
<para> |
| 84 |
<replaceable>A</replaceable> <literal>=</literal> |
| 85 |
<replaceable>A</replaceable> is true |
| 86 |
(<firstterm>reflexive law</firstterm>) |
| 87 |
</para> |
| 88 |
</listitem> |
| 89 |
<listitem> |
| 90 |
<para> |
| 91 |
if <replaceable>A</replaceable> <literal>=</literal> |
| 92 |
<replaceable>B</replaceable>, |
| 93 |
then <replaceable>B</replaceable> <literal>=</literal> |
| 94 |
<replaceable>A</replaceable> |
| 95 |
(<firstterm>symmetric law</firstterm>) |
| 96 |
</para> |
| 97 |
</listitem> |
| 98 |
<listitem> |
| 99 |
<para> |
| 100 |
if <replaceable>A</replaceable> <literal>=</literal> |
| 101 |
<replaceable>B</replaceable> and <replaceable>B</replaceable> |
| 102 |
<literal>=</literal> <replaceable>C</replaceable>, |
| 103 |
then <replaceable>A</replaceable> <literal>=</literal> |
| 104 |
<replaceable>C</replaceable> |
| 105 |
(<firstterm>transitive law</firstterm>) |
| 106 |
</para> |
| 107 |
</listitem> |
| 108 |
</itemizedlist> |
| 109 |
</para> |
| 110 |
</listitem> |
| 111 |
|
| 112 |
<listitem> |
| 113 |
<para> |
| 114 |
A <literal><</literal> operator must be a strong ordering relation; |
| 115 |
that is, for all non-null values <replaceable>A</replaceable>, |
| 116 |
<replaceable>B</replaceable>, <replaceable>C</replaceable>: |
| 117 |
|
| 118 |
<itemizedlist> |
| 119 |
<listitem> |
| 120 |
<para> |
| 121 |
<replaceable>A</replaceable> <literal><</literal> |
| 122 |
<replaceable>A</replaceable> is false |
| 123 |
(<firstterm>irreflexive law</firstterm>) |
| 124 |
</para> |
| 125 |
</listitem> |
| 126 |
<listitem> |
| 127 |
<para> |
| 128 |
if <replaceable>A</replaceable> <literal><</literal> |
| 129 |
<replaceable>B</replaceable> |
| 130 |
and <replaceable>B</replaceable> <literal><</literal> |
| 131 |
<replaceable>C</replaceable>, |
| 132 |
then <replaceable>A</replaceable> <literal><</literal> |
| 133 |
<replaceable>C</replaceable> |
| 134 |
(<firstterm>transitive law</firstterm>) |
| 135 |
</para> |
| 136 |
</listitem> |
| 137 |
</itemizedlist> |
| 138 |
</para> |
| 139 |
</listitem> |
| 140 |
|
| 141 |
<listitem> |
| 142 |
<para> |
| 143 |
Furthermore, the ordering is total; that is, for all non-null |
| 144 |
values <replaceable>A</replaceable>, <replaceable>B</replaceable>: |
| 145 |
|
| 146 |
<itemizedlist> |
| 147 |
<listitem> |
| 148 |
<para> |
| 149 |
exactly one of <replaceable>A</replaceable> <literal><</literal> |
| 150 |
<replaceable>B</replaceable>, <replaceable>A</replaceable> |
| 151 |
<literal>=</literal> <replaceable>B</replaceable>, and |
| 152 |
<replaceable>B</replaceable> <literal><</literal> |
| 153 |
<replaceable>A</replaceable> is true |
| 154 |
(<firstterm>trichotomy law</firstterm>) |
| 155 |
</para> |
| 156 |
</listitem> |
| 157 |
</itemizedlist> |
| 158 |
|
| 159 |
(The trichotomy law justifies the definition of the comparison support |
| 160 |
function, of course.) |
| 161 |
</para> |
| 162 |
</listitem> |
| 163 |
</itemizedlist> |
| 164 |
|
| 165 |
<para> |
| 166 |
The other three operators are defined in terms of <literal>=</literal> |
| 167 |
and <literal><</literal> in the obvious way, and must act consistently |
| 168 |
with them. |
| 169 |
</para> |
| 170 |
|
| 171 |
<para> |
| 172 |
For an operator family supporting multiple data types, the above laws must |
| 173 |
hold when <replaceable>A</replaceable>, <replaceable>B</replaceable>, |
| 174 |
<replaceable>C</replaceable> are taken from any data types in the family. |
| 175 |
The transitive laws are the trickiest to ensure, as in cross-type |
| 176 |
situations they represent statements that the behaviors of two or three |
| 177 |
different operators are consistent. |
| 178 |
As an example, it would not work to put <type>float8</type> |
| 179 |
and <type>numeric</type> into the same operator family, at least not with |
| 180 |
the current semantics that <type>numeric</type> values are converted |
| 181 |
to <type>float8</type> for comparison to a <type>float8</type>. Because |
| 182 |
of the limited accuracy of <type>float8</type>, this means there are |
| 183 |
distinct <type>numeric</type> values that will compare equal to the |
| 184 |
same <type>float8</type> value, and thus the transitive law would fail. |
| 185 |
</para> |
| 186 |
|
| 187 |
<para> |
| 188 |
Another requirement for a multiple-data-type family is that any implicit |
| 189 |
or binary-coercion casts that are defined between data types included in |
| 190 |
the operator family must not change the associated sort ordering. |
| 191 |
</para> |
| 192 |
|
| 193 |
<para> |
| 194 |
It should be fairly clear why a btree index requires these laws to hold |
| 195 |
within a single data type: without them there is no ordering to arrange |
| 196 |
the keys with. Also, index searches using a comparison key of a |
| 197 |
different data type require comparisons to behave sanely across two |
| 198 |
data types. The extensions to three or more data types within a family |
| 199 |
are not strictly required by the btree index mechanism itself, but the |
| 200 |
planner relies on them for optimization purposes. |
| 201 |
</para> |
| 202 |
|
| 203 |
</sect2> |
| 204 |
|
| 205 |
<sect2 id="btree-support-funcs"> |
| 206 |
<title>B-Tree Support Functions</title> |
| 207 |
|
| 208 |
<para> |
| 209 |
As shown in <xref linkend="xindex-btree-support-table"/>, btree defines |
| 210 |
one required and five optional support functions. The six |
| 211 |
user-defined methods are: |
| 212 |
</para> |
| 213 |
<variablelist> |
| 214 |
<varlistentry> |
| 215 |
<term><function>order</function></term> |
| 216 |
<listitem> |
| 217 |
<para> |
| 218 |
For each combination of data types that a btree operator family |
| 219 |
provides comparison operators for, it must provide a comparison |
| 220 |
support function, registered in |
| 221 |
<structname>pg_amproc</structname> with support function number 1 |
| 222 |
and |
| 223 |
<structfield>amproclefttype</structfield>/<structfield>amprocrighttype</structfield> |
| 224 |
equal to the left and right data types for the comparison (i.e., |
| 225 |
the same data types that the matching operators are registered |
| 226 |
with in <structname>pg_amop</structname>). The comparison |
| 227 |
function must take two non-null values |
| 228 |
<replaceable>A</replaceable> and <replaceable>B</replaceable> and |
| 229 |
return an <type>int32</type> value that is |
| 230 |
<literal><</literal> <literal>0</literal>, |
| 231 |
<literal>0</literal>, or <literal>></literal> |
| 232 |
<literal>0</literal> when <replaceable>A</replaceable> |
| 233 |
<literal><</literal> <replaceable>B</replaceable>, |
| 234 |
<replaceable>A</replaceable> <literal>=</literal> |
| 235 |
<replaceable>B</replaceable>, or <replaceable>A</replaceable> |
| 236 |
<literal>></literal> <replaceable>B</replaceable>, |
| 237 |
respectively. A null result is disallowed: all values of the |
| 238 |
data type must be comparable. See |
| 239 |
<filename>src/backend/access/nbtree/nbtcompare.c</filename> for |
| 240 |
examples. |
| 241 |
</para> |
| 242 |
|
| 243 |
<para> |
| 244 |
If the compared values are of a collatable data type, the |
| 245 |
appropriate collation OID will be passed to the comparison |
| 246 |
support function, using the standard |
| 247 |
<function>PG_GET_COLLATION()</function> mechanism. |
| 248 |
</para> |
| 249 |
</listitem> |
| 250 |
</varlistentry> |
| 251 |
<varlistentry> |
| 252 |
<term><function>sortsupport</function></term> |
| 253 |
<listitem> |
| 254 |
<para> |
| 255 |
Optionally, a btree operator family may provide <firstterm>sort |
| 256 |
support</firstterm> function(s), registered under support |
| 257 |
function number 2. These functions allow implementing |
| 258 |
comparisons for sorting purposes in a more efficient way than |
| 259 |
naively calling the comparison support function. The APIs |
| 260 |
involved in this are defined in |
| 261 |
<filename>src/include/utils/sortsupport.h</filename>. |
| 262 |
</para> |
| 263 |
</listitem> |
| 264 |
</varlistentry> |
| 265 |
<varlistentry> |
| 266 |
<term><function>in_range</function></term> |
| 267 |
<listitem> |
| 268 |
<indexterm> |
| 269 |
<primary>in_range support functions</primary> |
| 270 |
</indexterm> |
| 271 |
|
| 272 |
<indexterm> |
| 273 |
<primary>support functions</primary> |
| 274 |
<secondary>in_range</secondary> |
| 275 |
</indexterm> |
| 276 |
<para> |
| 277 |
Optionally, a btree operator family may provide |
| 278 |
<firstterm>in_range</firstterm> support function(s), registered |
| 279 |
under support function number 3. These are not used during btree |
| 280 |
index operations; rather, they extend the semantics of the |
| 281 |
operator family so that it can support window clauses containing |
| 282 |
the <literal>RANGE</literal> <replaceable>offset</replaceable> |
| 283 |
<literal>PRECEDING</literal> and <literal>RANGE</literal> |
| 284 |
<replaceable>offset</replaceable> <literal>FOLLOWING</literal> |
| 285 |
frame bound types (see <xref |
| 286 |
linkend="syntax-window-functions"/>). Fundamentally, the extra |
| 287 |
information provided is how to add or subtract an |
| 288 |
<replaceable>offset</replaceable> value in a way that is |
| 289 |
compatible with the family's data ordering. |
| 290 |
</para> |
| 291 |
|
| 292 |
<para> |
| 293 |
An <function>in_range</function> function must have the signature |
| 294 |
<synopsis> |
| 295 |
in_range(<replaceable>val</replaceable> type1, <replaceable>base</replaceable> type1, <replaceable>offset</replaceable> type2, <replaceable>sub</replaceable> bool, <replaceable>less</replaceable> bool) |
| 296 |
returns bool |
| 297 |
</synopsis> |
| 298 |
<replaceable>val</replaceable> and |
| 299 |
<replaceable>base</replaceable> must be of the same type, which |
| 300 |
is one of the types supported by the operator family (i.e., a |
| 301 |
type for which it provides an ordering). However, |
| 302 |
<replaceable>offset</replaceable> could be of a different type, |
| 303 |
which might be one otherwise unsupported by the family. An |
| 304 |
example is that the built-in <literal>time_ops</literal> family |
| 305 |
provides an <function>in_range</function> function that has |
| 306 |
<replaceable>offset</replaceable> of type <type>interval</type>. |
| 307 |
A family can provide <function>in_range</function> functions for |
| 308 |
any of its supported types and one or more |
| 309 |
<replaceable>offset</replaceable> types. Each |
| 310 |
<function>in_range</function> function should be entered in |
| 311 |
<structname>pg_amproc</structname> with |
| 312 |
<structfield>amproclefttype</structfield> equal to |
| 313 |
<type>type1</type> and <structfield>amprocrighttype</structfield> |
| 314 |
equal to <type>type2</type>. |
| 315 |
</para> |
| 316 |
|
| 317 |
<para> |
| 318 |
The essential semantics of an <function>in_range</function> |
| 319 |
function depend on the two Boolean flag parameters. It should |
| 320 |
add or subtract <replaceable>base</replaceable> and |
| 321 |
<replaceable>offset</replaceable>, then compare |
| 322 |
<replaceable>val</replaceable> to the result, as follows: |
| 323 |
<itemizedlist> |
| 324 |
<listitem> |
| 325 |
<para> |
| 326 |
if <literal>!</literal><replaceable>sub</replaceable> and |
| 327 |
<literal>!</literal><replaceable>less</replaceable>, return |
| 328 |
<replaceable>val</replaceable> <literal>>=</literal> |
| 329 |
(<replaceable>base</replaceable> <literal>+</literal> |
| 330 |
<replaceable>offset</replaceable>) |
| 331 |
</para> |
| 332 |
</listitem> |
| 333 |
<listitem> |
| 334 |
<para> |
| 335 |
if <literal>!</literal><replaceable>sub</replaceable> and |
| 336 |
<replaceable>less</replaceable>, return |
| 337 |
<replaceable>val</replaceable> <literal><=</literal> |
| 338 |
(<replaceable>base</replaceable> <literal>+</literal> |
| 339 |
<replaceable>offset</replaceable>) |
| 340 |
</para> |
| 341 |
</listitem> |
| 342 |
<listitem> |
| 343 |
<para> |
| 344 |
if <replaceable>sub</replaceable> and |
| 345 |
<literal>!</literal><replaceable>less</replaceable>, return |
| 346 |
<replaceable>val</replaceable> <literal>>=</literal> |
| 347 |
(<replaceable>base</replaceable> <literal>-</literal> |
| 348 |
<replaceable>offset</replaceable>) |
| 349 |
</para> |
| 350 |
</listitem> |
| 351 |
<listitem> |
| 352 |
<para> |
| 353 |
if <replaceable>sub</replaceable> and |
| 354 |
<replaceable>less</replaceable>, return |
| 355 |
<replaceable>val</replaceable> <literal><=</literal> |
| 356 |
(<replaceable>base</replaceable> <literal>-</literal> |
| 357 |
<replaceable>offset</replaceable>) |
| 358 |
</para> |
| 359 |
</listitem> |
| 360 |
</itemizedlist> |
| 361 |
Before doing so, the function should check the sign of |
| 362 |
<replaceable>offset</replaceable>: if it is less than zero, raise |
| 363 |
error |
| 364 |
<literal>ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE</literal> |
| 365 |
(22013) with error text like <quote>invalid preceding or |
| 366 |
following size in window function</quote>. (This is required by |
| 367 |
the SQL standard, although nonstandard operator families might |
| 368 |
perhaps choose to ignore this restriction, since there seems to |
| 369 |
be little semantic necessity for it.) This requirement is |
| 370 |
delegated to the <function>in_range</function> function so that |
| 371 |
the core code needn't understand what <quote>less than |
| 372 |
zero</quote> means for a particular data type. |
| 373 |
</para> |
| 374 |
|
| 375 |
<para> |
| 376 |
An additional expectation is that <function>in_range</function> |
| 377 |
functions should, if practical, avoid throwing an error if |
| 378 |
<replaceable>base</replaceable> <literal>+</literal> |
| 379 |
<replaceable>offset</replaceable> or |
| 380 |
<replaceable>base</replaceable> <literal>-</literal> |
| 381 |
<replaceable>offset</replaceable> would overflow. The correct |
| 382 |
comparison result can be determined even if that value would be |
| 383 |
out of the data type's range. Note that if the data type |
| 384 |
includes concepts such as <quote>infinity</quote> or |
| 385 |
<quote>NaN</quote>, extra care may be needed to ensure that |
| 386 |
<function>in_range</function>'s results agree with the normal |
| 387 |
sort order of the operator family. |
| 388 |
</para> |
| 389 |
|
| 390 |
<para> |
| 391 |
The results of the <function>in_range</function> function must be |
| 392 |
consistent with the sort ordering imposed by the operator family. |
| 393 |
To be precise, given any fixed values of |
| 394 |
<replaceable>offset</replaceable> and |
| 395 |
<replaceable>sub</replaceable>, then: |
| 396 |
<itemizedlist> |
| 397 |
<listitem> |
| 398 |
<para> |
| 399 |
If <function>in_range</function> with |
| 400 |
<replaceable>less</replaceable> = true is true for some |
| 401 |
<replaceable>val1</replaceable> and |
| 402 |
<replaceable>base</replaceable>, it must be true for every |
| 403 |
<replaceable>val2</replaceable> <literal><=</literal> |
| 404 |
<replaceable>val1</replaceable> with the same |
| 405 |
<replaceable>base</replaceable>. |
| 406 |
</para> |
| 407 |
</listitem> |
| 408 |
<listitem> |
| 409 |
<para> |
| 410 |
If <function>in_range</function> with |
| 411 |
<replaceable>less</replaceable> = true is false for some |
| 412 |
<replaceable>val1</replaceable> and |
| 413 |
<replaceable>base</replaceable>, it must be false for every |
| 414 |
<replaceable>val2</replaceable> <literal>>=</literal> |
| 415 |
<replaceable>val1</replaceable> with the same |
| 416 |
<replaceable>base</replaceable>. |
| 417 |
</para> |
| 418 |
</listitem> |
| 419 |
<listitem> |
| 420 |
<para> |
| 421 |
If <function>in_range</function> with |
| 422 |
<replaceable>less</replaceable> = true is true for some |
| 423 |
<replaceable>val</replaceable> and |
| 424 |
<replaceable>base1</replaceable>, it must be true for every |
| 425 |
<replaceable>base2</replaceable> <literal>>=</literal> |
| 426 |
<replaceable>base1</replaceable> with the same |
| 427 |
<replaceable>val</replaceable>. |
| 428 |
</para> |
| 429 |
</listitem> |
| 430 |
<listitem> |
| 431 |
<para> |
| 432 |
If <function>in_range</function> with |
| 433 |
<replaceable>less</replaceable> = true is false for some |
| 434 |
<replaceable>val</replaceable> and |
| 435 |
<replaceable>base1</replaceable>, it must be false for every |
| 436 |
<replaceable>base2</replaceable> <literal><=</literal> |
| 437 |
<replaceable>base1</replaceable> with the same |
| 438 |
<replaceable>val</replaceable>. |
| 439 |
</para> |
| 440 |
</listitem> |
| 441 |
</itemizedlist> |
| 442 |
Analogous statements with inverted conditions hold when |
| 443 |
<replaceable>less</replaceable> = false. |
| 444 |
</para> |
| 445 |
|
| 446 |
<para> |
| 447 |
If the type being ordered (<type>type1</type>) is collatable, the |
| 448 |
appropriate collation OID will be passed to the |
| 449 |
<function>in_range</function> function, using the standard |
| 450 |
PG_GET_COLLATION() mechanism. |
| 451 |
</para> |
| 452 |
|
| 453 |
<para> |
| 454 |
<function>in_range</function> functions need not handle NULL |
| 455 |
inputs, and typically will be marked strict. |
| 456 |
</para> |
| 457 |
</listitem> |
| 458 |
</varlistentry> |
| 459 |
<varlistentry> |
| 460 |
<term><function>equalimage</function></term> |
| 461 |
<listitem> |
| 462 |
<para> |
| 463 |
Optionally, a btree operator family may provide |
| 464 |
<function>equalimage</function> (<quote>equality implies image |
| 465 |
equality</quote>) support functions, registered under support |
| 466 |
function number 4. These functions allow the core code to |
| 467 |
determine when it is safe to apply the btree deduplication |
| 468 |
optimization. Currently, <function>equalimage</function> |
| 469 |
functions are only called when building or rebuilding an index. |
| 470 |
</para> |
| 471 |
<para> |
| 472 |
An <function>equalimage</function> function must have the |
| 473 |
signature |
| 474 |
<synopsis> |
| 475 |
equalimage(<replaceable>opcintype</replaceable> <type>oid</type>) returns bool |
| 476 |
</synopsis> |
| 477 |
The return value is static information about an operator class |
| 478 |
and collation. Returning <literal>true</literal> indicates that |
| 479 |
the <function>order</function> function for the operator class is |
| 480 |
guaranteed to only return <literal>0</literal> (<quote>arguments |
| 481 |
are equal</quote>) when its <replaceable>A</replaceable> and |
| 482 |
<replaceable>B</replaceable> arguments are also interchangeable |
| 483 |
without any loss of semantic information. Not registering an |
| 484 |
<function>equalimage</function> function or returning |
| 485 |
<literal>false</literal> indicates that this condition cannot be |
| 486 |
assumed to hold. |
| 487 |
</para> |
| 488 |
<para> |
| 489 |
The <replaceable>opcintype</replaceable> argument is the |
| 490 |
<literal><structname>pg_type</structname>.oid</literal> of the |
| 491 |
data type that the operator class indexes. This is a convenience |
| 492 |
that allows reuse of the same underlying |
| 493 |
<function>equalimage</function> function across operator classes. |
| 494 |
If <replaceable>opcintype</replaceable> is a collatable data |
| 495 |
type, the appropriate collation OID will be passed to the |
| 496 |
<function>equalimage</function> function, using the standard |
| 497 |
<function>PG_GET_COLLATION()</function> mechanism. |
| 498 |
</para> |
| 499 |
<para> |
| 500 |
As far as the operator class is concerned, returning |
| 501 |
<literal>true</literal> indicates that deduplication is safe (or |
| 502 |
safe for the collation whose OID was passed to its |
| 503 |
<function>equalimage</function> function). However, the core |
| 504 |
code will only deem deduplication safe for an index when |
| 505 |
<emphasis>every</emphasis> indexed column uses an operator class |
| 506 |
that registers an <function>equalimage</function> function, and |
| 507 |
each function actually returns <literal>true</literal> when |
| 508 |
called. |
| 509 |
</para> |
| 510 |
<para> |
| 511 |
Image equality is <emphasis>almost</emphasis> the same condition |
| 512 |
as simple bitwise equality. There is one subtle difference: When |
| 513 |
indexing a varlena data type, the on-disk representation of two |
| 514 |
image equal datums may not be bitwise equal due to inconsistent |
| 515 |
application of <acronym>TOAST</acronym> compression on input. |
| 516 |
Formally, when an operator class's |
| 517 |
<function>equalimage</function> function returns |
| 518 |
<literal>true</literal>, it is safe to assume that the |
| 519 |
<literal>datum_image_eq()</literal> C function will always agree |
| 520 |
with the operator class's <function>order</function> function |
| 521 |
(provided that the same collation OID is passed to both the |
| 522 |
<function>equalimage</function> and <function>order</function> |
| 523 |
functions). |
| 524 |
</para> |
| 525 |
<para> |
| 526 |
The core code is fundamentally unable to deduce anything about |
| 527 |
the <quote>equality implies image equality</quote> status of an |
| 528 |
operator class within a multiple-data-type family based on |
| 529 |
details from other operator classes in the same family. Also, it |
| 530 |
is not sensible for an operator family to register a cross-type |
| 531 |
<function>equalimage</function> function, and attempting to do so |
| 532 |
will result in an error. This is because <quote>equality implies |
| 533 |
image equality</quote> status does not just depend on |
| 534 |
sorting/equality semantics, which are more or less defined at the |
| 535 |
operator family level. In general, the semantics that one |
| 536 |
particular data type implements must be considered separately. |
| 537 |
</para> |
| 538 |
<para> |
| 539 |
The convention followed by the operator classes included with the |
| 540 |
core <productname>PostgreSQL</productname> distribution is to |
| 541 |
register a stock, generic <function>equalimage</function> |
| 542 |
function. Most operator classes register |
| 543 |
<function>btequalimage()</function>, which indicates that |
| 544 |
deduplication is safe unconditionally. Operator classes for |
| 545 |
collatable data types such as <type>text</type> register |
| 546 |
<function>btvarstrequalimage()</function>, which indicates that |
| 547 |
deduplication is safe with deterministic collations. Best |
| 548 |
practice for third-party extensions is to register their own |
| 549 |
custom function to retain control. |
| 550 |
</para> |
| 551 |
</listitem> |
| 552 |
</varlistentry> |
| 553 |
<varlistentry> |
| 554 |
<term><function>options</function></term> |
| 555 |
<listitem> |
| 556 |
<para> |
| 557 |
Optionally, a B-tree operator family may provide |
| 558 |
<function>options</function> (<quote>operator class specific |
| 559 |
options</quote>) support functions, registered under support |
| 560 |
function number 5. These functions define a set of user-visible |
| 561 |
parameters that control operator class behavior. |
| 562 |
</para> |
| 563 |
<para> |
| 564 |
An <function>options</function> support function must have the |
| 565 |
signature |
| 566 |
<synopsis> |
| 567 |
options(<replaceable>relopts</replaceable> <type>local_relopts *</type>) returns void |
| 568 |
</synopsis> |
| 569 |
The function is passed a pointer to a <structname>local_relopts</structname> |
| 570 |
struct, which needs to be filled with a set of operator class |
| 571 |
specific options. The options can be accessed from other support |
| 572 |
functions using the <literal>PG_HAS_OPCLASS_OPTIONS()</literal> and |
| 573 |
<literal>PG_GET_OPCLASS_OPTIONS()</literal> macros. |
| 574 |
</para> |
| 575 |
<para> |
| 576 |
Currently, no B-Tree operator class has an <function>options</function> |
| 577 |
support function. B-tree doesn't allow flexible representation of keys |
| 578 |
like GiST, SP-GiST, GIN and BRIN do. So, <function>options</function> |
| 579 |
probably doesn't have much application in the current B-tree index |
| 580 |
access method. Nevertheless, this support function was added to B-tree |
| 581 |
for uniformity, and will probably find uses during further |
| 582 |
evolution of B-tree in <productname>PostgreSQL</productname>. |
| 583 |
</para> |
| 584 |
</listitem> |
| 585 |
</varlistentry> |
| 586 |
<varlistentry> |
| 587 |
<term><function>skipsupport</function></term> |
| 588 |
<listitem> |
| 589 |
<para> |
| 590 |
Optionally, a btree operator family may provide a <firstterm>skip |
| 591 |
support</firstterm> function, registered under support function number 6. |
| 592 |
These functions give the B-tree code a way to iterate through every |
| 593 |
possible value that can be represented by an operator class's underlying |
| 594 |
input type, in key space order. This is used by the core code when it |
| 595 |
applies the skip scan optimization. The APIs involved in this are |
| 596 |
defined in <filename>src/include/utils/skipsupport.h</filename>. |
| 597 |
</para> |
| 598 |
<para> |
| 599 |
Operator classes that do not provide a skip support function are still |
| 600 |
eligible to use skip scan. The core code can still use its fallback |
| 601 |
strategy, though that might be suboptimal for some discrete types. It |
| 602 |
usually doesn't make sense (and may not even be feasible) for operator |
| 603 |
classes on continuous types to provide a skip support function. |
| 604 |
</para> |
| 605 |
<para> |
| 606 |
It is not sensible for an operator family to register a cross-type |
| 607 |
<function>skipsupport</function> function, and attempting to do so will |
| 608 |
result in an error. This is because determining the next indexable value |
| 609 |
must happen by incrementing a value copied from an index tuple. The |
| 610 |
values generated must all be of the same underlying data type (the |
| 611 |
<quote>skipped</quote> index column's opclass input type). |
| 612 |
</para> |
| 613 |
</listitem> |
| 614 |
</varlistentry> |
| 615 |
</variablelist> |
| 616 |
|
| 617 |
</sect2> |
| 618 |
|
| 619 |
<sect2 id="btree-implementation"> |
| 620 |
<title>Implementation</title> |
| 621 |
|
| 622 |
<para> |
| 623 |
This section covers B-Tree index implementation details that may be |
| 624 |
of use to advanced users. See |
| 625 |
<filename>src/backend/access/nbtree/README</filename> in the source |
| 626 |
distribution for a much more detailed, internals-focused description |
| 627 |
of the B-Tree implementation. |
| 628 |
</para> |
| 629 |
<sect3 id="btree-structure"> |
| 630 |
<title>B-Tree Structure</title> |
| 631 |
<para> |
| 632 |
<productname>PostgreSQL</productname> B-Tree indexes are |
| 633 |
multi-level tree structures, where each level of the tree can be |
| 634 |
used as a doubly-linked list of pages. A single metapage is stored |
| 635 |
in a fixed position at the start of the first segment file of the |
| 636 |
index. All other pages are either leaf pages or internal pages. |
| 637 |
Leaf pages are the pages on the lowest level of the tree. All |
| 638 |
other levels consist of internal pages. Each leaf page contains |
| 639 |
tuples that point to table rows. Each internal page contains |
| 640 |
tuples that point to the next level down in the tree. Typically, |
| 641 |
over 99% of all pages are leaf pages. Both internal pages and leaf |
| 642 |
pages use the standard page format described in <xref |
| 643 |
linkend="storage-page-layout"/>. |
| 644 |
</para> |
| 645 |
<para> |
| 646 |
New leaf pages are added to a B-Tree index when an existing leaf |
| 647 |
page cannot fit an incoming tuple. A <firstterm>page |
| 648 |
split</firstterm> operation makes room for items that originally |
| 649 |
belonged on the overflowing page by moving a portion of the items |
| 650 |
to a new page. Page splits must also insert a new |
| 651 |
<firstterm>downlink</firstterm> to the new page in the parent page, |
| 652 |
which may cause the parent to split in turn. Page splits |
| 653 |
<quote>cascade upwards</quote> in a recursive fashion. When the |
| 654 |
root page finally cannot fit a new downlink, a <firstterm>root page |
| 655 |
split</firstterm> operation takes place. This adds a new level to |
| 656 |
the tree structure by creating a new root page that is one level |
| 657 |
above the original root page. |
| 658 |
</para> |
| 659 |
</sect3> |
| 660 |
|
| 661 |
<sect3 id="btree-deletion"> |
| 662 |
<title>Bottom-up Index Deletion</title> |
| 663 |
<para> |
| 664 |
B-Tree indexes are not directly aware that under MVCC, there might |
| 665 |
be multiple extant versions of the same logical table row; to an |
| 666 |
index, each tuple is an independent object that needs its own index |
| 667 |
entry. <quote>Version churn</quote> tuples may sometimes |
| 668 |
accumulate and adversely affect query latency and throughput. This |
| 669 |
typically occurs with <command>UPDATE</command>-heavy workloads |
| 670 |
where most individual updates cannot apply the |
| 671 |
<link linkend="storage-hot"><acronym>HOT</acronym> optimization.</link> |
| 672 |
Changing the value of only |
| 673 |
one column covered by one index during an <command>UPDATE</command> |
| 674 |
<emphasis>always</emphasis> necessitates a new set of index tuples |
| 675 |
— one for <emphasis>each and every</emphasis> index on the |
| 676 |
table. Note in particular that this includes indexes that were not |
| 677 |
<quote>logically modified</quote> by the <command>UPDATE</command>. |
| 678 |
All indexes will need a successor physical index tuple that points |
| 679 |
to the latest version in the table. Each new tuple within each |
| 680 |
index will generally need to coexist with the original |
| 681 |
<quote>updated</quote> tuple for a short period of time (typically |
| 682 |
until shortly after the <command>UPDATE</command> transaction |
| 683 |
commits). |
| 684 |
</para> |
| 685 |
<para> |
| 686 |
B-Tree indexes incrementally delete version churn index tuples by |
| 687 |
performing <firstterm>bottom-up index deletion</firstterm> passes. |
| 688 |
Each deletion pass is triggered in reaction to an anticipated |
| 689 |
<quote>version churn page split</quote>. This only happens with |
| 690 |
indexes that are not logically modified by |
| 691 |
<command>UPDATE</command> statements, where concentrated build up |
| 692 |
of obsolete versions in particular pages would occur otherwise. A |
| 693 |
page split will usually be avoided, though it's possible that |
| 694 |
certain implementation-level heuristics will fail to identify and |
| 695 |
delete even one garbage index tuple (in which case a page split or |
| 696 |
deduplication pass resolves the issue of an incoming new tuple not |
| 697 |
fitting on a leaf page). The worst-case number of versions that |
| 698 |
any index scan must traverse (for any single logical row) is an |
| 699 |
important contributor to overall system responsiveness and |
| 700 |
throughput. A bottom-up index deletion pass targets suspected |
| 701 |
garbage tuples in a single leaf page based on |
| 702 |
<emphasis>qualitative</emphasis> distinctions involving logical |
| 703 |
rows and versions. This contrasts with the <quote>top-down</quote> |
| 704 |
index cleanup performed by autovacuum workers, which is triggered |
| 705 |
when certain <emphasis>quantitative</emphasis> table-level |
| 706 |
thresholds are exceeded (see <xref linkend="autovacuum"/>). |
| 707 |
</para> |
| 708 |
<note> |
| 709 |
<para> |
| 710 |
Not all deletion operations that are performed within B-Tree |
| 711 |
indexes are bottom-up deletion operations. There is a distinct |
| 712 |
category of index tuple deletion: <firstterm>simple index tuple |
| 713 |
deletion</firstterm>. This is a deferred maintenance operation |
| 714 |
that deletes index tuples that are known to be safe to delete |
| 715 |
(those whose item identifier's <literal>LP_DEAD</literal> bit is |
| 716 |
already set). Like bottom-up index deletion, simple index |
| 717 |
deletion takes place at the point that a page split is anticipated |
| 718 |
as a way of avoiding the split. |
| 719 |
</para> |
| 720 |
<para> |
| 721 |
Simple deletion is opportunistic in the sense that it can only |
| 722 |
take place when recent index scans set the |
| 723 |
<literal>LP_DEAD</literal> bits of affected items in passing. |
| 724 |
Prior to <productname>PostgreSQL</productname> 14, the only |
| 725 |
category of B-Tree deletion was simple deletion. The main |
| 726 |
differences between it and bottom-up deletion are that only the |
| 727 |
former is opportunistically driven by the activity of passing |
| 728 |
index scans, while only the latter specifically targets version |
| 729 |
churn from <command>UPDATE</command>s that do not logically modify |
| 730 |
indexed columns. |
| 731 |
</para> |
| 732 |
</note> |
| 733 |
<para> |
| 734 |
Bottom-up index deletion performs the vast majority of all garbage |
| 735 |
index tuple cleanup for particular indexes with certain workloads. |
| 736 |
This is expected with any B-Tree index that is subject to |
| 737 |
significant version churn from <command>UPDATE</command>s that |
| 738 |
rarely or never logically modify the columns that the index covers. |
| 739 |
The average and worst-case number of versions per logical row can |
| 740 |
be kept low purely through targeted incremental deletion passes. |
| 741 |
It's quite possible that the on-disk size of certain indexes will |
| 742 |
never increase by even one single page/block despite |
| 743 |
<emphasis>constant</emphasis> version churn from |
| 744 |
<command>UPDATE</command>s. Even then, an exhaustive <quote>clean |
| 745 |
sweep</quote> by a <command>VACUUM</command> operation (typically |
| 746 |
run in an autovacuum worker process) will eventually be required as |
| 747 |
a part of <emphasis>collective</emphasis> cleanup of the table and |
| 748 |
each of its indexes. |
| 749 |
</para> |
| 750 |
<para> |
| 751 |
Unlike <command>VACUUM</command>, bottom-up index deletion does not |
| 752 |
provide any strong guarantees about how old the oldest garbage |
| 753 |
index tuple may be. No index can be permitted to retain |
| 754 |
<quote>floating garbage</quote> index tuples that became dead prior |
| 755 |
to a conservative cutoff point shared by the table and all of its |
| 756 |
indexes collectively. This fundamental table-level invariant makes |
| 757 |
it safe to recycle table <acronym>TID</acronym>s. This is how it |
| 758 |
is possible for distinct logical rows to reuse the same table |
| 759 |
<acronym>TID</acronym> over time (though this can never happen with |
| 760 |
two logical rows whose lifetimes span the same |
| 761 |
<command>VACUUM</command> cycle). |
| 762 |
</para> |
| 763 |
</sect3> |
| 764 |
|
| 765 |
<sect3 id="btree-deduplication"> |
| 766 |
<title>Deduplication</title> |
| 767 |
<para> |
| 768 |
A duplicate is a leaf page tuple (a tuple that points to a table |
| 769 |
row) where <emphasis>all</emphasis> indexed key columns have values |
| 770 |
that match corresponding column values from at least one other leaf |
| 771 |
page tuple in the same index. Duplicate tuples are quite common in |
| 772 |
practice. B-Tree indexes can use a special, space-efficient |
| 773 |
representation for duplicates when an optional technique is |
| 774 |
enabled: <firstterm>deduplication</firstterm>. |
| 775 |
</para> |
| 776 |
<para> |
| 777 |
Deduplication works by periodically merging groups of duplicate |
| 778 |
tuples together, forming a single <firstterm>posting list</firstterm> tuple for each |
| 779 |
group. The column key value(s) only appear once in this |
| 780 |
representation. This is followed by a sorted array of |
| 781 |
<acronym>TID</acronym>s that point to rows in the table. This |
| 782 |
significantly reduces the storage size of indexes where each value |
| 783 |
(or each distinct combination of column values) appears several |
| 784 |
times on average. The latency of queries can be reduced |
| 785 |
significantly. Overall query throughput may increase |
| 786 |
significantly. The overhead of routine index vacuuming may also be |
| 787 |
reduced significantly. |
| 788 |
</para> |
| 789 |
<note> |
| 790 |
<para> |
| 791 |
B-Tree deduplication is just as effective with |
| 792 |
<quote>duplicates</quote> that contain a NULL value, even though |
| 793 |
NULL values are never equal to each other according to the |
| 794 |
<literal>=</literal> member of any B-Tree operator class. As far |
| 795 |
as any part of the implementation that understands the on-disk |
| 796 |
B-Tree structure is concerned, NULL is just another value from the |
| 797 |
domain of indexed values. |
| 798 |
</para> |
| 799 |
</note> |
| 800 |
<para> |
| 801 |
The deduplication process occurs lazily, when a new item is |
| 802 |
inserted that cannot fit on an existing leaf page, though only when |
| 803 |
index tuple deletion could not free sufficient space for the new |
| 804 |
item (typically deletion is briefly considered and then skipped |
| 805 |
over). Unlike GIN posting list tuples, B-Tree posting list tuples |
| 806 |
do not need to expand every time a new duplicate is inserted; they |
| 807 |
are merely an alternative physical representation of the original |
| 808 |
logical contents of the leaf page. This design prioritizes |
| 809 |
consistent performance with mixed read-write workloads. Most |
| 810 |
client applications will at least see a moderate performance |
| 811 |
benefit from using deduplication. Deduplication is enabled by |
| 812 |
default. |
| 813 |
</para> |
| 814 |
<para> |
| 815 |
<command>CREATE INDEX</command> and <command>REINDEX</command> |
| 816 |
apply deduplication to create posting list tuples, though the |
| 817 |
strategy they use is slightly different. Each group of duplicate |
| 818 |
ordinary tuples encountered in the sorted input taken from the |
| 819 |
table is merged into a posting list tuple |
| 820 |
<emphasis>before</emphasis> being added to the current pending leaf |
| 821 |
page. Individual posting list tuples are packed with as many |
| 822 |
<acronym>TID</acronym>s as possible. Leaf pages are written out in |
| 823 |
the usual way, without any separate deduplication pass. This |
| 824 |
strategy is well-suited to <command>CREATE INDEX</command> and |
| 825 |
<command>REINDEX</command> because they are once-off batch |
| 826 |
operations. |
| 827 |
</para> |
| 828 |
<para> |
| 829 |
Write-heavy workloads that don't benefit from deduplication due to |
| 830 |
having few or no duplicate values in indexes will incur a small, |
| 831 |
fixed performance penalty (unless deduplication is explicitly |
| 832 |
disabled). The <literal>deduplicate_items</literal> storage |
| 833 |
parameter can be used to disable deduplication within individual |
| 834 |
indexes. There is never any performance penalty with read-only |
| 835 |
workloads, since reading posting list tuples is at least as |
| 836 |
efficient as reading the standard tuple representation. Disabling |
| 837 |
deduplication isn't usually helpful. |
| 838 |
</para> |
| 839 |
<para> |
| 840 |
It is sometimes possible for unique indexes (as well as unique |
| 841 |
constraints) to use deduplication. This allows leaf pages to |
| 842 |
temporarily <quote>absorb</quote> extra version churn duplicates. |
| 843 |
Deduplication in unique indexes augments bottom-up index deletion, |
| 844 |
especially in cases where a long-running transaction holds a |
| 845 |
snapshot that blocks garbage collection. The goal is to buy time |
| 846 |
for the bottom-up index deletion strategy to become effective |
| 847 |
again. Delaying page splits until a single long-running |
| 848 |
transaction naturally goes away can allow a bottom-up deletion pass |
| 849 |
to succeed where an earlier deletion pass failed. |
| 850 |
</para> |
| 851 |
<tip> |
| 852 |
<para> |
| 853 |
A special heuristic is applied to determine whether a |
| 854 |
deduplication pass in a unique index should take place. It can |
| 855 |
often skip straight to splitting a leaf page, avoiding a |
| 856 |
performance penalty from wasting cycles on unhelpful deduplication |
| 857 |
passes. If you're concerned about the overhead of deduplication, |
| 858 |
consider setting <literal>deduplicate_items = off</literal> |
| 859 |
selectively. Leaving deduplication enabled in unique indexes has |
| 860 |
little downside. |
| 861 |
</para> |
| 862 |
</tip> |
| 863 |
<para> |
| 864 |
Deduplication cannot be used in all cases due to |
| 865 |
implementation-level restrictions. Deduplication safety is |
| 866 |
determined when <command>CREATE INDEX</command> or |
| 867 |
<command>REINDEX</command> is run. |
| 868 |
</para> |
| 869 |
<para> |
| 870 |
Note that deduplication is deemed unsafe and cannot be used in the |
| 871 |
following cases involving semantically significant differences |
| 872 |
among equal datums: |
| 873 |
</para> |
| 874 |
<para> |
| 875 |
<itemizedlist> |
| 876 |
<listitem> |
| 877 |
<para> |
| 878 |
<type>text</type>, <type>varchar</type>, and <type>char</type> |
| 879 |
cannot use deduplication when a |
| 880 |
<emphasis>nondeterministic</emphasis> collation is used. Case |
| 881 |
and accent differences must be preserved among equal datums. |
| 882 |
</para> |
| 883 |
</listitem> |
| 884 |
|
| 885 |
<listitem> |
| 886 |
<para> |
| 887 |
<type>numeric</type> cannot use deduplication. Numeric display |
| 888 |
scale must be preserved among equal datums. |
| 889 |
</para> |
| 890 |
</listitem> |
| 891 |
|
| 892 |
<listitem> |
| 893 |
<para> |
| 894 |
<type>jsonb</type> cannot use deduplication, since the |
| 895 |
<type>jsonb</type> B-Tree operator class uses |
| 896 |
<type>numeric</type> internally. |
| 897 |
</para> |
| 898 |
</listitem> |
| 899 |
|
| 900 |
<listitem> |
| 901 |
<para> |
| 902 |
<type>float4</type> and <type>float8</type> cannot use |
| 903 |
deduplication. These types have distinct representations for |
| 904 |
<literal>-0</literal> and <literal>0</literal>, which are |
| 905 |
nevertheless considered equal. This difference must be |
| 906 |
preserved. |
| 907 |
</para> |
| 908 |
</listitem> |
| 909 |
</itemizedlist> |
| 910 |
</para> |
| 911 |
<para> |
| 912 |
There is one further implementation-level restriction that may be |
| 913 |
lifted in a future version of |
| 914 |
<productname>PostgreSQL</productname>: |
| 915 |
</para> |
| 916 |
<para> |
| 917 |
<itemizedlist> |
| 918 |
<listitem> |
| 919 |
<para> |
| 920 |
Container types (such as composite types, arrays, or range |
| 921 |
types) cannot use deduplication. |
| 922 |
</para> |
| 923 |
</listitem> |
| 924 |
</itemizedlist> |
| 925 |
</para> |
| 926 |
<para> |
| 927 |
There is one further implementation-level restriction that applies |
| 928 |
regardless of the operator class or collation used: |
| 929 |
</para> |
| 930 |
<para> |
| 931 |
<itemizedlist> |
| 932 |
<listitem> |
| 933 |
<para> |
| 934 |
<literal>INCLUDE</literal> indexes can never use deduplication. |
| 935 |
</para> |
| 936 |
</listitem> |
| 937 |
</itemizedlist> |
| 938 |
</para> |
| 939 |
|
| 940 |
</sect3> |
| 941 |
</sect2> |
| 942 |
|
| 943 |
</sect1> |