0

I have a SQL (MSSQL) table storing data like the following, with id as primary key.

id col1 col2 col3 data valid
1 A B C 1
2 A B C 0
10 X Y Z 1
15 X Y Z 0
75 A B C 1
99 X Y Z 1

The kind of retrieval that the application needs is a 3-step process.

  1. First, get all the ids where col1, col2, col3 are of some value, and valid is 1, similar to this:

    select id
    from table
    where col1 = 'A' and col2 = 'B' and col3 = 'C' and valid = 1;
    
  2. Then, from the list of ids, select a single id based on some computation.

  3. Given a single id from step #2, retrieve the data.

Question

How to speed up the process of looking up all the ids in step #1? Because at some point, the table will grow to 10 millions+ and looking up would be slow.

One way is to create index in MSSQL on col1, col2, col3, and valid columns, so that the query would be fast. But I believe it would still be ~ O(logN).

Another solution I can think of is to have a background process to create a key-value database alongside the SQL table. This background process would build something like this:

key value
A:B:C 1, 75, ...
X:Y:Z 10, 99, ...

The reason why I want to create a key-value index alongside SQL table is because the number of valid records could be relatively very small (~100) compared to the whole size of the table (~10M+). So we wouldn't have to search/scan through the invalid records. And with key-value, the lookup, and therefore the step #1, would be O(1).

I was just wondering if this is common, or there is other database technology that supports this better.

Edit

  • Sorry, I oversimplified the question and it could affect the answer. The valid column doesn't actually exist in the original SQL table; it is computed at runtime and stored in another table. @Akina 's reply in the comment regarding the partition on the valid column (soft delete?) should still help though.
4
  • the number of valid records could be relatively very small (~100) compared to the whole size of the table (~10M+) - if so then this column must be index prefix. I.e. CREATE INDEX idx ON table (valid, col1, col2, col3). Moreover, you may partition your table by valid (i.e. CREATE PARTITION FUNCTION pfn (INT) AS RANGE LEFT FOR VALUES (0); GO; CREATE PARTITION SCHEME psc AS PARTITION pfn TO (invalid, valid);) which will made the rows selection O(1) because of the partition pruning.
    – Akina
    Aug 16, 2022 at 11:50
  • @Akina Sorry, I kind of oversimplify the question. In my intended question, the valid column doesn't actually exist in the original SQL table; it is computed at runtime and stored in another table (id, valid). But I could try to have valid column in the same table as well, which in that case, your suggestion regarding the partition is very interesting. Aug 16, 2022 at 12:22
  • @Akina Thanks for pointing out about the partitioning; I read about it and I think it is definitely going to work. But in case the valid column is not part of the original SQL table, do you see other options other than creating a key-value index alongside? Aug 16, 2022 at 15:05
  • Partitioning is only useful if you want to bulk load, otherwise it just introduces complexity to no benefit, as you can just use a normal index Aug 17, 2022 at 14:01

2 Answers 2

2

The number of index keys on the single page at the 1st level of the BTree is N. Each index key has a page pointer to a page on the next level. So at the 2nd level there are N pages, each with N index keys. and so on

Level   Index Keys
1          N^1
2          N^2
3          N^3
4          N^4

So if you need to span M keys, how many levels L are required?

N^L=M
ln(N^L)=ln(M)
L*ln(N)=ln(M)
L=ln(M)/ln(N)
L=logN(M)

Note that on the non-leaf levels the records store (index key,page pointer) and on the leaf level they store (index key, row locator), and perhaps included columns.

2

I'm not sure if Akina's suggestion is truly O(1). I also believe you're mistaken that the key-value store solution would truly be O(1) (given that the same key exists multiple times). But neither of this matters, because O(Log2(n)) is very fast. I think you may be underestimating how fast.

Here's some math: Log2(10 million) = ~23 and 23 nodes seeked through in a B-Tree < 100 key lookups. So a B-Tree index is actually faster in your particular use case. Let's grow the table out to 10 billion records. Log2(10 billion) = ~33. Seeking through 33 nodes is less than a millisecond operation on any kind of modern hardware.

Here's some real life experience: I've worked with tables in the 10s of billions of rows, on modest hardware, and reading small amounts of data such as 100 rows from them would come back immediately (~1 ms). There's really no tangible number of rows you can grow your table to that will affect read performance, if all you're interested in is a small subset of rows at any given time.

So I agree with Akina in regards to his index recommendation for CREATE INDEX idx ON table (valid, col1, col2, col3). (It actually doesn't matter what order you specify the columns in this case since they are all used in your query and are all equality predicates.)

The key takeaway here is don't try to prematurely optimize your database by re-architecting an uncommon solution, otherwise you may miss out on practical and standard solutions, such as clsssic indexing.

7
  • 1
    I'm not sure if Akina's suggestion is truly O(1). Partition pruning will cause only partition valid to be scanned. But true, the value for the column will be checked despite this is the only value in the partition and all rows in it matches.
    – Akina
    Aug 16, 2022 at 13:00
  • 1
    Note by the way that log here is not base 2, but to the base of F which represents the fan-out. In most databases that is very high, so the number of lookups is usually only a handful. Aug 17, 2022 at 13:59
  • 2
    And so in practice for SQL Server BTrees are no more than 3 or 4 levels deep because F is the number of index keys that fit on a 8KB page. Aug 17, 2022 at 14:41
  • @Charlieface ah interesting, I always assumed base 2. Do you have any resources I can learn more about this factor F for the fan-out? (I imagine it's a variable based on the data distribution.)
    – J.D.
    Aug 17, 2022 at 14:43
  • 1
    @J.D. I added an answer for this. Aug 17, 2022 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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