Hotels on Wheels
Parking garages and predicates have a “lot” in common.
GET IT?
No no but seriously. They do.
If you’ve ever lost your ticket, forgotten where you’ve parked, or just driven around hopelessly waiting to see an empty spot, you probably wish there were a better way to do things.
1 2 3 4 5 6 7 8 | CREATE TABLE dbo.PahkinLaht ( FloorId INT NOT NULL, LaneId INT NOT NULL, SpaceId INT NOT NULL, CarId INT NOT NULL, IsEmpty BIT NOT NULL ); |
Maybe even a data-driven way of doing things.
Informal poll: Is anyone reading this blog data-driven?
If You Had To Index That…
Say you wanted to quickly find your car. An index on CarId would be awesome, if you know what it is.
If you got a parking slip with your Space Number on it, that’s sort of helpful. But then you need to figure out which floor and lane you’re in.
On the other end, if you need an empty space, an index on IsEmpty sounds pretty optimal.
Let’s say you’re Seinfelding
I don’t mean that, I mean this.
If Jerry, et al. knew where their car was, they’d have been able to walk directly to it. That’s like a Seek predicate.
Molon Labe
If they knew which floor and lane they were on, they’d have been able to start Seeking in the right place, and then double check each car. That’s like a Seek predicate with a Residual predicate.
ULLO JOHN GOT A NEW MOTOR
Likewise, if they know the lane and spot number, they could have done this:
This is where you start pressing the door unlock button and waiting to hear a chirp
Of course, they didn’t know anything, so they had to scan the entire joint. It looked something like this:
That’s a lot of walking
I don’t have the patience to paste that many thinking faces in.
There’s much to consider here. But I don’t even have a license, so let’s look at things in a Real Table®
Seek and Not Seek Walk Into A Bar
Using the miniaturized version of the StackOverflow database, I’m gonna focus in on the Users table.
The only thing on it is a Primary Key/Clustered index on the Id column. A query like this can use that quite easily.
1 2 3 | SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.Id = 1 |
Seeky Kid
This query only requires three reads to locate the page it needs and return a single row.
If we’re talking parking lots, a seek would look something like this.
The PK/CX is considerably less efficient for this query, taking nearly 7400 logical reads to return the same single row.
1 2 3 | SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.Reputation = 42510 |
Hit Scan
It’s Not Seek vs Scan Though
What I’m interested in is the Seek Predicate vs Predicate. For instance, this query returns the same results, with the same 3 logical reads as the first query.
1 2 3 4 | SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.Id < 2 AND u.Reputation > 42509 |
Double up
- A predicate by itself is like having to walk through the entire parking garage trying to find your car.
- A seek predicate by itself is like being able to start your search where your car is.
- A seek predicate with a residual predicate is like walking along along the right lane and having to check parking space numbers.
What Makes For A Seek Predicate vs a Residual Predicate?
Mostly placement in the index, but SARGability plays an important role as well.
Let’s create an index and look at a couple slightly different queries.
1 2 3 4 5 6 7 8 9 10 11 12 | CREATE INDEX ix_helper ON dbo.Users(Reputation, Id) INCLUDE (DisplayName); SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WITH (INDEX = PK_Users_Id) WHERE u.Id = 1 AND u.Reputation = 42510 SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WITH (INDEX = ix_helper) WHERE u.Id = 1 AND u.Reputation = 42510 |
This index leads with reputation, and also has Id as a key column. DisplayName is an included column, which puts it in just about the same place as Reputation was when we were only working with the clustered index.
The first query plan looks like this, seeking to the right key, and then evaluating the predicate on Reputation. This one is using the clustered index.
Party!
The second query uses the nonclustered index, but supports multiple seek keys.
Seeky Monkey
When I mentioned that SARGability plays a part, that’s because if you do something this stupid, neither predicate will be seekable.
1 2 3 4 | SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE ABS(u.Id) = 1 AND ABS(u.Reputation) = 42510 |
Just don’t
Bumming Around
While I have your attention, and before I run DropIndexes, let’s look at how included columns work a little bit.
Right now, DisplayName is included in our nonclustered index. All three of these queries can use our index.
1 2 3 4 5 6 7 8 9 10 11 12 13 | SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.DisplayName LIKE 'Jeff Atwood%' SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.DisplayName LIKE '%Jeff Atwood%' SELECT Id, u.DisplayName, u.Reputation FROM dbo.Users AS u WHERE u.DisplayName LIKE '%Jeff Atwood' |
All of them will do the same number of logical reads (1279).
All three of them will have our LIKE condition as a predicate — we can’t seek here because it’s not in the key of the nonclustered index.
But only the first query, where the string search doesn’t lead with a wildcard will register a missing index.
In other words, a lack of SARGability with leading wild card searches shut down missing index requests.
Chimney Sweep
If we add the missing index request, the reason becomes pretty apparent.
1 2 3 | CREATE NONCLUSTERED INDEX [<Name of Missing Index, sysname,>] ON [dbo].[Users] ([DisplayName]) INCLUDE ([Reputation]) |
I did not seek that coming
The index really does only help the first query. The other two queries do the same number of logical reads as before. Adding this index doesn’t change much for them.
Beat It
This is a small step towards understanding seek and residual predicates, and how indexes support searches.
The thing to keep in mind is that you can really only seek into an index when a SARGable predicate hits the leading key column. Multi-key indexes can support multiple seek keys.
If you’re only searching secondary (or beyond) columns, you’re only able to scan with a regular predicate. The same goes for included columns.
Thanks for reading!
10 Comments. Leave new
That’s a great analogy. Kudos for coming up with something that can be used to replace the phone book analogy.
Now instead of “What’s a phone book?” the kids will ask “Who’s Seinfeld?”
Hahaha, oh man. I never thought of that.
My God, you actually named your missing index [<Name of Missing Index, sysname,>] … a kitty died somewhere.
FTFY 😉
This is one of the best articles on indexing I have read. Simple example that is easy to conceptualize then diving into the SQL. Definitely passing this along to some of the new hires at my organization. Thanks Erik.
Thanks Joe!
Hi Erik, brilliant as usual, thanks for being there for all of us 🙂
> CarId INT NOT NULL
What is the proposed value for CarId when IsEmpty = 1?
Overall the article was great, but I’d love to see more discussion/examples of these points:
> Multi-key indexes can support multiple seek keys.
> If you’re only searching secondary (or beyond) columns, you’re only able to scan with a regular predicate. The same goes for included columns.
SO Question ID 2292662 has some interesting information but I’d love to see your explanation over how multiple seek keys work, how searching secondary columns only forces a regular predicate, and how included columns factor into these concerns.
Chris – that question has tons of highly upvoted answers. It doesn’t really make sense for more people to pile on there.
If you have a new question, definitely think about posting it at Stack – but of course, like any Stack question, you want it to be focused and answerable. (It’s tough to answer a question like “how do multiple seek keys work” – that’s kind of where our training classes come in.)
I almost lost one of my kids at soccer practice yesterday but he was able to seek the car out in its space