indexam.sgml

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

   remains the same.  This function is also called by
   <function>RelationGetIndexScan()</>, so it is used for initial setup
   of an index scan as well as rescanning.
  </para>

  <para>
<programlisting>
void
amendscan (IndexScanDesc scan);
</programlisting>
   End a scan and release resources.  The <literal>scan</> struct itself
   should not be freed, but any locks or pins taken internally by the
   access method must be released.
  </para>

  <para>
<programlisting>
void
ammarkpos (IndexScanDesc scan);
</programlisting>
   Mark current scan position.  The access method need only support one
   remembered scan position per scan.
  </para>

  <para>
<programlisting>
void
amrestrpos (IndexScanDesc scan);
</programlisting>
   Restore the scan to the most recently marked position.
  </para>

  <para>
<programlisting>
void
amcostestimate (PlannerInfo *root,
                IndexOptInfo *index,
                List *indexQuals,
                Cost *indexStartupCost,
                Cost *indexTotalCost,
                Selectivity *indexSelectivity,
                double *indexCorrelation);
</programlisting>
   Estimate the costs of an index scan.  This function is described fully
   in <xref linkend="index-cost-estimation">, below.
  </para>

  <para>
   By convention, the <literal>pg_proc</literal> entry for any index
   access method function should show the correct number of arguments,
   but declare them all as type <type>internal</> (since most of the arguments
   have types that are not known to SQL, and we don't want users calling
   the functions directly anyway).  The return type is declared as
   <type>void</>, <type>internal</>, or <type>boolean</> as appropriate.
  </para>

 </sect1>

 <sect1 id="index-scanning">
  <title>Index Scanning</title>

  <para>
   In an index scan, the index access method is responsible for regurgitating
   the TIDs of all the tuples it has been told about that match the
   <firstterm>scan keys</>.  The access method is <emphasis>not</> involved in
   actually fetching those tuples from the index's parent table, nor in
   determining whether they pass the scan's time qualification test or other
   conditions.
  </para>

  <para>
   A scan key is the internal representation of a <literal>WHERE</> clause of
   the form <replaceable>index_key</> <replaceable>operator</>
   <replaceable>constant</>, where the index key is one of the columns of the
   index and the operator is one of the members of the operator class
   associated with that index column.  An index scan has zero or more scan
   keys, which are implicitly ANDed &mdash; the returned tuples are expected
   to satisfy all the indicated conditions.
  </para>

  <para>
   The operator class may indicate that the index is <firstterm>lossy</> for a
   particular operator; this implies that the index scan will return all the
   entries that pass the scan key, plus possibly additional entries that do
   not.  The core system's index-scan machinery will then apply that operator
   again to the heap tuple to verify whether or not it really should be
   selected.  For non-lossy operators, the index scan must return exactly the
   set of matching entries, as there is no recheck.
  </para>

  <para>
   Note that it is entirely up to the access method to ensure that it
   correctly finds all and only the entries passing all the given scan keys.
   Also, the core system will simply hand off all the <literal>WHERE</>
   clauses that match the index keys and operator classes, without any
   semantic analysis to determine whether they are redundant or
   contradictory.  As an example, given
   <literal>WHERE x &gt; 4 AND x &gt; 14</> where <literal>x</> is a b-tree
   indexed column, it is left to the b-tree <function>amrescan</> function
   to realize that the first scan key is redundant and can be discarded.
   The extent of preprocessing needed during <function>amrescan</> will
   depend on the extent to which the index access method needs to reduce
   the scan keys to a <quote>normalized</> form.
  </para>

  <para>
   The <function>amgettuple</> function has a <literal>direction</> argument,
   which can be either <literal>ForwardScanDirection</> (the normal case)
   or  <literal>BackwardScanDirection</>.  If the first call after
   <function>amrescan</> specifies <literal>BackwardScanDirection</>, then the
   set of matching index entries is to be scanned back-to-front rather than in
   the normal front-to-back direction, so <function>amgettuple</> must return
   the last matching tuple in the index, rather than the first one as it
   normally would.  (This will only occur for access
   methods that advertise they support ordered scans by setting
   <structname>pg_am</>.<structfield>amorderstrategy</> nonzero.)  After the
   first call, <function>amgettuple</> must be prepared to advance the scan in
   either direction from the most recently returned entry.
  </para>

  <para>
   The access method must support <quote>marking</> a position in a scan
   and later returning to the marked position.  The same position may be
   restored multiple times.  However, only one position need be remembered
   per scan; a new <function>ammarkpos</> call overrides the previously
   marked position.
  </para>

  <para>
   Both the scan position and the mark position (if any) must be maintained
   consistently in the face of concurrent insertions or deletions in the
   index.  It is OK if a freshly-inserted entry is not returned by a scan that
   would have found the entry if it had existed when the scan started, or for
   the scan to return such an entry upon rescanning or backing
   up even though it had not been returned the first time through.  Similarly,
   a concurrent delete may or may not be reflected in the results of a scan.
   What is important is that insertions or deletions not cause the scan to
   miss or multiply return entries that were not themselves being inserted or
   deleted.  (For an index type that does not set
   <structname>pg_am</>.<structfield>amconcurrent</>, it is sufficient to
   handle these cases for insertions or deletions performed by the same
   backend that's doing the scan.  But when <structfield>amconcurrent</> is
   true, insertions or deletions from other backends must be handled as well.)
  </para>

  <para>
   Instead of using <function>amgettuple</>, an index scan can be done with 
   <function>amgetmulti</> to fetch multiple tuples per call.  This can be
   noticeably more efficient than <function>amgettuple</> because it allows
   avoiding lock/unlock cycles within the access method.  In principle
   <function>amgetmulti</> should have the same effects as repeated
   <function>amgettuple</> calls, but we impose several restrictions to
   simplify matters.  In the first place, <function>amgetmulti</> does not
   take a <literal>direction</> argument, and therefore it does not support
   backwards scan nor intrascan reversal of direction.  The access method
   need not support marking or restoring scan positions during an
   <function>amgetmulti</> scan, either.  (These restrictions cost little
   since it would be difficult to use these features in an
   <function>amgetmulti</> scan anyway: adjusting the caller's buffered
   list of TIDs would be complex.)  Finally, <function>amgetmulti</> does
   not guarantee any locking of the returned tuples, with implications
   spelled out in <xref linkend="index-locking">.
  </para>

 </sect1>

 <sect1 id="index-locking">
  <title>Index Locking Considerations</title>

  <para>
   An index access method can choose whether it supports concurrent updates
   of the index by multiple processes.  If the method's
   <structname>pg_am</>.<structfield>amconcurrent</> flag is true, then
   the core <productname>PostgreSQL</productname> system obtains
   <literal>AccessShareLock</> on the index during an index scan, and
   <literal>RowExclusiveLock</> when updating the index.  Since these lock
   types do not conflict, the access method is responsible for handling any
   fine-grained locking it may need.  An exclusive lock on the index as a whole
   will be taken only during index creation, destruction, or
   <literal>REINDEX</>.  When <structfield>amconcurrent</> is false,
   <productname>PostgreSQL</productname> still obtains
   <literal>AccessShareLock</> during index scans, but it obtains
   <literal>AccessExclusiveLock</> during any update.  This ensures that
   updaters have sole use of the index.  Note that this implicitly assumes
   that index scans are read-only; an access method that might modify the
   index during a scan will still have to do its own locking to handle the
   case of concurrent scans.
  </para>

  <para>
   Recall that a backend's own locks never conflict; therefore, even a
   non-concurrent index type must be prepared to handle the case where
   a backend is inserting or deleting entries in an index that it is itself
   scanning.  (This is of course necessary to support an <command>UPDATE</>
   that uses the index to find the rows to be updated.)
  </para>

  <para>
   Building an index type that supports concurrent updates usually requires
   extensive and subtle analysis of the required behavior.  For the b-tree
   and hash index types, you can read about the design decisions involved in
   <filename>src/backend/access/nbtree/README</> and
   <filename>src/backend/access/hash/README</>.
  </para>

  <para>
   Aside from the index's own internal consistency requirements, concurrent
   updates create issues about consistency between the parent table (the
   <firstterm>heap</>) and the index.  Because
   <productname>PostgreSQL</productname> separates accesses 
   and updates of the heap from those of the index, there are windows in
   which the index may be inconsistent with the heap.  We handle this problem
   with the following rules:

    <itemizedlist>
     <listitem>
      <para>
       A new heap entry is made before making its index entries.  (Therefore
       a concurrent index scan is likely to fail to see the heap entry.
       This is okay because the index reader would be uninterested in an
       uncommitted row anyway.  But see <xref linkend="index-unique-checks">.)
      </para>
     </listitem>
     <listitem>
      <para>
       When a heap entry is to be deleted (by <command>VACUUM</>), all its
       index entries must be removed first.
      </para>
     </listitem>
     <listitem>
      <para>
       For concurrent index types, an index scan must maintain a pin
       on the index page holding the item last returned by
       <function>amgettuple</>, and <function>ambulkdelete</> cannot delete
       entries from pages that are pinned by other backends.  The need
       for this rule is explained below.
      </para>
     </listitem>
    </itemizedlist>

   If an index is concurrent then it is possible for an index reader to
   see an index entry just before it is removed by <command>VACUUM</>, and
   then to arrive at the corresponding heap entry after that was removed by
   <command>VACUUM</>.  (With a nonconcurrent index, this is not possible
   because of the conflicting index-level locks that will be taken out.)
   This creates no serious problems if that item
   number is still unused when the reader reaches it, since an empty
   item slot will be ignored by <function>heap_fetch()</>.  But what if a
   third backend has already re-used the item slot for something else?
   When using an MVCC-compliant snapshot, there is no problem because
   the new occupant of the slot is certain to be too new to pass the
   snapshot test.  However, with a non-MVCC-compliant snapshot (such as
   <literal>SnapshotNow</>), it would be possible to accept and return
   a row that does not in fact match the scan keys.  We could defend
   against this scenario by requiring the scan keys to be rechecked
   against the heap row in all cases, but that is too expensive.  Instead,
   we use a pin on an index page as a proxy to indicate that the reader
   may still be <quote>in flight</> from the index entry to the matching
   heap entry.  Making <function>ambulkdelete</> block on such a pin ensures
   that <command>VACUUM</> cannot delete the heap entry before the reader
   is done with it.  This solution costs little in run time, and adds blocking
   overhead only in the rare cases where there actually is a conflict.
  </para>

  <para>
   This solution requires that index scans be <quote>synchronous</>: we have
   to fetch each heap tuple immediately after scanning the corresponding index
   entry.  This is expensive for a number of reasons.  An
   <quote>asynchronous</> scan in which we collect many TIDs from the index,
   and only visit the heap tuples sometime later, requires much less index
   locking overhead and may allow a more efficient heap access pattern.
   Per the above analysis, we must use the synchronous approach for
   non-MVCC-compliant snapshots, but an asynchronous scan is workable
   for a query using an MVCC snapshot.
  </para>

  <para>
   In an <function>amgetmulti</> index scan, the access method need not
   guarantee to keep an index pin on any of the returned tuples.  (It would be
   impractical to pin more than the last one anyway.)  Therefore
   it is only safe to use such scans with MVCC-compliant snapshots.
  </para>

 </sect1>

 <sect1 id="index-unique-checks">
  <title>Index Uniqueness Checks</title>

  <para>
   <productname>PostgreSQL</productname> enforces SQL uniqueness constraints
   using <firstterm>unique indexes</>, which are indexes that disallow
   multiple entries with identical keys.  An access method that supports this
   feature sets <structname>pg_am</>.<structfield>amcanunique</> true.
   (At present, only b-tree supports it.)
  </para>