Can multi indexing speed up "AND" of comparisons?

Question

I am using PostgreSQL and have query of type:

SELECT * from t
WHERE a > 30 AND b < 20

where a and b are columns of table t. I have indexed columns a and b. Would that speed up this query or do I need to add a multi index (a, b)?

This post mentions that multi index speeds up query of type a = 3 and b = 4 and a = 3 but I am not sure if same applies for comparisons.

Also official PostgreSQL docs says that it can speed up queries of type SELECT name FROM test2 WHERE major = constant AND minor = constant, but in the later text it says many things which I don't really understand and hence asking this question here.

Answer 1

A multi-column index cannot be used for both conditions. For example, an index on (a, b) could be used for the condition a > 30, but not for b < 20.

If one of the conditions alone is selective enough and the other does not reduce the result set considerably, just create an index for that condition.

If you need index support for both conditions because neither of them is selective enough on its own, create two indexes, one for each condition. Then PostgreSQL can use a bitmap index scan on both indexes and a “bitmap or” to combine the results.

Answer 2

All the indexes you mention can in principle speed up the query (relative to no indexes), but not by equal amounts. And it would depend on how many rows meet each individual condition, and how many meet the combined condition.

With a btree index on (a,b), for example, it can jump to the part of the index where A>30, and then scan to the end of the index. But it can throw away things with B<20 just based on data stored in the index, without having to visit the table. This won't be as fast as if it could jump to a spot where everything with B<20 lives (which it can't because there is no single spot which meets that condition since B is not the leading column and the leading column can have multiple values of interest), but will still be faster than visiting the table for each row, like it would have to do with an index on just (a).

So yes, (a,b) can speed up the given query compared to having no index, and compared to having just (a). But if the query were something like WHERE A = 31 AND b < 20 while still returning the same number of rows, that index would speed up that query much more than your given query. Because in the new case, it could jump where A=31, and start scanning from there. But then it can stop the scan either where A is no longer =31, or where B is no longer <20. So that is unlike the first instance, where it can't stop earlier than the end of the index.

As Laurenz says, it can also use separate indexes on (a) and (b) and combine them with BitmapAnd. Whether doing so will actually be faster than just doing a scan on (a,b) is hard to say. We would have to know more about your data distributions, and even then would probably need to do the experiments and see.

You could also try a fancier index, like using gist (a,b) (you would have to use the btree_gist extension). In theory that could be better, but I rarely find them to be better in practise for something like two scalars. I think the problem is that the GiST indexes don't end up being very well balanced.