Postgresql – the algorithmic complexity of a PosgtreSQL greater than or lesser than index query (compared to equality)

indexperformancepostgresqlquery-performance

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!

Best Answer

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.

Related Question