In this post, we will look at how SQL Server accesses indexes when an OR predicate is used.
For this demo, I am going to use the Stack Overflow Database. I am using the large 2024 version provided under cc-by-sa 4.0 licence from Stack Exchange Data Dump and running in compatibility level 160 on a SQL Server 2022 instance installed on a VM with 8 cores and 35GB RAM.
Clean Slate
First, I’ll ensure I’ve dropped all the indexes on this database, in case there’s anything lingering from other demos:
EXEC dbo.DropIndexes;
Now, let’s execute our query. I want to find all users who live in a particular location or have a specific reputation value:
SELECT Id,
[Location],
Reputation
FROM dbo.Users
WHERE Reputation = 1000 OR
[Location] = 'London, United Kingdom';
Here is the execution plan:
It probably comes as no surprise that SQL Server chose to do a clustered index scan. To be honest, there wasn’t much “choice” about it – we dropped all our indexes so this is all SQL Server could do.
Let’s create an index to try and make this query more efficient:
CREATE INDEX IX_Reputation ON dbo.Users
(
Reputation,
[Location]
);
We’ve created an index on both of the columns in the WHERE clause both of which are also in the SELECT list. As a reminder, non-clustered indexes implicitly include the clustered index key in the included columns even if we have not explicitly specified it and so with this in mind, our index fully covers our query. This index should be good for an index seek right? Let’s execute our query again:
Womp womp, trombone noise.
SQL Server scanned the index we created. Granted, this is better than the clustered index scan as the index is narrower and therefore fewer pages are scanned but it was not really what we were looking for.
What happens if, instead of the index above, we created the index with the columns the other way around maybe?
DROP INDEX IX_Reputation ON dbo.Users;
CREATE INDEX IX_Location ON dbo.Users
(
[Location],
Reputation
);
Now let’s execute our SELECT query again:
Still performing an index scan!
Maybe we know best and SQL Server is actually wrong? Let’s force it to seek:
SELECT Id,
[Location],
Reputation
FROM dbo.Users WITH (FORCESEEK)
WHERE Reputation = 1000 OR
[Location] = 'London, United Kingdom';
Not so fast! We get an error:
Msg 8622, Level 16, State 1, Line 24
Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.
SQL Server cannot compile a plan with the hints we have specified. It is actually impossible for SQL Server to seek our index and therefore that is why it scanned it, but why?
Scanning Our Index Ourselves
Here’s how the data is organised in the index IX_Location. It is ordered by Location then Reputation and includes the Id. We can see how the data is stored logically in the index by running:
SELECT [Location],
Reputation,
Id
FROM dbo.Users
ORDER BY [Location],
[Reputation];
Let’s seek down to the location of London, United Kingdom to find records that match that predicate in our OR clause:
The highlighted row is the first London, United Kingdom record (note there are a few typos preceding our correct spelling). So we’ll keep going until the left column no longer says London, United Kingdom:
So we seeked straight to London, United Kingdom in our index and found all the records that matched. However, remember that our predicate is an OR predicate and the other side is Reputation = 1000 and so by seeking to London, United Kingdom in this index, we have skipped past all the other locations before that may have had users with a reputation of 1000. This is why the index seek is invalid for this query, seeking to one predicate means we skip past records that may match the other. The same would be true with our original index that led on reputation – we’d skip to reputation = 1000 records but in doing so may skip past records where the location was London, United Kingdom but with a reputation less than 1000.
Seek Me Baby
With our previously created location index, let’s create our original index on reputation again, leaving us with a covering index on both columns in the predicate:
CREATE INDEX IX_Reputation ON dbo.Users
(
Reputation,
[Location]
);
Now let’s run our query again, but remove our previous FORCESEEK hint:
SELECT Id,
[Location],
Reputation
FROM dbo.Users
WHERE Reputation = 1000 OR
[Location] = 'London, United Kingdom';
Now we get the coveted seek (actually seeks) – we seek the Reputation index to get the users with a reputation of 1000 and we also seek the location index to get the London, United Kingdom records. The concatenation operator adds both sets of records together which will leave some duplicate records (those users who are in London, United Kingdom AND have a reputation of 1000). The hash match aggregate then removes the dupes.
So here we have managed to improve our query, get an index seek (or two) and prevent scanning the entire table.
OR on the Same Column
Now, a slightly different but simpler example of an index seek with an OR.
In this query, our OR predicates are both on the same column, we are looking for users from one of two locations and we are using the same covering index as before (definition included again below for clarity)
CREATE INDEX IX_Location ON dbo.Users
(
[Location],
Reputation
);
SELECT Id,
[Location],
Reputation
FROM dbo.Users
WHERE Location = 'London, United Kingdom' OR
Location = 'Washington, United States';
The plan is a lot clearer, we get a single index seek and the properties show that we have two seek keys, one for each predicate:
Note that the above is effectively an IN clause, if we rewrite our query as an IN, we get the same behaviour.
Conclusion
We have looked at some of the behaviour of the SQL Server optimizer in relation to index seeks with OR predicates. We saw that SQL server didn’t seek an index when the index supported only one of our predicates, where the other predicate was on a different column.
We saw where SQL Server did use a single index for multiple predicates when the multiple predicates are on the same column.