pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: [GENERAL] Creation of tsearch2 index is very
13+ messages / 6 participants
[nested] [flat]
* Re: [GENERAL] Creation of tsearch2 index is very
@ 2006-01-21 12:22 Ron <rjpeace@earthlink.net>
2006-01-21 13:34 ` Re: [GENERAL] Creation of tsearch2 index is very Oleg Bartunov <oleg@sai.msu.su>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 13+ messages in thread
From: Ron @ 2006-01-21 12:22 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
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
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-21 13:34 ` Oleg Bartunov <oleg@sai.msu.su>
2006-01-21 16:11 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
1 sibling, 1 reply; 13+ messages in thread
From: Oleg Bartunov @ 2006-01-21 13:34 UTC (permalink / raw)
To: Ron <rjpeace@earthlink.net>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
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
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 13:34 ` Re: [GENERAL] Creation of tsearch2 index is very Oleg Bartunov <oleg@sai.msu.su>
@ 2006-01-21 16:11 ` Ron <rjpeace@earthlink.net>
2006-01-21 16:33 ` Re: [GENERAL] Creation of tsearch2 index is very Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 1 reply; 13+ messages in thread
From: Ron @ 2006-01-21 16:11 UTC (permalink / raw)
To: Oleg Bartunov <oleg@sai.msu.su>; pgsql-performance; +Cc: Tom Lane <tgl@sss.pgh.pa.us>
Perhaps a different approach to this problem is called for:
_Managing Gigabytes: Compressing and Indexing Documents and Images_ 2ed
Witten, Moffat, Bell
ISBN 1-55860-570-3
This is a VERY good book on the subject.
I'd also suggest looking at the publicly available work on indexing
and searching for search engines like Inktomi (sp?) and Google.
Ron
At 08:34 AM 1/21/2006, Oleg Bartunov wrote:
>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.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 13:34 ` Re: [GENERAL] Creation of tsearch2 index is very Oleg Bartunov <oleg@sai.msu.su>
2006-01-21 16:11 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-21 16:33 ` Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 0 replies; 13+ messages in thread
From: Oleg Bartunov @ 2006-01-21 16:33 UTC (permalink / raw)
To: Ron <rjpeace@earthlink.net>; +Cc: pgsql-performance@postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>
On Sat, 21 Jan 2006, Ron wrote:
> Perhaps a different approach to this problem is called for:
>
> _Managing Gigabytes: Compressing and Indexing Documents and Images_ 2ed
> Witten, Moffat, Bell
> ISBN 1-55860-570-3
>
> This is a VERY good book on the subject.
>
> I'd also suggest looking at the publicly available work on indexing and
> searching for search engines like Inktomi (sp?) and Google.
> Ron
Ron,
you completely miss the problem ! We do know MG and other SE. Actually,
we've implemented several search engines based on inverted index technology
(see, for example, pgsql.ru/db/pgsearch). tsearch2 was designed for
online indexing, while keeping inverted index online is rather difficult
problem. We do have plan to implement inverted index as an option for
large read-only archives, but now we discuss how to organize online
index and if possible to optimize current storage for signatures
without breaking search performance.
>
>
> At 08:34 AM 1/21/2006, Oleg Bartunov wrote:
>> 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.
>
>
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
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-21 18:27 ` Tom Lane <tgl@sss.pgh.pa.us>
2006-01-21 20:19 ` Re: [GENERAL] Creation of tsearch2 index is very David Lang <dlang@invendra.net>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
1 sibling, 2 replies; 13+ messages in thread
From: Tom Lane @ 2006-01-21 18:27 UTC (permalink / raw)
To: Ron <rjpeace@earthlink.net>; +Cc: pgsql-performance
Ron <rjpeace@earthlink.net> writes:
> At 07:23 PM 1/20/2006, Tom Lane wrote:
>> 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?
Search performance will go to hell in a handbasket :-(. We have to make
at least some effort to split the page in a way that will allow searches
to visit only one of the two child pages rather than both.
It's certainly true though that finding the furthest pair is not a
necessary component of that. It's reasonable if you try to visualize
the problem in 2D or 3D, but I'm not sure that that geometric intuition
holds up in such a high-dimensional space as we have here.
regards, tom lane
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
@ 2006-01-21 20:19 ` David Lang <dlang@invendra.net>
2006-01-21 20:55 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 13+ messages in thread
From: David Lang @ 2006-01-21 20:19 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Ron <rjpeace@earthlink.net>; pgsql-performance
On Sat, 21 Jan 2006, Tom Lane wrote:
> Ron <rjpeace@earthlink.net> writes:
>> At 07:23 PM 1/20/2006, Tom Lane wrote:
>>> 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?
>
> Search performance will go to hell in a handbasket :-(. We have to make
> at least some effort to split the page in a way that will allow searches
> to visit only one of the two child pages rather than both.
does the order of the items within a given page matter? if not this sounds
like a partial quicksort algorithm would work. you don't need to fully
sort things, but you do want to make sure that everything on the first
page is 'less' then everything on the second page so you can skip passes
that don't cross a page boundry
> It's certainly true though that finding the furthest pair is not a
> necessary component of that. It's reasonable if you try to visualize
> the problem in 2D or 3D, but I'm not sure that that geometric intuition
> holds up in such a high-dimensional space as we have here.
I will say that I'm not understanding the problem well enough to
understand themulti-dimentional nature of this problem.
David Lang
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-21 20:19 ` Re: [GENERAL] Creation of tsearch2 index is very David Lang <dlang@invendra.net>
@ 2006-01-21 20:55 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 13+ messages in thread
From: Tom Lane @ 2006-01-21 20:55 UTC (permalink / raw)
To: David Lang <dlang@invendra.net>; +Cc: Ron <rjpeace@earthlink.net>; pgsql-performance
David Lang <dlang@invendra.net> writes:
> On Sat, 21 Jan 2006, Tom Lane wrote:
>> Ron <rjpeace@earthlink.net> writes:
>>> 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?
>>
>> Search performance will go to hell in a handbasket :-(. We have to make
>> at least some effort to split the page in a way that will allow searches
>> to visit only one of the two child pages rather than both.
> does the order of the items within a given page matter?
AFAIK the items within a GIST index page are just stored in insertion
order (which is exactly why Ron's suggestion above doesn't work well).
There's no semantic significance to it. It's only when we have to split
the page that we need to classify the items more finely.
regards, tom lane
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
@ 2006-01-27 00:18 ` Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Re: [GENERAL] Creation of tsearch2 index is very Alvaro Herrera <alvherre@alvh.no-ip.org>
1 sibling, 1 reply; 13+ messages in thread
From: Ron @ 2006-01-27 00:18 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
At 01:27 PM 1/21/2006, Tom Lane wrote:
>Ron <rjpeace@earthlink.net> writes:
> > At 07:23 PM 1/20/2006, Tom Lane wrote:
> >> 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?
>
>Search performance will go to hell in a handbasket :-(. We have to make
>at least some effort to split the page in a way that will allow searches
>to visit only one of the two child pages rather than both.
>
>It's certainly true though that finding the furthest pair is not a
>necessary component of that. It's reasonable if you try to visualize
>the problem in 2D or 3D, but I'm not sure that that geometric intuition
>holds up in such a high-dimensional space as we have here.
After reading the various papers available on GiST and RD trees, I
think I have a decent suggestion.
Since RD tree keys contain the keys of their descendents/components
in them, they are basically a representation of a depth first
search. This can be useful for intra-document searches.
OTOH, inter-document searches are going to be more akin to breadth
first searches using RD trees.
Thus my suggestion is that we maintain =two= index structures for text data.
The first contains as many keys and all their descendents as
possible. When we can no longer fit a specific complete "path" into
a page, we start a new one; trying to keep complete top level to leaf
key sets within a page. This will minimize paging during
intra-document searches.
The second index keeps siblings within a page and avoids putting
parents or children within a page unless the entire depth first
search can be kept within the page in addition to the siblings
present. This will minimize paging during inter-document searches.
Traditional B-tree ordering methods can be used to define the
ordering/placement of pages within each index, which will minimize
head seeks to find the correct page to scan.
Since the criteria for putting a key within a page or starting a new
page is simple, performance for those tasks should be O(1).
The price is the extra space used for two indexes instead of one, but
at first glance that seems well worth it.
Comments?
Ron
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-27 01:00 ` Alvaro Herrera <alvherre@alvh.no-ip.org>
2006-01-27 01:55 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
0 siblings, 1 reply; 13+ messages in thread
From: Alvaro Herrera @ 2006-01-27 01:00 UTC (permalink / raw)
To: Ron <rjpeace@earthlink.net>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
Ron wrote:
> At 01:27 PM 1/21/2006, Tom Lane wrote:
> >Ron <rjpeace@earthlink.net> writes:
> >> At 07:23 PM 1/20/2006, Tom Lane wrote:
> >>> 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).
> After reading the various papers available on GiST and RD trees, I
> think I have a decent suggestion.
I for one don't understand what does your suggestion have to do with the
problem at hand ... not that I have a better one myself.
--
Alvaro Herrera http://www.amazon.com/gp/registry/CTMLCN8V17R4
"Siempre hay que alimentar a los dioses, aunque la tierra esté seca" (Orual)
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Re: [GENERAL] Creation of tsearch2 index is very Alvaro Herrera <alvherre@alvh.no-ip.org>
@ 2006-01-27 01:55 ` Ron <rjpeace@earthlink.net>
2006-01-27 02:29 ` Re: [GENERAL] Creation of tsearch2 index is very Craig A. James <cjames@modgraph-usa.com>
0 siblings, 1 reply; 13+ messages in thread
From: Ron @ 2006-01-27 01:55 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@alvh.no-ip.org>; pgsql-performance
At 08:00 PM 1/26/2006, Alvaro Herrera wrote:
>Ron wrote:
> > At 01:27 PM 1/21/2006, Tom Lane wrote:
> > >Ron <rjpeace@earthlink.net> writes:
> > >> At 07:23 PM 1/20/2006, Tom Lane wrote:
> > >>> 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).
>
> > After reading the various papers available on GiST and RD trees, I
> > think I have a decent suggestion.
>
>I for one don't understand what does your suggestion have to do with the
>problem at hand ... not that I have a better one myself.
We have two problems here.
The first is that the page splitting code for these indexes currently
has O(N^2) performance.
The second is that whatever solution we do use for this
functionality, we still need good performance during searches that
use the index. It's not clear that the solutions we've discussed to
splitting index pages thus far will result in good performance during searches.
My suggestion is intended to address both issues.
If I'm right it helps obtain high performance during searches while
allowing the index page splitting code to be O(1)
Ron.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Re: [GENERAL] Creation of tsearch2 index is very Alvaro Herrera <alvherre@alvh.no-ip.org>
2006-01-27 01:55 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-27 02:29 ` Craig A. James <cjames@modgraph-usa.com>
2006-01-27 03:33 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
0 siblings, 1 reply; 13+ messages in thread
From: Craig A. James @ 2006-01-27 02:29 UTC (permalink / raw)
To: Ron <rjpeace@earthlink.net>; pgsql-performance
Ron <rjpeace@earthlink.net> writes:
> We have two problems here.
> The first is that the page splitting code for these indexes currently
> has O(N^2) performance.
> The second is that whatever solution we do use for this functionality,
> we still need good performance during searches that use the index.
No, unfortunately that's not the problem that needs to be solved.
The problem is figuring out WHICH records to put in the "left" and "right" trees once you split them. If you can figure that out, then your suggestion (and perhaps other techniques) could be useful.
The problem boils down to this: You have a whole bunch of essentially random bitmaps. You have two buckets. You want to put half of the bitmaps in one bucket, and half in the other bucket, and when you get through, you want all of the bitmaps in each bucket to be maximally similar to each other, and maximally dissimilar to the ones in the other bucket.
That way, when you OR all the bitmaps in each bucket together to build the bitmap for the left and right child nodes of the tree, you'll get maximum separation -- the chances that you'll have to descend BOTH the left and right nodes of the tree are minimized.
Unfortunately, this problem is very likely in the set of NP-complete problems, i.e. like the famous "Traveling Salesman Problem," you can prove there's no algorithm that will give the answer in a reasonable time. In this case, "reasonable" would be measured in milliseconds to seconds, but in fact an actual "perfect" split of a set of bitmaps probably can't be computed in the lifetime of the universe for more than a few hundred bitmaps.
That's the problem that's being discussed: How do you decide which bitmaps go in each of the two buckets? Any solution will necessarily be imperfect, a pragmatic algorithm that gives an imperfect, but acceptable, answer.
As I mentioned earlier, chemists make extensive use of bitmaps to categorize and group molecules. They use Tanimoto or Tversky similarity metrics (Tanimoto is a special case of Tversky), because it's extremely fast to compare two bitmaps, and the score is highly correlated with the number of bits the two bitmaps have in common.
But even with a fast "distance" metric like Tanimoto, there's still no easy way to decide which bucket to put each bitmap into.
Craig
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Re: [GENERAL] Creation of tsearch2 index is very Alvaro Herrera <alvherre@alvh.no-ip.org>
2006-01-27 01:55 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 02:29 ` Re: [GENERAL] Creation of tsearch2 index is very Craig A. James <cjames@modgraph-usa.com>
@ 2006-01-27 03:33 ` Ron <rjpeace@earthlink.net>
2006-01-27 07:52 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
0 siblings, 1 reply; 13+ messages in thread
From: Ron @ 2006-01-27 03:33 UTC (permalink / raw)
To: Craig A. James <cjames@modgraph-usa.com>; pgsql-performance
You seem to have missed my point. I just gave a very clear
description of how to "decide which bitmaps go in each of the two
buckets" by reformulating the question into "decide which bitmaps go
in each of =four= buckets".
The intent is to have two indexes, one optimized for one common class
of searches, and the other optimized for another common class of searches.
By decomposing the optimization problem into two simpler problems,
the hope is that we address all the issues reasonably simply while
still getting decent performance.
Nothing is free. The price we pay, and it is significant, is that we
now have two indexes where before we had only one.
Ron
At 09:29 PM 1/26/2006, Craig A. James wrote:
>Ron <rjpeace@earthlink.net> writes:
>>We have two problems here.
>>The first is that the page splitting code for these indexes
>>currently has O(N^2) performance.
>>The second is that whatever solution we do use for this
>>functionality, we still need good performance during searches that
>>use the index.
>
>No, unfortunately that's not the problem that needs to be solved.
>
>The problem is figuring out WHICH records to put in the "left" and
>"right" trees once you split them. If you can figure that out, then
>your suggestion (and perhaps other techniques) could be useful.
>
>The problem boils down to this: You have a whole bunch of
>essentially random bitmaps. You have two buckets. You want to put
>half of the bitmaps in one bucket, and half in the other bucket, and
>when you get through, you want all of the bitmaps in each bucket to
>be maximally similar to each other, and maximally dissimilar to the
>ones in the other bucket.
>
>That way, when you OR all the bitmaps in each bucket together to
>build the bitmap for the left and right child nodes of the tree,
>you'll get maximum separation -- the chances that you'll have to
>descend BOTH the left and right nodes of the tree are minimized.
>
>Unfortunately, this problem is very likely in the set of NP-complete
>problems, i.e. like the famous "Traveling Salesman Problem," you can
>prove there's no algorithm that will give the answer in a reasonable
>time. In this case, "reasonable" would be measured in milliseconds
>to seconds, but in fact an actual "perfect" split of a set of
>bitmaps probably can't be computed in the lifetime of the universe
>for more than a few hundred bitmaps.
>
>That's the problem that's being discussed: How do you decide which
>bitmaps go in each of the two buckets? Any solution will
>necessarily be imperfect, a pragmatic algorithm that gives an
>imperfect, but acceptable, answer.
>
>As I mentioned earlier, chemists make extensive use of bitmaps to
>categorize and group molecules. They use Tanimoto or Tversky
>similarity metrics (Tanimoto is a special case of Tversky), because
>it's extremely fast to compare two bitmaps, and the score is highly
>correlated with the number of bits the two bitmaps have in common.
>
>But even with a fast "distance" metric like Tanimoto, there's still
>no easy way to decide which bucket to put each bitmap into.
>
>Craig
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: [GENERAL] Creation of tsearch2 index is very
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 18:27 ` Re: [GENERAL] Creation of tsearch2 index is very Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Re: [GENERAL] Creation of tsearch2 index is very Alvaro Herrera <alvherre@alvh.no-ip.org>
2006-01-27 01:55 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-27 02:29 ` Re: [GENERAL] Creation of tsearch2 index is very Craig A. James <cjames@modgraph-usa.com>
2006-01-27 03:33 ` Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
@ 2006-01-27 07:52 ` Ron <rjpeace@earthlink.net>
0 siblings, 0 replies; 13+ messages in thread
From: Ron @ 2006-01-27 07:52 UTC (permalink / raw)
To: Craig A. James <cjames@modgraph-usa.com>; pgsql-performance; +Cc: Tom Lane <tgl@sss.pgh.pa.us>
At 11:13 PM 1/26/2006, Craig A. James wrote:
>Ron,
>
>I'll write to you privately, because these discussions can get messy
>"in public".
I'm responding to this missive publicly in an attempt to help the
discussion along. It is not my usual practice to respond to private
messages publicly, but this seems a good case for an exception.
>>You seem to have missed my point. I just gave a very clear
>>description of how to "decide which bitmaps go in each of the two
>>buckets" by reformulating the question into "decide which bitmaps
>>go in each of =four= buckets".
>
>Sorry to disagree, but here's the problem. It's not whether you put
>them into two, or four, or N buckets. The problem is, how do you
>categorize them to begin with, so that you have some reasonable
>criterion for which item goes in which bucket? THAT is the hard
>problem, not whether you have two or four buckets.
Agreed. ...and I've given the answer to "how do you categorize them"
using a general property of RD Trees which should result in "a
reasonable criterion for which item goes in which bucket" when used
for text searching.
The definition of RD tree keys being either "atomic" (non
decomposable) or "molecular" (containing the keys of their
descendents) is the one source of our current problems figuring out
how to split them and, if I'm correct, a hint as to how to solve the
splitting problem in O(1) time while helping to foster high
performance during seearches.
>Earlier, you wrote:
>>Traditional B-tree ordering methods can be used to define the
>>ordering/placement of pages within each index, which will minimize
>>head seeks to find the correct page to scan.
>>Since the criteria for putting a key within a page or starting a
>>new page is simple, performance for those tasks should be O(1).
>
>What are the "traditional B-tree ordering methods"? That's the
>issue, right there. The problem is that bitmaps HAVE NO ORDERING
>METHOD. You can't sort them numerically or alphabetically.
The =bitmaps= have no ordering method. =Pages= of bitmaps MUST have
an ordering method or we have no idea which page to look at when
searching for a key.
Treating the "root" bitmaps (those that may have descendents but have
no parents) as numbers and ordering the pages using B tree creation
methods that use those numbers as keys is a simple way to create a
balanced data structure with high fan out. IOW, a recipe for finding
the proper page(s) to scan using minimal seeks.
>Take a crowd of people. It's easy to divide them in half by names:
>just alphabetize and split the list in half. That's what your
>solution would improve on.
>
>But imagine I gave you a group of people and told you to put them
>into two rooms, such that when you are through, the people in each
>room are maximally similar to each other and maximally dissimilar to
>the people in the other room. How would you do it?
>
>First of all, you'd have to define what "different" and "same"
>are. Is your measure based on skin color, hair color, age, height,
>weight, girth, intelligence, speed, endurance, body odor, ...
>? Suppose I tell you, "All of those". You have to sort the people
>so that your two groups are separated such that the group
>differences are maximized in this N-dimensional
>space. Computationally, it's a nearly impossible problem.
I'm =changing= the problem using the semantics of RD trees. Using an
RD tree representation, we'd create and assign a key for each person
that ranked them compared to everyone else for each of the metrics we
decided to differentiate on.
Then we start to form trees of keys to these people by creating
"parent" keys as roots that contain the union of everyone with the
same or possibly similar value for some quality. By iterating this
process, we end up with a bottom up construction method for an RD
tree whose root key will the union of all the keys representing these
people. If this is one data structure, we end up with an efficient
and effective way of answering not only Boolean but also ranking and
similarity type queries.
The problem comes when we have to split this monolithic DS into
pieces for best performance. As many have noted, there is no
simple way to decide how to do such a thing.
OTOH, we =do= have the knowledge of how RD trees are built and what
their keys represent, and we know that queries are going to tend
strongly to either a) traverse the path from parent to child (depth
first) or b) find all siblings with (dis)similar characteristics
(breadth first), or c) contain a mixture of a) and b).
So I'm suggesting that conceptually we clone the original RD tree and
we split each clone according to two different methods.
Method A results in pages that contain as many complete depth first
paths from root to leave as possible on each page.
Method B results in pages that contain as many siblings as possible per page.
...and we use the appropriate index during each type of query or query part.
In return for using 2x as much space, we should have a general method
that is O(1) for decomposing RD trees in such a way as to support
high performance during searches.
>Here's a much simpler version of the problem. Suppose I give you
>1000 numbers, and tell you to divide them in half so that the two
>groups have the smallest standard deviation within each group
>possible, and the two average values of the groups of numbers are
>the farthest apart possible. Pretty easy, right?
>
>Now do it where "distance" is evaluated modulo(10), that is, 1 and 9
>are closer together than 1 and 3. Now try it -- you'll find that
>this problem is almost impossible to solve.
This is orthogonal to the discussion at hand since the above is not
akin to text searching nor best done with RD trees and that is
exactly what this discussion is about. We don't have to solve a
general problem for all domains. We only have to solve it for the
specific domain of text search using the specific DS of RD trees.
>The problem is that, as database designers, we're used to text and
>numbers, which have an inherent order. Bitmaps have no ordering --
>you can't say one is "greater than" or "less than" the other. All
>you can do is determine that A and B are "more similar" or "less
>similar" than A and C.
Text and numbers only have an order because we deem them to. There
is even a very common default order we tend to use. But even in the
trivial case of ranking we've all said that "1" is better than "2" in
one situation and "2" is better than "1" in another.
In the case of text searching, the bitmaps represent where to find
legomena, AKA specific tokens. Particularly hapax legomena, AKA
unique tokens. Hapax Legomena are particularly important because
they are maximally efficient at driving the search needed to answer a query.
While absolute hapax legomena are great for quickly pruning things
within a document or document region, relative hapax legomena can do
the same thing when searching among multiple documents or document regions.
The two indexes I'm suggesting are designed to take advantage of this
general property of text searching.
Hopefully this clarifies things and motivates a better discussion?
Ron
^ permalink raw reply [nested|flat] 13+ messages in thread
end of thread, other threads:[~2006-01-27 07:52 UTC | newest]
Thread overview: 13+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-01-21 12:22 Re: [GENERAL] Creation of tsearch2 index is very Ron <rjpeace@earthlink.net>
2006-01-21 13:34 ` Oleg Bartunov <oleg@sai.msu.su>
2006-01-21 16:11 ` Ron <rjpeace@earthlink.net>
2006-01-21 16:33 ` Oleg Bartunov <oleg@sai.msu.su>
2006-01-21 18:27 ` Tom Lane <tgl@sss.pgh.pa.us>
2006-01-21 20:19 ` David Lang <dlang@invendra.net>
2006-01-21 20:55 ` Tom Lane <tgl@sss.pgh.pa.us>
2006-01-27 00:18 ` Ron <rjpeace@earthlink.net>
2006-01-27 01:00 ` Alvaro Herrera <alvherre@alvh.no-ip.org>
2006-01-27 01:55 ` Ron <rjpeace@earthlink.net>
2006-01-27 02:29 ` Craig A. James <cjames@modgraph-usa.com>
2006-01-27 03:33 ` Ron <rjpeace@earthlink.net>
2006-01-27 07:52 ` Ron <rjpeace@earthlink.net>
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