I've not yet been involved in postgresql's development process, so here's a first. Please find attached a patch for improving the BT binary search speeds, with accompanying performance data.
v1-0001 adapts _bt_compare and _bt_binsrch* to make use of static properties of L&Y-style nbtree indexes to speed up finding an initial position in the nbtee.
I alter the logic from _bt_compare to accept a 'start-comparing-at-column' argument, and to also return which column the comparison result came from. This allows us to keep track of which columns we've already checked for equality, and when getting deeper into the index this allows us to skip checking the already equal key columns.
Specifically, when binary-searching through a page, we keep track of which column was checked for the high-key, and which for the low-key. The first column of these that is not yet equal will be used for the next comparison. Any columns before this column must be equal, as both the high- and the low-keys in that page have already been validated as having an equal prefix. The column number is then passed on through the insertion key, allowing the optimization to be used in the climbing of the nbtree index.
v1-0001 will be especially performant in nbtree indexes with a relatively low initial cardinality and high compare cost. My own performance testing was done on a laptop (4c/8t), after first getting it warm with other benchmarks & compilations, so the results are a bit unstable.
While testing this I also noticed that there were a lot of pipeline stalls around the arguments and results of _bt_compare in the hot loops of _bt_binsrch* where the new functionality would be used, so I've moved the core logic of _bt_compare to a static inline function _bt_compare_inline, which helped the code to go from a 2% TPS decrease for single-column indexes to ~ 8% TPS increase for an insert-only workload, and for 3-column text all-collated indexes a TPS increase of 20% on my system. This also allowed me to keep the signature of _bt_compare the same as it was, limiting the scope of the changes to only the named functions.
Finally, this could be a great start on prefix truncation for btree indexes, though that is _not_ the goal of this patch. This patch skips, but does not truncate, the common prefix.
