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

On Fri, 11 Sep 2020 at 19:41, Peter Geoghegan <pg@bowt.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.