Index for OR operator: a=x or b=x

Question

I have table with three integer columns id, a and b.
I want to get all records where a or b match specified parameter ordered by id:

select id, a, b from t where a=x or b=x order by id

Note that x value is same for a and b.

What it the most suitable index here?

Upd: Is there any use of the fact that we always look for same value in columns a and b? Can we create an expression index for that?

Answer 1

The simple and fast solution are two indexes on (a, id) and (b, id). Be sure to have a respectively b as leading column:

• Working of indexes in PostgreSQL

The added id is not going to help for your particular query, you could as well just create them on (a) and (b) to get the bitmap index scans that @shx explained. But the index for two integer is exactly as big as for one column. There may be other use cases that actually benefit from the added id.

• Is a composite index also good for queries on the first field?

If your actual SELECT list is narrow like in your example and some preconditions are met, I would go for index-only scans.
Create indexes on (a, b, id) and (b, a, id).

This equivalent query (given that id or at least (id,a,b) is unique) helps Postgres choose the query plan with index-only scans:

EXPLAIN
SELECT id,a,b FROM t WHERE a = 10
UNION
SELECT id,a,b FROM t WHERE b = 10
ORDER  BY id;

Sort  (cost=110.45..112.92 rows=988 width=12)
  Sort Key: t.id
  ->  HashAggregate  (cost=51.42..61.31 rows=988 width=12)
        Group Key: t.id, t.a, t.b
        ->  Append  (cost=0.42..44.02 rows=988 width=12)
              ->  Index Only Scan using t_ab_id_idx on t  (cost=0.42..17.07 rows=494 width=12)
                    Index Cond: (a = 10)
              ->  Index Only Scan using t_ba_id_idx on t t_1  (cost=0.42..17.07 rows=494 width=12)
                    Index Cond: (b = 10)

Performance depends on data distribution, write patterns and value frequencies, among other things. In my tests on pg 9.5 I see similar performance to the solution in @shx's answer - as long as we select whole rows (i.e. heap tuples are not much bigger than index tuples).

Typically, there are additional columns in the underlying table - which would not impair performance of this query at all, while the alternative loses ground since it has to read more pages for wider rows in the underlying table.

Answer to added question

Is there any use of the fact that we always look for same value in columns a and b? Can we create an expression index for that?

I can't think of a way to capitalize on that for the table as is. An index entry can only reference a single table row. Theoretically, a GIN index on (ARRAY[a,b]) might work, but I could not get useful results with it (nor did I expect to).

You would need two rows per row in the base table (except where a = b) to enable a single pass on a b-tree index for the job. Actually possible with the help of a MATERIALIZED VIEW. The added overhead and maintenance cost only seems reasonable if you have much more read than write activity and you need to optimize performance for your given query. You need to understand MVs and know when to refresh.

CREATE MATERIALIZED VIEW mv_t AS
SELECT a AS x, id, a, b FROM t
UNION  -- eliminate dupes
SELECT b AS x, id, a, b FROM t
ORDER  BY x, id;

x is the unified search key. Rows in the base table are listed once for every distinct value in [a, b]. This query returns the same result as your original, but faster:

SELECT id,a,b FROM mv_t WHERE x = 10 ORDER BY id;

The query can benefit from a single pass on a single index now. Plus, rows in the MV are sorted physically like they are returned, which helps the approach with a simple index:

CREATE INDEX mv_t_x_idx ON mv_t (x); -- simple

Sort  (cost=88.01..90.48 rows=990 width=12)
  Sort Key: id
  ->  Index Scan using mv_t_x_idx on mv_t  (cost=0.42..38.75 rows=990 width=12)
        Index Cond: (x = 10)

Also ideal for a BRIN index (Postgres 9.5+) for huge tables:

• Speed up creation of Postgres partial index

You can go for index-only scans again:

CREATE INDEX mv_t_full_idx ON mv_t (x, id, a, b);  -- covering index

Index Only Scan using mv_t_full_idx on mv_t  (cost=0.42..33.75 rows=990 width=12)
  Index Cond: (x = 10)

Answer 2

Since PostgreSQL has BitmapOr, i think you have only to create two indexes of a and b. Also you can create an index of id if necessary.

testdb=# CREATE TABLE t (id int, a int, b int);
CREATE TABLE
testdb=# CREATE INDEX t_a_idx ON t (a);
CREATE INDEX
testdb=# CREATE INDEX t_b_idx ON t (b);
CREATE INDEX
testdb=# CREATE INDEX t_id_idx ON t (id);
CREATE INDEX
testdb=# INSERT INTO t SELECT generate_series(0,1000000), 700*random(), 700*random();
INSERT 0 1000001
testdb=# ANALYZE t;
ANALYZE

In addition, I create two other indexes:

testdb=# CREATE INDEX t_ia_idx ON t (id, a);
CREATE INDEX
testdb=# CREATE INDEX t_ib_idx ON t (id, b);
CREATE INDEX
testdb=# ANALYZE t;
ANALYZE

The result of EXPLAIN ANALYZE is shown below:

testdb=# EXPLAIN ANALYZE SELECT id,a,b FROM t WHERE a = 10 OR b = 10 order by id;
                                                            QUERY PLAN                                                             
-----------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=5117.32..5124.33 rows=2803 width=12) (actual time=5.785..5.958 rows=2864 loops=1)
   Sort Key: id
   Sort Method: quicksort  Memory: 231kB
   ->  Bitmap Heap Scan on t  (cost=41.26..4956.81 rows=2803 width=12) (actual time=1.430..4.430 rows=2864 loops=1)
         Recheck Cond: ((a = 10) OR (b = 10))
         Heap Blocks: exact=2206
         ->  BitmapOr  (cost=41.26..41.26 rows=2805 width=0) (actual time=1.155..1.155 rows=0 loops=1)
               ->  Bitmap Index Scan on t_a_idx  (cost=0.00..19.94 rows=1406 width=0) (actual time=0.918..0.918 rows=1464 loops=1)
                     Index Cond: (a = 10)
               ->  Bitmap Index Scan on t_b_idx  (cost=0.00..19.92 rows=1399 width=0) (actual time=0.236..0.236 rows=1404 loops=1)
                     Index Cond: (b = 10)
 Planning time: 0.268 ms
 Execution time: 6.137 ms
(13 rows)