Re: [patch] _bt_binsrch* improvements - equal-prefix-skip binary search

On Fri, 11 Sep 2020 at 19:41, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
>
> Are you familiar with this thread?
>
>
https://www.postgresql.org/message-id/CAH2-Wzn_NAyK4pR0HRWO0StwHmxjP5qyu+X8vppt030XpqrO6w@mail.gmail.com
>
> I wrote a patch that implemented the same idea, which is sometimes
> called dynamic prefix truncation. I found some very subtle problems
> with it, though. Concurrent page deletions could occur, which could
> cause a scan that skips a prefix to miss that the page it landed on
> doesn't have the same common prefix anymore.

Thank you for pointing me to that thread, I was not yet familiar with it.
It took me some time to get familiar with the Lanin and Shasha [0] paper,
but the concerns regarding concurrent page deletion are indeed problematic
for algorithmic prefix truncation, and do make it near impossible to use
algorithmic prefix truncation without resetting the accumulated prefix
every page.

At that, I will retract this current patch, and (unless someone's already
working on it) start research on implementing physical prefix truncation
through deduplicating the prefix shared with a page's highkey. This would
likely work fine for inner nodes (there are still flag bits left unused,
and the concerns related to deduplication of equal-but-distinct values do
not apply there), though I'm uncertain about the ability to truncate
duplicate prefixes in leaf nodes as it is basically prefix deduplication
with the same problems attached as 'normal' deduplication.

Thanks,

Matthias van de Meent

[0] https://archive.org/stream/symmetricconcurr00lani