pgsql: Indexes with INCLUDE columns and their support in B-tree

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/56168952(dot)4010101(at)postgrespro(dot)ru

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/8224de4f42ccf98e08db07b43d52fed72f962ebb

Modified Files
--------------
contrib/amcheck/expected/check_btree.out | 46 +++
contrib/amcheck/sql/check_btree.sql | 19 ++
contrib/amcheck/verify_nbtree.c | 98 +++++-
contrib/bloom/blutils.c | 1 +
contrib/dblink/dblink.c | 26 +-
contrib/dblink/expected/dblink.out | 55 ++++
contrib/dblink/sql/dblink.sql | 38 +++
contrib/tcn/tcn.c | 6 +-
doc/src/sgml/btree.sgml | 17 +
doc/src/sgml/catalogs.sgml | 12 +-
doc/src/sgml/indexam.sgml | 5 +-
doc/src/sgml/indices.sgml | 7 +-
doc/src/sgml/ref/create_index.sgml | 62 +++-
doc/src/sgml/ref/create_table.sgml | 33 +-
src/backend/access/brin/brin.c | 1 +
src/backend/access/common/indextuple.c | 31 ++
src/backend/access/gin/ginutil.c | 1 +
src/backend/access/gist/gist.c | 1 +
src/backend/access/hash/hash.c | 1 +
src/backend/access/heap/heapam.c | 4 +-
src/backend/access/index/genam.c | 19 +-
src/backend/access/nbtree/README | 17 +
src/backend/access/nbtree/nbtinsert.c | 119 ++++---
src/backend/access/nbtree/nbtpage.c | 23 +-
src/backend/access/nbtree/nbtree.c | 1 +
src/backend/access/nbtree/nbtsearch.c | 63 +++-
src/backend/access/nbtree/nbtsort.c | 52 +++-
src/backend/access/nbtree/nbtutils.c | 54 +++-
src/backend/access/nbtree/nbtxlog.c | 34 +-
src/backend/access/rmgrdesc/nbtdesc.c | 8 +
src/backend/access/spgist/spgutils.c | 1 +
src/backend/bootstrap/bootparse.y | 2 +
src/backend/bootstrap/bootstrap.c | 2 +-
src/backend/catalog/heap.c | 3 +-
src/backend/catalog/index.c | 86 +++--
src/backend/catalog/indexing.c | 1 +
src/backend/catalog/pg_constraint.c | 27 +-
src/backend/catalog/toasting.c | 1 +
src/backend/commands/indexcmds.c | 63 +++-
src/backend/commands/matview.c | 6 +-
src/backend/commands/tablecmds.c | 9 +-
src/backend/commands/trigger.c | 1 +
src/backend/commands/typecmds.c | 1 +
src/backend/executor/execIndexing.c | 14 +-
src/backend/executor/execReplication.c | 6 +-
src/backend/executor/nodeIndexscan.c | 8 +-
src/backend/nodes/copyfuncs.c | 2 +
src/backend/nodes/equalfuncs.c | 2 +
src/backend/nodes/outfuncs.c | 4 +
src/backend/optimizer/README | 10 +-
src/backend/optimizer/path/indxpath.c | 2 +-
src/backend/optimizer/path/pathkeys.c | 13 +-
src/backend/optimizer/util/plancat.c | 33 +-
src/backend/parser/analyze.c | 6 +-
src/backend/parser/gram.y | 65 ++--
src/backend/parser/parse_relation.c | 2 +-
src/backend/parser/parse_target.c | 3 +-
src/backend/parser/parse_utilcmd.c | 340 ++++++++++++++------
src/backend/utils/adt/ruleutils.c | 31 ++
src/backend/utils/adt/selfuncs.c | 4 +-
src/backend/utils/cache/relcache.c | 87 +++---
src/backend/utils/sort/tuplesort.c | 5 +-
src/bin/pg_dump/pg_dump.c | 40 ++-
src/bin/pg_dump/pg_dump.h | 6 +-
src/include/access/amapi.h | 2 +
src/include/access/hash.h | 2 +-
src/include/access/itup.h | 7 +-
src/include/access/nbtree.h | 91 ++++--
src/include/access/nbtxlog.h | 12 +-
src/include/catalog/catversion.h | 2 +-
src/include/catalog/pg_constraint.h | 23 +-
src/include/catalog/pg_constraint_fn.h | 1 +
src/include/catalog/pg_index.h | 38 +--
src/include/nodes/execnodes.h | 9 +-
src/include/nodes/parsenodes.h | 7 +-
src/include/nodes/relation.h | 13 +-
src/include/parser/kwlist.h | 1 +
src/include/utils/rel.h | 16 +-
.../specs/insert-conflict-do-nothing-2.spec | 2 +-
.../specs/insert-conflict-do-update-2.spec | 2 +-
.../isolation/specs/lock-committed-keyupdate.spec | 2 +-
.../isolation/specs/lock-update-traversal.spec | 5 +-
src/test/regress/expected/create_index.out | 19 ++
src/test/regress/expected/index_including.out | 346 +++++++++++++++++++++
src/test/regress/parallel_schedule | 2 +-
src/test/regress/serial_schedule | 1 +
src/test/regress/sql/create_index.sql | 20 ++
src/test/regress/sql/index_including.sql | 203 ++++++++++++
src/test/subscription/t/001_rep_changes.pl | 19 +-
89 files changed, 2115 insertions(+), 470 deletions(-)