19 Index Access Methods
PostgreSQL 14 · Translated from Russian by Liudmila Mantrova · Chinese translation by Xiong Cancan
19.1 Indexes and Extensibility
Indexes are database objects that mainly serve the purpose of accelerating data access. These are auxiliary structures: any index can be deleted and recreated based on heap data. In addition to data access speedup, indexes are also used to enforce some integrity constraints.
The PostgreSQL core provides six built-in index access methods (index types):
PostgreSQL’s extensibility implies that new access methods can be added without modifying the core. One such extension (the bloom method) is included into the standard set of modules. (v. 9.6)
Despite all the differences between various index types, all of them eventually match a key (such as a value of an indexed column) against heap tuples that contain this key. Tuples are referred to by six-byte tuple IDs, or TIDs. Knowing the key or some information about the key, it is possible to quickly read the tuples that are likely to contain the required data without scanning the whole table. (p. 342)
To ensure that a new access method can be added as an extension, PostgreSQL implements a common indexing engine. Its main objective is to retrieve and process TIDs returned by a particular access method:
read data from the corresponding heap tuples
check tuple visibility against a particular snapshot (p. 80)
recheck conditions if their evaluation by the method is indecisive
The indexing engine also participates in execution of plans built at the optimization stage. When assessing various execution paths, the optimizer needs to know the properties of all potentially applicable access methods: can the method return the data in the required order, or do we need a separate sorting stage? is it possible to return several first values right away, or do we have to wait for the whole result set to be fetched? and so on.
It is not only the optimizer that needs to know specifics of the access method. Index creation poses more questions to answer: does the access method support multicolumn indexes? can this index guarantee uniqueness?
The indexing engine allows using a variety of access methods; in order to be supported, an access method must implement a particular interface to declare its features and properties.
Access methods are used to address the following tasks:
implement algorithms for building indexes, as well as inserting and deleting index entries
distribute index entries between pages (to be further handled by the buffer cache manager) (p. 147)
implement the algorithm of vacuuming (p. 102)
acquire locks to ensure correct concurrent operation (p. 240)
generate WAL entries (p. 164)
search indexed data by the key
estimate index scan costs
Extensibility also manifests itself as the ability to add new data types, which the access method knows nothing of in advance. Therefore, access methods have to define their own interfaces for plugging in arbitrary data types.
To enable usage of a new data type with a particular access method, you have to implement the corresponding interface—that is, provide operators that can be used with an index, and possibly some auxiliary support functions. Such a set of operators and functions is called an operator class.
The indexing logic is partially implemented by the access method itself, but some of it is outsourced to operator classes. This distribution is rather arbitrary: while B-trees have all the logic wired into the access method, some other methods may provide only the main framework, leaving all the implementation details at the discretion of particular operator classes. One and the same data type is often supported by several operator classes, and the user can select the one with the most suitable behavior.
Here is a small fraction of the overall picture:
19.2 Operator Classes and Families
Operator Classes
An access method interface1 is implemented by an operator class,2 which is a set of operators and support functions applied by the access method to a particular data type.
Classes of operators are stored in the pg_opclass table in the system catalog. The following query returns the complete data for the above illustration:
In most cases, we do not have to know anything about operator classes. We simply create an index that uses some operator class by default.
For example, here are B-tree operator classes that support the text type. One of the classes is always marked as the default one:
A typical command for index creation looks as follows:
But it is just a shorthand notation that expands to the following syntax:
If you would like to use an index of a different type or achieve some custom behavior, you have to specify the desired access method or operator class explicitly.
Each operator class defined for a particular access method and data type must contain a set of operators that take parameters of this type and implement the semantics of this access method.
For example, the btree access method defines five mandatory comparison operators. Any btree operator class must contain all the five:
The semantics of an operator implied by the access method is reflected by the strategy number shown as amopstrategy.3 For example, strategy 1 for btree means less than, 2 denotes less than or equal to, and so on. Operators themselves can have arbitrary names.
The example above shows two kinds of operators. The difference between regular operators and those with a tilde is that the latter do not take collation4 into account and perform bitwise comparison of strings. Nevertheless, both flavors implement the same logical operations of comparison.
The text_pattern_ops operator class is designed to address the limitation in support of the ~~ operator (which corresponds to the LIKE operator). In a database using any collation other than C, this operator cannot use a regular index on a text field:
An index with the text_pattern_ops operator class behaves differently:
Note how the filter expression has changed in the Index Cond condition. The search now uses only the template’s prefix before %, while false-positive hits are filtered out during a recheck based on the Filter condition. The operator class for the btree access method provides no operator for comparing templates, and the only way to apply a B-tree here is to rewrite this condition using comparison operators. The operators of the text_pattern_ops class do not take collation into account, which gives us an opportunity to use an equivalent condition instead.5
An index can be used to speed up access by a filter condition if the following two prerequisites are met:
1 the condition is written as “indexed-column operator expression” (if the operator has a commuting counterpart specified,6 the condition can also have the form of “expression operator indexed-column”)7
2 and the operator belongs to the operator class specified for the indexed-column in the index declaration.
For example, the following query can use an index:
Note the position of arguments in the Index Cond condition: at the execution stage, the indexed field must be on the left. When the arguments are permuted, the operator is replaced by a commuting one; in this particular case, it is the same operator because the equality relation is commutative.
In the next query, it is technically impossible to use a regular index because the column name in the condition is replaced by a function call:
Here you can use an expression index,8 which has an arbitrary expression specified in its declaration instead of a column:
An index expression can depend only on heap tuple values and must be affected by neither other data stored in the database nor configuration parameters (such as locale settings).
In other words, if the expression contains any function calls, these functions must be IMMUTABLE,9 and they must observe this volatility category. Otherwise, an index scan and a heap scan may return different results for the same query.
Apart from regular operators, an operator class can provide support functions10 required by the access method. For example, the btree access method defines five support functions;11 the first one (which compares two values) is mandatory, while all the rest can be absent:
Operator Families
Each operator class always belongs to some operator family12 (listed in the system catalog in the pg_opfamily table). A family can comprise several classes that handle similar data types in the same way.
For example, the integer_ops family includes several classes for integral data types that have the same semantics but differ in size:
The datetime_ops family comprises operator classes that process dates:
While each operator class supports a single data type, a family can comprise operator classes for different data types:
Thanks to such grouping of various operators into a single family, the planner can do without type casting when an index is used for conditions involving values of different types.
19.3 Indexing Engine Interface
Just like for table access methods, the amhandler column of the pg_am table contains the name of the function that implements the interface:13 (v. 9.6)
This function fills placeholders in the interface structure14 with actual values. Some of them are functions responsible for separate tasks related to index access (for example, they can perform an index scan and return heap tuple IDs), while others are index method properties that the indexing engine must be aware of.
All properties are grouped into three categories:15
access method properties
properties of a particular index
column-level properties of an index
The distinction between access method and index-level properties is provided with a view to the future: right now, all the indexes based on a particular access method always have the same properties at these two levels.
Access Method Properties
The following five properties are defined at the access method level (shown for the B-tree method here): (v. 11)
CAN ORDER The ability to receive sorted data.16 This property is currently supported only by B-trees.
To get the results in the required order, you can always scan the table and then sort the fetched data:
But if there is an index that supports this property, the data can be returned in the desired order at once:
CAN UNIQUE Support for unique and primary key constraints.17 This property applies only to B-trees.
Each time a unique or primary key constraint is declared, PostgreSQL automatically creates a unique index to support this constraint.
That said, if you simply create a unique index without explicitly declaring an integrity constraint, the effect will seem to be exactly the same: the indexed column will not allow duplicates. So what is the difference?
An integrity constraint defines the property that must never be violated, while an index is just a mechanism to guarantee it. In theory, a constraint could be imposed using other means.
For example, PostgreSQL does not support global indexes for partitioned tables, but nevertheless, you can create a unique constraint on such tables (if it includes the partition key). In this case, the global uniqueness is ensured by local unique indexes of each partition, as different partitions cannot have the same partition keys.
CAN MULTI COL The ability to build a multicolumn index.18
A multicolumn index can speed up search by several conditions imposed on different table columns. For example, the ticket_flights table has a composite primary key, so the corresponding index is built on more than one column:
A flight search by a ticket number and a flight ID is performed using an index:
As a rule, a multicolumn index can speed up search even if filter conditions involve only some of its columns. In the case of a B-tree, the search will be efficient if the filter condition spans a range of columns that appear first in the index declaration:
In all other cases (for example, if the condition includes only flights_id), search will be virtually limited to the initial columns (if the query includes the corresponding conditions), while other conditions will only be used to filter out the returned results. Indexes of other types may behave differently though.
CAN EXCLUDE Support for EXCLUDE constraints.19
An EXCLUDE constraint guarantees that a condition defined by an operator will not be satisfied for any pair of table rows. To impose this constraint, PostgreSQL automatically creates an index; there must be an operator class that contains the operator used in the constraint’s condition.
It is the intersection operator && that usually serves this purpose. For instance, you can use it to explicitly declare that a conference room cannot be booked twice for the same time, or that buildings on a map cannot overlap.
With the equality operator, the exclusion constraint takes on the meaning of uniqueness: the table is forbidden to have two rows with the same key values. Nevertheless, it is not the same as a UNIQUE constraint: in particular, the exclusion constraint key cannot be referred to from foreign keys, and neither can it be used in the ON CONFLICT clause.
CAN INCLUDE The ability to add non-key columns to an index, which make this index covering. (v. 11) (p. 339)
Using this property, you can extend a unique index with additional columns. Such an index still guarantees that all the key column values are unique, while data retrieval from the included columns incurs no heap access:
Index-Level Properties
Here are the properties related to an index (shown for an existing one):
CLUSTERABLE The ability to physically move heap tuples in accordance with the order in which their IDs are returned by an index scan. (p. 284)
This property shows whether the CLUSTER command is supported.
INDEX SCAN Index scan support. (p. 330)
This property implies that the access method can return TIDs one by one. Strange as it may seem, some indexes do not provide this functionality.
BITMAP SCAN Bitmap scan support. (p. 340)
This property defines whether the access method can build and return a bitmap of all TIDs at once.
BACKWARD SCAN The ability to return results in reverse order as compared to the one specified at index creation.
This property makes sense only if the access method supports index scans.
Column-Level Properties
And finally, let’s take a look at the column properties:
ASC, DESC, NULLS FIRST, NULLS LAST Ordering column values.
These properties define whether column values should be stored in ascending or descending order, and whether NULL values should appear before or after regular values. All these properties are applicable only to B-trees. (p. 274)
ORDERABLE The ability to sort column values using the ORDER BY clause.
This property is applicable only to B-trees.
DISTANCE ORDERABLE Support for ordering operators.20 (p. 327)
Unlike regular indexing operators that return logical values, ordering operators return a real number that denotes the “distance” from one argument to another. Indexes support such operators specified in the ORDER BY clause of a query.
For example, the ordering operator <-> can find the airports located at the shortest distance to the specified point:
RETURNABLE The ability to return data without accessing the table (index-only scan support). (p. 337)
This property defines whether an index structure allows retrieving indexed values. It is not always possible: for example, some indexes may store hash codes rather than actual values. In this case, the CAN INCLUDE property will not be available either.
SEARCH ARRAY Support for searching several elements in an array.
An explicit use of arrays is not the only case when it might be necessary. For example, the planner transforms the IN (list) expression into an array scan:
If the index method does not support such operators, the executor may have to perform several iterations to find particular values (which can make the index scan less efficient).
SEARCH NULLS Search for IS NULL and IS NOT NULL conditions.
Should we index NULL values? On the one hand, it allows us to perform index scans for conditions like IS [NOT] NULL, as well as use the index as a covering one if no filter conditions are provided (in this case, the index has to return the data of all the heap tuples, including those that contain NULL values). But on the other hand, skipping NULL values can reduce the index size.
The decision remains at the discretion of access method developers, but more often than not NULL values do get indexed.
If you do not need NULL values in an index, you can exclude them by building a partial index21 that covers only those rows that are required. For example:
A partial index is smaller than the full one, and it gets updated only if the modified row is indexed, which can sometimes lead to tangible performance gains. Obviously, apart from NULL checks, the WHERE clause can provide any condition (that can be used with immutable functions).
The ability to build partial indexes is provided by the indexing engine, so it does not depend on the access method.
Naturally, the interface includes only those properties of index methods that must be known in advance for a correct decision to be taken. For example, it does not list any properties that enable such features as support for predicate locks or non-blocking index creation (CONCURRENTLY). Such properties are defined in the code of the functions that implement the interface.
postgresql.org/docs/14/collation.html postgresql.org/docs/14/indexes-collations.html ↩︎
postgresql.org/docs/14/xoper-optimization.html#id-1.8.3.18.6 ↩︎
backend/optimizer/path/indxpath.c, match_clause_to_indexcol function ↩︎
backend/utils/adt/amutils.c, indexam_property function ↩︎
postgresql.org/docs/14/ddl-constraints.html#DDL-CONSTRAINTS-EXCLUSION ↩︎