| 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 — 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->ii_Context</literal> and store a pointer to the |
| 380 |
data in <literal>indexInfo->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->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->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->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->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->xs_itup</literal>, |
| 729 |
with tuple descriptor <literal>scan->xs_itupdesc</literal>; or in the form of |
| 730 |
a <structname>HeapTuple</structname> pointer stored at <literal>scan->xs_hitup</literal>, |
| 731 |
with tuple descriptor <literal>scan->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 — 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 > 4 AND x > 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->indexquals, |
| 1523 |
path->indexinfo->rel->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->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(&index_qual_cost, path->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> |