Efficient sorted bounding box query

How would I create indexes in PostgresSQL 8.3 which would make a sorted bounding box query efficient? The table I'm querying has quite a few rows.

That is I want the create indexes that makes the following query as efficient as possible:

S开发者_高级运维ELECT * FROM features 
WHERE lat BETWEEN ? AND ?
AND lng BETWEEN ? AND ?
ORDER BY score DESC

The features table look like this:

   Column   |          Type          |   
------------+------------------------+
 id         | integer                |
 name       | character varying(255) | 
 type       | character varying(255) | 
 lat        | double precision       | 
 lng        | double precision       | 
 score      | double precision       | 
 html       | text                   | 

To create a GiST index on a point attribute so that we can efficiently use box operators on the result of the conversion function:

CREATE INDEX pointloc
    ON points USING gist (box(location,location));
SELECT * FROM points
    WHERE box(location,location) && '(0,0),(1,1)'::box;

http://www.postgresql.org/docs/9.0/static/sql-createindex.html

This is the example in 9.0 docs. It should work for 8.3 though as these are features that have been around for ages.

You could try using a GiST index to implement an R-Tree. This type of index is poorly documented, so you might have to trawl through example code in the source distribution.

(Note: My prior advice to use R-Tree indexes appears to be out of date; they are deprecated.)

Sounds like you'd want to take a look at PostGIS, a PostgreSQL module for spatial data types and queries. It supports quick lookups using GiST indexes. Unfortunately I can't guide you further as I haven't used PostGIS myself.