begriffs open source - ai-pg/blob - full-docs/txt/index-scanning.txt

   1
   2 63.3. Index Scanning #
   3
   4    In an index scan, the index access method is responsible for
   5    regurgitating the TIDs of all the tuples it has been told about that
   6    match the scan keys. The access method is not involved in actually
   7    fetching those tuples from the index's parent table, nor in determining
   8    whether they pass the scan's visibility test or other conditions.
   9
  10    A scan key is the internal representation of a WHERE clause of the form
  11    index_key operator constant, where the index key is one of the columns
  12    of the index and the operator is one of the members of the operator
  13    family associated with that index column. An index scan has zero or
  14    more scan keys, which are implicitly ANDed — the returned tuples are
  15    expected to satisfy all the indicated conditions.
  16
  17    The access method can report that the index is lossy, or requires
  18    rechecks, for a particular query. This implies that the index scan will
  19    return all the entries that pass the scan key, plus possibly additional
  20    entries that do not. The core system's index-scan machinery will then
  21    apply the index conditions again to the heap tuple to verify whether or
  22    not it really should be selected. If the recheck option is not
  23    specified, the index scan must return exactly the set of matching
  24    entries.
  25
  26    Note that it is entirely up to the access method to ensure that it
  27    correctly finds all and only the entries passing all the given scan
  28    keys. Also, the core system will simply hand off all the WHERE clauses
  29    that match the index keys and operator families, without any semantic
  30    analysis to determine whether they are redundant or contradictory. As
  31    an example, given WHERE x > 4 AND x > 14 where x is a b-tree indexed
  32    column, it is left to the b-tree amrescan function to realize that the
  33    first scan key is redundant and can be discarded. The extent of
  34    preprocessing needed during amrescan will depend on the extent to which
  35    the index access method needs to reduce the scan keys to a “normalized”
  36    form.
  37
  38    Some access methods return index entries in a well-defined order,
  39    others do not. There are actually two different ways that an access
  40    method can support sorted output:
  41      * Access methods that always return entries in the natural ordering
  42        of their data (such as btree) should set amcanorder to true.
  43        Currently, such access methods must use btree-compatible strategy
  44        numbers for their equality and ordering operators.
  45      * Access methods that support ordering operators should set
  46        amcanorderbyop to true. This indicates that the index is capable of
  47        returning entries in an order satisfying ORDER BY index_key
  48        operator constant. Scan modifiers of that form can be passed to
  49        amrescan as described previously.
  50
  51    The amgettuple function has a direction argument, which can be either
  52    ForwardScanDirection (the normal case) or BackwardScanDirection. If the
  53    first call after amrescan specifies BackwardScanDirection, then the set
  54    of matching index entries is to be scanned back-to-front rather than in
  55    the normal front-to-back direction, so amgettuple must return the last
  56    matching tuple in the index, rather than the first one as it normally
  57    would. (This will only occur for access methods that set amcanorder to
  58    true.) After the first call, amgettuple must be prepared to advance the
  59    scan in either direction from the most recently returned entry. (But if
  60    amcanbackward is false, all subsequent calls will have the same
  61    direction as the first one.)
  62
  63    Access methods that support ordered scans must support “marking” a
  64    position in a scan and later returning to the marked position. The same
  65    position might be restored multiple times. However, only one position
  66    need be remembered per scan; a new ammarkpos call overrides the
  67    previously marked position. An access method that does not support
  68    ordered scans need not provide ammarkpos and amrestrpos functions in
  69    IndexAmRoutine; set those pointers to NULL instead.
  70
  71    Both the scan position and the mark position (if any) must be
  72    maintained consistently in the face of concurrent insertions or
  73    deletions in the index. It is OK if a freshly-inserted entry is not
  74    returned by a scan that would have found the entry if it had existed
  75    when the scan started, or for the scan to return such an entry upon
  76    rescanning or backing up even though it had not been returned the first
  77    time through. Similarly, a concurrent delete might or might not be
  78    reflected in the results of a scan. What is important is that
  79    insertions or deletions not cause the scan to miss or multiply return
  80    entries that were not themselves being inserted or deleted.
  81
  82    If the index stores the original indexed data values (and not some
  83    lossy representation of them), it is useful to support index-only
  84    scans, in which the index returns the actual data not just the TID of
  85    the heap tuple. This will only avoid I/O if the visibility map shows
  86    that the TID is on an all-visible page; else the heap tuple must be
  87    visited anyway to check MVCC visibility. But that is no concern of the
  88    access method's.
  89
  90    Instead of using amgettuple, an index scan can be done with amgetbitmap
  91    to fetch all tuples in one call. This can be noticeably more efficient
  92    than amgettuple because it allows avoiding lock/unlock cycles within
  93    the access method. In principle amgetbitmap should have the same
  94    effects as repeated amgettuple calls, but we impose several
  95    restrictions to simplify matters. First of all, amgetbitmap returns all
  96    tuples at once and marking or restoring scan positions isn't supported.
  97    Secondly, the tuples are returned in a bitmap which doesn't have any
  98    specific ordering, which is why amgetbitmap doesn't take a direction
  99    argument. (Ordering operators will never be supplied for such a scan,
 100    either.) Also, there is no provision for index-only scans with
 101    amgetbitmap, since there is no way to return the contents of index
 102    tuples. Finally, amgetbitmap does not guarantee any locking of the
 103    returned tuples, with implications spelled out in Section 63.4.
 104
 105    Note that it is permitted for an access method to implement only
 106    amgetbitmap and not amgettuple, or vice versa, if its internal
 107    implementation is unsuited to one API or the other.