Support index-only scans using the visibility map to avoid heap fetches.

When a btree index contains all columns required by the query, and the
visibility map shows that all tuples on a target heap page are
visible-to-all, we don't need to fetch that heap page.  This patch depends
on the previous patches that made the visibility map reliable.

There's a fair amount left to do here, notably trying to figure out a less
chintzy way of estimating the cost of an index-only scan, but the core
functionality seems ready to commit.

Robert Haas and Ibrar Ahmed, with some previous work by Heikki Linnakangas.

10 files changed, 54 insertions, 28 deletions

diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index 7154ae385ba..dd62680dd54 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -144,6 +144,9 @@ extern void index_rescan(IndexScanDesc scan,
 extern void index_endscan(IndexScanDesc scan);
 extern void index_markpos(IndexScanDesc scan);
 extern void index_restrpos(IndexScanDesc scan);
+extern ItemPointer index_getnext_tid(IndexScanDesc scan,
+				  ScanDirection direction);
+extern HeapTuple index_fetch_heap(IndexScanDesc scan);
 extern HeapTuple index_getnext(IndexScanDesc scan, ScanDirection direction);
 extern int64 index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap);
 
diff --git a/src/include/access/relscan.h b/src/include/access/relscan.h
index 57d08b9656e..656aefcceec 100644
--- a/src/include/access/relscan.h
+++ b/src/include/access/relscan.h
@@ -16,6 +16,7 @@
 
 #include "access/genam.h"
 #include "access/heapam.h"
+#include "access/itup.h"
 
 
 typedef struct HeapScanDescData
@@ -66,6 +67,7 @@ typedef struct IndexScanDescData
 	int			numberOfOrderBys;		/* number of ordering operators */
 	ScanKey		keyData;		/* array of index qualifier descriptors */
 	ScanKey		orderByData;	/* array of ordering op descriptors */
+	bool		xs_want_itup;	/* caller requests index tuples */
 
 	/* signaling to index AM about killing index tuples */
 	bool		kill_prior_tuple;		/* last-returned tuple is dead */
@@ -76,6 +78,9 @@ typedef struct IndexScanDescData
 	/* index access method's private state */
 	void	   *opaque;			/* access-method-specific info */
 
+	/* in an index-only scan, this is valid after a successful amgettuple */
+	IndexTuple	xs_itup;		/* index tuple returned by AM, or NULL */
+
 	/* xs_ctup/xs_cbuf/xs_recheck are valid after a successful index_getnext */
 	HeapTupleData xs_ctup;		/* current heap tuple, if any */
 	Buffer		xs_cbuf;		/* current heap buffer in scan, if any */
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index f3c8bb41422..e4eb7b1294f 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201109071
+#define CATALOG_VERSION_NO	201110071
 
 #endif
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index feab4201deb..c3c864f95f5 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -45,6 +45,7 @@ CATALOG(pg_am,2601)
 	bool		amcanbackward;	/* does AM support backward scan? */
 	bool		amcanunique;	/* does AM support UNIQUE indexes? */
 	bool		amcanmulticol;	/* does AM support multi-column indexes? */
+	bool		amcanreturn;	/* can AM return IndexTuples? */
 	bool		amoptionalkey;	/* can query omit key for the first column? */
 	bool		amsearchnulls;	/* can AM search for NULL/NOT NULL entries? */
 	bool		amstorage;		/* can storage type differ from column type? */
@@ -78,7 +79,7 @@ typedef FormData_pg_am *Form_pg_am;
  *		compiler constants for pg_am
  * ----------------
  */
-#define Natts_pg_am						28
+#define Natts_pg_am						29
 #define Anum_pg_am_amname				1
 #define Anum_pg_am_amstrategies			2
 #define Anum_pg_am_amsupport			3
@@ -87,42 +88,43 @@ typedef FormData_pg_am *Form_pg_am;
 #define Anum_pg_am_amcanbackward		6
 #define Anum_pg_am_amcanunique			7
 #define Anum_pg_am_amcanmulticol		8
-#define Anum_pg_am_amoptionalkey		9
-#define Anum_pg_am_amsearchnulls		10
-#define Anum_pg_am_amstorage			11
-#define Anum_pg_am_amclusterable		12
-#define Anum_pg_am_ampredlocks			13
-#define Anum_pg_am_amkeytype			14
-#define Anum_pg_am_aminsert				15
-#define Anum_pg_am_ambeginscan			16
-#define Anum_pg_am_amgettuple			17
-#define Anum_pg_am_amgetbitmap			18
-#define Anum_pg_am_amrescan				19
-#define Anum_pg_am_amendscan			20
-#define Anum_pg_am_ammarkpos			21
-#define Anum_pg_am_amrestrpos			22
-#define Anum_pg_am_ambuild				23
-#define Anum_pg_am_ambuildempty			24
-#define Anum_pg_am_ambulkdelete			25
-#define Anum_pg_am_amvacuumcleanup		26
-#define Anum_pg_am_amcostestimate		27
-#define Anum_pg_am_amoptions			28
+#define Anum_pg_am_amcanreturn			9
+#define Anum_pg_am_amoptionalkey		10
+#define Anum_pg_am_amsearchnulls		11
+#define Anum_pg_am_amstorage			12
+#define Anum_pg_am_amclusterable		13
+#define Anum_pg_am_ampredlocks			14
+#define Anum_pg_am_amkeytype			15
+#define Anum_pg_am_aminsert				16
+#define Anum_pg_am_ambeginscan			17
+#define Anum_pg_am_amgettuple			18
+#define Anum_pg_am_amgetbitmap			19
+#define Anum_pg_am_amrescan				20
+#define Anum_pg_am_amendscan			21
+#define Anum_pg_am_ammarkpos			22
+#define Anum_pg_am_amrestrpos			23
+#define Anum_pg_am_ambuild				24
+#define Anum_pg_am_ambuildempty			25
+#define Anum_pg_am_ambulkdelete			26
+#define Anum_pg_am_amvacuumcleanup		27
+#define Anum_pg_am_amcostestimate		28
+#define Anum_pg_am_amoptions			29
 
 /* ----------------
  *		initial contents of pg_am
  * ----------------
  */
 
-DATA(insert OID = 403 (  btree	5 1 t f t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete btvacuumcleanup btcostestimate btoptions ));
+DATA(insert OID = 403 (  btree	5 1 t f t t t t t t f t t 0 btinsert btbeginscan btgettuple btgetbitmap btrescan btendscan btmarkpos btrestrpos btbuild btbuildempty btbulkdelete btvacuumcleanup btcostestimate btoptions ));
 DESCR("b-tree index access method");
 #define BTREE_AM_OID 403
-DATA(insert OID = 405 (  hash	1 1 f f t f f f f f f f 23 hashinsert hashbeginscan hashgettuple hashgetbitmap hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbuildempty hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions ));
+DATA(insert OID = 405 (  hash	1 1 f f t f f f f f f f f 23 hashinsert hashbeginscan hashgettuple hashgetbitmap hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbuildempty hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions ));
 DESCR("hash index access method");
 #define HASH_AM_OID 405
-DATA(insert OID = 783 (  gist	0 8 f t f f t t t t t f 0 gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbuildempty gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
+DATA(insert OID = 783 (  gist	0 8 f t f f t f t t t t f 0 gistinsert gistbeginscan gistgettuple gistgetbitmap gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbuildempty gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
 DESCR("GiST index access method");
 #define GIST_AM_OID 783
-DATA(insert OID = 2742 (  gin	0 5 f f f f t t f t f f 0 gininsert ginbeginscan - gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbuildempty ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
+DATA(insert OID = 2742 (  gin	0 5 f f f f t f t f t f f 0 gininsert ginbeginscan - gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbuildempty ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
 DESCR("GIN index access method");
 #define GIN_AM_OID 2742
 
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index c8a0b598645..3885fa0099d 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1226,6 +1226,7 @@ typedef struct
  *		RuntimeContext	   expr context for evaling runtime Skeys
  *		RelationDesc	   index relation descriptor
  *		ScanDesc		   index scan descriptor
+ *		VMBuffer		   buffer in use for visibility map testing, if any
  * ----------------
  */
 typedef struct IndexScanState
@@ -1242,6 +1243,7 @@ typedef struct IndexScanState
 	ExprContext *iss_RuntimeContext;
 	Relation	iss_RelationDesc;
 	IndexScanDesc iss_ScanDesc;
+	Buffer		iss_VMBuffer;
 } IndexScanState;
 
 /* ----------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 535eca77a7e..60467f52769 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -300,6 +300,10 @@ typedef Scan SeqScan;
  * that the sort ordering is fully determinable from the top-level operators.
  * indexorderbyorig is unused at run time, but is needed for EXPLAIN.
  * (Note these fields are used for amcanorderbyop cases, not amcanorder cases.)
+ *
+ * indexorderdir specifies the scan ordering, for indexscans on amcanorder
+ * indexes (for other indexes it should be "don't care").  indexonly specifies
+ * an index-only scan, for indexscans on amcanreturn indexes.
  * ----------------
  */
 typedef struct IndexScan
@@ -311,6 +315,7 @@ typedef struct IndexScan
 	List	   *indexorderby;	/* list of index ORDER BY exprs */
 	List	   *indexorderbyorig;		/* the same in original form */
 	ScanDirection indexorderdir;	/* forward or backward or don't care */
+	bool		indexonly;		/* attempt to skip heap fetches? */
 } IndexScan;
 
 /* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index ecbbc1cd39a..cf48ba433c8 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -482,6 +482,7 @@ typedef struct IndexOptInfo
 	bool		unique;			/* true if a unique index */
 	bool		hypothetical;	/* true if index doesn't really exist */
 	bool		amcanorderbyop; /* does AM support order by operator result? */
+	bool		amcanreturn;	/* does AM know how to return tuples? */
 	bool		amoptionalkey;	/* can query omit key for the first column? */
 	bool		amsearchnulls;	/* can AM search for NULL/NOT NULL entries? */
 	bool		amhasgettuple;	/* does AM have amgettuple interface? */
@@ -672,6 +673,10 @@ typedef struct Path
  * NoMovementScanDirection for an indexscan, but the planner wants to
  * distinguish ordered from unordered indexes for building pathkeys.)
  *
+ * 'indexonly' is TRUE for an index-only scan, that is, the index's access
+ * method has amcanreturn = TRUE and we only need columns available from the
+ * index.
+ *
  * 'indextotalcost' and 'indexselectivity' are saved in the IndexPath so that
  * we need not recompute them when considering using the same index in a
  * bitmap index/heap scan (see BitmapHeapPath).  The costs of the IndexPath
@@ -693,6 +698,7 @@ typedef struct IndexPath
 	List	   *indexorderbys;
 	bool		isjoininner;
 	ScanDirection indexscandir;
+	bool		indexonly;
 	Cost		indextotalcost;
 	Selectivity indexselectivity;
 	double		rows;			/* estimated number of result tuples */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 604df335d2d..125808ae980 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -52,6 +52,7 @@ extern PGDLLIMPORT int effective_cache_size;
 extern Cost disable_cost;
 extern bool enable_seqscan;
 extern bool enable_indexscan;
+extern bool enable_indexonlyscan;
 extern bool enable_bitmapscan;
 extern bool enable_tidscan;
 extern bool enable_sort;
@@ -67,7 +68,8 @@ extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
 					double index_pages, PlannerInfo *root);
 extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
 extern void cost_index(IndexPath *path, PlannerInfo *root, IndexOptInfo *index,
-		   List *indexQuals, List *indexOrderBys, RelOptInfo *outer_rel);
+		   List *indexQuals, List *indexOrderBys,
+		   bool indexonly, RelOptInfo *outer_rel);
 extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
 					  Path *bitmapqual, RelOptInfo *outer_rel);
 extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index ee02732fe1c..38c8c1c9a35 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -34,6 +34,7 @@ extern IndexPath *create_index_path(PlannerInfo *root,
 				  List *indexorderbys,
 				  List *pathkeys,
 				  ScanDirection indexscandir,
+				  bool indexonly,
 				  RelOptInfo *outer_rel);
 extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
 						RelOptInfo *rel,
diff --git a/src/include/optimizer/var.h b/src/include/optimizer/var.h
index 5d7e2d93e91..4fd0052f2df 100644
--- a/src/include/optimizer/var.h
+++ b/src/include/optimizer/var.h
@@ -31,7 +31,7 @@ typedef enum
 } PVCPlaceHolderBehavior;
 
 extern Relids pull_varnos(Node *node);
-extern void pull_varattnos(Node *node, Bitmapset **varattnos);
+extern void pull_varattnos(Node *node, Index varno, Bitmapset **varattnos);
 extern bool contain_var_clause(Node *node);
 extern bool contain_vars_of_level(Node *node, int levelsup);
 extern int	locate_var_of_level(Node *node, int levelsup);