Re: [PROPOSAL] Effective storage of duplicates in B-tree index.

From: Peter Geoghegan <pg(at)heroku(dot)com>
To: Anastasia Lubennikova <a(dot)lubennikova(at)postgrespro(dot)ru>
Cc: Pg Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: [PROPOSAL] Effective storage of duplicates in B-tree index.
Date: 2015-09-27 23:23:39
Message-ID: CAM3SWZR9uvu97Xse8-iJgRzLt8RM0WRHnhZnfE_EMV5+-39VRg@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Sun, Sep 27, 2015 at 4:11 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Debugging this stuff is sometimes like keyhole surgery. If you could
> just see at/get to the structure that you care about, it would be 10
> times easier. Hopefully this tool makes it easier to identify problems.

I should add that the way that the L&Y technique works, and the way
that Postgres code is generally very robust/defensive can make direct
testing a difficult thing. I have seen cases where a completely messed
up B-Tree still gave correct results most of the time, and was just
slower. That can happen, for example, because the "move right" thing
results in a degenerate linear scan of the entire index. The
comparisons in the internal pages were totally messed up, but it
"didn't matter" once a scan could get to leaf pages and could move
right and find the value that way.

I wrote amcheck because I thought it was scary how B-Tree indexes
could be *completely* messed up without it being obvious; what hope is
there of a test finding a subtle problem in their structure, then?
Testing the invariants directly seemed like the only way to have a
chance of not introducing bugs when adding new stuff to the B-Tree
code. I believe that adding optimizations to the B-Tree code will be
important in the next couple of years, and there is no other way to
approach it IMV.

--
Peter Geoghegan

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Gavin Wahl 2015-09-28 00:44:54 Re: BRIN indexes for MAX, MIN, ORDER BY?
Previous Message Peter Geoghegan 2015-09-27 23:11:51 Re: [PROPOSAL] Effective storage of duplicates in B-tree index.