nbtdedup.c's "single value strategy" is used when we have a leaf page
that is full of duplicates of the same value. We infer that we will
have many more in the future, and cooperate with the "single value
strategy" used within nbtsplitloc.c. Deduplication should create 6
large posting list tuples that will remain on the page after an
anticipated page split, plus some remaining non-dedup'd regular tuples
that go on the new right page. So nbtdedup.c anticipates how an
eventual page split will need to work to keep space utilization high,
but not too high (though only in this specific "single value strategy"
case).
(Note that the choice of 6 posting list tuples is arbitrary -- it
seemed like limiting the size of posting list tuples to 1/3 of a page
(the long established maximum) was a bit too aggressive, so the
posting list tuple size limit was halved to 1/6 of the page.)
Sometimes, an append-only inserter of low cardinality data (just a few
distinct values) can leave some "single value" pages with perhaps 8 or
9 tuples -- not the intended 7 (i.e. not the intended 6 tuples plus 1
high key). This isn't really a problem. It can only happen when a
plain tuple is "wedged" between two existing max-sized posting list
tuples, where we cannot merge the plain tuple with either
adjoining/neighboring posting list tuple (since that violates the 1/6
of a page limit on posting list tuple size). This scenario is rare,
and in any case the space utilization is almost exactly what it's
supposed to be in the end (the BTREE_SINGLEVAL_FILLFACTOR "fill
factor" that was added to Postgres 12 is still respected in the
presence of deduplication in Postgres 13). This much is okay.
However, I noticed that it's also possible to confuse "single value
strategy" in nbtdedup.c into thinking that it has already observed 6
"max sized" tuples, when in fact it has not. This can lead to the
occasional page that contains perhaps 50 or 70 tuples. This is rare
enough that you have to really be paying attention to the structure of
the index to notice it -- most of my test case indexes that use
"single value strategy" a lot aren't even affected. I'm not okay with
this, because it's not how nbtdedup.c is intended to work -- clearly
nbtdedup.c gets confused as a consequence of the "plain tuple gets
wedged" issue. I'm not okay with this.
Attached patch nails down the behavior of single value strategy. This
slightly improves the space utilization in a small minority of my test
case indexes, though not by enough to matter. For example, the TPC-H
idx_customer_nationkey index goes from 1193 pages to 1182 pages. This
is an utterly insignificant issue, but there is no reason to allow it.
When I think about space utilization, I don't just look at the index
overall -- I also expect a certain amount of consistency within
related subsets of the index's key space.
--
Peter Geoghegan