Key value alongside SQL table

Question

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.

Answer 1

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.

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