Обсуждение: pgsql: Add support for building GiST index by sorting.

Add support for building GiST index by sorting.

This adds a new optional support function to the GiST access method:
sortsupport. If it is defined, the GiST index is built by sorting all data
to the order defined by the sortsupport's comparator function, and packing
the tuples in that order to GiST pages. This is similar to how B-tree
index build works, and is much faster than inserting the tuples one by
one. The resulting index is smaller too, because the pages are packed more
tightly, upto 'fillfactor'. The normal build method works by splitting
pages, which tends to lead to more wasted space.

The quality of the resulting index depends on how good the opclass-defined
sort order is. A good order preserves locality of the input data.

As the first user of this facility, add 'sortsupport' function to the
point_ops opclass. It sorts the points in Z-order (aka Morton Code), by
interleaving the bits of the X and Y coordinates.

Author: Andrey Borodin
Reviewed-by: Pavel Borisov, Thomas Munro
Discussion: https://www.postgresql.org/message-id/1A36620E-CAD8-4267-9067-FB31385E7C0D%40yandex-team.ru

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/16fa9b2b30a357b4aea982bd878ec2e5e002dbcc

Modified Files
--------------
doc/src/sgml/gist.sgml                     |  70 ++++
src/backend/access/gist/gistbuild.c        | 510 ++++++++++++++++++++++++-----
src/backend/access/gist/gistproc.c         | 229 +++++++++++++
src/backend/access/gist/gistutil.c         |  53 ++-
src/backend/access/gist/gistvalidate.c     |   6 +-
src/backend/access/transam/xloginsert.c    |  57 ++++
src/backend/utils/sort/sortsupport.c       |  34 ++
src/backend/utils/sort/tuplesort.c         |  57 ++++
src/include/access/gist.h                  |   3 +-
src/include/access/gist_private.h          |   3 +
src/include/access/xloginsert.h            |   2 +
src/include/catalog/catversion.h           |   1 +
src/include/catalog/pg_amproc.dat          |   2 +
src/include/catalog/pg_proc.dat            |   3 +
src/include/utils/sortsupport.h            |   1 +
src/include/utils/tuplesort.h              |   4 +
src/test/regress/expected/create_index.out |   6 +-
17 files changed, 935 insertions(+), 106 deletions(-)

On Thu, Sep 17, 2020 at 1:34 AM Heikki Linnakangas
<heikki.linnakangas@iki.fi> wrote:
> Add support for building GiST index by sorting.

You forgot to bump catversion, despite your best efforts.  :-)

You left this behind:

+/* FIXME: bump this before pushing! */

I have settled on a system for this: I write myself a reminder on a
prominently placed post-it note, days in advance of commit. I rarely
have to bump catversion (due to the kinds of things I work on), and
iso t's just too easy to forget any other way.

-- 
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:
> On Thu, Sep 17, 2020 at 1:34 AM Heikki Linnakangas
> <heikki.linnakangas@iki.fi> wrote:
>> Add support for building GiST index by sorting.

> You forgot to bump catversion, despite your best efforts.  :-)
> You left this behind:
> +/* FIXME: bump this before pushing! */

Yeah, I noticed that, and just fixed it while pushing something else.

            regards, tom lane

On 17/09/2020 23:07, Peter Geoghegan wrote:
> On Thu, Sep 17, 2020 at 1:34 AM Heikki Linnakangas
> <heikki.linnakangas@iki.fi> wrote:
>> Add support for building GiST index by sorting.
> 
> You forgot to bump catversion, despite your best efforts.  :-)
> 
> You left this behind:
> 
> +/* FIXME: bump this before pushing! */
> 
> I have settled on a system for this: I write myself a reminder on a
> prominently placed post-it note, days in advance of commit. I rarely
> have to bump catversion (due to the kinds of things I work on), and
> iso t's just too easy to forget any other way.

D'oh! I think I'm going to write a git post-push hook for this. 
Apparently even a FIXME comment in the code is not enough of a reminder 
to me.

Thanks for fixing it, Tom.

- Heikki