3

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?

Erwin Brandstetter
  • 605,456
  • 145
  • 1,078
  • 1,228
Ernest Friedman-Hill
  • 80,601
  • 10
  • 150
  • 186

1 Answers1

5

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.

Garen
  • 941
  • 2
  • 9
  • 20
Erwin Brandstetter
  • 605,456
  • 145
  • 1,078
  • 1,228
  • @ErnestFriedman-Hill: Nice! I added a bit about a new feature of 9.2 that might also intrigue you. :) – Erwin Brandstetter Aug 30 '12 at 03:31
  • What can I do if index is not used for next condition: `sys_time() <@ sys_period`. For `...using gist ( sys_period )` – Eugen Konkov Jul 06 '19 at 19:59
  • @EugenKonkov: Depends. Maybe start a new question [with all relevant details](https://stackoverflow.com/tags/postgresql-performance/info). You can always link to this one for context. – Erwin Brandstetter Jul 09 '19 at 12:29