Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.