Re: B-tree performance improvements in 8.x

Quoting Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>:

> 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.
> ...
> 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