Indexes with INCLUDE columns and their support in B-tree

This patch introduces INCLUDE clause to index definition.  This clause
specifies a list of columns which will be included as a non-key part in
the index.  The INCLUDE columns exist solely to allow more queries to
benefit from index-only scans.  Also, such columns don't need to have
appropriate operator classes.  Expressions are not supported as INCLUDE
columns since they cannot be used in index-only scans.

Index access methods supporting INCLUDE are indicated by amcaninclude flag
in IndexAmRoutine.  For now, only B-tree indexes support INCLUDE clause.

In B-tree indexes INCLUDE columns are truncated from pivot index tuples
(tuples located in non-leaf pages and high keys).  Therefore, B-tree indexes
now might have variable number of attributes.  This patch also provides
generic facility to support that: pivot tuples contain number of their
attributes in t_tid.ip_posid.  Free 13th bit of t_info is used for indicating
that.  This facility will simplify further support of index suffix truncation.
The changes of above are backward-compatible, pg_upgrade doesn't need special
handling of B-tree indexes for that.

Bump catalog version

Author: Anastasia Lubennikova with contribition by Alexander Korotkov and me
Reviewed by: Peter Geoghegan, Tomas Vondra, Antonin Houska, Jeff Janes,
			 David Rowley, Alexander Korotkov
Discussion: https://www.postgresql.org/message-id/flat/[email protected]

1 files changed, 17 insertions, 0 deletions

diff --git a/doc/src/sgml/btree.sgml b/doc/src/sgml/btree.sgml
index 10abf90189e..ca81fbbc848 100644
--- a/doc/src/sgml/btree.sgml
+++ b/doc/src/sgml/btree.sgml
@@ -433,6 +433,23 @@ returns bool
 
 </sect1>
 
+<sect1 id="btree-included-attributes">
+ <title>Included attributes in B-tree indexes</title>
+
+ <para>
+  As of <productname>PostgreSQL</productname> 11.0 there is an optional
+  INCLUDE clause, which allows to add non-key (included) attributes to index.
+  Those included attributes allow more queries to benefit from index-only scans.
+  We never use included attributes in ScanKeys for search.  That allows us to
+  include into B-tree any datatypes, even those which don't have suitable
+  operator classes.  Included columns only stored in regular tuples on leaf
+  pages.  All pivot tuples on non-leaf pages and highkey tuples are truncated
+  to contain only key attributes.  That helps to slightly reduce the size of
+  index.
+ </para>
+
+</sect1>
+
 <sect1 id="btree-implementation">
  <title>Implementation</title>