Re: B-tree performance improvements in 8.x

jao(at)geophile(dot)com writes:
> In the 8.0 release notes, (section E.10.4.1), I noticed this
> statement:

> Improve B-tree index performance for duplicate keys (Dmitry Tkach, Tom)

> This improves the way indexes are scanned when many duplicate
> values exist in the index.

> Can someone describe these improvements in more detail? How were such
> scans done in 7.x, and what exactly is different in 8.x?

IIRC, this change had to do with the initial-positioning rules for btree
index descent. Before 8.0, the tree descent code had only one behavior:
"find first index entry >= target value X". If the query was "WHERE
indexcol > X" then the descent would go to the first entry equal to X
(if any) and then, if it was equal, step forward to the first entry
greater than X. This could be quite slow if there were many entries
equal to X. Conversely, for a backward scan, the initial positioning
was OK for query "indexcol < X": go to first entry >= X, step back one;
but not so hot for "indexcol <= X": go to first entry >= X, step forward
over all entries = X, step back one. In 8.0, the descent code can do
either "first entry >= X" or "first entry > X", and the positioning
rules never need to step more than one entry to locate the desired
starting position (details left as exercise for the reader). The impact
of having N equal entries is now only O(log N) rather than O(N), since
tree descent is O(log N) in either case.

regards, tom lane