jao@xxxxxxxxxxxx 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
