Skip site navigation (1) Skip section navigation (2)

Re: GiST indexing tuples

From: Matthew <matthew(at)flymine(dot)org>
To: pgsql-performance(at)postgresql(dot)org
Subject: Re: GiST indexing tuples
Date: 2007-11-30 13:45:41
Message-ID: Pine.LNX.4.58.0711301333040.3731@aragorn.flymine.org (view raw or flat)
Thread:
Lists: pgsql-performance
On Thu, 29 Nov 2007, Matthew T. O'Connor wrote:
> Matthew wrote:
> > For instance, the normal B-tree index on (a, b) is able to answer queries
> > like "a = 5 AND b > 1" or "a > 5". An R-tree would be able to index these,
> > plus queries like "a > 5 AND b < 1".
>
> Sorry in advance if this is a stupid question, but how is this better
> than two index, one on "a" and one on "b"?  I supposed there could be a
> space savings but beyond that?

Imagine you have a table with columns "a" and "b". The table has a
bazillion rows, and the values of "a" and "b" both range from a negative
bazillion to a positive bazillion. (Note this is exactly the case in our
database, for some value of a bazillion.) Then, you run the query:

SELECT * FROM table WHERE a > 5 AND b < 1;

So, an index on "a" will return half a bazillion results for the
constraint "a > 5". Likewise, the index on "b" will return half a
bazillion results for the constraint "b < 1". However, the intersection of
these two constraints could be just a few rows. (Note this is exactly the
case in our database.)

Now, Postgres has two options. It could use just the one index and filter
half a bazillion rows (which is what it used to do), or it could create a
bitmap with a bazillion bits from each index, and do a logical AND
operation on them to create a new bitmap with just a few bits set (which
it now can do under some circumstances). Either way, it's going to be a
heavy operation.

An R-tree index on "a, b" would instantly return just those few rows,
without using significant amounts of memory or time.

Hope that helps,

Matthew

-- 
Patron: "I am looking for a globe of the earth."
Librarian: "We have a table-top model over here."
Patron: "No, that's not good enough. Don't you have a life-size?"
Librarian: (pause) "Yes, but it's in use right now."

In response to

pgsql-performance by date

Next:From: Bill MoranDate: 2007-11-30 14:20:33
Subject: Re: Appending "LIMIT" to query drastically decreases performance
Previous:From: MatthewDate: 2007-11-30 13:30:28
Subject: Re: Appending "LIMIT" to query drastically decreases performance

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group