Comment by rand_r | Hacker News Reader

Comment by rand_r | Hacker News Reader

Parent Full thread

This is sort of an aside, but a very interesting thing about Postgres is that it can efficiently combine independent column indexes together, so there is much less of a need, compared to older databases, to even create multi-column indexes. It's a feature from 8.1 called "Bitmap Scan". Basically, if you create an index on column X and an index on column Y, it can use them to do queries involving either or both columns pretty efficiently (for any number of columns).

It's not as fast as a multi-column index, but the savings of not having to worry about all the combinations of columns that can be queried together could well be worth it.

- https://www.postgresql.org/docs/release/8.1.0/

- https://www.postgresql.org/docs/current/indexes-bitmap-scans...

It’s very cool, but at high throughput you really see the difference. This bitmap scan can take huge amounts of cpu, reduced to nothing (and much faster) when setting up a proper multi column index.

On small/medium tables and lowish throughout though, yeah it’s often good enough and avoids having many indexes for specific use cases (which is a cost in itself, in memory/cpu/storage)

Do you have any benchmarks? Be interesting to compare.

Bitmap Scan sounds a lot like Rushmore technology in Foxpro[1]. Are they the same?

1) https://en.wikipedia.org/wiki/FoxPro

It is difficult to find a complete explanation for Rushmore nowadays, from what I remember, it would create a bitmap where each bit represented the nth record of the table you wanted to search, then with a single, fast sequential scan it would set the nth bit to 1 if the record satisfied all clauses of your search, 0 otherwise.

Try to see if this makes any sense to you: http://www.foxpert.com/docs/howfoxproworks.en.htm

Is there any potential that indexes could be created over foreign key joins in the future? I know that as of today, no multi-table indices or statistics exist for Postgres, which has had led me to do some further denormalisations.

Reply on news.ycombinator.com