Re: Constant time insertion into highly non-unique - Mailing list pgsql-hackers

From Simon Riggs
Subject Re: Constant time insertion into highly non-unique
Date
Msg-id 1113494116.16721.1916.camel@localhost.localdomain
Whole thread Raw
In response to Re: Constant time insertion into highly non-unique indexes  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
On Thu, 2005-04-14 at 11:15 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> 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.

OK... point accepted. Darn, but also thank goodness it performs.

P(N) > 0.999 for W byte keys, at...

N    W        Mean blocks read/insert
3    4 bytes        1.1
5    8 bytes        1.4
11    16 bytes    2.1
22    32 bytes    3.6
43    64 bytes    6.7
83    128 bytes    12.5
lots    256 bytes    23

> > IMHO the performance figures show this to be true.
> 
> *What* performance figures?  

The figures shown on PERFORM recently, with graphs. We still have a
performance issue with insertion rate for large indexes. 

Best Regards, Simon Riggs



pgsql-hackers by date:

Previous
From: Robert Treat
Date:
Subject: Re: Interactive docs idea
Next
From: Tom Lane
Date:
Subject: Re: Constant time insertion into highly non-unique indexes