Currently, nbtree code compares each and every column of an index tuple during the binary search on the index page. With large indexes that have many duplicate prefix column values (e.g. an index on (bool, bool, uuid) ) that means a lot of wasted time getting to the right column.
The attached patch improves on that by doing per-page dynamic prefix truncation: If we know that on both the right and left side there are index tuples where the first two attributes are equal to the scan key, we skip comparing those attributes at the current index tuple and start with comparing attribute 3, saving two attribute compares. We gain performance whenever comparing prefixing attributes is expensive and when there are many tuples with a shared prefix - in unique indexes this doesn't gain much, but we also don't lose much in this case.
This patch was originally suggested at [0], but it was mentioned that they could be pulled out into it's own thread. Earlier, the performance gains were not clearly there for just this patch, but after further benchmarking this patch stands on its own for performance: it sees no obvious degradation of performance, while gaining 0-5% across various normal indexes on the cc-complete sample dataset, with the current worst-case index shape getting a 60%+ improved performance on INSERTs in the tests at [0].
+1
This can be nice functionality. I had a customer with a very slow index scan - the main problem was a long common prefix like prg010203xxxx.
