Understanding about SQL index on DateTime Column

Question

I have about 1 million records. When searching through the date range, it is surprisingly slow. Then I do the google search and someone suggested to do the index on the "DateTime" column. I am not convinced because I always thought index is for O(1) search - which means equality search; and since my query is a date range search, how can it be possible to improve the performance?

But, out of curiosity, I tried anyway and to my surprise, it does improve the performance significantly.

Here is my table

tblOrder
--------
OrderId (Primary Key)
CurrencyId
ProductId
...
...
...
OrderDate DATETIME

I am using linqtosql and the code is:

return (from rec in tblOrders.AsNoTracking()
 where (rec.CurrencyId == CurrencyId) && (rec.OrderDate >= startDate) && (rec.OrderDate < endDate)
 select rec).ToList();

I created a composite index on both CurrencyId and OrderDate. The result is a huge improvement. My question is, how is it possible? Why do indexes work on range search (not equal but >= or <=).

Can someone explain to me how does SQL index work in regards to date range search?

Thank you...

• Randi Vertongen: Hi, The compositie indexes, did you create an index on [CurrencyId,Orderdate] and [Orderdate,CurrencyId] as the key columns? Could you add the statements used? Otherwise it might come down to how much CurrencyId filters, your statistics, the query, .... Have you looked at this blogpost which explains it further?
• David Browne - Microsoft: Explained also in the docs: learn.microsoft.com/en-us/sql/relational-databases/…
• Sam: @RandiVertongen yes yes, that blogpost is actually exactly what I need. I tried to read the documentation from Microsoft as listed in the answer/comment, but it is too technical for me. You guys (David and Mike) are awesome because you guys are very technical. My question deserved downvotes. My apology and thanks y'all for your help...
• Randi Vertongen: @Sam That is great to hear! Don't beat yourself up too much about the downvotes, we have all been there starting out! It was a good question in itself but as much details as possible are always best :). Hope to see more from you on this forum.

Answer 1

B-tree indexes don't work by comparing only for equality. They're designed (the algorithm is designed) to use ranges.

Figure 1.3 shows an index fragment to illustrate a search for the key "57". The tree traversal starts at the root node on the left-hand side. Each entry is processed in ascending order until a value is greater than or equal to (>=) the search term (57). In the figure it is the entry 83. The database follows the reference to the corresponding branch node and repeats the procedure until the tree traversal reaches a leaf node.

References

• The Search Tree (B-Tree) Makes the Index Fast See especially section 1.3, B-Tree traversal
• SQL Server index structure and concepts