I wrote a prototype quality patch that implements what I call
"classic" suffix truncation. That is, the patch makes nbtree leaf page
splits generate a short prefix datum for the new high key for
variable-length datatypes, generated using new opclass infrastructure.
This is useful for string-like datatypes such as text, especially when
we happen to be indexing long text strings, where we don't truly need
to use long strings in internal pages. The feature is "classic" in the
sense that it works in more or less the way that Bayer and Unterauer
anticipate in the "Prefix B-Trees" paper. We already have a limited
form of suffix truncation that only works at the whole-column
granularity. To some degree, I approached writing this patch as
finishing off the work that was started in Postgres 12. It started out
that way, at least.
I believe that the prototype is representative of the benefits that
we'd get from a high quality implementation of the same feature. Those
benefits turn out to be relatively small, which is discouraging. I'm
not going to pursue the project any further in the near-term, because
there is more important work to be done, but I thought that I'd share
what I found here. Highlights:
* There were changes required to nbtsplitloc.c to make it work well,
unsurprisingly. It has to be sensitive to the final size of the new
high key, rather than just caring about the number of columns that can
be truncated. At the same time, it's important to not break the
duplicate handling stuff. I ended up changing the penalty logic for
leaf splits, making it give primary consideration to the discrete cost
that is the total number of columns that are left in the new high key,
and secondary consideration to the continuous cost that is the exact
final size of the new high key with classic suffix truncation. This
seemed to work well, though I didn't get as far as worrying about the
extra cycles (I only implemented classic suffix truncation for "C"
locale text).
* I saw a tiny reduction in the number of leaf pages with affected
indexes in my test suite, and small reductions in the number of
internal pages.
* There were 2 or 3 existing indexes from my test suite that happened
to index very large strings, such as an index on a "notes" column.
These indexes had massive reductions in the number of internal pages
(e.g. a 5x+ reduction), along with a very small reduction in the
number of leaf pages. Users that happen to have a lot of indexes that
look like this are likely to find classic suffix truncation
compelling, but that doesn't seem like a good enough reason to push
ahead with the patch.
--
Peter Geoghegan
