Index for OR operator: a=x or b=x
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)