Quoting Tom Lane <tgl@xxxxxxxxxxxxx>:
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.
...
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).
What about a compound index (x, y), in which there are many y values
for a given x? My query is "... WHERE x = ? and y = ?".
If the b-tree treats the compound index key is treated as a single
value, then it seems like the pre-8.0 logic you describe would not
apply, and I would expect O(log n) access to the record of interest.
But if the pre-8.0 b-tree starts at the first value >= x and does a
linear scan for the y value, I'd have a problem.
Can you comment on how 7.x and 8.x handle my index and query?
Thanks in advance.
Jack Orenstein
