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

---------------------------(end of broadcast)---------------------------
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

---------------------------(end of broadcast)---------------------------
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.

---------------------------(end of broadcast)---------------------------
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.

---------------------------(end of broadcast)---------------------------
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

---------------------------(end of broadcast)---------------------------
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

>---------------------------(end of broadcast)---------------------------
>TIP 2: you can get off all lists at once with the unregister command


---------------------------(end of broadcast)---------------------------
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

---------------------------(end of broadcast)---------------------------
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.
Our database is about 500 million tuples with about 100 fields.
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

>---------------------------(end of broadcast)---------------------------
>TIP 4: Don't 'kill -9' the postmaster

---------------------------(end of broadcast)---------------------------
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

> >---------------------------(end of broadcast)---------------------------
> >TIP 2: you can get off all lists at once with the unregister command

> ---------------------------(end of broadcast)---------------------------
> 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

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster



Thu, 24 Mar 2005 12:07:18 GMT
 
 [ 9 post ] 

 Relevant Pages 

1. HELP - Accessing column values in multi-column ComboBox

2. Dropping column silently kills multi-coumn index (was [ODBC] Error when accessing tables with deleted columns)

3. Multiple indexes or multi-column index?

4. Multi column index versus many indexes (7 vs 2000)

5. Dropping column silently kills multi-coumn index (was [ODBC] Error when accessing tables with deleted columns)

6. Maximum Value of a REAL Column

7. multi-columns with getdate as default - same value?

8. Identity column value in multi-table updates

9. Return multi column empty table with values() ?

10. FMP Multi Column Unique Index

11. Multi-column indexes

12. Dropping column silently kills multi-coumn index


 
Powered by phpBB® Forum Software