How many B-tree indexes do I need to support lookups by any subset of n columns?
How many B-tree indexes do I need to support lookups by any subset of n columns


At least for Oracle (12.x) and Postgres the answer is: n

That is: one index for each column. Both DBMS are able to combine multiple indexes for a single query. In older Oracle versions you would need to use a single bitmap index on all columns. Oracle 12.1 can do a bitmap "scan" on the fly (don't know if that was already possible in 11.x - I don't have an 11.x installation to test). 

Test setup:

create table idx_test (a int, b int, c int, d int, e int);
create index idx_a on idx_test(a);
create index idx_b on idx_test(b);
create index idx_c on idx_test(c);
create index idx_d on idx_test(d);


Now populate the table with million rows and random values for each column. I did this in Postgres using: 

insert into idx_test (a,b,c,d,e)
select (random() * 10000 + 1)::int, 
       (random() * 100000 + 1)::int, 
       (random() * 1000000 + 1)::int, 
       (random() * 100000 + 1)::int, 
       (random() * 10000 + 1)::int
from generate_series(1,1000000);


Then copied the rows over to the Oracle server.

The following query

select *
from idx_test
where b = 42 or a = 24 or c = 100;


shows the following execution plan in Postgres:

QUERY PLAN                                                                                                                    
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on idx_test  (cost=6.25..166.36 rows=111 width=20) (actual time=0.032..0.244 rows=113 loops=1)               
  Recheck Cond: ((b = 42) OR (a = 24) OR (c = 100))                                                                           
  Heap Blocks: exact=113                                                                                                      
  -&gt;  BitmapOr  (cost=6.25..6.25 rows=111 width=0) (actual time=0.020..0.020 rows=0 loops=1)                                  
        -&gt;  Bitmap Index Scan on idx_test_b_idx  (cost=0.00..1.96 rows=11 width=0) (actual time=0.009..0.009 rows=11 loops=1) 
              Index Cond: (b = 42)                                                                                            
        -&gt;  Bitmap Index Scan on idx_test_a_idx  (cost=0.00..2.27 rows=98 width=0) (actual time=0.007..0.007 rows=100 loops=1)
              Index Cond: (a = 24)                                                                                            
        -&gt;  Bitmap Index Scan on idx_test_c_idx  (cost=0.00..1.93 rows=2 width=0) (actual time=0.003..0.003 rows=2 loops=1)   
              Index Cond: (c = 100)                                                                                           
Planning time: 0.077 ms                                                                                                       
Execution time: 0.270 ms                                                                                                      


You can see that the corresponding index for each column was used. The execution plan for Oracle 12.1 is nearly identical:

PLAN_TABLE_OUTPUT                                                                     
--------------------------------------------------------------------------------------
Plan hash value: 2332290563                                                           

--------------------------------------------------------------------------------------
| Id  | Operation                           | Name     | E-Rows |E-Bytes| Cost (%CPU)|
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |          |     43 |  2795 |   740   (0)|
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| IDX_TEST |     43 |  2795 |   740   (0)|
|   2 |   BITMAP CONVERSION TO ROWIDS       |          |        |       |            |
|   3 |    BITMAP OR                        |          |        |       |            |
|   4 |     BITMAP CONVERSION FROM ROWIDS   |          |        |       |            |
|*  5 |      INDEX RANGE SCAN               | IDX_C    |        |       |     3   (0)|
|   6 |     BITMAP AND                      |          |        |       |            |
|   7 |      BITMAP CONVERSION FROM ROWIDS  |          |        |       |            |
|*  8 |       INDEX RANGE SCAN              | IDX_A    |        |       |     3   (0)|
|   9 |      BITMAP CONVERSION FROM ROWIDS  |          |        |       |            |
|* 10 |       INDEX RANGE SCAN              | IDX_B    |        |       |     3   (0)|
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):                                   
---------------------------------------------------                                   

   5 - access("C"=100)                                                                
   8 - access("A"=24)                                                                 
  10 - access("B"=42)                                                                 


A query with only two columns will only use two indexes:

select *
from idx_test
where a = 1001 and b = 45877;


Postgres:

QUERY PLAN                                                                                                                   
-----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on idx_test  (cost=4.48..5.99 rows=1 width=20) (actual time=0.118..0.118 rows=0 loops=1)                    
  Recheck Cond: ((b = 45877) AND (a = 1001))                                                                                 
  -&gt;  BitmapAnd  (cost=4.48..4.48 rows=1 width=0) (actual time=0.117..0.117 rows=0 loops=1)                                  
        -&gt;  Bitmap Index Scan on idx_test_b_idx  (cost=0.00..1.96 rows=11 width=0) (actual time=0.075..0.075 rows=11 loops=1)
              Index Cond: (b = 45877)                                                                                        
        -&gt;  Bitmap Index Scan on idx_test_a_idx  (cost=0.00..2.27 rows=98 width=0) (actual time=0.038..0.038 rows=93 loops=1)
              Index Cond: (a = 1001)                                                                                         
Planning time: 0.150 ms                                                                                                      
Execution time: 0.157 ms                                                                                                     


And Oracle:

PLAN_TABLE_OUTPUT                                                                     
--------------------------------------------------------------------------------------
Plan hash value: 3618970768                                                           

--------------------------------------------------------------------------------------
| Id  | Operation                           | Name     | E-Rows |E-Bytes| Cost (%CPU)|
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |          |     78 |  5070 |    22   (0)|
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| IDX_TEST |     78 |  5070 |    22   (0)|
|   2 |   BITMAP CONVERSION TO ROWIDS       |          |        |       |            |
|   3 |    BITMAP AND                       |          |        |       |            |
|   4 |     BITMAP CONVERSION FROM ROWIDS   |          |        |       |            |
|*  5 |      INDEX RANGE SCAN               | IDX_A    |     43 |       |     3   (0)|
|   6 |     BITMAP CONVERSION FROM ROWIDS   |          |        |       |            |
|*  7 |      INDEX RANGE SCAN               | IDX_B    |     43 |       |     3   (0)|
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):                                   
---------------------------------------------------                                   

   5 - access("A"=1001)                                                               
   7 - access("B"=45877)                                                              


The indexes are also used for an OR condition:

select *
from idx_test
where a = 1001 or b = 45877;


Postgres:

QUERY PLAN                                                                                                                   
-----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on idx_test  (cost=4.29..161.31 rows=109 width=20) (actual time=0.053..0.240 rows=104 loops=1)              
  Recheck Cond: ((a = 1001) OR (b = 45877))                                                                                  
  Heap Blocks: exact=104                                                                                                     
  -&gt;  BitmapOr  (cost=4.29..4.29 rows=109 width=0) (actual time=0.038..0.038 rows=0 loops=1)                                 
        -&gt;  Bitmap Index Scan on idx_test_a_idx  (cost=0.00..2.27 rows=98 width=0) (actual time=0.030..0.030 rows=93 loops=1)
              Index Cond: (a = 1001)                                                                                         
        -&gt;  Bitmap Index Scan on idx_test_b_idx  (cost=0.00..1.96 rows=11 width=0) (actual time=0.007..0.007 rows=11 loops=1)
              Index Cond: (b = 45877)                                                                                        
Planning time: 0.111 ms                                                                                                      
Execution time: 0.273 ms                                                                                                     


Oracle:

PLAN_TABLE_OUTPUT                                                                     
--------------------------------------------------------------------------------------
Plan hash value: 2853963857                                                           

--------------------------------------------------------------------------------------
| Id  | Operation                           | Name     | E-Rows |E-Bytes| Cost (%CPU)|
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |          |     62 |  4030 |   879   (0)|
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| IDX_TEST |     62 |  4030 |   879   (0)|
|   2 |   BITMAP CONVERSION TO ROWIDS       |          |        |       |            |
|   3 |    BITMAP OR                        |          |        |       |            |
|   4 |     BITMAP CONVERSION FROM ROWIDS   |          |        |       |            |
|*  5 |      INDEX RANGE SCAN               | IDX_A    |        |       |     3   (0)|
|   6 |     BITMAP CONVERSION FROM ROWIDS   |          |        |       |            |
|*  7 |      INDEX RANGE SCAN               | IDX_B    |        |       |     3   (0)|
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):                                   
---------------------------------------------------                                   

   5 - access("A"=1001)                                                               
   7 - access("B"=45877)                                                              


A quick test with SQL Server 2016 shows that it does essentially the same thing:

StmtText                                                                                                                             | StmtId | NodeId | Parent | PhysicalOp   | LogicalOp  | Argument                                                                                                  
-------------------------------------------------------------------------------------------------------------------------------------+--------+--------+--------+--------------+------------+------------------------------------------------------------------------------------------------------
select * from idx_test where b = 42 and a = 24                                                                                       |      1 |      1 |      0 |              |            | 1                                                                                                         
  |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))                                                                          |      1 |      2 |      1 | Nested Loops | Inner Join | OUTER REFERENCES:([Bmk1000])                                                                              
       |--Hash Match(Inner Join, HASH:([Bmk1000])=([Bmk1000]), RESIDUAL:([Bmk1000] = [Bmk1000]))                                     |      1 |      4 |      2 | Hash Match   | Inner Join | HASH:([Bmk1000])=([Bmk1000]), RESIDUAL:([Bmk1000] = [Bmk1000])                                            
       |    |--Index Seek(OBJECT:([TestDB].[dbo].[idx_test].[idx_b]), SEEK:([TestDB].[dbo].[idx_test].[b]=(42)) ORDERED FORWARD)     |      1 |      5 |      4 | Index Seek   | Index Seek | OBJECT:([TestDB].[dbo].[idx_test].[idx_b]), SEEK:([TestDB].[dbo].[idx_test].[b]=(42)) ORDERED FORWARD 
       |    |--Index Seek(OBJECT:([TestDB].[dbo].[idx_test].[idx_a]), SEEK:([TestDB].[dbo].[idx_test].[a]=(24)) ORDERED FORWARD)     |      1 |      6 |      4 | Index Seek   | Index Seek | OBJECT:([TestDB].[dbo].[idx_test].[idx_a]), SEEK:([TestDB].[dbo].[idx_test].[a]=(24)) ORDERED FORWARD 
       |--RID Lookup(OBJECT:([TestDB].[dbo].[idx_test]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)                          |      1 |     16 |      2 | RID Lookup   | RID Lookup | OBJECT:([TestDB].[dbo].[idx_test]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD                  




Is this the most efficient index access possible? Probably not, but it is most probably the best compromise between indexing overhead and query flexibility.