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

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?

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

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

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.

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:

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

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)
```
• So the `t_ia_idx` and `t_ib_idx` indexes not really useful here, right? – Alexei Osipov Mar 22 '16 at 0:46
• According to my investigation, t_ia_idx and t_ib_idx are not needed. These were prepared for comparison. – shx Mar 22 '16 at 1:28