4

First, some background ideas

Generally, an SQL database which supports multi-column B-tree indexes also supports doing a lookup by a subset of the columns in the index if and only if they're the first columns in the index. For example, if I have an index on columns (a, b, c, d) and would like to execute:

SELECT * FROM my_table
WHERE b = 7 AND a = 'foo';

then this will use the index and be fast, because the pair (a, b) is located at the start of the index and so the database can navigate the tree looking for index records starting with ('foo', 7, ... ). However, if I run

SELECT * FROM my_table
WHERE b = 7 AND c = 'bar';

then the index will not be used*, because matching records will be distributed all over the index depending upon the value they have in column a.

* (except perhaps by doing a full or partial scan of the index, as described in Evan's answer below - but since a full index scan still has the same time complexity as a full table scan, and a partial index scan potentially does too, this doesn't help much.)

The problem

I have a table with n columns and a potentially huge number of rows. I also have a front-end GUI that allows the user to filter by the exact value of an arbitrary combination of those columns and view a table of results. It is not acceptable for any query generated by this front end to cause a full table scan to get its results; every possible filter has to be supported by an index.

With n columns, what is the minimum number of B-tree indexes I need to create to ensure that every possible combination of columns is covered by some index?

Example with n=4

Suppose my table has 4 columns: a, b, c, and d. There are then 15 different combinations of columns my user might filter by:

a b c d
a b c  
a b d  
a c d  
b c d  
a b    
a c    
a d    
b c    
b d    
c d    
a      
b      
c      
d      

However, I can support lookups from any arbitrary subset of these 4 columns using only the following 6 B-tree indexes:

(a, b, c, d)
(b, c, d)
(c, d, a)
(d, b, a)
(a, c)
(a, d)

To illustrate this, below are the 15 possible subsets alongside the index that can be used to do a lookup by that subset:

a b c d   (a, b, c, d)
a b c     (a, b, c, d)
a b d     (d, b, a)
a c d     (c, d, a)
b c d     (b, c, d)
a b       (a, b, c, d)
a c       (a, c)
a d       (a, d)
b c       (b, c, d)
b d       (d, b, a)
c d       (c, d, a)
a         (a, b, c, d)
b         (b, c, d)
c         (c, d, a)
d         (d, b, a)

I'm unsure how to generalise this idea to tables with large numbers of columns, though, or how the number of indexes required scales with n. Hence my question: how many indexes are needed to extend this approach to n columns, and how can I determine what they are?

(I'm primarily interested in the specific theoretical problem of how to support these lookups using B-tree indexes - but I'm open to other solutions, if for example there's an index type that neatly solves this precise problem better than a bunch of B-tree indexes would.)

5

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                                                                                                      
  ->  BitmapOr  (cost=6.25..6.25 rows=111 width=0) (actual time=0.020..0.020 rows=0 loops=1)                                  
        ->  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)                                                                                            
        ->  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)                                                                                            
        ->  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))                                                                                 
  ->  BitmapAnd  (cost=4.48..4.48 rows=1 width=0) (actual time=0.117..0.117 rows=0 loops=1)                                  
        ->  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)                                                                                        
        ->  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                                                                                                     
  ->  BitmapOr  (cost=4.29..4.29 rows=109 width=0) (actual time=0.038..0.038 rows=0 loops=1)                                 
        ->  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)                                                                                         
        ->  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.

3

Pushing theory aside a little, you are likely to see vanishing returns with wider and wider indexes so might be better to provide, for instance, just indexes on each two-column combination.

Is a search for a=1 AND b=2 on an index (a,b) followed by a lookup to check c=3 going to be significantly less efficient (or at all measurably less efficient) than searching an index on (a,b,c) especially if you have to refer to the clustered index anyway to pull out data that isn't in the filtering clauses? You will likely save a couple of page reads on the clustered index but might save page reads on the index due to each index page holding more rows as the index is smaller, and as well as saving space on disk you may make more efficient use of buffer cache (assuming your DB is not much smaller RAM so this matters) as you won't have a pages for a wider index that is only used for a small number of your regular queries.

The answer in that case being n * (n-1) /2 or if one of the columns is your clustering key (n * (n-1) / 2) - 1.

For a really wide table maybe you would go as far as one index for some or all three column combinations.

Of course, the selectivity of your columns is going to make a difference too, and how likely your users are to query certain combinations. And yet another consideration is if you allow the users to specify filters other than equality: how efficient a compound index is in the face of greater-than or less-than searches will vary according to the order of the index - do you want each combination of ASC & DESC to be taking into consideration too?

For specific databases, some support skip-scan searches so can make use of indexes where the first column(s) are not found in the filtering clauses (Oracle does, IIRC Postgres does, SQL Server does in some cases with partitioned indexes). This may again change the balance of usefulness for some combinations, particularly the wider ones.

0

RDBMS-specific example

if and only if they're the first columns then this will use the index [... otherwise] then the index will not be used, because matching records will be distributed all over the index depending upon the value they have in column a.

That's simply not true. In PostgreSQL for instance this is not applicable. Following the example you used, let say you had an index on (a, b, c, d) and wanted to execute:

SELECT * FROM my_table
WHERE c = 7 AND a = 'foo';

That'll still use the index. In fact,

SELECT * FROM my_table
WHERE c = 7 AND b = 5;

will also use the index if the planner finds it appropriate. Need proof? You can use this sample data and run those queries above. They'll all result in index scans.

CREATE TABLE my_table
AS
  SELECT
    CASE WHEN x%3=0 THEN 'foo' END AS a,
    x::int % 7 AS b,
    x::int % 5 AS c,
    x AS d
  FROM generate_series(1,1e6)
    AS gs(x);

CREATE INDEX ON my_table (a,b,c,d);

ANALYZE my_table;

SET enable_seqscan = 0; -- just to be sure it uses them =)

From the docs on PostgreSQL's multicolumn indexes

A multicolumn B-tree index can be used with query conditions that involve any subset of the index's columns, but the index is most efficient when there are constraints on the leading (leftmost) columns. The exact rule is that equality constraints on leading columns, plus any inequality constraints on the first column that does not have an equality constraint, will be used to limit the portion of the index that is scanned. Constraints on columns to the right of these columns are checked in the index, so they save visits to the table proper, but they do not reduce the portion of the index that has to be scanned. For example, given an index on (a, b, c) and a query condition WHERE a = 5 AND b >= 42 AND c < 77, the index would have to be scanned from the first entry with a = 5 and b = 42 up through the last entry with a = 5. Index entries with c >= 77 would be skipped, but they'd still have to be scanned through. This index could in principle be used for queries that have constraints on b and/or c with no constraint on a — but the entire index would have to be scanned, so in most cases the planner would prefer a sequential table scan over using the index.

Emphasis added by me. That's hardly an if and only if. In essence, the left-most condition can be use to greatly reduce the cost estimation on scanning the index but it's still quite possible that scanning the whole index is cheaper than visiting the table with a sequential scan.

With this information, let's review the request. In the question, you ask for an index on

(a, c)
(a, d)

But an index on (a,c,d) will successfully cover (a,c), and the worst case scenario for (a,d) is that it has to scan the entire range of (a,c) to find the d.

That kind of renders this whole question's foundation flawed. Now what index is really necessary for your task?

On creating indexes without skills

More to the point about the question, this form of creating an index is very problematic. Every index slows down inserts and updates and disables heap-only-updates on the row -- at least in PostgreSQL which has that optimization. If creating customized index is too much of a skill that you don't want to acquire I would pay someone to assist, or use a tool like dexter.

Math

In the event you want a mathmatical solution to this problem, my suggestion is Mathmatics.SE. I believe it falls under combinatorics.

References

  • Erwin has an excellent post on this with some numbers, albeit they're very old and this is likely an understatement as imagine more work was done in 6 years on this.
  • Maybe I'm reading this wrong, but it looks like a scan will still be performed if the leading column(s) are not specified in the predicate: ...to limit the portion of the index that is scanned. This sounds like it will perform a range scan but not a seek that is being requested by the OP. Maybe I'm missing something here though? – John Eisbrener Oct 23 '17 at 23:44
  • @JohnEisbrener he explicitly says "then the index will not be used, because matching records will be distributed all over the index depending upon the value they have in column a." That's not true. It may still be used. – Evan Carroll Oct 23 '17 at 23:46
  • 3
    ... but before that he says "supports doing a lookup" which I take to mean a seek, but that's how I read it. I'll let the OP clarify. If he's not concerned with it being a scan/range scan on the index, Oracle also supports this by way of skip scans. Regardless it's a valid answer and worth my upvote. :) – John Eisbrener Oct 23 '17 at 23:49
  • You're right that the specifics of my claim about index usage are incorrect, and I've updated the question to fix the error (with reference to this answer). However, as @JohnEisbrener explains, the error does not "[render] this whole question's foundation flawed", or even really harm the foundation at all - it's still desirable from a read performance perspective to support seeks on all column combinations. Beyond that, I think I'll note my offence at the gratuitous, arrogant insults about my "skills" and the suggestion that I hire somebody to do my job for me, and then leave it at that. – Mark Amery Oct 24 '17 at 9:46
0

Two.

In the first you combine all field values, in all combinations, in column order. So you'll end up with (a,b), (a,c) .. (c,d), (a,b,c), (a,b,d) .. (a,b,c,d). Hash this combined value. Use the hash as the key of the first index. This index gives a unique surrogate key to the data table. Use that surrogate to find the data row. The second index is on the surrogate key in the data table.

As an example, say my data table has these rows:

+----+--------+--------+--------+-------+
| id |   a    |   b    |   c    |   d   |
+----+--------+--------+--------+-------+
|  1 | foo    | bar    | baz    | qux   |
|  2 | foo    | quux   | quuz   | corge |
|  3 | wibble | wobble | wubble | flob  |
|  4 | blep   | blah   | boop   | blem  |
+----+--------+--------+--------+-------+

Table 1: data

Note specifically that rows 1 and 2 have the same value in column "a".

So for row id 1 we generate the following hashes (using my magical hash function):

+--------------+-------------+
|    value     |    hash     |
+--------------+-------------+
| foo          |  2085198204 |
| bar          |  1242944992 |
| ..           |             |
| foobar       |  1242667234 |
| ..           |             |
| foobarbaz    | -1417643972 |
| ..           |             |
| barbaz       | -1478044229 |
| ..           |             |
| foobarbazqux |    54278474 |
+--------------+-------------+

And row id 2 generates these hashes

+------------------+-------------+
|      value       |    hash     |
+------------------+-------------+
| foo              |  2085198204 |
| quux             |  -406244122 |
| quuz             |  -821744750 |
| corge            |    -4773002 |
| fooquux          |  -237289772 |
| fooquuz          | -1705377365 |
| ..               |             |
| fooquuxquuzcorge |   174363790 |
+------------------+-------------+

Since rows 1 and 2 have the same value in column "a" they generate the same hash output when that column alone's value is hashed.

We can now populate a table with hash / id mappings:

+-------------+----+
|    hash     | id |
+-------------+----+
|  2085198204 |  1 |
|  1242944992 |  1 |
|  1242667234 |  1 |
| -1417643972 |  1 |
| -1478044229 |  1 |
|    54278474 |  1 |
|  2085198204 |  2 |
|  -406244122 |  2 |
|  -821744750 |  2 |
|    -4773002 |  2 |
|  -237289772 |  2 |
| -1705377365 |  2 |
|   174363790 |  2 |
+-------------+----+

Table 2: hash/id map

.. plus the others I skipped from the example hash calculations previously.

Now a query comes in. The predicate is "a=foo". We take the value and hash it, getting 2085198204. We read table 2 where hash = 2085198204. We get two rows: id 1 and id 2. We read table 1 where id = 1 or id = 2 and get our full rows.

A second query arrives. It has predicates "c=baz and b=bar". We order the values in column sequence getting "barbaz" which hashes to -1478044229. Reading table 2 for this hash value gives id 1.

If values could occur in more than one column -- perhaps "foo" could be in column d as well as column a -- the naive scheme above could return false positives. Secondary checking of the data rows would be cumbersome. Better to include the columns in the hash, I think, so "a=foo" hashes to a diferent value than "d=foo".

  • -1; maybe I'm being thick (always a distinct possibility), but I don't see how this strategy makes the slightest bit of sense. If the surrogate key is a function of all the columns in the table, then surely I can't possibly compute its value in order to do a lookup on it without first knowing the value of every column in the row I want to look up (which would render the query unnecessary in the first place!). Also, I can't see how repeating a column in an index would ever be useful. – Mark Amery Oct 24 '17 at 9:59
  • (Unless, of course, you mean that the first index should have each combination of columns in it as a separate entry, meaning that to index a table with r rows and c columns would require r * 2^c index entries. In which case, sure, clever semantic trick, you've taken the super-inefficient r * 2^c indexes solution and technically made it into a single index by basically just concatenating all 2^c indexes together. It's completely pointless, though, neither answering the mathematical question nor the practical one.) – Mark Amery Oct 24 '17 at 10:04
  • Darn it Mark, you caught me! Yes, that first paragraph was a bit tongue-in-cheek. The rest, though, I sand by. As a workable solution to the search-on-any-columns problem I'd opine that a point lookup on a trillion row table could hold its own against many thousands of indexes once writes and optimizer overhead it taken into account. As for the maths, I'll leave that to cleverer heads than mine. – Michael Green Oct 24 '17 at 23:03
  • Another downside of this approach is that you're not storing the column position, so you'll always have a recheck condition on the actual table (if you search a=5 AND b=1 you'll get b=5 AND a=1 and you'll have to recheck on the heap) – Evan Carroll Oct 24 '17 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.