Re: Max size of a btree index entry - Mailing list pgsql-hackers

On Tue, Jul 11, 2006 at 10:02:49AM -0400, Tom Lane wrote:
> Currently, we restrict btree index tuples to a size that ensures three of
> them will fit on a page.  The motivation for this is the following two
> considerations:
> 
> 1. In a non-rightmost page, we need to include a "high key", or page
> boundary key, that isn't one of the useful data keys.
Why does a leaf page need a boundary key? ISTM if that wasn't the case,
we could actually allow keys to be nearly 8K, constrained by a non-leaf
page needing to include two pointers.

I guess I must be missing something here (and nbtree/README isn't
helping).

> 2. In a non-leaf page, there had better be at least two child pages
> (downlink entries), else we have failed to subdivide the page's key
> range at all, and thus there would be a nonterminating recursion.
> 
> However: a non-leaf page actually has one more pointer than key,
> eg a page with three children needs only two data keys:
> 
> ---------------- entire key range assigned to page ------------------
> 
> -- range 1 --  boundary key -- range 2 --  boundary key -- range 3 --
>      |                           |                           |
>      v                           v                           v
> child page 1               child page 2                 child page 3
> 
> We implement this by having the first data "tuple" on a non-leaf page
> contain only a downlink TID and no key data, ie it's just the header.
> 
> So it appears to me that we could allow the maximum size of a btree
> entry to be just less than half a page, rather than just less than
> a third of a page --- the worst-case requirement for a non-leaf page
> is not three real tuples, but one tuple header and two real tuples.
> On a leaf page we might manage to fit only one real data item, but
> AFAICS that doesn't pose any correctness problems.
> 
> Obviously a tree containing many such pages would be awfully inefficient
> to search, but I think a more common case is that there are a few wide
> entries in an index of mostly short entries, and so pushing the hard
> limit up a little would add some flexibility with little performance
> cost in real-world cases.
> 
> Have I missed something?  Is this worth changing?
> 
>             regards, tom lane
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 1: if posting/reading through Usenet, please send an appropriate
>        subscribe-nomail command to majordomo@postgresql.org so that your
>        message can get through to the mailing list cleanly
> 

-- 
Jim C. Nasby, Sr. Engineering Consultant      jnasby@pervasive.com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461