From: Ron <rjpeace@earthlink.net>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-performance@postgresql.org
Subject: Re: [GENERAL] Creation of tsearch2 index is very
Date: Sat, 21 Jan 2006 07:22:32 -0500
Message-ID: <7.0.1.0.2.20060121064930.03aba810@earthlink.net> (raw)
In-Reply-To: <6743.1137802990@sss.pgh.pa.us>
References: <26153.1137784469@sss.pgh.pa.us>
<20060120201036.GE31908@svana.org>
<26583.1137788505@sss.pgh.pa.us>
<20060120205132.GF31908@svana.org>
<26958.1137791955@sss.pgh.pa.us>
<20060120213754.GG31908@svana.org>
<7.0.1.0.2.20060120174141.039b03e8@earthlink.net>
<6111.1137797436@sss.pgh.pa.us>
<20060120225751.GA27230@uio.no>
<6532.1137801157@sss.pgh.pa.us>
<20060121000519.GA29755@uio.no>
<6743.1137802990@sss.pgh.pa.us>
At 07:23 PM 1/20/2006, Tom Lane wrote:
>"Steinar H. Gunderson" <sgunderson@bigfoot.com> writes:
> > On Fri, Jan 20, 2006 at 06:52:37PM -0500, Tom Lane wrote:
> >> It's also worth considering that the entire approach is a heuristic,
> >> really --- getting the furthest-apart pair of seeds doesn't guarantee
> >> an optimal split as far as I can see. Maybe there's some totally
> >> different way to do it.
>
> > For those of us who don't know what tsearch2/gist is trying to accomplish
> > here, could you provide some pointers? :-)
>
>Well, we're trying to split an index page that's gotten full into
>two index pages, preferably with approximately equal numbers of items in
>each new page (this isn't a hard requirement though).
Maybe we are over thinking this. What happens if we do the obvious
and just make a new page and move the "last" n/2 items on the full
page to the new page?
Various forms of "move the last n/2 items" can be tested here:
0= just split the table in half. Sometimes KISS works. O(1).
1= the one's with the highest (or lowest) "x" value.
2= the one's with the highest sum of coordinates (x+y+...= values in
the top/bottom n/2 of entries).
3= split the table so that each table has entries whose size_waste
values add up to approximately the same value.
4= I'm sure there are others.
1-5 can be done in O(n) time w/o auxiliary data. They can be done in
O(1) if we've kept track of the appropriate metric as we've built the
current page.
>I think the true figure of merit for a split is how often will
>subsequent searches have to descend into *both* of the resulting
>pages as opposed to just one
>--- the less often that is true, the better. I'm not very clear on
>what tsearch2 is doing with these bitmaps, but it looks like an
>upper page's downlink has the union (bitwise OR) of the one-bits in
>the values on the lower page, and you have to visit the lower page
>if this union has a nonempty intersection with the set you are
>looking for. If that's correct, what you really want is to divide
>the values so that the unions of the two sets have minimal overlap
>... which seems to me to have little to do with what the code does at present.
I'm not sure what "upper page" and "lower page" mean here?
>Teodor, Oleg, can you clarify what's needed here?
Ditto. Guys what is the real motivation and purpose for this code?
Ron
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: rjpeace@earthlink.net, tgl@sss.pgh.pa.us
Subject: Re: [GENERAL] Creation of tsearch2 index is very
In-Reply-To: <7.0.1.0.2.20060121064930.03aba810@earthlink.net>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox