NBTree Prefix Truncation

== Prefix truncation ==
Prefix truncation allows us to skip saving duplicated data, and
potentially skip comparing these duplicated attributes. This can be
a huge win for multi-column indexes where not all attributes can be
safely deduplicated, and for inner pages of indexes with a lot of
duplicate prefixes (e.g. non-unique indexes, and multi-column
indexes).
In this research document, we truncate away attributes of index
tuples that they share when compared to a reference index tuple, and
store the count of truncated attributes in the tuple. As
btree-indexes have an absolute limit of 2^12 - 1 columns (as of this
moment), this count should not take more than 2 bytes. Prefix
truncation, when correctly applied, will therefore start saving data
once the 2 first bytes of a tuple can be truncated away.
Once we've compared the truncated columns of a tuple, we can reuse
the compare-result of these columns for other tuples that have been
truncated with the same reference tuple. This allows us to
potentially improve the binary search efficiency of pages by a large
margin without getting into problems with concurrent page deletion
(as detailed in ).
== Prefix truncation relative to an arbitrary tuple ==
You could truncate attributes away based on the attributes shared by
your right (or left) neighbour tuple.
This, however has the following limitations:
=== 1.) Tuple delete efficiency ===
When the attribute is extracted from an arbitrary sibling index
tuple, tuple deletion can become a O(n) operation, because it needs
to check all tuples on the page, and potentially update all of them
to point to a different index tuple.
=== 2.) Tuple attribute extraction efficiency ===
When a prefix-truncated tuple points to another tuple to indicate
where the truncated attributes are stored, and this other tuple may
also be truncated, this makes an attribute lookup effectively
traversing a linked list, which is O(n).
This issue can be solved by having all tuples prefix-truncated against a single static tuple on that page. A good
candidate is the highkey - it is available on all pages except the
rightmost on each level, and is positioned at a well-known offset.
== Prefix truncation relative to the page highkey ==
The HighKey is a static value on each page, and can only become more
specific to that page through page splits. Page deletions will grow
the key space, but as deletions (at this moment) only happen for
empty pages, that case is not a problem here - there is no truncated
key that would need de-truncation on an empty page.
Additional benefits to highkey-based prefix truncation are that the
highkey already is compared to the searchkey in _bt_moveright, so
that once you have a pin on the page and start searching, for a
prefix-truncated tuple you can compare the amount of truncated
attributes with the amount of equal attributes with the high-key,
and compare those to skip comparing several attributes. This is in
addition to 'normal' keeping track of equal attributes for the high
and low of the binary search.
But, prefix truncation that uses a page's highkey as a reference
needs a lot of consideration, especially with how postgres has
currently implemented nbtrees:
=== 1.) Suffix-truncation; -INF in high keys ===
A suffix-truncated HighKey with N untruncated attributes only shares
(up to) N-1 attributes with the data on that page, because to the -INF
used as the seperator will put all tuples with a shared prefix of N
attributes on the next page over. This limits the amount of attributes
that can be truncated away, and with that limits the effectiveness of
prefix truncation.
Example:
A page split between two indexed tuples, (New York, 1010) and
(New Jersey, 1010) would currently result in a page (New York, 1010)
with high key (New Jersey, <-INF>), and a right page of
(New Jersey, 1010). As you can see, this puts a 'foreign' value onto
the left page, limiting the ability of prefix truncation to truncate
away common attributes based on the P_HIKEY.
This limitation can be solved by altering suffix truncation to
instead truncate the left key, and interpret truncated attributes as
positive infinity. The example above would then result in a left
page (New York, 1010) with high key (New York, +INF) and a right
page (New Jersey, 1010). It is clear that prefix truncation could
benefit from this situation, as there are more similar values on the
same page.
A side effect of the solution would be that index tuples that sort
between the lastleft and firstright of a page split would now be
inserted on the right page instead of on the left page. I do not
know whether or not this could be a problem, except that some
optimizations could not apply anymore (or would be less effective).
It is my understanding that this solution can be achieved in a
backwards-compatible manner by using a spare bit in the high-key's
t_tid.t_offset to indicate that this highkey has has a +INF
truncated value.
This optimization could also be limited to only inner pages; such that the
=== 2.) index_getattr, attribute extraction ===
BTree currently makes extensive use of index_getattr to extract each
attribute from the tuple. This cannot directly be used with
prefix-truncated tuples, due to the possibly incorrect offsets in
Form_pg_attribute->attcacheoff which is used by index_getattr to
efficiently find the offset of the attribute in the stored index
tuple. This can be mitigated by explicitly setting the truncated
attributes to NULL, but that would potentially add the overhead of a
NULL-bitmap, and would force index_getattr into a slow path:
index_getattr is horribly non-performant for tuples which have early
null or varlen attributes, due to the inability to use the
pg_indatt_desc->attcacheoff offset cache.
The need to set the attribute to NULL, and the inefficient
iterations over index attributes with index_getattr could be solved
through iterating over the tuple's attributes whilst keeping track
of the current offset in the tuple, instead of requesting each
attribute sequentially through index_getattr. This could be done
using new iterating helper functions and structures, which would
keep track of the current offset in the tuple.
The solution to this limitation would be a useful addition to the
current toolset in btrees, as I've seen large amounts of time being
wasted in index_getattr (see also this footnote).
=== 3.) reindex, rightmost page insertions ===
When we use the highkey as the reference tuple for on-page prefix
truncation, we cannot truncate away the prefix of tuples located on
the rightmost page. This is problematic for reindex and indexes on
incremental columns, as they insert on the rightmost page, which has
no highkey and therefore cannot benefit from the prefix truncation.
The problem for reindex can be solved by constructing indexes
right-to-left instead of left-to-right. This way, each tuple is
written to a page that has a definite highkey (except the rightmost
page of each level), and can therefore benefit from prefix
truncation. This does not solve the problem of no prefix truncation
on rightmost pages, but it does work around the problem for indexes
with random insertion patterns and index creation.
=== 4.) leaf pages, deduplication ===
On inner pages we can freely truncate prefixes away, as they are
nothing but guides to the binary search algorithm. On leaf pages,
the truncation of prefixes is actually not distinguishable from
attribute-level deduplication, which means the same problems from
tuple deduplication exist for prefix truncation, and subsequently
the same limitations apply as for 'normal' deduplication. So, prefix
attribute deduplication on leaf pages can only happen for
allequalimage indexes (or, prefix attributes that are equalimage,
whenever we get to storing per-attribute equalimage-ness).
For optimal use of prefix truncation, whilst keeping in mind the
limitations of non-allequalimage-attributes, it would be useful to
add a 'prefix equal image' attribute to the index (where
keyattributes >= prefixequalimage), such that prefix truncation can
still happen for indexes that do not have allequalimage, but could
benefit from deduplication through prefix truncation. Similarly, it
could be useful for other index optimizations to add a precomputed
'att-is-equalimage' bitmap to the btree index data, from which we
can derive the allEqualImage and prefixEqualImage fields and other
future optimizations based on the equalImage-ness of attributes.
=== 5.) representation, pivot tuples ===
For pivot tuples, we potentially need to store an additional number
in each tuple. This can be achieved in two ways:
* using part of the space available for the number of attributes stored in this tuple (12) and using the reclaimed bits. This approach allows for up to 63 truncated attributes, but also limits the maximum amount of attributes in an index that can make use of prefix truncation: currently, technically indexes with up to 4095 columns are possible (by setting the correct values in header files). If we require that all attributes are truncatable, the max number of of attributes we can support in a btree-index would drop to 63, just shy of double the default amount. This approach would not require any additional flag bits specific to prefix truncation, but would limit adoption in versions of PG that are compiled with INDEX_MAX_KEYS>=64.
* using a flag bit, and adding an extra data field of 1 or 2 bytes in the stored data, similar how to the workings of the BT_PIVOT_HEAP_TID_ATTR flag. This would also be backwards compatible, as there are flag bits left in BT_STATUS_OFFSET_MASK. However, it would increase the minimum size of a prefix-truncated pivot tuple. That is not too much of a problem, though: A saving of the equivalent of 2 1-aligned attributes, or 1 2-aligned attributes would already make this investment worthwhile by being able to skip comparing these attributes.
=== 6.) representation, leaf tuples ===
For leaf tuples, we only need to store the amount of attributes
we've truncated away. As there are no unused flag bits, the only way
to store more information is to use INDEX_ALT_TID_MASK, fully
claiming the itup->t_tid->ip_posid field. This requires us to find a
new place to store the posid containd, which should be possible by
adding a 2-byte data holder that contains this ip_posid.
== Progress ==
These are the current results of my personal research branch on
nbtree prefix truncation / prefix-skip search. I have found several
limitations, most of which are solvable without a major version
change in the physical storage format.
My research branch is mostly work on the proposed highkey-based
solution, and contains a complete solution to #2 (attribute extraction)
and I have a solution to #3 somewhere in my history as well.
For highkey limitations 1, 4, 5 and 6 I would like to have some feedback
before I start to work on the actual implementation, as tuple
de/serialization is not a part I've familiarized myself with yet.
My current priorities are, in order:
* #2, IndexTuple attribute extraction improvements: ready. Patch will be provided on-list shortly, for CF 2021-07. includes short patch with page-wise dynamic prefix truncation.
* #5, PT inner page tuples: work is starting
* #3, backwards index build: Patch requires updates.
* #1, (optional) +INF truncation, which improves the overall efficiency in #5
* #6, PT leaf tuples
* #4, attIsEqualImage for index atts / nPrefixEqualImage. This will increast the efficiency of #6
== Footnotes ==
=== _bt_compare profile ===
For an index `(text COLLATE NONSTANDARD, text COLLATE NONSTANDARD, text COLLATE NONSTANDARD)` with short columns, the profile of that _bt_compare flamegraph section was:
 74% FunctionCall2Coll -- thanks lookup_collation_cache!
 17.4% nocache_index_getattr
 4% BTreeTupleIsPivot
 ...tailings
effectively, nocache_index_getattr was slow and taking up >50% (17.4 %pt out of 26%pt)
of the overhead of _bt_compare when we assume all compare function 
calls are useful work.