Debian Codegraph @

doc/src/sgml/indexam.sgml

raw
1 <!-- doc/src/sgml/indexam.sgml -->
2
3 <chapter id="indexam">
4 <title>Index Access Method Interface Definition</title>
5
6 <indexterm>
7 <primary>Index Access Method</primary>
8 </indexterm>
9 <indexterm>
10 <primary>indexam</primary>
11 <secondary>Index Access Method</secondary>
12 </indexterm>
13
14 <para>
15 This chapter defines the interface between the core
16 <productname>PostgreSQL</productname> system and <firstterm>index access
17 methods</firstterm>, which manage individual index types. The core system
18 knows nothing about indexes beyond what is specified here, so it is
19 possible to develop entirely new index types by writing add-on code.
20 </para>
21
22 <para>
23 All indexes in <productname>PostgreSQL</productname> are what are known
24 technically as <firstterm>secondary indexes</firstterm>; that is, the index is
25 physically separate from the table file that it describes. Each index
26 is stored as its own physical <firstterm>relation</firstterm> and so is described
27 by an entry in the <structname>pg_class</structname> catalog. The contents of an
28 index are entirely under the control of its index access method. In
29 practice, all index access methods divide indexes into standard-size
30 pages so that they can use the regular storage manager and buffer manager
31 to access the index contents. (All the existing index access methods
32 furthermore use the standard page layout described in <xref
33 linkend="storage-page-layout"/>, and most use the same format for index
34 tuple headers; but these decisions are not forced on an access method.)
35 </para>
36
37 <para>
38 An index is effectively a mapping from some data key values to
39 <firstterm>tuple identifiers</firstterm>, or <acronym>TIDs</acronym>, of row versions
40 (tuples) in the index's parent table. A TID consists of a
41 block number and an item number within that block (see <xref
42 linkend="storage-page-layout"/>). This is sufficient
43 information to fetch a particular row version from the table.
44 Indexes are not directly aware that under MVCC, there might be multiple
45 extant versions of the same logical row; to an index, each tuple is
46 an independent object that needs its own index entry. Thus, an
47 update of a row always creates all-new index entries for the row, even if
48 the key values did not change. (<link linkend="storage-hot">HOT
49 tuples</link> are an exception to this
50 statement; but indexes do not deal with those, either.) Index entries for
51 dead tuples are reclaimed (by vacuuming) when the dead tuples themselves
52 are reclaimed.
53 </para>
54
55 <sect1 id="index-api">
56 <title>Basic API Structure for Indexes</title>
57
58 <para>
59 Each index access method is described by a row in the
60 <link linkend="catalog-pg-am"><structname>pg_am</structname></link>
61 system catalog. The <structname>pg_am</structname> entry
62 specifies a name and a <firstterm>handler function</firstterm> for the index
63 access method. These entries can be created and deleted using the
64 <xref linkend="sql-create-access-method"/> and
65 <xref linkend="sql-drop-access-method"/> SQL commands.
66 </para>
67
68 <para>
69 An index access method handler function must be declared to accept a
70 single argument of type <type>internal</type> and to return the
71 pseudo-type <type>index_am_handler</type>. The argument is a dummy value that
72 simply serves to prevent handler functions from being called directly from
73 SQL commands. The result of the function must be a palloc'd struct of
74 type <structname>IndexAmRoutine</structname>, which contains everything
75 that the core code needs to know to make use of the index access method.
76 The <structname>IndexAmRoutine</structname> struct, also called the access
77 method's <firstterm>API struct</firstterm>, includes fields specifying assorted
78 fixed properties of the access method, such as whether it can support
79 multicolumn indexes. More importantly, it contains pointers to support
80 functions for the access method, which do all of the real work to access
81 indexes. These support functions are plain C functions and are not
82 visible or callable at the SQL level. The support functions are described
83 in <xref linkend="index-functions"/>.
84 </para>
85
86 <para>
87 The structure <structname>IndexAmRoutine</structname> is defined thus:
88 <programlisting>
89 typedef struct IndexAmRoutine
90 {
91 NodeTag type;
92
93 /*
94 * Total number of strategies (operators) by which we can traverse/search
95 * this AM. Zero if AM does not have a fixed set of strategy assignments.
96 */
97 uint16 amstrategies;
98 /* total number of support functions that this AM uses */
99 uint16 amsupport;
100 /* opclass options support function number or 0 */
101 uint16 amoptsprocnum;
102 /* does AM support ORDER BY indexed column's value? */
103 bool amcanorder;
104 /* does AM support ORDER BY result of an operator on indexed column? */
105 bool amcanorderbyop;
106 /* does AM support hashing using API consistent with the hash AM? */
107 bool amcanhash;
108 /* do operators within an opfamily have consistent equality semantics? */
109 bool amconsistentequality;
110 /* do operators within an opfamily have consistent ordering semantics? */
111 bool amconsistentordering;
112 /* does AM support backward scanning? */
113 bool amcanbackward;
114 /* does AM support UNIQUE indexes? */
115 bool amcanunique;
116 /* does AM support multi-column indexes? */
117 bool amcanmulticol;
118 /* does AM require scans to have a constraint on the first index column? */
119 bool amoptionalkey;
120 /* does AM handle ScalarArrayOpExpr quals? */
121 bool amsearcharray;
122 /* does AM handle IS NULL/IS NOT NULL quals? */
123 bool amsearchnulls;
124 /* can index storage data type differ from column data type? */
125 bool amstorage;
126 /* can an index of this type be clustered on? */
127 bool amclusterable;
128 /* does AM handle predicate locks? */
129 bool ampredlocks;
130 /* does AM support parallel scan? */
131 bool amcanparallel;
132 /* does AM support parallel build? */
133 bool amcanbuildparallel;
134 /* does AM support columns included with clause INCLUDE? */
135 bool amcaninclude;
136 /* does AM use maintenance_work_mem? */
137 bool amusemaintenanceworkmem;
138 /* does AM summarize tuples, with at least all tuples in the block
139 * summarized in one summary */
140 bool amsummarizing;
141 /* OR of parallel vacuum flags */
142 uint8 amparallelvacuumoptions;
143 /* type of data stored in index, or InvalidOid if variable */
144 Oid amkeytype;
145
146 /* interface functions */
147 ambuild_function ambuild;
148 ambuildempty_function ambuildempty;
149 aminsert_function aminsert;
150 aminsertcleanup_function aminsertcleanup; /* can be NULL */
151 ambulkdelete_function ambulkdelete;
152 amvacuumcleanup_function amvacuumcleanup;
153 amcanreturn_function amcanreturn; /* can be NULL */
154 amcostestimate_function amcostestimate;
155 amgettreeheight_function amgettreeheight; /* can be NULL */
156 amoptions_function amoptions;
157 amproperty_function amproperty; /* can be NULL */
158 ambuildphasename_function ambuildphasename; /* can be NULL */
159 amvalidate_function amvalidate;
160 amadjustmembers_function amadjustmembers; /* can be NULL */
161 ambeginscan_function ambeginscan;
162 amrescan_function amrescan;
163 amgettuple_function amgettuple; /* can be NULL */
164 amgetbitmap_function amgetbitmap; /* can be NULL */
165 amendscan_function amendscan;
166 ammarkpos_function ammarkpos; /* can be NULL */
167 amrestrpos_function amrestrpos; /* can be NULL */
168
169 /* interface functions to support parallel index scans */
170 amestimateparallelscan_function amestimateparallelscan; /* can be NULL */
171 aminitparallelscan_function aminitparallelscan; /* can be NULL */
172 amparallelrescan_function amparallelrescan; /* can be NULL */
173
174 /* interface functions to support planning */
175 amtranslate_strategy_function amtranslatestrategy; /* can be NULL */
176 amtranslate_cmptype_function amtranslatecmptype; /* can be NULL */
177 } IndexAmRoutine;
178 </programlisting>
179 </para>
180
181 <para>
182 To be useful, an index access method must also have one or more
183 <firstterm>operator families</firstterm> and
184 <firstterm>operator classes</firstterm> defined in
185 <link linkend="catalog-pg-opfamily"><structname>pg_opfamily</structname></link>,
186 <link linkend="catalog-pg-opclass"><structname>pg_opclass</structname></link>,
187 <link linkend="catalog-pg-amop"><structname>pg_amop</structname></link>, and
188 <link linkend="catalog-pg-amproc"><structname>pg_amproc</structname></link>.
189 These entries allow the planner
190 to determine what kinds of query qualifications can be used with
191 indexes of this access method. Operator families and classes are described
192 in <xref linkend="xindex"/>, which is prerequisite material for reading
193 this chapter.
194 </para>
195
196 <para>
197 An individual index is defined by a
198 <link linkend="catalog-pg-class"><structname>pg_class</structname></link>
199 entry that describes it as a physical relation, plus a
200 <link linkend="catalog-pg-index"><structname>pg_index</structname></link>
201 entry that shows the logical content of the index &mdash; that is, the set
202 of index columns it has and the semantics of those columns, as captured by
203 the associated operator classes. The index columns (key values) can be
204 either simple columns of the underlying table or expressions over the table
205 rows. The index access method normally has no interest in where the index
206 key values come from (it is always handed precomputed key values) but it
207 will be very interested in the operator class information in
208 <structname>pg_index</structname>. Both of these catalog entries can be
209 accessed as part of the <structname>Relation</structname> data structure that is
210 passed to all operations on the index.
211 </para>
212
213 <para>
214 Some of the flag fields of <structname>IndexAmRoutine</structname> have nonobvious
215 implications. The requirements of <structfield>amcanunique</structfield>
216 are discussed in <xref linkend="index-unique-checks"/>.
217 The <structfield>amcanmulticol</structfield> flag asserts that the
218 access method supports multi-key-column indexes, while
219 <structfield>amoptionalkey</structfield> asserts that it allows scans
220 where no indexable restriction clause is given for the first index column.
221 When <structfield>amcanmulticol</structfield> is false,
222 <structfield>amoptionalkey</structfield> essentially says whether the
223 access method supports full-index scans without any restriction clause.
224 Access methods that support multiple index columns <emphasis>must</emphasis>
225 support scans that omit restrictions on any or all of the columns after
226 the first; however they are permitted to require some restriction to
227 appear for the first index column, and this is signaled by setting
228 <structfield>amoptionalkey</structfield> false.
229 One reason that an index <acronym>AM</acronym> might set
230 <structfield>amoptionalkey</structfield> false is if it doesn't index
231 null values. Since most indexable operators are
232 strict and hence cannot return true for null inputs,
233 it is at first sight attractive to not store index entries for null values:
234 they could never be returned by an index scan anyway. However, this
235 argument fails when an index scan has no restriction clause for a given
236 index column. In practice this means that
237 indexes that have <structfield>amoptionalkey</structfield> true must
238 index nulls, since the planner might decide to use such an index
239 with no scan keys at all. A related restriction is that an index
240 access method that supports multiple index columns <emphasis>must</emphasis>
241 support indexing null values in columns after the first, because the planner
242 will assume the index can be used for queries that do not restrict
243 these columns. For example, consider an index on (a,b) and a query with
244 <literal>WHERE a = 4</literal>. The system will assume the index can be
245 used to scan for rows with <literal>a = 4</literal>, which is wrong if the
246 index omits rows where <literal>b</literal> is null.
247 It is, however, OK to omit rows where the first indexed column is null.
248 An index access method that does index nulls may also set
249 <structfield>amsearchnulls</structfield>, indicating that it supports
250 <literal>IS NULL</literal> and <literal>IS NOT NULL</literal> clauses as search
251 conditions.
252 </para>
253
254 <para>
255 The <structfield>amcaninclude</structfield> flag indicates whether the
256 access method supports <quote>included</quote> columns, that is it can
257 store (without processing) additional columns beyond the key column(s).
258 The requirements of the preceding paragraph apply only to the key
259 columns. In particular, the combination
260 of <structfield>amcanmulticol</structfield>=<literal>false</literal>
261 and <structfield>amcaninclude</structfield>=<literal>true</literal> is
262 sensible: it means that there can only be one key column, but there can
263 also be included column(s). Also, included columns must be allowed to be
264 null, independently of <structfield>amoptionalkey</structfield>.
265 </para>
266
267 <para>
268 The <structfield>amsummarizing</structfield> flag indicates whether the
269 access method summarizes the indexed tuples, with summarizing granularity
270 of at least per block.
271 Access methods that do not point to individual tuples, but to block ranges
272 (like <acronym>BRIN</acronym>), may allow the <acronym>HOT</acronym> optimization
273 to continue. This does not apply to attributes referenced in index
274 predicates, an update of such an attribute always disables <acronym>HOT</acronym>.
275 </para>
276
277 </sect1>
278
279 <sect1 id="index-functions">
280 <title>Index Access Method Functions</title>
281
282 <para>
283 The index construction and maintenance functions that an index access
284 method must provide in <structname>IndexAmRoutine</structname> are:
285 </para>
286
287 <para>
288 <programlisting>
289 IndexBuildResult *
290 ambuild (Relation heapRelation,
291 Relation indexRelation,
292 IndexInfo *indexInfo);
293 </programlisting>
294 Build a new index. The index relation has been physically created,
295 but is empty. It must be filled in with whatever fixed data the
296 access method requires, plus entries for all tuples already existing
297 in the table. Ordinarily the <function>ambuild</function> function will call
298 <function>table_index_build_scan()</function> to scan the table for existing tuples
299 and compute the keys that need to be inserted into the index.
300 The function must return a palloc'd struct containing statistics about
301 the new index.
302 The <structfield>amcanbuildparallel</structfield> flag indicates whether
303 the access method supports parallel index builds. When set to <literal>true</literal>,
304 the system will attempt to allocate parallel workers for the build.
305 Access methods supporting only non-parallel index builds should leave
306 this flag set to <literal>false</literal>.
307 </para>
308
309 <para>
310 <programlisting>
311 void
312 ambuildempty (Relation indexRelation);
313 </programlisting>
314 Build an empty index, and write it to the initialization fork (<symbol>INIT_FORKNUM</symbol>)
315 of the given relation. This method is called only for unlogged indexes; the
316 empty index written to the initialization fork will be copied over the main
317 relation fork on each server restart.
318 </para>
319
320 <para>
321 <programlisting>
322 bool
323 aminsert (Relation indexRelation,
324 Datum *values,
325 bool *isnull,
326 ItemPointer heap_tid,
327 Relation heapRelation,
328 IndexUniqueCheck checkUnique,
329 bool indexUnchanged,
330 IndexInfo *indexInfo);
331 </programlisting>
332 Insert a new tuple into an existing index. The <literal>values</literal> and
333 <literal>isnull</literal> arrays give the key values to be indexed, and
334 <literal>heap_tid</literal> is the TID to be indexed.
335 If the access method supports unique indexes (its
336 <structfield>amcanunique</structfield> flag is true) then
337 <literal>checkUnique</literal> indicates the type of uniqueness check to
338 perform. This varies depending on whether the unique constraint is
339 deferrable; see <xref linkend="index-unique-checks"/> for details.
340 Normally the access method only needs the <literal>heapRelation</literal>
341 parameter when performing uniqueness checking (since then it will have to
342 look into the heap to verify tuple liveness).
343 </para>
344
345 <para>
346 The <literal>indexUnchanged</literal> Boolean value gives a hint
347 about the nature of the tuple to be indexed. When it is true,
348 the tuple is a duplicate of some existing tuple in the index. The
349 new tuple is a logically unchanged successor MVCC tuple version. This
350 happens when an <command>UPDATE</command> takes place that does not
351 modify any columns covered by the index, but nevertheless requires a
352 new version in the index. The index AM may use this hint to decide
353 to apply bottom-up index deletion in parts of the index where many
354 versions of the same logical row accumulate. Note that updating a non-key
355 column or a column that only appears in a partial index predicate does not
356 affect the value of <literal>indexUnchanged</literal>. The core code
357 determines each tuple's <literal>indexUnchanged</literal> value using a low
358 overhead approach that allows both false positives and false negatives.
359 Index AMs must not treat <literal>indexUnchanged</literal> as an
360 authoritative source of information about tuple visibility or versioning.
361 </para>
362
363 <para>
364 The function's Boolean result value is significant only when
365 <literal>checkUnique</literal> is <literal>UNIQUE_CHECK_PARTIAL</literal>.
366 In this case a true result means the new entry is known unique, whereas
367 false means it might be non-unique (and a deferred uniqueness check must
368 be scheduled). For other cases a constant false result is recommended.
369 </para>
370
371 <para>
372 Some indexes might not index all tuples. If the tuple is not to be
373 indexed, <function>aminsert</function> should just return without doing anything.
374 </para>
375
376 <para>
377 If the index AM wishes to cache data across successive index insertions
378 within an SQL statement, it can allocate space
379 in <literal>indexInfo-&gt;ii_Context</literal> and store a pointer to the
380 data in <literal>indexInfo-&gt;ii_AmCache</literal> (which will be NULL
381 initially). If resources other than memory have to be released after
382 index insertions, <function>aminsertcleanup</function> may be provided,
383 which will be called before the memory is released.
384 </para>
385
386 <para>
387 <programlisting>
388 void
389 aminsertcleanup (Relation indexRelation,
390 IndexInfo *indexInfo);
391 </programlisting>
392 Clean up state that was maintained across successive inserts in
393 <literal>indexInfo-&gt;ii_AmCache</literal>. This is useful if the data
394 requires additional cleanup steps (e.g., releasing pinned buffers), and
395 simply releasing the memory is not sufficient.
396 </para>
397
398 <para>
399 <programlisting>
400 IndexBulkDeleteResult *
401 ambulkdelete (IndexVacuumInfo *info,
402 IndexBulkDeleteResult *stats,
403 IndexBulkDeleteCallback callback,
404 void *callback_state);
405 </programlisting>
406 Delete tuple(s) from the index. This is a <quote>bulk delete</quote> operation
407 that is intended to be implemented by scanning the whole index and checking
408 each entry to see if it should be deleted.
409 The passed-in <literal>callback</literal> function must be called, in the style
410 <literal>callback(<replaceable>TID</replaceable>, callback_state) returns bool</literal>,
411 to determine whether any particular index entry, as identified by its
412 referenced TID, is to be deleted. Must return either NULL or a palloc'd
413 struct containing statistics about the effects of the deletion operation.
414 It is OK to return NULL if no information needs to be passed on to
415 <function>amvacuumcleanup</function>.
416 </para>
417
418 <para>
419 Because of limited <varname>maintenance_work_mem</varname>,
420 <function>ambulkdelete</function> might need to be called more than once when many
421 tuples are to be deleted. The <literal>stats</literal> argument is the result
422 of the previous call for this index (it is NULL for the first call within a
423 <command>VACUUM</command> operation). This allows the AM to accumulate statistics
424 across the whole operation. Typically, <function>ambulkdelete</function> will
425 modify and return the same struct if the passed <literal>stats</literal> is not
426 null.
427 </para>
428
429 <para>
430 <programlisting>
431 IndexBulkDeleteResult *
432 amvacuumcleanup (IndexVacuumInfo *info,
433 IndexBulkDeleteResult *stats);
434 </programlisting>
435 Clean up after a <command>VACUUM</command> operation (zero or more
436 <function>ambulkdelete</function> calls). This does not have to do anything
437 beyond returning index statistics, but it might perform bulk cleanup
438 such as reclaiming empty index pages. <literal>stats</literal> is whatever the
439 last <function>ambulkdelete</function> call returned, or NULL if
440 <function>ambulkdelete</function> was not called because no tuples needed to be
441 deleted. If the result is not NULL it must be a palloc'd struct.
442 The statistics it contains will be used to update <structname>pg_class</structname>,
443 and will be reported by <command>VACUUM</command> if <literal>VERBOSE</literal> is given.
444 It is OK to return NULL if the index was not changed at all during the
445 <command>VACUUM</command> operation, but otherwise correct stats should
446 be returned.
447 </para>
448
449 <para>
450 <function>amvacuumcleanup</function> will also be called at completion of an
451 <command>ANALYZE</command> operation. In this case <literal>stats</literal> is always
452 NULL and any return value will be ignored. This case can be distinguished
453 by checking <literal>info-&gt;analyze_only</literal>. It is recommended
454 that the access method do nothing except post-insert cleanup in such a
455 call, and that only in an autovacuum worker process.
456 </para>
457
458 <para>
459 <programlisting>
460 bool
461 amcanreturn (Relation indexRelation, int attno);
462 </programlisting>
463 Check whether the index can support <link
464 linkend="indexes-index-only-scans"><firstterm>index-only scans</firstterm></link> on
465 the given column, by returning the column's original indexed value.
466 The attribute number is 1-based, i.e., the first column's attno is 1.
467 Returns true if supported, else false.
468 This function should always return true for included columns
469 (if those are supported), since there's little point in an included
470 column that can't be retrieved.
471 If the access method does not support index-only scans at all,
472 the <structfield>amcanreturn</structfield> field in its <structname>IndexAmRoutine</structname>
473 struct can be set to NULL.
474 </para>
475
476 <para>
477 <programlisting>
478 void
479 amcostestimate (PlannerInfo *root,
480 IndexPath *path,
481 double loop_count,
482 Cost *indexStartupCost,
483 Cost *indexTotalCost,
484 Selectivity *indexSelectivity,
485 double *indexCorrelation,
486 double *indexPages);
487 </programlisting>
488 Estimate the costs of an index scan. This function is described fully
489 in <xref linkend="index-cost-estimation"/>, below.
490 </para>
491
492 <para>
493 <programlisting>
494 int
495 amgettreeheight (Relation rel);
496 </programlisting>
497 Compute the height of a tree-shaped index. This information is supplied to
498 the <function>amcostestimate</function> function in
499 <literal>path->indexinfo->tree_height</literal> and can be used to support
500 the cost estimation. The result is not used anywhere else, so this
501 function can actually be used to compute any kind of data (that fits into
502 an integer) about the index that the cost estimation function might want to
503 know. If the computation is expensive, it could be useful to cache the
504 result as part of <literal>RelationData.rd_amcache</literal>.
505 </para>
506
507 <para>
508 <programlisting>
509 bytea *
510 amoptions (ArrayType *reloptions,
511 bool validate);
512 </programlisting>
513 Parse and validate the reloptions array for an index. This is called only
514 when a non-null reloptions array exists for the index.
515 <parameter>reloptions</parameter> is a <type>text</type> array containing entries of the
516 form <replaceable>name</replaceable><literal>=</literal><replaceable>value</replaceable>.
517 The function should construct a <type>bytea</type> value, which will be copied
518 into the <structfield>rd_options</structfield> field of the index's relcache entry.
519 The data contents of the <type>bytea</type> value are open for the access
520 method to define; most of the standard access methods use struct
521 <structname>StdRdOptions</structname>.
522 When <parameter>validate</parameter> is true, the function should report a suitable
523 error message if any of the options are unrecognized or have invalid
524 values; when <parameter>validate</parameter> is false, invalid entries should be
525 silently ignored. (<parameter>validate</parameter> is false when loading options
526 already stored in <structname>pg_catalog</structname>; an invalid entry could only
527 be found if the access method has changed its rules for options, and in
528 that case ignoring obsolete entries is appropriate.)
529 It is OK to return NULL if default behavior is wanted.
530 </para>
531
532 <para>
533 <programlisting>
534 bool
535 amproperty (Oid index_oid, int attno,
536 IndexAMProperty prop, const char *propname,
537 bool *res, bool *isnull);
538 </programlisting>
539 The <function>amproperty</function> method allows index access methods to override
540 the default behavior of <function>pg_index_column_has_property</function>
541 and related functions.
542 If the access method does not have any special behavior for index property
543 inquiries, the <structfield>amproperty</structfield> field in
544 its <structname>IndexAmRoutine</structname> struct can be set to NULL.
545 Otherwise, the <function>amproperty</function> method will be called with
546 <parameter>index_oid</parameter> and <parameter>attno</parameter> both zero for
547 <function>pg_indexam_has_property</function> calls,
548 or with <parameter>index_oid</parameter> valid and <parameter>attno</parameter> zero for
549 <function>pg_index_has_property</function> calls,
550 or with <parameter>index_oid</parameter> valid and <parameter>attno</parameter> greater than
551 zero for <function>pg_index_column_has_property</function> calls.
552 <parameter>prop</parameter> is an enum value identifying the property being tested,
553 while <parameter>propname</parameter> is the original property name string.
554 If the core code does not recognize the property name
555 then <parameter>prop</parameter> is <literal>AMPROP_UNKNOWN</literal>.
556 Access methods can define custom property names by
557 checking <parameter>propname</parameter> for a match (use <function>pg_strcasecmp</function>
558 to match, for consistency with the core code); for names known to the core
559 code, it's better to inspect <parameter>prop</parameter>.
560 If the <structfield>amproperty</structfield> method returns <literal>true</literal> then
561 it has determined the property test result: it must set <literal>*res</literal>
562 to the Boolean value to return, or set <literal>*isnull</literal>
563 to <literal>true</literal> to return a NULL. (Both of the referenced variables
564 are initialized to <literal>false</literal> before the call.)
565 If the <structfield>amproperty</structfield> method returns <literal>false</literal> then
566 the core code will proceed with its normal logic for determining the
567 property test result.
568 </para>
569
570 <para>
571 Access methods that support ordering operators should
572 implement <literal>AMPROP_DISTANCE_ORDERABLE</literal> property testing, as the
573 core code does not know how to do that and will return NULL. It may
574 also be advantageous to implement <literal>AMPROP_RETURNABLE</literal> testing,
575 if that can be done more cheaply than by opening the index and calling
576 <function>amcanreturn</function>, which is the core code's default behavior.
577 The default behavior should be satisfactory for all other standard
578 properties.
579 </para>
580
581 <para>
582 <programlisting>
583 char *
584 ambuildphasename (int64 phasenum);
585 </programlisting>
586 Return the textual name of the given build phase number.
587 The phase numbers are those reported during an index build via the
588 <function>pgstat_progress_update_param</function> interface.
589 The phase names are then exposed in the
590 <structname>pg_stat_progress_create_index</structname> view.
591 </para>
592
593 <para>
594 <programlisting>
595 bool
596 amvalidate (Oid opclassoid);
597 </programlisting>
598 Validate the catalog entries for the specified operator class, so far as
599 the access method can reasonably do that. For example, this might include
600 testing that all required support functions are provided.
601 The <function>amvalidate</function> function must return false if the opclass is
602 invalid. Problems should be reported with <function>ereport</function>
603 messages, typically at <literal>INFO</literal> level.
604 </para>
605
606 <para>
607 <programlisting>
608 void
609 amadjustmembers (Oid opfamilyoid,
610 Oid opclassoid,
611 List *operators,
612 List *functions);
613 </programlisting>
614 Validate proposed new operator and function members of an operator family,
615 so far as the access method can reasonably do that, and set their
616 dependency types if the default is not satisfactory. This is called
617 during <command>CREATE OPERATOR CLASS</command> and during
618 <command>ALTER OPERATOR FAMILY ADD</command>; in the latter
619 case <parameter>opclassoid</parameter> is <literal>InvalidOid</literal>.
620 The <type>List</type> arguments are lists
621 of <structname>OpFamilyMember</structname> structs, as defined
622 in <filename>amapi.h</filename>.
623
624 Tests done by this function will typically be a subset of those
625 performed by <function>amvalidate</function>,
626 since <function>amadjustmembers</function> cannot assume that it is
627 seeing a complete set of members. For example, it would be reasonable
628 to check the signature of a support function, but not to check whether
629 all required support functions are provided. Any problems can be
630 reported by throwing an error.
631
632 The dependency-related fields of
633 the <structname>OpFamilyMember</structname> structs are initialized by
634 the core code to create hard dependencies on the opclass if this
635 is <command>CREATE OPERATOR CLASS</command>, or soft dependencies on the
636 opfamily if this is <command>ALTER OPERATOR FAMILY ADD</command>.
637 <function>amadjustmembers</function> can adjust these fields if some other
638 behavior is more appropriate. For example, GIN, GiST, and SP-GiST
639 always set operator members to have soft dependencies on the opfamily,
640 since the connection between an operator and an opclass is relatively
641 weak in these index types; so it is reasonable to allow operator members
642 to be added and removed freely. Optional support functions are typically
643 also given soft dependencies, so that they can be removed if necessary.
644 </para>
645
646
647 <para>
648 The purpose of an index, of course, is to support scans for tuples matching
649 an indexable <literal>WHERE</literal> condition, often called a
650 <firstterm>qualifier</firstterm> or <firstterm>scan key</firstterm>. The semantics of
651 index scanning are described more fully in <xref linkend="index-scanning"/>,
652 below. An index access method can support <quote>plain</quote> index scans,
653 <quote>bitmap</quote> index scans, or both. The scan-related functions that an
654 index access method must or may provide are:
655 </para>
656
657 <para>
658 <programlisting>
659 IndexScanDesc
660 ambeginscan (Relation indexRelation,
661 int nkeys,
662 int norderbys);
663 </programlisting>
664 Prepare for an index scan. The <literal>nkeys</literal> and <literal>norderbys</literal>
665 parameters indicate the number of quals and ordering operators that will be
666 used in the scan; these may be useful for space allocation purposes.
667 Note that the actual values of the scan keys aren't provided yet.
668 The result must be a palloc'd struct.
669 For implementation reasons the index access method
670 <emphasis>must</emphasis> create this struct by calling
671 <function>RelationGetIndexScan()</function>. In most cases
672 <function>ambeginscan</function> does little beyond making that call and perhaps
673 acquiring locks;
674 the interesting parts of index-scan startup are in <function>amrescan</function>.
675 </para>
676
677 <para>
678 <programlisting>
679 void
680 amrescan (IndexScanDesc scan,
681 ScanKey keys,
682 int nkeys,
683 ScanKey orderbys,
684 int norderbys);
685 </programlisting>
686 Start or restart an index scan, possibly with new scan keys. (To restart
687 using previously-passed keys, NULL is passed for <literal>keys</literal> and/or
688 <literal>orderbys</literal>.) Note that it is not allowed for
689 the number of keys or order-by operators to be larger than
690 what was passed to <function>ambeginscan</function>. In practice the restart
691 feature is used when a new outer tuple is selected by a nested-loop join
692 and so a new key comparison value is needed, but the scan key structure
693 remains the same.
694 </para>
695
696 <para>
697 <programlisting>
698 bool
699 amgettuple (IndexScanDesc scan,
700 ScanDirection direction);
701 </programlisting>
702 Fetch the next tuple in the given scan, moving in the given
703 direction (forward or backward in the index). Returns true if a tuple was
704 obtained, false if no matching tuples remain. In the true case the tuple
705 TID is stored into the <literal>scan</literal> structure. Note that
706 <quote>success</quote> means only that the index contains an entry that matches
707 the scan keys, not that the tuple necessarily still exists in the heap or
708 will pass the caller's snapshot test. On success, <function>amgettuple</function>
709 must also set <literal>scan-&gt;xs_recheck</literal> to true or false.
710 False means it is certain that the index entry matches the scan keys.
711 True means this is not certain, and the conditions represented by the
712 scan keys must be rechecked against the heap tuple after fetching it.
713 This provision supports <quote>lossy</quote> index operators.
714 Note that rechecking will extend only to the scan conditions; a partial
715 index predicate (if any) is never rechecked by <function>amgettuple</function>
716 callers.
717 </para>
718
719 <para>
720 If the index supports <link linkend="indexes-index-only-scans">index-only
721 scans</link> (i.e., <function>amcanreturn</function> returns true for any
722 of its columns),
723 then on success the AM must also check <literal>scan-&gt;xs_want_itup</literal>,
724 and if that is true it must return the originally indexed data for the
725 index entry. Columns for which <function>amcanreturn</function> returns
726 false can be returned as nulls.
727 The data can be returned in the form of an
728 <structname>IndexTuple</structname> pointer stored at <literal>scan-&gt;xs_itup</literal>,
729 with tuple descriptor <literal>scan-&gt;xs_itupdesc</literal>; or in the form of
730 a <structname>HeapTuple</structname> pointer stored at <literal>scan-&gt;xs_hitup</literal>,
731 with tuple descriptor <literal>scan-&gt;xs_hitupdesc</literal>. (The latter
732 format should be used when reconstructing data that might possibly not fit
733 into an <structname>IndexTuple</structname>.) In either case,
734 management of the data referenced by the pointer is the access method's
735 responsibility. The data must remain good at least until the next
736 <function>amgettuple</function>, <function>amrescan</function>, or <function>amendscan</function>
737 call for the scan.
738 </para>
739
740 <para>
741 The <function>amgettuple</function> function need only be provided if the access
742 method supports <quote>plain</quote> index scans. If it doesn't, the
743 <structfield>amgettuple</structfield> field in its <structname>IndexAmRoutine</structname>
744 struct must be set to NULL.
745 </para>
746
747 <para>
748 <programlisting>
749 int64
750 amgetbitmap (IndexScanDesc scan,
751 TIDBitmap *tbm);
752 </programlisting>
753 Fetch all tuples in the given scan and add them to the caller-supplied
754 <type>TIDBitmap</type> (that is, OR the set of tuple IDs into whatever set is already
755 in the bitmap). The number of tuples fetched is returned (this might be
756 just an approximate count, for instance some AMs do not detect duplicates).
757 While inserting tuple IDs into the bitmap, <function>amgetbitmap</function> can
758 indicate that rechecking of the scan conditions is required for specific
759 tuple IDs. This is analogous to the <literal>xs_recheck</literal> output parameter
760 of <function>amgettuple</function>. Note: in the current implementation, support
761 for this feature is conflated with support for lossy storage of the bitmap
762 itself, and therefore callers recheck both the scan conditions and the
763 partial index predicate (if any) for recheckable tuples. That might not
764 always be true, however.
765 <function>amgetbitmap</function> and
766 <function>amgettuple</function> cannot be used in the same index scan; there
767 are other restrictions too when using <function>amgetbitmap</function>, as explained
768 in <xref linkend="index-scanning"/>.
769 </para>
770
771 <para>
772 The <function>amgetbitmap</function> function need only be provided if the access
773 method supports <quote>bitmap</quote> index scans. If it doesn't, the
774 <structfield>amgetbitmap</structfield> field in its <structname>IndexAmRoutine</structname>
775 struct must be set to NULL.
776 </para>
777
778 <para>
779 <programlisting>
780 void
781 amendscan (IndexScanDesc scan);
782 </programlisting>
783 End a scan and release resources. The <literal>scan</literal> struct itself
784 should not be freed, but any locks or pins taken internally by the
785 access method must be released, as well as any other memory allocated
786 by <function>ambeginscan</function> and other scan-related functions.
787 </para>
788
789 <para>
790 <programlisting>
791 void
792 ammarkpos (IndexScanDesc scan);
793 </programlisting>
794 Mark current scan position. The access method need only support one
795 remembered scan position per scan.
796 </para>
797
798 <para>
799 The <function>ammarkpos</function> function need only be provided if the access
800 method supports ordered scans. If it doesn't,
801 the <structfield>ammarkpos</structfield> field in its <structname>IndexAmRoutine</structname>
802 struct may be set to NULL.
803 </para>
804
805 <para>
806 <programlisting>
807 void
808 amrestrpos (IndexScanDesc scan);
809 </programlisting>
810 Restore the scan to the most recently marked position.
811 </para>
812
813 <para>
814 The <function>amrestrpos</function> function need only be provided if the access
815 method supports ordered scans. If it doesn't,
816 the <structfield>amrestrpos</structfield> field in its <structname>IndexAmRoutine</structname>
817 struct may be set to NULL.
818 </para>
819
820 <para>
821 In addition to supporting ordinary index scans, some types of index
822 may wish to support <firstterm>parallel index scans</firstterm>, which allow
823 multiple backends to cooperate in performing an index scan. The
824 index access method should arrange things so that each cooperating
825 process returns a subset of the tuples that would be performed by
826 an ordinary, non-parallel index scan, but in such a way that the
827 union of those subsets is equal to the set of tuples that would be
828 returned by an ordinary, non-parallel index scan. Furthermore, while
829 there need not be any global ordering of tuples returned by a parallel
830 scan, the ordering of that subset of tuples returned within each
831 cooperating backend must match the requested ordering. The following
832 functions may be implemented to support parallel index scans:
833 </para>
834
835 <para>
836 <programlisting>
837 Size
838 amestimateparallelscan (Relation indexRelation,
839 int nkeys,
840 int norderbys);
841 </programlisting>
842 Estimate and return the number of bytes of dynamic shared memory which
843 the access method will be needed to perform a parallel scan. (This number
844 is in addition to, not in lieu of, the amount of space needed for
845 AM-independent data in <structname>ParallelIndexScanDescData</structname>.)
846 </para>
847
848 <para>
849 The <literal>nkeys</literal> and <literal>norderbys</literal>
850 parameters indicate the number of quals and ordering operators that will be
851 used in the scan; the same values will be passed to <function>amrescan</function>.
852 Note that the actual values of the scan keys aren't provided yet.
853 </para>
854
855 <para>
856 It is not necessary to implement this function for access methods which
857 do not support parallel scans or for which the number of additional bytes
858 of storage required is zero.
859 </para>
860
861 <para>
862 <programlisting>
863 void
864 aminitparallelscan (void *target);
865 </programlisting>
866 This function will be called to initialize dynamic shared memory at the
867 beginning of a parallel scan. <parameter>target</parameter> will point to at least
868 the number of bytes previously returned by
869 <function>amestimateparallelscan</function>, and this function may use that
870 amount of space to store whatever data it wishes.
871 </para>
872
873 <para>
874 It is not necessary to implement this function for access methods which
875 do not support parallel scans or in cases where the shared memory space
876 required needs no initialization.
877 </para>
878
879 <para>
880 <programlisting>
881 void
882 amparallelrescan (IndexScanDesc scan);
883 </programlisting>
884 This function, if implemented, will be called when a parallel index scan
885 must be restarted. It should reset any shared state set up by
886 <function>aminitparallelscan</function> such that the scan will be restarted from
887 the beginning.
888 </para>
889
890 <para>
891 <programlisting>
892 CompareType
893 amtranslatestrategy (StrategyNumber strategy, Oid opfamily, Oid opcintype);
894
895 StrategyNumber
896 amtranslatecmptype (CompareType cmptype, Oid opfamily, Oid opcintype);
897 </programlisting>
898 These functions, if implemented, will be called by the planner and executor
899 to convert between fixed <type>CompareType</type> values and the specific
900 strategy numbers used by the access method. These functions can be
901 implemented by access methods that implement functionality similar to the
902 built-in btree or hash access methods, and by implementing these
903 translations, the system can learn about the semantics of the access
904 method's operations and can use them in place of btree or hash indexes in
905 various places. If the functionality of the access method is not similar
906 to those built-in access methods, these functions do not need to be
907 implemented. If the functions are not implemented, the access method will
908 be ignored for certain planner and executor decisions, but is otherwise
909 fully functional.
910 </para>
911
912 </sect1>
913
914 <sect1 id="index-scanning">
915 <title>Index Scanning</title>
916
917 <para>
918 In an index scan, the index access method is responsible for regurgitating
919 the TIDs of all the tuples it has been told about that match the
920 <firstterm>scan keys</firstterm>. The access method is <emphasis>not</emphasis> involved in
921 actually fetching those tuples from the index's parent table, nor in
922 determining whether they pass the scan's visibility test or other
923 conditions.
924 </para>
925
926 <para>
927 A scan key is the internal representation of a <literal>WHERE</literal> clause of
928 the form <replaceable>index_key</replaceable> <replaceable>operator</replaceable>
929 <replaceable>constant</replaceable>, where the index key is one of the columns of the
930 index and the operator is one of the members of the operator family
931 associated with that index column. An index scan has zero or more scan
932 keys, which are implicitly ANDed &mdash; the returned tuples are expected
933 to satisfy all the indicated conditions.
934 </para>
935
936 <para>
937 The access method can report that the index is <firstterm>lossy</firstterm>, or
938 requires rechecks, for a particular query. This implies that the index
939 scan will return all the entries that pass the scan key, plus possibly
940 additional entries that do not. The core system's index-scan machinery
941 will then apply the index conditions again to the heap tuple to verify
942 whether or not it really should be selected. If the recheck option is not
943 specified, the index scan must return exactly the set of matching entries.
944 </para>
945
946 <para>
947 Note that it is entirely up to the access method to ensure that it
948 correctly finds all and only the entries passing all the given scan keys.
949 Also, the core system will simply hand off all the <literal>WHERE</literal>
950 clauses that match the index keys and operator families, without any
951 semantic analysis to determine whether they are redundant or
952 contradictory. As an example, given
953 <literal>WHERE x &gt; 4 AND x &gt; 14</literal> where <literal>x</literal> is a b-tree
954 indexed column, it is left to the b-tree <function>amrescan</function> function
955 to realize that the first scan key is redundant and can be discarded.
956 The extent of preprocessing needed during <function>amrescan</function> will
957 depend on the extent to which the index access method needs to reduce
958 the scan keys to a <quote>normalized</quote> form.
959 </para>
960
961 <para>
962 Some access methods return index entries in a well-defined order, others
963 do not. There are actually two different ways that an access method can
964 support sorted output:
965
966 <itemizedlist>
967 <listitem>
968 <para>
969 Access methods that always return entries in the natural ordering
970 of their data (such as btree) should set
971 <structfield>amcanorder</structfield> to true.
972 Currently, such access methods must use btree-compatible strategy
973 numbers for their equality and ordering operators.
974 </para>
975 </listitem>
976 <listitem>
977 <para>
978 Access methods that support ordering operators should set
979 <structfield>amcanorderbyop</structfield> to true.
980 This indicates that the index is capable of returning entries in
981 an order satisfying <literal>ORDER BY</literal> <replaceable>index_key</replaceable>
982 <replaceable>operator</replaceable> <replaceable>constant</replaceable>. Scan modifiers
983 of that form can be passed to <function>amrescan</function> as described
984 previously.
985 </para>
986 </listitem>
987 </itemizedlist>
988 </para>
989
990 <para>
991 The <function>amgettuple</function> function has a <literal>direction</literal> argument,
992 which can be either <literal>ForwardScanDirection</literal> (the normal case)
993 or <literal>BackwardScanDirection</literal>. If the first call after
994 <function>amrescan</function> specifies <literal>BackwardScanDirection</literal>, then the
995 set of matching index entries is to be scanned back-to-front rather than in
996 the normal front-to-back direction, so <function>amgettuple</function> must return
997 the last matching tuple in the index, rather than the first one as it
998 normally would. (This will only occur for access
999 methods that set <structfield>amcanorder</structfield> to true.) After the
1000 first call, <function>amgettuple</function> must be prepared to advance the scan in
1001 either direction from the most recently returned entry. (But if
1002 <structfield>amcanbackward</structfield> is false, all subsequent
1003 calls will have the same direction as the first one.)
1004 </para>
1005
1006 <para>
1007 Access methods that support ordered scans must support <quote>marking</quote> a
1008 position in a scan and later returning to the marked position. The same
1009 position might be restored multiple times. However, only one position need
1010 be remembered per scan; a new <function>ammarkpos</function> call overrides the
1011 previously marked position. An access method that does not support ordered
1012 scans need not provide <function>ammarkpos</function> and <function>amrestrpos</function>
1013 functions in <structname>IndexAmRoutine</structname>; set those pointers to NULL
1014 instead.
1015 </para>
1016
1017 <para>
1018 Both the scan position and the mark position (if any) must be maintained
1019 consistently in the face of concurrent insertions or deletions in the
1020 index. It is OK if a freshly-inserted entry is not returned by a scan that
1021 would have found the entry if it had existed when the scan started, or for
1022 the scan to return such an entry upon rescanning or backing
1023 up even though it had not been returned the first time through. Similarly,
1024 a concurrent delete might or might not be reflected in the results of a scan.
1025 What is important is that insertions or deletions not cause the scan to
1026 miss or multiply return entries that were not themselves being inserted or
1027 deleted.
1028 </para>
1029
1030 <para>
1031 If the index stores the original indexed data values (and not some lossy
1032 representation of them), it is useful to
1033 support <link linkend="indexes-index-only-scans">index-only scans</link>, in
1034 which the index returns the actual data not just the TID of the heap tuple.
1035 This will only avoid I/O if the visibility map shows that the TID is on an
1036 all-visible page; else the heap tuple must be visited anyway to check
1037 MVCC visibility. But that is no concern of the access method's.
1038 </para>
1039
1040 <para>
1041 Instead of using <function>amgettuple</function>, an index scan can be done with
1042 <function>amgetbitmap</function> to fetch all tuples in one call. This can be
1043 noticeably more efficient than <function>amgettuple</function> because it allows
1044 avoiding lock/unlock cycles within the access method. In principle
1045 <function>amgetbitmap</function> should have the same effects as repeated
1046 <function>amgettuple</function> calls, but we impose several restrictions to
1047 simplify matters. First of all, <function>amgetbitmap</function> returns all
1048 tuples at once and marking or restoring scan positions isn't
1049 supported. Secondly, the tuples are returned in a bitmap which doesn't
1050 have any specific ordering, which is why <function>amgetbitmap</function> doesn't
1051 take a <literal>direction</literal> argument. (Ordering operators will never be
1052 supplied for such a scan, either.)
1053 Also, there is no provision for index-only scans with
1054 <function>amgetbitmap</function>, since there is no way to return the contents of
1055 index tuples.
1056 Finally, <function>amgetbitmap</function>
1057 does not guarantee any locking of the returned tuples, with implications
1058 spelled out in <xref linkend="index-locking"/>.
1059 </para>
1060
1061 <para>
1062 Note that it is permitted for an access method to implement only
1063 <function>amgetbitmap</function> and not <function>amgettuple</function>, or vice versa,
1064 if its internal implementation is unsuited to one API or the other.
1065 </para>
1066
1067 </sect1>
1068
1069 <sect1 id="index-locking">
1070 <title>Index Locking Considerations</title>
1071
1072 <para>
1073 Index access methods must handle concurrent updates
1074 of the index by multiple processes.
1075 The core <productname>PostgreSQL</productname> system obtains
1076 <literal>AccessShareLock</literal> on the index during an index scan, and
1077 <literal>RowExclusiveLock</literal> when updating the index (including plain
1078 <command>VACUUM</command>). Since these lock types do not conflict, the access
1079 method is responsible for handling any fine-grained locking it might need.
1080 An <literal>ACCESS EXCLUSIVE</literal> lock on the index as a whole will be
1081 taken only during index creation, destruction, or <command>REINDEX</command>
1082 (<literal>SHARE UPDATE EXCLUSIVE</literal> is taken instead with
1083 <literal>CONCURRENTLY</literal>).
1084 </para>
1085
1086 <para>
1087 Building an index type that supports concurrent updates usually requires
1088 extensive and subtle analysis of the required behavior. For the b-tree
1089 and hash index types, you can read about the design decisions involved in
1090 <filename>src/backend/access/nbtree/README</filename> and
1091 <filename>src/backend/access/hash/README</filename>.
1092 </para>
1093
1094 <para>
1095 Aside from the index's own internal consistency requirements, concurrent
1096 updates create issues about consistency between the parent table (the
1097 <firstterm>heap</firstterm>) and the index. Because
1098 <productname>PostgreSQL</productname> separates accesses
1099 and updates of the heap from those of the index, there are windows in
1100 which the index might be inconsistent with the heap. We handle this problem
1101 with the following rules:
1102
1103 <itemizedlist>
1104 <listitem>
1105 <para>
1106 A new heap entry is made before making its index entries. (Therefore
1107 a concurrent index scan is likely to fail to see the heap entry.
1108 This is okay because the index reader would be uninterested in an
1109 uncommitted row anyway. But see <xref linkend="index-unique-checks"/>.)
1110 </para>
1111 </listitem>
1112 <listitem>
1113 <para>
1114 When a heap entry is to be deleted (by <command>VACUUM</command>), all its
1115 index entries must be removed first.
1116 </para>
1117 </listitem>
1118 <listitem>
1119 <para>
1120 An index scan must maintain a pin
1121 on the index page holding the item last returned by
1122 <function>amgettuple</function>, and <function>ambulkdelete</function> cannot delete
1123 entries from pages that are pinned by other backends. The need
1124 for this rule is explained below.
1125 </para>
1126 </listitem>
1127 </itemizedlist>
1128
1129 Without the third rule, it is possible for an index reader to
1130 see an index entry just before it is removed by <command>VACUUM</command>, and
1131 then to arrive at the corresponding heap entry after that was removed by
1132 <command>VACUUM</command>.
1133 This creates no serious problems if that item
1134 number is still unused when the reader reaches it, since an empty
1135 item slot will be ignored by <function>heap_fetch()</function>. But what if a
1136 third backend has already re-used the item slot for something else?
1137 When using an MVCC-compliant snapshot, there is no problem because
1138 the new occupant of the slot is certain to be too new to pass the
1139 snapshot test. However, with a non-MVCC-compliant snapshot (such as
1140 <literal>SnapshotAny</literal>), it would be possible to accept and return
1141 a row that does not in fact match the scan keys. We could defend
1142 against this scenario by requiring the scan keys to be rechecked
1143 against the heap row in all cases, but that is too expensive. Instead,
1144 we use a pin on an index page as a proxy to indicate that the reader
1145 might still be <quote>in flight</quote> from the index entry to the matching
1146 heap entry. Making <function>ambulkdelete</function> block on such a pin ensures
1147 that <command>VACUUM</command> cannot delete the heap entry before the reader
1148 is done with it. This solution costs little in run time, and adds blocking
1149 overhead only in the rare cases where there actually is a conflict.
1150 </para>
1151
1152 <para>
1153 This solution requires that index scans be <quote>synchronous</quote>: we have
1154 to fetch each heap tuple immediately after scanning the corresponding index
1155 entry. This is expensive for a number of reasons. An
1156 <quote>asynchronous</quote> scan in which we collect many TIDs from the index,
1157 and only visit the heap tuples sometime later, requires much less index
1158 locking overhead and can allow a more efficient heap access pattern.
1159 Per the above analysis, we must use the synchronous approach for
1160 non-MVCC-compliant snapshots, but an asynchronous scan is workable
1161 for a query using an MVCC snapshot.
1162 </para>
1163
1164 <para>
1165 In an <function>amgetbitmap</function> index scan, the access method does not
1166 keep an index pin on any of the returned tuples. Therefore
1167 it is only safe to use such scans with MVCC-compliant snapshots.
1168 </para>
1169
1170 <para>
1171 When the <structfield>ampredlocks</structfield> flag is not set, any scan using that
1172 index access method within a serializable transaction will acquire a
1173 nonblocking predicate lock on the full index. This will generate a
1174 read-write conflict with the insert of any tuple into that index by a
1175 concurrent serializable transaction. If certain patterns of read-write
1176 conflicts are detected among a set of concurrent serializable
1177 transactions, one of those transactions may be canceled to protect data
1178 integrity. When the flag is set, it indicates that the index access
1179 method implements finer-grained predicate locking, which will tend to
1180 reduce the frequency of such transaction cancellations.
1181 </para>
1182
1183 </sect1>
1184
1185 <sect1 id="index-unique-checks">
1186 <title>Index Uniqueness Checks</title>
1187
1188 <para>
1189 <productname>PostgreSQL</productname> enforces SQL uniqueness constraints
1190 using <firstterm>unique indexes</firstterm>, which are indexes that disallow
1191 multiple entries with identical keys. An access method that supports this
1192 feature sets <structfield>amcanunique</structfield> true.
1193 (At present, only b-tree supports it.) Columns listed in the
1194 <literal>INCLUDE</literal> clause are not considered when enforcing
1195 uniqueness.
1196 </para>
1197
1198 <para>
1199 Because of MVCC, it is always necessary to allow duplicate entries to
1200 exist physically in an index: the entries might refer to successive
1201 versions of a single logical row. The behavior we actually want to
1202 enforce is that no MVCC snapshot could include two rows with equal
1203 index keys. This breaks down into the following cases that must be
1204 checked when inserting a new row into a unique index:
1205
1206 <itemizedlist>
1207 <listitem>
1208 <para>
1209 If a conflicting valid row has been deleted by the current transaction,
1210 it's okay. (In particular, since an UPDATE always deletes the old row
1211 version before inserting the new version, this will allow an UPDATE on
1212 a row without changing the key.)
1213 </para>
1214 </listitem>
1215 <listitem>
1216 <para>
1217 If a conflicting row has been inserted by an as-yet-uncommitted
1218 transaction, the would-be inserter must wait to see if that transaction
1219 commits. If it rolls back then there is no conflict. If it commits
1220 without deleting the conflicting row again, there is a uniqueness
1221 violation. (In practice we just wait for the other transaction to
1222 end and then redo the visibility check in toto.)
1223 </para>
1224 </listitem>
1225 <listitem>
1226 <para>
1227 Similarly, if a conflicting valid row has been deleted by an
1228 as-yet-uncommitted transaction, the would-be inserter must wait
1229 for that transaction to commit or abort, and then repeat the test.
1230 </para>
1231 </listitem>
1232 </itemizedlist>
1233 </para>
1234
1235 <para>
1236 Furthermore, immediately before reporting a uniqueness violation
1237 according to the above rules, the access method must recheck the
1238 liveness of the row being inserted. If it is committed dead then
1239 no violation should be reported. (This case cannot occur during the
1240 ordinary scenario of inserting a row that's just been created by
1241 the current transaction. It can happen during
1242 <command>CREATE UNIQUE INDEX CONCURRENTLY</command>, however.)
1243 </para>
1244
1245 <para>
1246 We require the index access method to apply these tests itself, which
1247 means that it must reach into the heap to check the commit status of
1248 any row that is shown to have a duplicate key according to the index
1249 contents. This is without a doubt ugly and non-modular, but it saves
1250 redundant work: if we did a separate probe then the index lookup for
1251 a conflicting row would be essentially repeated while finding the place to
1252 insert the new row's index entry. What's more, there is no obvious way
1253 to avoid race conditions unless the conflict check is an integral part
1254 of insertion of the new index entry.
1255 </para>
1256
1257 <para>
1258 If the unique constraint is deferrable, there is additional complexity:
1259 we need to be able to insert an index entry for a new row, but defer any
1260 uniqueness-violation error until end of statement or even later. To
1261 avoid unnecessary repeat searches of the index, the index access method
1262 should do a preliminary uniqueness check during the initial insertion.
1263 If this shows that there is definitely no conflicting live tuple, we
1264 are done. Otherwise, we schedule a recheck to occur when it is time to
1265 enforce the constraint. If, at the time of the recheck, both the inserted
1266 tuple and some other tuple with the same key are live, then the error
1267 must be reported. (Note that for this purpose, <quote>live</quote> actually
1268 means <quote>any tuple in the index entry's HOT chain is live</quote>.)
1269 To implement this, the <function>aminsert</function> function is passed a
1270 <literal>checkUnique</literal> parameter having one of the following values:
1271
1272 <itemizedlist>
1273 <listitem>
1274 <para>
1275 <literal>UNIQUE_CHECK_NO</literal> indicates that no uniqueness checking
1276 should be done (this is not a unique index).
1277 </para>
1278 </listitem>
1279 <listitem>
1280 <para>
1281 <literal>UNIQUE_CHECK_YES</literal> indicates that this is a non-deferrable
1282 unique index, and the uniqueness check must be done immediately, as
1283 described above.
1284 </para>
1285 </listitem>
1286 <listitem>
1287 <para>
1288 <literal>UNIQUE_CHECK_PARTIAL</literal> indicates that the unique
1289 constraint is deferrable. <productname>PostgreSQL</productname>
1290 will use this mode to insert each row's index entry. The access
1291 method must allow duplicate entries into the index, and report any
1292 potential duplicates by returning false from <function>aminsert</function>.
1293 For each row for which false is returned, a deferred recheck will
1294 be scheduled.
1295 </para>
1296
1297 <para>
1298 The access method must identify any rows which might violate the
1299 unique constraint, but it is not an error for it to report false
1300 positives. This allows the check to be done without waiting for other
1301 transactions to finish; conflicts reported here are not treated as
1302 errors and will be rechecked later, by which time they may no longer
1303 be conflicts.
1304 </para>
1305 </listitem>
1306 <listitem>
1307 <para>
1308 <literal>UNIQUE_CHECK_EXISTING</literal> indicates that this is a deferred
1309 recheck of a row that was reported as a potential uniqueness violation.
1310 Although this is implemented by calling <function>aminsert</function>, the
1311 access method must <emphasis>not</emphasis> insert a new index entry in this
1312 case. The index entry is already present. Rather, the access method
1313 must check to see if there is another live index entry. If so, and
1314 if the target row is also still live, report error.
1315 </para>
1316
1317 <para>
1318 It is recommended that in a <literal>UNIQUE_CHECK_EXISTING</literal> call,
1319 the access method further verify that the target row actually does
1320 have an existing entry in the index, and report error if not. This
1321 is a good idea because the index tuple values passed to
1322 <function>aminsert</function> will have been recomputed. If the index
1323 definition involves functions that are not really immutable, we
1324 might be checking the wrong area of the index. Checking that the
1325 target row is found in the recheck verifies that we are scanning
1326 for the same tuple values as were used in the original insertion.
1327 </para>
1328 </listitem>
1329 </itemizedlist>
1330 </para>
1331
1332 </sect1>
1333
1334 <sect1 id="index-cost-estimation">
1335 <title>Index Cost Estimation Functions</title>
1336
1337 <para>
1338 The <function>amcostestimate</function> function is given information describing
1339 a possible index scan, including lists of WHERE and ORDER BY clauses that
1340 have been determined to be usable with the index. It must return estimates
1341 of the cost of accessing the index and the selectivity of the WHERE
1342 clauses (that is, the fraction of parent-table rows that will be
1343 retrieved during the index scan). For simple cases, nearly all the
1344 work of the cost estimator can be done by calling standard routines
1345 in the optimizer; the point of having an <function>amcostestimate</function> function is
1346 to allow index access methods to provide index-type-specific knowledge,
1347 in case it is possible to improve on the standard estimates.
1348 </para>
1349
1350 <para>
1351 Each <function>amcostestimate</function> function must have the signature:
1352
1353 <programlisting>
1354 void
1355 amcostestimate (PlannerInfo *root,
1356 IndexPath *path,
1357 double loop_count,
1358 Cost *indexStartupCost,
1359 Cost *indexTotalCost,
1360 Selectivity *indexSelectivity,
1361 double *indexCorrelation,
1362 double *indexPages);
1363 </programlisting>
1364
1365 The first three parameters are inputs:
1366
1367 <variablelist>
1368 <varlistentry>
1369 <term><parameter>root</parameter></term>
1370 <listitem>
1371 <para>
1372 The planner's information about the query being processed.
1373 </para>
1374 </listitem>
1375 </varlistentry>
1376
1377 <varlistentry>
1378 <term><parameter>path</parameter></term>
1379 <listitem>
1380 <para>
1381 The index access path being considered. All fields except cost and
1382 selectivity values are valid.
1383 </para>
1384 </listitem>
1385 </varlistentry>
1386
1387 <varlistentry>
1388 <term><parameter>loop_count</parameter></term>
1389 <listitem>
1390 <para>
1391 The number of repetitions of the index scan that should be factored
1392 into the cost estimates. This will typically be greater than one when
1393 considering a parameterized scan for use in the inside of a nestloop
1394 join. Note that the cost estimates should still be for just one scan;
1395 a larger <parameter>loop_count</parameter> means that it may be appropriate
1396 to allow for some caching effects across multiple scans.
1397 </para>
1398 </listitem>
1399 </varlistentry>
1400 </variablelist>
1401 </para>
1402
1403 <para>
1404 The last five parameters are pass-by-reference outputs:
1405
1406 <variablelist>
1407 <varlistentry>
1408 <term><parameter>*indexStartupCost</parameter></term>
1409 <listitem>
1410 <para>
1411 Set to cost of index start-up processing
1412 </para>
1413 </listitem>
1414 </varlistentry>
1415
1416 <varlistentry>
1417 <term><parameter>*indexTotalCost</parameter></term>
1418 <listitem>
1419 <para>
1420 Set to total cost of index processing
1421 </para>
1422 </listitem>
1423 </varlistentry>
1424
1425 <varlistentry>
1426 <term><parameter>*indexSelectivity</parameter></term>
1427 <listitem>
1428 <para>
1429 Set to index selectivity
1430 </para>
1431 </listitem>
1432 </varlistentry>
1433
1434 <varlistentry>
1435 <term><parameter>*indexCorrelation</parameter></term>
1436 <listitem>
1437 <para>
1438 Set to correlation coefficient between index scan order and
1439 underlying table's order
1440 </para>
1441 </listitem>
1442 </varlistentry>
1443
1444 <varlistentry>
1445 <term><parameter>*indexPages</parameter></term>
1446 <listitem>
1447 <para>
1448 Set to number of index leaf pages
1449 </para>
1450 </listitem>
1451 </varlistentry>
1452 </variablelist>
1453 </para>
1454
1455 <para>
1456 Note that cost estimate functions must be written in C, not in SQL or
1457 any available procedural language, because they must access internal
1458 data structures of the planner/optimizer.
1459 </para>
1460
1461 <para>
1462 The index access costs should be computed using the parameters used by
1463 <filename>src/backend/optimizer/path/costsize.c</filename>: a sequential
1464 disk block fetch has cost <varname>seq_page_cost</varname>, a nonsequential fetch
1465 has cost <varname>random_page_cost</varname>, and the cost of processing one index
1466 row should usually be taken as <varname>cpu_index_tuple_cost</varname>. In
1467 addition, an appropriate multiple of <varname>cpu_operator_cost</varname> should
1468 be charged for any comparison operators invoked during index processing
1469 (especially evaluation of the indexquals themselves).
1470 </para>
1471
1472 <para>
1473 The access costs should include all disk and CPU costs associated with
1474 scanning the index itself, but <emphasis>not</emphasis> the costs of retrieving or
1475 processing the parent-table rows that are identified by the index.
1476 </para>
1477
1478 <para>
1479 The <quote>start-up cost</quote> is the part of the total scan cost that
1480 must be expended before we can begin to fetch the first row. For most
1481 indexes this can be taken as zero, but an index type with a high start-up
1482 cost might want to set it nonzero.
1483 </para>
1484
1485 <para>
1486 The <parameter>indexSelectivity</parameter> should be set to the estimated fraction of the parent
1487 table rows that will be retrieved during the index scan. In the case
1488 of a lossy query, this will typically be higher than the fraction of
1489 rows that actually pass the given qual conditions.
1490 </para>
1491
1492 <para>
1493 The <parameter>indexCorrelation</parameter> should be set to the correlation (ranging between
1494 -1.0 and 1.0) between the index order and the table order. This is used
1495 to adjust the estimate for the cost of fetching rows from the parent
1496 table.
1497 </para>
1498
1499 <para>
1500 The <parameter>indexPages</parameter> should be set to the number of leaf pages.
1501 This is used to estimate the number of workers for parallel index scan.
1502 </para>
1503
1504 <para>
1505 When <parameter>loop_count</parameter> is greater than one, the returned numbers
1506 should be averages expected for any one scan of the index.
1507 </para>
1508
1509 <procedure>
1510 <title>Cost Estimation</title>
1511 <para>
1512 A typical cost estimator will proceed as follows:
1513 </para>
1514
1515 <step>
1516 <para>
1517 Estimate and return the fraction of parent-table rows that will be visited
1518 based on the given qual conditions. In the absence of any index-type-specific
1519 knowledge, use the standard optimizer function <function>clauselist_selectivity()</function>:
1520
1521 <programlisting>
1522 *indexSelectivity = clauselist_selectivity(root, path-&gt;indexquals,
1523 path-&gt;indexinfo-&gt;rel-&gt;relid,
1524 JOIN_INNER, NULL);
1525 </programlisting>
1526 </para>
1527 </step>
1528
1529 <step>
1530 <para>
1531 Estimate the number of index rows that will be visited during the
1532 scan. For many index types this is the same as <parameter>indexSelectivity</parameter> times
1533 the number of rows in the index, but it might be more. (Note that the
1534 index's size in pages and rows is available from the
1535 <literal>path-&gt;indexinfo</literal> struct.)
1536 </para>
1537 </step>
1538
1539 <step>
1540 <para>
1541 Estimate the number of index pages that will be retrieved during the scan.
1542 This might be just <parameter>indexSelectivity</parameter> times the index's size in pages.
1543 </para>
1544 </step>
1545
1546 <step>
1547 <para>
1548 Compute the index access cost. A generic estimator might do this:
1549
1550 <programlisting>
1551 /*
1552 * Our generic assumption is that the index pages will be read
1553 * sequentially, so they cost seq_page_cost each, not random_page_cost.
1554 * Also, we charge for evaluation of the indexquals at each index row.
1555 * All the costs are assumed to be paid incrementally during the scan.
1556 */
1557 cost_qual_eval(&amp;index_qual_cost, path-&gt;indexquals, root);
1558 *indexStartupCost = index_qual_cost.startup;
1559 *indexTotalCost = seq_page_cost * numIndexPages +
1560 (cpu_index_tuple_cost + index_qual_cost.per_tuple) * numIndexTuples;
1561 </programlisting>
1562
1563 However, the above does not account for amortization of index reads
1564 across repeated index scans.
1565 </para>
1566 </step>
1567
1568 <step>
1569 <para>
1570 Estimate the index correlation. For a simple ordered index on a single
1571 field, this can be retrieved from pg_statistic. If the correlation
1572 is not known, the conservative estimate is zero (no correlation).
1573 </para>
1574 </step>
1575 </procedure>
1576
1577 <para>
1578 Examples of cost estimator functions can be found in
1579 <filename>src/backend/utils/adt/selfuncs.c</filename>.
1580 </para>
1581 </sect1>
1582 </chapter>