Skip to content

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):

=> SELECT amname FROM pg_am WHERE amtype = 'i';
 amname
--------
 btree
 hash
 gist
 gin
 spgist
 brin
(6 rows)

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.1 Indexes and Extensibility: bool\_opsboolean; int4\_opsinteger; btree; text\_ops; text; text\_pattern\_ops; Indexing; engine; gist\_int4\_ops; gistgist\_text\_ops; point\_opspoint; access methodsoperator classesdata types
Figure 19.1 19.1 Indexes and Extensibility

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:

=> SELECT amname, opcname, opcintype::regtype
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid;
 amname |           opcname            |          opcintype
--------+------------------------------+-----------------------------
 btree  | array_ops                    | anyarray
 hash   | array_ops                    | anyarray
 btree  | bit_ops                      | bit
 btree  | bool_ops                     | boolean
 ...
 brin   | pg_lsn_minmax_multi_ops      | pg_lsn
 brin   | pg_lsn_bloom_ops             | pg_lsn
 brin   | box_inclusion_ops            | box
(177 rows)

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:

=> SELECT opcname, opcdefault
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
WHERE amname = 'btree'
  AND opcintype = 'text'::regtype;
       opcname       | opcdefault
---------------------+------------
 text_ops            | t
 varchar_ops         | f
 text_pattern_ops    | f
 varchar_pattern_ops | f
(4 rows)

A typical command for index creation looks as follows:

CREATE INDEX ON aircrafts(model, range);

But it is just a shorthand notation that expands to the following syntax:

CREATE INDEX ON aircrafts
USING btree -- the default access method
(
  model text_ops, -- the default operator class for text
  range int4_ops  -- the default operator class for integer
);

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:

=> SELECT opcname, amopstrategy, amopopr::regoperator
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_opclass opc ON opcfamily = opf.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
WHERE amname = 'btree'
  AND opcname IN ('text_ops', 'text_pattern_ops')
  AND amoplefttype = 'text'::regtype
  AND amoprighttype = 'text'::regtype
ORDER BY opcname, amopstrategy;
     opcname      | amopstrategy |     amopopr
------------------+--------------+-----------------
 text_ops         |            1 | <(text,text)
 text_ops         |            2 | <=(text,text)
 text_ops         |            3 | =(text,text)
 text_ops         |            4 | >=(text,text)
 text_ops         |            5 | >(text,text)
 text_pattern_ops |            1 | ~<~(text,text)
 text_pattern_ops |            2 | ~<=~(text,text)
 text_pattern_ops |            3 | =(text,text)
 text_pattern_ops |            4 | ~>=~(text,text)
 text_pattern_ops |            5 | ~>~(text,text)
(10 rows)

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:

=> SHOW lc_collate;
 lc_collate
-------------
 en_US.UTF-8
(1 row)
=> CREATE INDEX ON tickets(passenger_name);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
                  QUERY PLAN
----------------------------------------------
 Seq Scan on tickets
   Filter: (passenger_name ~~ 'ELENA%'::text)
(2 rows)

An index with the text_pattern_ops operator class behaves differently:

=> CREATE INDEX tickets_passenger_name_pattern_idx
ON tickets(passenger_name text_pattern_ops);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
                          QUERY PLAN
--------------------------------------------------------------
 Bitmap Heap Scan on tickets
   Filter: (passenger_name ~~ 'ELENA%'::text)
   -> Bitmap Index Scan on tickets_passenger_name_pattern_idx
       Index Cond: ((passenger_name ~>=~ 'ELENA'::text) AND
       (passenger_name ~<~ 'ELENB'::text))
(5 rows)

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:

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE 'ELENA BELOVA' = passenger_name;
                       QUERY PLAN
--------------------------------------------------------
 Index Scan using tickets_passenger_name_idx on tickets
   Index Cond: (passenger_name = 'ELENA BELOVA'::text)
(2 rows)

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:

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tickets
   Filter: (initcap(passenger_name) = 'Elena Belova'::text)
(2 rows)

Here you can use an expression index,8 which has an arbitrary expression specified in its declaration instead of a column:

=> CREATE INDEX ON tickets( (initcap(passenger_name)) );
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
                             QUERY PLAN
--------------------------------------------------------------------
 Bitmap Heap Scan on tickets
   Recheck Cond: (initcap(passenger_name) = 'Elena Belova'::text)
   -> Bitmap Index Scan on tickets_initcap_idx
       Index Cond: (initcap(passenger_name) = 'Elena Belova'::text)
(4 rows)

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:

=> SELECT amprocnum, amproc::regproc
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_opclass opc ON opcfamily = opf.oid
  JOIN pg_amproc amproc ON amprocfamily = opcfamily
WHERE amname = 'btree'
  AND opcname = 'text_ops'
  AND amproclefttype = 'text'::regtype
  AND amprocrighttype = 'text'::regtype
ORDER BY amprocnum;
 amprocnum |       amproc
-----------+--------------------
         1 | bttextcmp
         2 | bttextsortsupport
         4 | btvarstrequalimage
(3 rows)

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:

=> SELECT opcname, opcintype::regtype
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_opclass opc ON opcfamily = opf.oid
WHERE amname = 'btree'
  AND opfname = 'integer_ops';
 opcname  | opcintype
----------+-----------
 int2_ops | smallint
 int4_ops | integer
 int8_ops | bigint
(3 rows)

The datetime_ops family comprises operator classes that process dates:

=> SELECT opcname, opcintype::regtype
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_opclass opc ON opcfamily = opf.oid
WHERE amname = 'btree'
  AND opfname = 'datetime_ops';
     opcname     |          opcintype
-----------------+-----------------------------
 date_ops        | date
 timestamptz_ops | timestamp with time zone
 timestamp_ops   | timestamp without time zone
(3 rows)

While each operator class supports a single data type, a family can comprise operator classes for different data types:

=> SELECT opcname, amopopr::regoperator
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_opclass opc ON opcfamily = opf.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
WHERE amname = 'btree'
  AND opfname = 'integer_ops'
  AND amoplefttype = 'integer'::regtype
  AND amopstrategy = 1
ORDER BY opcname;
 opcname  |       amopopr
----------+---------------------
 int2_ops | <(integer,bigint)
 int2_ops | <(integer,smallint)
 int2_ops | <(integer,integer)
 int4_ops | <(integer,bigint)
 int4_ops | <(integer,smallint)
 int4_ops | <(integer,integer)
 int8_ops | <(integer,bigint)
 int8_ops | <(integer,smallint)
 int8_ops | <(integer,integer)
(9 rows)

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)

=> SELECT amname, amhandler
FROM pg_am
WHERE amtype = 'i';
 amname |  amhandler
--------+-------------
 btree  | bthandler
 hash   | hashhandler
 gist   | gisthandler
 gin    | ginhandler
 spgist | spghandler
 brin   | brinhandler
(6 rows)

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)

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'btree';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 btree  | can_order     | t
 btree  | can_unique    | t
 btree  | can_multi_col | t
 btree  | can_exclude   | t
 btree  | can_include   | t
(5 rows)

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:

=> EXPLAIN (costs off)
SELECT * FROM seats ORDER BY seat_no;
       QUERY PLAN
------------------------
 Sort
   Sort Key: seat_no
   -> Seq Scan on seats
(3 rows)

But if there is an index that supports this property, the data can be returned in the desired order at once:

=> EXPLAIN (costs off)
SELECT * FROM seats ORDER BY aircraft_code;
              QUERY PLAN
--------------------------------------
 Index Scan using seats_pkey on seats
(1 row)

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.

=> INSERT INTO bookings(book_ref, book_date, total_amount)
VALUES ('000004', now(), 100.00);
ERROR:  duplicate key value violates unique constraint
"bookings_pkey"
DETAIL:  Key (book_ref)=(000004) already exists.

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:

=> \d ticket_flights_pkey
     Index "bookings.ticket_flights_pkey"
  Column   |     Type      | Key? | Definition
-----------+---------------+------+------------
 ticket_no | character(13) | yes  | ticket_no
 flight_id | integer       | yes  | flight_id
primary key, btree, for table "bookings.ticket_flights"

A flight search by a ticket number and a flight ID is performed using an index:

=> EXPLAIN (costs off)
SELECT * FROM ticket_flights
WHERE ticket_no = '0005432001355'
  AND flight_id = 51618;
                        QUERY PLAN
----------------------------------------------------------
 Index Scan using ticket_flights_pkey on ticket_flights
   Index Cond: ((ticket_no = '0005432001355'::bpchar) AND
   (flight_id = 51618))
(3 rows)

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:

=> EXPLAIN (costs off)
SELECT *
FROM ticket_flights
WHERE ticket_no = '0005432001355';
                       QUERY PLAN
--------------------------------------------------------
 Index Scan using ticket_flights_pkey on ticket_flights
   Index Cond: (ticket_no = '0005432001355'::bpchar)
(2 rows)

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:

=> CREATE UNIQUE INDEX ON flights(flight_id) INCLUDE (status);
=> EXPLAIN (costs off)
SELECT status FROM flights
WHERE flight_id = 51618;
                          QUERY PLAN
---------------------------------------------------------------
 Index Only Scan using flights_flight_id_status_idx on flights
   Index Cond: (flight_id = 51618)
(2 rows)

Index-Level Properties

Here are the properties related to an index (shown for an existing one):

=>  SELECT p.name, pg_index_has_property('seats_pkey', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t
(4 rows)

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:

=> SELECT p.name,
  pg_index_column_has_property('seats_pkey', 1, p.name)
FROM unnest(array[
  'asc', 'desc', 'nulls_first', 'nulls_last', 'orderable',
  'distance_orderable', 'returnable', 'search_array', 'search_nulls'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 asc                | t
 desc               | f
 nulls_first        | f
 nulls_last         | t
 orderable          | t
 distance_orderable | f
 returnable         | t
 search_array       | t
 search_nulls       | t
(9 rows)

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:

=> CREATE INDEX ON airports_data USING gist(coordinates);
=> EXPLAIN (costs off)
SELECT * FROM airports
ORDER BY coordinates <-> point (43.578,57.593)
LIMIT 3;
                           QUERY PLAN
-----------------------------------------------------------------
 Limit
   -> Index Scan using airports_data_coordinates_idx on airpo...
       Order By: (coordinates <-> '(43.578,57.593)'::point)
(3 rows)

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:

=> EXPLAIN (costs off)
SELECT * FROM bookings
WHERE book_ref IN ('C7C821', 'A5D060', 'DDE1BB');
                 QUERY PLAN
--------------------------------------------
 Index Scan using bookings_pkey on bookings
   Index Cond: (book_ref = ANY
   ('{C7C821,A5D060,DDE1BB}'::bpchar[]))
(3 rows)

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:

=> CREATE INDEX ON flights(actual_arrival)
WHERE actual_arrival IS NOT NULL;
=> EXPLAIN (costs off)
SELECT * FROM flights
WHERE actual_arrival = '2017-06-13 10:33:00+03';
                           QUERY PLAN
-----------------------------------------------------------------
 Index Scan using flights_actual_arrival_idx on flights
   Index Cond: (actual_arrival = '2017-06-13 10:33:00+03'::ti...
(2 rows)

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.