<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <HTML ><HEAD ><TITLE >Index Scanning</TITLE ><META NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK REV="MADE" HREF="mailto:pgsql-docs@postgresql.org"><LINK REL="HOME" TITLE="PostgreSQL 8.4.12 Documentation" HREF="index.html"><LINK REL="UP" TITLE="Index Access Method Interface Definition" HREF="indexam.html"><LINK REL="PREVIOUS" TITLE="Index Access Method Functions" HREF="index-functions.html"><LINK REL="NEXT" TITLE="Index Locking Considerations" HREF="index-locking.html"><LINK REL="STYLESHEET" TYPE="text/css" HREF="stylesheet.css"><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"><META NAME="creation" CONTENT="2012-05-31T23:30:11"></HEAD ><BODY CLASS="SECT1" ><DIV CLASS="NAVHEADER" ><TABLE SUMMARY="Header navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TH COLSPAN="5" ALIGN="center" VALIGN="bottom" >PostgreSQL 8.4.12 Documentation</TH ></TR ><TR ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="index-functions.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="indexam.html" >Fast Backward</A ></TD ><TD WIDTH="60%" ALIGN="center" VALIGN="bottom" >Chapter 50. Index Access Method Interface Definition</TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="indexam.html" >Fast Forward</A ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="index-locking.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="SECT1" ><H1 CLASS="SECT1" ><A NAME="INDEX-SCANNING" >50.3. Index Scanning</A ></H1 ><P > 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 <I CLASS="FIRSTTERM" >scan keys</I >. The access method is <SPAN CLASS="emphasis" ><I CLASS="EMPHASIS" >not</I ></SPAN > 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. </P ><P > A scan key is the internal representation of a <TT CLASS="LITERAL" >WHERE</TT > clause of the form <TT CLASS="REPLACEABLE" ><I >index_key</I ></TT > <TT CLASS="REPLACEABLE" ><I >operator</I ></TT > <TT CLASS="REPLACEABLE" ><I >constant</I ></TT >, where the index key is one of the columns of the index and the operator is one of the members of the operator family associated with that index column. An index scan has zero or more scan keys, which are implicitly ANDed — the returned tuples are expected to satisfy all the indicated conditions. </P ><P > The access method can report that the index is <I CLASS="FIRSTTERM" >lossy</I >, or requires rechecks, for a particular query. 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 the index conditions again to the heap tuple to verify whether or not it really should be selected. If the recheck option is not specified, the index scan must return exactly the set of matching entries. </P ><P > 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 <TT CLASS="LITERAL" >WHERE</TT > clauses that match the index keys and operator families, without any semantic analysis to determine whether they are redundant or contradictory. As an example, given <TT CLASS="LITERAL" >WHERE x > 4 AND x > 14</TT > where <TT CLASS="LITERAL" >x</TT > is a b-tree indexed column, it is left to the b-tree <CODE CLASS="FUNCTION" >amrescan</CODE > function to realize that the first scan key is redundant and can be discarded. The extent of preprocessing needed during <CODE CLASS="FUNCTION" >amrescan</CODE > will depend on the extent to which the index access method needs to reduce the scan keys to a <SPAN CLASS="QUOTE" >"normalized"</SPAN > form. </P ><P > Some access methods return index entries in a well-defined order, others do not. If entries are returned in sorted order, the access method should set <TT CLASS="STRUCTNAME" >pg_am</TT >.<TT CLASS="STRUCTFIELD" >amcanorder</TT > true to indicate that it supports ordered scans. All such access methods must use btree-compatible strategy numbers for their equality and ordering operators. </P ><P > The <CODE CLASS="FUNCTION" >amgettuple</CODE > function has a <TT CLASS="LITERAL" >direction</TT > argument, which can be either <TT CLASS="LITERAL" >ForwardScanDirection</TT > (the normal case) or <TT CLASS="LITERAL" >BackwardScanDirection</TT >. If the first call after <CODE CLASS="FUNCTION" >amrescan</CODE > specifies <TT CLASS="LITERAL" >BackwardScanDirection</TT >, then the set of matching index entries is to be scanned back-to-front rather than in the normal front-to-back direction, so <CODE CLASS="FUNCTION" >amgettuple</CODE > 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.) After the first call, <CODE CLASS="FUNCTION" >amgettuple</CODE > must be prepared to advance the scan in either direction from the most recently returned entry. (But if <TT CLASS="STRUCTNAME" >pg_am</TT >.<TT CLASS="STRUCTFIELD" >amcanbackward</TT > is false, all subsequent calls will have the same direction as the first one.) </P ><P > Access methods that support ordered scans must support <SPAN CLASS="QUOTE" >"marking"</SPAN > a position in a scan and later returning to the marked position. The same position might be restored multiple times. However, only one position need be remembered per scan; a new <CODE CLASS="FUNCTION" >ammarkpos</CODE > call overrides the previously marked position. An access method that does not support ordered scans should still provide mark and restore functions in <TT CLASS="STRUCTNAME" >pg_am</TT >, but it is sufficient to have them throw errors if called. </P ><P > 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 might or might 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. </P ><P > Instead of using <CODE CLASS="FUNCTION" >amgettuple</CODE >, an index scan can be done with <CODE CLASS="FUNCTION" >amgetbitmap</CODE > to fetch all tuples in one call. This can be noticeably more efficient than <CODE CLASS="FUNCTION" >amgettuple</CODE > because it allows avoiding lock/unlock cycles within the access method. In principle <CODE CLASS="FUNCTION" >amgetbitmap</CODE > should have the same effects as repeated <CODE CLASS="FUNCTION" >amgettuple</CODE > calls, but we impose several restrictions to simplify matters. First of all, <CODE CLASS="FUNCTION" >amgetbitmap</CODE > returns all tuples at once and marking or restoring scan positions isn't supported. Secondly, the tuples are returned in a bitmap which doesn't have any specific ordering, which is why <CODE CLASS="FUNCTION" >amgetbitmap</CODE > doesn't take a <TT CLASS="LITERAL" >direction</TT > argument. Finally, <CODE CLASS="FUNCTION" >amgetbitmap</CODE > does not guarantee any locking of the returned tuples, with implications spelled out in <A HREF="index-locking.html" >Section 50.4</A >. </P ><P > Note that it is permitted for an access method to implement only <CODE CLASS="FUNCTION" >amgetbitmap</CODE > and not <CODE CLASS="FUNCTION" >amgettuple</CODE >, or vice versa, if its internal implementation is unsuited to one API or the other. </P ></DIV ><DIV CLASS="NAVFOOTER" ><HR ALIGN="LEFT" WIDTH="100%"><TABLE SUMMARY="Footer navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><A HREF="index-functions.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="index.html" ACCESSKEY="H" >Home</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" ><A HREF="index-locking.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" >Index Access Method Functions</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="indexam.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Index Locking Considerations</TD ></TR ></TABLE ></DIV ></BODY ></HTML >