Re: Constant time insertion into highly non-unique indexes

From: Tom Lane
Subject: Re: Constant time insertion into highly non-unique indexes
Date: ,
Msg-id: 881.1113491709@sss.pgh.pa.us
(view: Whole thread, Raw)
In response to: Re: Constant time insertion into highly non-unique  (Simon Riggs)
Responses: Re: Constant time insertion into highly non-unique  (Simon Riggs)
List: pgsql-hackers


Simon Riggs <> writes:
> The move right only occurs when the page is full, so the chance of
> moving right is not 0.99^250, but 0.99, since the previous 249 inserts
> would not cause a page split.

Sure, but given that we have a full page, the probability that 250
successive insertions *all* decide to move right rather than split
that page is 0.99^250.  And it only takes one decision to split to
maintain the constant-time behavior.  So I still think your analysis
is incorrect.

> IMHO the performance figures show this to be true.

*What* performance figures?  You have shown none.  We did do performance
testing of this algorithm when we adopted it, and it worked fine ---
though as I say, I don't think we tested with any very wide keys.
        regards, tom lane



pgsql-hackers by date:

From: "Joshua D. Drake"
Date:
Subject: Re: Interactive docs idea
From: Greg Stark
Date:
Subject: Re: Interactive docs idea