Take the 2-minute tour ×
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.

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

1 Answer

up vote 1 down vote accepted

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

WHERE X > y

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
1  
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
add comment

Your Answer

 
discard

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.