Take the 2-minute tour ×

Assuming there is an index idx_int on an int_col column, what is the algorithmic complexity of a query like this?

SELECT id FROM table
    WHERE table.int_col > 1;

I'm specifically interested in knowing if the query is significantly more inefficient than if doing an equality clause (which, if I understand correctly is O(log N)). I am pretty sure both of them can use a B-tree, so I would expect them to be about the same in terms of complexity / efficiency.

Thanks very much!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I don't know the PostgreSQL engine, however in the real world, doing


will cause the engine to seek to the point in the B-tree index where X = y, then scan the rest of the data to return the relevant rows. With enough data, it will take significant time to return.

Clearly, WHERE X = y will return more quickly since it only has to return a single row, necessitating only the initial seek operation.

This is, of course, assuming X is indexed.

share|improve this answer
Excellent. If this applies to PostgreSQL, it's good news. I would return only one record (limit 1) or at most a few, so that's great. Thanks! –  Juan Carlos Coto Mar 27 '13 at 21:16

Your Answer


