1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Chapter48.Index Access Method Interface Definition</title>
<link rel="stylesheet" href="stylesheet.css" type="text/css">
<link rev="made" href="pgsql-docs@postgresql.org">
<meta name="generator" content="DocBook XSL Stylesheets V1.70.0">
<link rel="start" href="index.html" title="PostgreSQL 8.1.4 Documentation">
<link rel="up" href="internals.html" title="PartVII.Internals">
<link rel="prev" href="geqo-biblio.html" title="47.4.Further Reading">
<link rel="next" href="index-functions.html" title="48.2.Index Access Method Functions">
<link rel="copyright" href="ln-legalnotice.html" title="Legal Notice">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="chapter" lang="en" id="indexam">
<div class="titlepage"><div><div><h2 class="title">
<a name="indexam"></a>Chapter48.Index Access Method Interface Definition</h2></div></div></div>
<div class="toc">
<p><b>Table of Contents</b></p>
<dl>
<dt><span class="sect1"><a href="indexam.html#index-catalog">48.1. Catalog Entries for Indexes</a></span></dt>
<dt><span class="sect1"><a href="index-functions.html">48.2. Index Access Method Functions</a></span></dt>
<dt><span class="sect1"><a href="index-scanning.html">48.3. Index Scanning</a></span></dt>
<dt><span class="sect1"><a href="index-locking.html">48.4. Index Locking Considerations</a></span></dt>
<dt><span class="sect1"><a href="index-unique-checks.html">48.5. Index Uniqueness Checks</a></span></dt>
<dt><span class="sect1"><a href="index-cost-estimation.html">48.6. Index Cost Estimation Functions</a></span></dt>
</dl>
</div>
<p> This chapter defines the interface between the core
<span class="productname">PostgreSQL</span> system and <em class="firstterm">index access
methods</em>, which manage individual index types. The core system
knows nothing about indexes beyond what is specified here, so it is
possible to develop entirely new index types by writing add-on code.
</p>
<p> All indexes in <span class="productname">PostgreSQL</span> are what are known
technically as <em class="firstterm">secondary indexes</em>; that is, the index is
physically separate from the table file that it describes. Each index
is stored as its own physical <em class="firstterm">relation</em> and so is described
by an entry in the <code class="structname">pg_class</code> catalog. The contents of an
index are entirely under the control of its index access method. In
practice, all index access methods divide indexes into standard-size
pages so that they can use the regular storage manager and buffer manager
to access the index contents. (All the existing index access methods
furthermore use the standard page layout described in <a href="storage-page-layout.html" title="50.3.Database Page Layout">Section50.3, “Database Page Layout”</a>, and they all use the same format for index
tuple headers; but these decisions are not forced on an access method.)
</p>
<p> An index is effectively a mapping from some data key values to
<em class="firstterm">tuple identifiers</em>, or <acronym class="acronym">TIDs</acronym>, of row versions
(tuples) in the index's parent table. A TID consists of a
block number and an item number within that block (see <a href="storage-page-layout.html" title="50.3.Database Page Layout">Section50.3, “Database Page Layout”</a>). This is sufficient
information to fetch a particular row version from the table.
Indexes are not directly aware that under MVCC, there may be multiple
extant versions of the same logical row; to an index, each tuple is
an independent object that needs its own index entry. Thus, an
update of a row always creates all-new index entries for the row, even if
the key values did not change. Index entries for dead tuples are
reclaimed (by vacuuming) when the dead tuples themselves are reclaimed.
</p>
<div class="sect1" lang="en">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="index-catalog"></a>48.1.Catalog Entries for Indexes</h2></div></div></div>
<p> Each index access method is described by a row in the
<code class="structname">pg_am</code> system catalog (see
<a href="catalog-pg-am.html" title="42.3.pg_am">Section42.3, “<code class="structname">pg_am</code>”</a>). The principal contents of a
<code class="structname">pg_am</code> row are references to
<a href="catalog-pg-proc.html" title="42.27.pg_proc"><code class="structname">pg_proc</code></a>
entries that identify the index access
functions supplied by the access method. The APIs for these functions
are defined later in this chapter. In addition, the
<code class="structname">pg_am</code> row specifies a few fixed properties of
the access method, such as whether it can support multicolumn indexes.
There is not currently any special support
for creating or deleting <code class="structname">pg_am</code> entries;
anyone able to write a new access method is expected to be competent
to insert an appropriate row for themselves.
</p>
<p> To be useful, an index access method must also have one or more
<em class="firstterm">operator classes</em> defined in
<a href="catalog-pg-opclass.html" title="42.24.pg_opclass"><code class="structname">pg_opclass</code></a>,
<a href="catalog-pg-amop.html" title="42.4.pg_amop"><code class="structname">pg_amop</code></a>, and
<a href="catalog-pg-amproc.html" title="42.5.pg_amproc"><code class="structname">pg_amproc</code></a>.
These entries allow the planner
to determine what kinds of query qualifications can be used with
indexes of this access method. Operator classes are described
in <a href="xindex.html" title="32.14.Interfacing Extensions To Indexes">Section32.14, “Interfacing Extensions To Indexes”</a>, which is prerequisite material for reading
this chapter.
</p>
<p> An individual index is defined by a
<a href="catalog-pg-class.html" title="42.12.pg_class"><code class="structname">pg_class</code></a>
entry that describes it as a physical relation, plus a
<a href="catalog-pg-index.html" title="42.18.pg_index"><code class="structname">pg_index</code></a>
entry that shows the logical content of the index [mdash ] that is, the set
of index columns it has and the semantics of those columns, as captured by
the associated operator classes. The index columns (key values) can be
either simple columns of the underlying table or expressions over the table
rows. The index access method normally has no interest in where the index
key values come from (it is always handed precomputed key values) but it
will be very interested in the operator class information in
<code class="structname">pg_index</code>. Both of these catalog entries can be
accessed as part of the <code class="structname">Relation</code> data structure that is
passed to all operations on the index.
</p>
<p> Some of the flag columns of <code class="structname">pg_am</code> have nonobvious
implications. The requirements of <code class="structfield">amcanunique</code>
are discussed in <a href="index-unique-checks.html" title="48.5.Index Uniqueness Checks">Section48.5, “Index Uniqueness Checks”</a>, and those of
<code class="structfield">amconcurrent</code> in <a href="index-locking.html" title="48.4.Index Locking Considerations">Section48.4, “Index Locking Considerations”</a>.
The <code class="structfield">amcanmulticol</code> flag asserts that the
access method supports multicolumn indexes, while
<code class="structfield">amoptionalkey</code> asserts that it allows scans
where no indexable restriction clause is given for the first index column.
When <code class="structfield">amcanmulticol</code> is false,
<code class="structfield">amoptionalkey</code> essentially says whether the
access method allows full-index scans without any restriction clause.
Access methods that support multiple index columns <span class="emphasis"><em>must</em></span>
support scans that omit restrictions on any or all of the columns after
the first; however they are permitted to require some restriction to
appear for the first index column, and this is signaled by setting
<code class="structfield">amoptionalkey</code> false.
<code class="structfield">amindexnulls</code> asserts that index entries are
created for NULL key values. Since most indexable operators are
strict and hence cannot return TRUE for NULL inputs,
it is at first sight attractive to not store index entries for null values:
they could never be returned by an index scan anyway. However, this
argument fails when an index scan has no restriction clause for a given
index column. In practice this means that
indexes that have <code class="structfield">amoptionalkey</code> true must
index nulls, since the planner might decide to use such an index
with no scan keys at all. A related restriction is that an index
access method that supports multiple index columns <span class="emphasis"><em>must</em></span>
support indexing null values in columns after the first, because the planner
will assume the index can be used for queries that do not restrict
these columns. For example, consider an index on (a,b) and a query with
<code class="literal">WHERE a = 4</code>. The system will assume the index can be
used to scan for rows with <code class="literal">a = 4</code>, which is wrong if the
index omits rows where <code class="literal">b</code> is null.
It is, however, OK to omit rows where the first indexed column is null.
(GiST currently does so.) Thus,
<code class="structfield">amindexnulls</code> should be set true only if the
index access method indexes all rows, including arbitrary combinations of
null values.
</p>
</div>
</div></body>
</html>
|
