Fast table indexing for range lookup

Question

I have a Postgres table with about 4.5 million rows. The columns are basically just

low BIGINT,
high BIGINT,
data1,
data2, 
...

When you query this table, you have a long integer, and want to find the data corresponding to the range between low and high that includes that value. What would be the best way to index this table for fast lookups?

Answer 1

A multi-column index with reversed sort order:

CREATE INDEX tbl_low_high_idx on tbl(low, high DESC);

This way, the index can be scanned forward to where low is high enough, then take all rows until high is too low - all in one scan. That's the main reason why sort order is implemented for indexes to begin with: to combine different sort orders in a multi-column index with different order. Basically, a b-tree index can be traversed in both directions at practically the same speed, so ASC / DESC would hardly be needed for single-column indexes.

---

You may also be interested in the new range types of PostgreSQL 9.2. Can be indexed with a GiST index like this:

CREATE INDEX tbl_idx ON tbl USING gist (low_high);

Should make a query of this form perform very fast:

SELECT * FROM tbl WHERE my_value <@ low_high;

<@ being the "element is contained by" operator.