[WiP] GiST intrapage indexing

From: Andrey Borodin <x4mmm(at)yandex-team(dot)ru>
To: PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org>
Cc: Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>, Oleg Bartunov <obartunov(at)gmail(dot)com>, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
Subject: [WiP] GiST intrapage indexing
Date: 2018-02-12 06:46:31
Message-ID: 7780A07B-4D04-41E2-B228-166B41D07EEE@yandex-team.ru
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Hi, hackers!

Few years ago I've posted proposal [0] to improve GiST performance by building small GiST inside each GiST page.
Currently each page is just an unordered vector of tuples. Scan is testing each tuple one by one. This causes suboptimal performance for both inserts and searches.
I've attached patch with intrapage indexing to this message.

==How it works==
The patch implements two-level scheme (thanks to Heikki for the suggestion to give up multilevel scheme - it'd take forever to debug). Among regular tuples, page contains so-called skip tuples. Skip tuple does not have tid, but instead has counter of tuples, whose keys this tuple covers (thanks to Alexander for this suggestions - earliest versions of the patch had to pg_upgrade).
When the page is scanned, if key of skip tuples does not match - all the group is skipped.
When GiST is choosing subtree - if given skiptuple has penalty more than already found - it is skipped. Here I rely on the assumption that adjusted (extended) key have penalty always less or equal to not adjusted tuple (each tuple in it's group).
When GiST is splitting page - if possible it splits by skipgroups.

Currently, skip tuples are placed only on intrapages. This is a tradeoff in favor of inserts and scans, searching for big amount of data.
Skiptuples are first formed when new root is created. Then, skiptuple count grows when group overgrowth threshold of 16 tuples - it is splitted by regular split algorithm.

1. Buffered build does not create skip tuples as for now
2. KNN searches do not take advantage of skiptuples. Current approach of KNN scan has node lookup overhead suitable for page-size nodes, but in case of skipgroups this overhead may be just too much. I've not tested though. I'm trying to compose some lean hacks for KNN with skipgroups.
3. More scrupulous performance testing needed

Currently I observe 30-40% gain in performance of inserts, independently of datatype and distribution.
On grid-alligned points I observe about 5-10% improvement of searches.
On randomized points I do not observe statistically significant improvement of searches.
I expect that this technology will protect GiST from degradation on big block sizes (thanks to Oleg for suggestion)

Currently, patch is stable, passes all my test and checkworlds, WAL seems to work. Though, it is "work in progress".

Best regards, Andrey Borodin.

[0] https://www.postgresql.org/message-id/CAJEAwVE0rrr%2BOBT-P0gDCtXbVDkBBG_WcXwCBK%3DGHo4fewu3Yg%40mail.gmail.com <https://www.postgresql.org/message-id/CAJEAwVE0rrr+OBT-P0gDCtXbVDkBBG_WcXwCBK=GHo4fewu3Yg@mail.gmail.com>

Browse pgsql-hackers by date

  From Date Subject
Next Message Pavan Deolasee 2018-02-12 07:09:28 Re: [HACKERS] MERGE SQL Statement for PG11
Previous Message Bruce Momjian 2018-02-12 06:28:53 Re: proposal: alternative psql commands quit and exit