multi-column btree index for real values
Author Message
multi-column btree index for real values
Folks,

Can someone quickly describe how the btree is implemented for multiple
columns?  In particular, under what (if any) circumstances is there an
advantage if the index is over floating point values?

Thanks!

--Martin

TIP 6: Have you searched our list archives?

http://www.***.com/

Tue, 22 Mar 2005 21:18:21 GMT
multi-column btree index for real values

Folks,

Can someone quickly describe how the btree is implemented for multiple
columns?  In particular, under what (if any) circumstances is there an
advantage if the index is over floating point values?

Thanks!

--Martin

TIP 2: you can get off all lists at once with the unregister command

Wed, 23 Mar 2005 01:46:53 GMT
multi-column btree index for real values

Quote:

> Folks,

> Can someone quickly describe how the btree is implemented for multiple
> columns?  In particular, under what (if any) circumstances is there an
> advantage if the index is over floating point values?

AFAIK, multi-column btrees and simply handled by building a btree of the
first column. Each leaf contains a reference to another btree for the second
column, etc...

btrees are useful for < and > comparisons, meaning that queries saying WHERE
x BETWEEN 1.0 and 1.5 can use the index.
--

Quote:
> There are 10 kinds of people in the world, those that can do binary
> arithmetic and those that can't.

TIP 4: Don't 'kill -9' the postmaster

Wed, 23 Mar 2005 22:03:54 GMT
multi-column btree index for real values
Martijn,

Thanks.  So that implies that a multidimensional btree index is
useless for two columns of floats (one will probably always
be searching on the first index for a tree of large height).

Let me restate my question as an example.  Supose I have columns
of longitude and latitude.  What is the best indexing strategy to
find all tuples with in a two dimensional bound of longitude and
latitude.  E.g. with where clause

lat between 21.49 and 37.41 and
lon between 70.34 and 75.72
--Martin

Martijn van Oosterhout wrote on
Sun, 06 Oct 2002 00:02:58 +1000

Quote:

>> Folks,

>> Can someone quickly describe how the btree is implemented for multiple
>> columns?  In particular, under what (if any) circumstances is there an
>> advantage if the index is over floating point values?

>AFAIK, multi-column btrees and simply handled by building a btree of the
>first column. Each leaf contains a reference to another btree for the second
>column, etc...

>btrees are useful for < and > comparisons, meaning that queries saying WHERE
>x BETWEEN 1.0 and 1.5 can use the index.
>--

>> There are 10 kinds of people in the world, those that can do binary
>> arithmetic and those that can't.

TIP 6: Have you searched our list archives?

http://archives.postgresql.org

Wed, 23 Mar 2005 23:36:49 GMT
multi-column btree index for real values

Quote:

> Martijn,

> Thanks.  So that implies that a multidimensional btree index is
> useless for two columns of floats (one will probably always
> be searching on the first index for a tree of large height).

> Let me restate my question as an example.  Supose I have columns
> of longitude and latitude.  What is the best indexing strategy to
> find all tuples with in a two dimensional bound of longitude and
> latitude.  E.g. with where clause

>            lat between 21.49 and 37.41 and

Oh, rtree.  That is exactly the index type you want.

--
Bruce Momjian                        |  http://candle.pha.pa.us

+  If your life is a hard drive,     |  13 Roberts Road
+  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

TIP 2: you can get off all lists at once with the unregister command

Thu, 24 Mar 2005 02:31:35 GMT
multi-column btree index for real values
Thanks Bruce.  Some simple tests on a 10 million tuple data base shows
that r-tree works well for this. (It took me a while to realize
that I had to sort boxes of zero area rather than points).

However, it seems that the rtree index has a serious memory leak for
7.2.2.  Is that known?

--Martin

Bruce Momjian wrote on Sat, 05 Oct 2002 14:30:47 EDT

Quote:

>> Martijn,

>> Thanks.  So that implies that a multidimensional btree index is
>> useless for two columns of floats (one will probably always
>> be searching on the first index for a tree of large height).

>> Let me restate my question as an example.  Supose I have columns
>> of longitude and latitude.  What is the best indexing strategy to
>> find all tuples with in a two dimensional bound of longitude and
>> latitude.  E.g. with where clause

>>            lat between 21.49 and 37.41 and

>Oh, rtree.  That is exactly the index type you want.

>--
>  Bruce Momjian                        |  http://candle.pha.pa.us

>  +  If your life is a hard drive,     |  13 Roberts Road
>  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

>TIP 2: you can get off all lists at once with the unregister command

TIP 4: Don't 'kill -9' the postmaster

Thu, 24 Mar 2005 04:39:36 GMT
multi-column btree index for real values

Quote:

> Thanks Bruce.  Some simple tests on a 10 million tuple data base shows
> that r-tree works well for this. (It took me a while to realize
> that I had to sort boxes of zero area rather than points).

> However, it seems that the rtree index has a serious memory leak for
> 7.2.2.  Is that known?

Uh, I am not aware of that, but you can try 7.3beta to see if it is
better, and if not, report back.

--
Bruce Momjian                        |  http://candle.pha.pa.us

+  If your life is a hard drive,     |  13 Roberts Road
+  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

TIP 4: Don't 'kill -9' the postmaster

Thu, 24 Mar 2005 05:40:48 GMT
multi-column btree index for real values
Ok.  I don't have the disk space to migrate to 7.3 right now.
However, I checked out the beta source and noticed the following new
lines near line 934 in src/backend/access/rtree/rtree.c in 7.2.2:

+                       pfree(DatumGetPointer(union_dl));
+                       pfree(DatumGetPointer(union_dr));

Looks like a leak fix to me.  Patching these in, I found that the leak
is much reduced; still looks like a tiny leak remains.  We will try
7.3beta asap.

Thanks.

Bruce Momjian wrote on Sat, 05 Oct 2002 17:39:45 EDT

Quote:

>> Thanks Bruce.  Some simple tests on a 10 million tuple data base shows
>> that r-tree works well for this. (It took me a while to realize
>> that I had to sort boxes of zero area rather than points).

>> However, it seems that the rtree index has a serious memory leak for
>> 7.2.2.  Is that known?

>Uh, I am not aware of that, but you can try 7.3beta to see if it is
>better, and if not, report back.

>--
>  Bruce Momjian                        |  http://candle.pha.pa.us

>  +  If your life is a hard drive,     |  13 Roberts Road
>  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

>TIP 4: Don't 'kill -9' the postmaster

TIP 4: Don't 'kill -9' the postmaster

Thu, 24 Mar 2005 07:05:49 GMT
multi-column btree index for real values

Quote:

> Thanks Bruce.  Some simple tests on a 10 million tuple data base shows
> that r-tree works well for this. (It took me a while to realize
> that I had to sort boxes of zero area rather than points).

> However, it seems that the rtree index has a serious memory leak for
> 7.2.2.  Is that known?

probably, try contrib/rtree_gist

Quote:

> --Martin

> Bruce Momjian wrote on Sat, 05 Oct 2002 14:30:47 EDT

> >> Martijn,

> >> Thanks.  So that implies that a multidimensional btree index is
> >> useless for two columns of floats (one will probably always
> >> be searching on the first index for a tree of large height).

> >> Let me restate my question as an example.  Supose I have columns
> >> of longitude and latitude.  What is the best indexing strategy to
> >> find all tuples with in a two dimensional bound of longitude and
> >> latitude.  E.g. with where clause

> >>            lat between 21.49 and 37.41 and

> >Oh, rtree.  That is exactly the index type you want.

> >--
> >  Bruce Momjian                        |  http://candle.pha.pa.us

> >  +  If your life is a hard drive,     |  13 Roberts Road
> >  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

> >TIP 2: you can get off all lists at once with the unregister command

> TIP 4: Don't 'kill -9' the postmaster

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)

phone: +007(095)939-16-83, +007(095)939-23-83