On 09/02/16 07:15, Andrew Borodin wrote:
Hi, hackers!
I want to propose improvement of GiST page layout.
GiST is optimized to reduce disk operations on search queries, for
example, windows search queries in case of R-tree.
I expect that more complicated page layout will help to tradeoff some
of CPU efficiency for disk efficiency.
GiST tree is a balanced tree structure with two kinds of pages:
internal pages and leaf pages. Each tree page contains bunch of tuples
with the same structure. Tuples of an internal page reference other
pages of the same tree, while a leaf page tuples holds heap TIDs.
During execution of search query GiST for each tuple on page invokes
key comparison algorithm with two possible outcomes: 'no' and 'may
be'. 'May be' answer recursively descends search algorithms to
referenced page (in case of internal page) or yields tuple (in case of
leaf page).
Expected tuples count on page is around of tenth to hundreds. This
count is big enough to try to save some cache lines from loading into
CPU during enumeration.
For B-trees during inspection of a page we effectively apply binary
search algorithm, which is not possible in GiST tree.
Let's consider R-tree with arbitrary fan-out f. If a given query will
find exactly one data tuple, it is easily to show that keys comparison
count is minimal if f->e /*round_to_optimal(2.78) == 3*/ (tree have to
review f*h keys, h=logf(N), f*logf(N) is minimal when f->e). Smaller
keys comparison count means less cache lines are touched. So fan-out
reduction means cache pressure reduction (except avg fan-out 2, which
seems to be too small) and less time waiting for RAM. I suppose, all
that reasoning holds true in a cases when not just one tuple will be
found.
GiST comparison operators tend to be quite expensive, so I suspect much
of the gain is simply from reducing the number of comparisons, rather
than cache efficiency. The conclusion is the same though, so it doesn't
matter.
How do we reduce tree fan-out? Obviously, we can’t fill page with just
3 tuples. But we can install small tree-like structure inside one
page. General GiST index has root page. But a page tree should have
“root” layer of tuples. Private (or internal, intermediate, auxiliary,
I can’t pick precise word) tuples have only keys and fixed-size(F)
array of underlying records offsets. Each layer is linked-list. After
page have just been allocated there is only “ground” level of regular
tuples. Eventually record count reaches F-1 and we create new root
layer with two tuples. Each new tuple references half of preexisting
records. Placement of new “ground” tuples on page eventually will
cause internal tuple to split. If there is not enough space to spilt
internal tuple we mark page for whole page-split during next iteration
of insertion algorithms of owning tree. That is why tuple-spilt
happens on F-1 tuples, not on F: if we have no space for splitting, we
just adding reference to last slot. In this algorithm, page split will
cause major page defragmentation: we take root layer, halve it and
place halves on different pages. When half of a data is gone to other
page, restructuration should tend to place records in such a fashion
that accessed together tuples lie together. I think, placing whole
level together is a good strategy.
Yeah, something like that would make a lot of sense. I've actually been
thinking of this same idea myself over the years, but never got around
to implement it.
I'm not wedded to that particular layout, it seems a bit complicated. A
two-level setup within each page might be good enough in practice: there
would regular tuples, like today, and also "container" tuples, which
represent a group of regular tuples. Also note that you can freely move
tuples around in a page, so instead of storing an actual array of
offsets with the container tuples, you could store just a range of line
pointers, and keep all the child tuples packed together.
I wonder if it's really a good idea to perform page split by simply
using the "container" tuples. It certainly saves CPU time when
splitting, but I'm worried that the split might not be as good as today.
The mini-groups within the page are grown "organically" as tuples are
inserted, and the page split algorithm might come up with a better
grouping if it sees all the tuples at once.
I expect that implementation of this proposal could speed up
insertions into index by 20% and performance of queries by 30% when
all index accommodates in shared buffer. In case of buffer starvation,
when index is accessed through disk this feature will cause 15%
performance degrade since effective page capacity will be smaller.
Not sure how you got those numbers, but the general direction sounds right.
Should this feature be configurable? May be this should be other
access method?
I think this should be included in GiST, and always enabled. Or at least
enabled by default. While the index will be slightly larger because of
the extra tuples, it'd almost always be a good tradeoff.
I need help to assess amount for work TDB. WAL redo, vacuum, bulk
index construction: what else parts are touched and have to be
reconstructed?
Something to keep in mind is pg_upgrade. The new code needs to still be
able to read the old disk format. That means that it's easier to keep
the page format as close to the current format as possible, and there
needs to be a version number or something that you can use to
distinguish the old and new format pages.
Overall, +1 for pursuing this idea!
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
