pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Oleg Bartunov <oleg@sai.msu.su>
To: Ron <rjpeace@earthlink.net>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-performance@postgresql.org
Subject: Re: [GENERAL] Creation of tsearch2 index is very
Date: Sat, 21 Jan 2006 16:34:38 +0300 (MSK)
Message-ID: <Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su> (raw)
In-Reply-To: <7.0.1.0.2.20060121064930.03aba810@earthlink.net>
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>
	<7.0.1.0.2.20060121064930.03aba810@earthlink.net>

On Sat, 21 Jan 2006, Ron wrote:

> 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?

we want not just split the page by two very distinct parts, but to keep
resulted signatures which is ORed signature of all signatures in the page
as much 'sparse' as can. 
some information available here
http://www.sai.msu.su/~megera/oddmuse/index.cgi/Tsearch_V2_internals

Unfortunately, we're rather busy right now and couldn't be very useful.

>
> Ron 
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend
>

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83



view thread (13+ messages)  latest in thread

Message-ID: <Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su>
Permalink:  ../Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su/
Also on:    postgresql.org/message-id/Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su

 · 

reply

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 from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: oleg@sai.msu.su, rjpeace@earthlink.net, tgl@sss.pgh.pa.us
  Subject: Re: [GENERAL] Creation of tsearch2 index is very
  In-Reply-To: <Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su>
  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> <7.0.1.0.2.20060121064930.03aba810@earthlink.net> <Pine.GSO.4.63.0601211629510.14417@ra.sai.msu.su>

* 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