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

Started by Teodor Sigaevabout 8 years ago13 messagescomitters
Jump to latest
#1Teodor Sigaev
teodor@sigaev.ru

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: /messages/by-id/56168952.4010101@postgrespro.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(-)

#2Erik Rijkers
er@xs4all.nl
In reply to: Teodor Sigaev (#1)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On 2018-04-07 22:01, Teodor Sigaev wrote:

Indexes with INCLUDE columns and their support in B-tree

Author: Anastasia Lubennikova with contribition by Alexander Korotkov
and me
Reviewed by: Peter Geoghegan, Tomas Vondra, Antonin Houska, Jeff Janes,
David Rowley, Alexander Korotkov

I've put quite some time in testing this patch, and although I don't
really mind not being mentioned, I think it's better to err on the side
of including too many names than too few.

Erik Rijkers

#3Teodor Sigaev
teodor@sigaev.ru
In reply to: Erik Rijkers (#2)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

Ooops, sorry, if it possible, I'd like to change list of reviewers to
add you, but I don't know how do it.

Nevertheless, thank you very much for your work

BTW, I miss Andrey Borodin in that list too...

Erik Rijkers wrote:

On 2018-04-07 22:01, Teodor Sigaev wrote:

Indexes with INCLUDE columns and their support in B-tree

Author: Anastasia Lubennikova with contribition by Alexander Korotkov
and me
Reviewed by: Peter Geoghegan, Tomas Vondra, Antonin Houska, Jeff Janes,
О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫О©╫ David Rowley, Alexander Korotkov

I've put quite some time in testing this patch, and although I don't
really mind not being mentioned, I think it's better to err on the side
of including too many names than too few.

Erik Rijkers

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

#4Erik Rijkers
er@xs4all.nl
In reply to: Teodor Sigaev (#3)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On 2018-04-07 22:51, Teodor Sigaev wrote:

Ooops, sorry, if it possible, I'd like to change list of reviewers to
add you, but I don't know how do it.

No problem, really.

Thanks, great feature! I'm glad it got in.

#5Andrey Borodin
amborodin@acm.org
In reply to: Teodor Sigaev (#3)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

8 апр. 2018 г., в 1:51, Teodor Sigaev <teodor@sigaev.ru> написал(а):

Ooops, sorry, if it possible, I'd like to change list of reviewers to add you, but I don't know how do it.

Nevertheless, thank you very much for your work

BTW, I miss Andrey Borodin in that list too...

No problem :) Thanks for pushing this!

Best regards, Andrey Borodin.

#6Tom Lane
tgl@sss.pgh.pa.us
In reply to: Teodor Sigaev (#1)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

Teodor Sigaev <teodor@sigaev.ru> writes:

Indexes with INCLUDE columns and their support in B-tree

The valgrind-using animals seem to think this broke stuff.
There are at least two different problems here:

https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=lousyjack&amp;dt=2018-04-07%2020%3A03%3A02

regards, tom lane

#7Alexander Korotkov
aekorotkov@gmail.com
In reply to: Tom Lane (#6)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On Sun, Apr 8, 2018 at 5:41 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Teodor Sigaev <teodor@sigaev.ru> writes:

Indexes with INCLUDE columns and their support in B-tree

The valgrind-using animals seem to think this broke stuff.
There are at least two different problems here:

https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=
lousyjack&dt=2018-04-07%2020%3A03%3A02

I think attached patch should fix one of those problems.
We should match clauses to only key columns of index.
I will further investigate the problem with CheckIndexCompatible().

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Attachments:

covering-fix-match-clause-to-indexcol.patchapplication/octet-stream; name=covering-fix-match-clause-to-indexcol.patchDownload+1-1
#8Teodor Sigaev
teodor@sigaev.ru
In reply to: Alexander Korotkov (#7)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

Thank you, pushed

Alexander Korotkov wrote:

On Sun, Apr 8, 2018 at 5:41 PM, Tom Lane <tgl@sss.pgh.pa.us
<mailto:tgl@sss.pgh.pa.us>> wrote:

Teodor Sigaev <teodor@sigaev.ru <mailto:teodor@sigaev.ru>> writes:

Indexes with INCLUDE columns and their support in B-tree

The valgrind-using animals seem to think this broke stuff.
There are at least two different problems here:

https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=lousyjack&amp;dt=2018-04-07%2020%3A03%3A02
<https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=lousyjack&amp;dt=2018-04-07%2020%3A03%3A02&gt;

I think attached patch should fix one of those problems.
We should match clauses to only key columns of index.
I will further investigate the problem with CheckIndexCompatible().

------
Alexander Korotkov
Postgres Professional:http://www.postgrespro.com
<http://www.postgrespro.com/&gt;
The Russian Postgres Company

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

#9Alexander Korotkov
aekorotkov@gmail.com
In reply to: Teodor Sigaev (#8)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On Sun, Apr 8, 2018 at 7:58 PM, Teodor Sigaev <teodor@sigaev.ru> wrote:

Thank you, pushed

Thank you!

There is also patch for valgrind error in CheckIndexCompatible().
It appears that this function didn't initialize ii_NumIndexAttrs and
ii_NumIndexKeyAttrs before calling ComputeIndexAttrs(). This
variables weren't used before, but now they're used to determine
whether index column is key. Also, this patch makes ComputeIndexAttrs()
initialize classOidP elements with InvalidOid for non-key attributes.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Attachments:

covering-fix-compute-index-attrs.patchapplication/octet-stream; name=covering-fix-compute-index-attrs.patchDownload+6-1
#10Tom Lane
tgl@sss.pgh.pa.us
In reply to: Alexander Korotkov (#9)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

Alexander Korotkov <a.korotkov@postgrespro.ru> writes:

There is also patch for valgrind error in CheckIndexCompatible().
It appears that this function didn't initialize ii_NumIndexAttrs and
ii_NumIndexKeyAttrs before calling ComputeIndexAttrs(). This
variables weren't used before, but now they're used to determine
whether index column is key. Also, this patch makes ComputeIndexAttrs()
initialize classOidP elements with InvalidOid for non-key attributes.

You didn't test this quite enough, because when I tried it I got a batch
of warnings about memory chunk inconsistencies. The reason was that
DefineIndex only allocated a classObjectId array large enough for the
key columns, so that the change in ComputeIndexAttrs made it write past
the end of that array. But I think it's a good idea to make those output
arrays all the same length, so I kept that change and changed DefineIndex.

Pushed; I've not checked to see if this makes valgrind happy, but
the buildfarm will tell us.

regards, tom lane

#11Alexander Korotkov
aekorotkov@gmail.com
In reply to: Tom Lane (#10)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On Mon, Apr 9, 2018 at 12:27 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Alexander Korotkov <a.korotkov@postgrespro.ru> writes:

There is also patch for valgrind error in CheckIndexCompatible().
It appears that this function didn't initialize ii_NumIndexAttrs and
ii_NumIndexKeyAttrs before calling ComputeIndexAttrs(). This
variables weren't used before, but now they're used to determine
whether index column is key. Also, this patch makes ComputeIndexAttrs()
initialize classOidP elements with InvalidOid for non-key attributes.

You didn't test this quite enough, because when I tried it I got a batch
of warnings about memory chunk inconsistencies. The reason was that
DefineIndex only allocated a classObjectId array large enough for the
key columns, so that the change in ComputeIndexAttrs made it write past
the end of that array.

Sorry, my bad.

But I think it's a good idea to make those output

arrays all the same length, so I kept that change and changed DefineIndex.

Pushed; I've not checked to see if this makes valgrind happy, but
the buildfarm will tell us.

Thank you!

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

#12Peter Eisentraut
peter_e@gmx.net
In reply to: Teodor Sigaev (#1)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

On 4/7/18 16:01, Teodor Sigaev wrote:

Indexes with INCLUDE columns and their support in B-tree

pg_dump from <8.2 servers is now failing.

The last branch in getIndexes() is not producing the required
indnkeyatts column.

--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#13Teodor Sigaev
teodor@sigaev.ru
In reply to: Peter Eisentraut (#12)
Re: pgsql: Indexes with INCLUDE columns and their support in B-tree

Thank you, will see

Peter Eisentraut wrote:

On 4/7/18 16:01, Teodor Sigaev wrote:

Indexes with INCLUDE columns and their support in B-tree

pg_dump from <8.2 servers is now failing.

The last branch in getIndexes() is not producing the required
indnkeyatts column.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/