Search results matching tags 'sqlpass', 'indexing', and 'sql'

Using SQL Execution Plans to discover the Swedish alphabet

rob_farley — Mon, 03 Jan 2011 05:54:00 GMT

SQL Server is quite remarkable in a bunch of ways. In this post, I’m using the way that the Query Optimizer handles LIKE to keep it SARGable, the Execution Plans that result, Collations, and PowerShell to come up with the Swedish alphabet.

SARGability is the ability to seek for items in an index according to a particular set of criteria. If you don’t have SARGability in play, you need to scan the whole index (or table if you don’t have an index). For example, I can find myself in the phonebook easily, because it’s sorted by LastName and I can find Farley in there by moving to the Fs, and so on. I can’t find everyone in my suburb easily, because the phonebook isn’t sorted that way. I can’t even find people who have six letters in their last name, because also the book is sorted by LastName, it’s not sorted by LEN(LastName). This is all stuff I’ve looked at before, including in the talk I gave at SQLBits in October 2010.

If I try to find everyone who’s names start with F, I can do that using a query a bit like:

SELECT LastName FROM dbo.PhoneBook WHERE LEFT(LastName,1) = 'F';

Unfortunately, the Query Optimizer doesn’t realise that all the entries that satisfy LEFT(LastName,1) = 'F' will be together, and it has to scan the whole table to find them.

But if I write:

SELECT LastName FROM dbo.PhoneBook WHERE LastName LIKE 'F%';

then SQL is smart enough to understand this, and performs an Index Seek instead.

To see why, I look further into the plan, in particular, the properties of the Index Seek operator. The ToolTip shows me what I’m after:

You’ll see that it does a Seek to find any entries that are at least F, but not yet G. There’s an extra Predicate in there (a Residual Predicate if you like), which checks that each LastName is really LIKE F% – I suppose it doesn’t consider that the Seek Predicate is quite enough – but most of the benefit is seen by its working out the Seek Predicate, filtering to just the “at least F but not yet G” section of the data.

This got me curious though, particularly about where the G comes from, and whether I could leverage it to create the Swedish alphabet.

I know that in the Swedish language, there are three extra letters that appear at the end of the alphabet. One of them is ä that appears in the word Västerås. It turns out that Västerås is quite hard to find in an index when you’re looking it up in a Swedish map. I talked about this briefly in my five-minute talk on Collation from SQLPASS (the one which was slightly less than serious).

So by looking at the plan, I can work out what the next letter is in the alphabet of the collation used by the column. In other words, if my alphabet were Swedish, I’d be able to tell what the next letter after F is – just in case it’s not G.

It turns out it is… Yes, the Swedish letter after F is G. But I worked this out by using a copy of my PhoneBook table that used the Finnish_Swedish_CI_AI collation. I couldn’t find how the Query Optimizer calculates the G, and my friend Paul White (@SQL_Kiwi) tells me that it’s frustratingly internal to the QO. He’s particularly smart, even if he is from New Zealand.

To investigate further, I decided to do some PowerShell, leveraging the Get-SqlPlan function that I blogged about recently (make sure you also have the SqlServerCmdletSnapin100 snap-in added. To do that, run get-pssnapin -reg to see if it's on the machine, and get-pssnapin -reg | add-pssnapin to make the cmdlet available).

I started by indicating that I was going to use Finnish_Swedish_CI_AI as my collation of choice, and that I’d start whichever letter came straight after the number 9. I figure that this is a cheat’s way of guessing the first letter of the alphabet (but it doesn’t actually work in Unicode – luckily I’m using varchar not nvarchar. Actually, there are a few aspects of this code that only work using ASCII, so apologies if you were wanting to apply it to Greek, Japanese, etc). I also initialised my $alphabet variable.

$collation = 'Finnish_Swedish_CI_AI';
$firstletter = '9';
$alphabet = '';

Now I created the table for my test. A single field would do, and putting a Clustered Index on it would suffice for the Seeks. [Edit: You may need to insert some rows if you find that it's producing an Index Scan. Theoretically it should prefer to Scan, knowing there's no rows, but my tests showed it would always Seek]

Invoke-Sqlcmd -server . -data tempdb -query "create table dbo.collation_test (col varchar(10) collate $collation primary key);"

Now I get into the looping.

$c = $firstletter;
$stillgoing = $true;
while ($stillgoing)
{

I construct the query I want, seeking for entries which start with whatever $c has reached, and get the plan for it:

$query = "select col from dbo.collation_test where col like '$($c)%';";
[xml] $pl = get-sqlplan $query "." "tempdb";

At this point, my $pl variable is a scary piece of XML, representing the execution plan. A bit of hunting through it showed me that the EndRange element contained what I was after, and that if it contained NULL, then I was done.

$stillgoing = ($pl.ShowPlanXML.BatchSequence.Batch.Statements.StmtSimple.QueryPlan.RelOp.IndexScan.SeekPredicates.SeekPredicateNew.SeekKeys.EndRange -ne $null);

Now I could grab the value out of it (which came with apostrophes that needed stripping), and append that to my $alphabet variable.

if ($stillgoing)
{
$c=$pl.ShowPlanXML.BatchSequence.Batch.Statements.StmtSimple.QueryPlan.RelOp.IndexScan.SeekPredicates.SeekPredicateNew.SeekKeys.EndRange.RangeExpressions.ScalarOperator.ScalarString.Replace("'","");
$alphabet += $c;
}

Finally, finishing the loop, dropping the table, and showing my alphabet!

}
Invoke-Sqlcmd -server . -data tempdb -query "drop table dbo.collation_test;";
$alphabet;

When I run all this, I see that the Swedish alphabet is ABCDEFGHIJKLMNOPQRSTUVXYZÅÄÖ, which matches what I see at Wikipedia. Interesting to see that the letters on the end are still there, even with Case Insensitivity. Turns out they’re not just “letters with accents”, they’re letters in their own right.

I’m sure you gave up reading long ago, and really aren’t that grabbed about the idea of doing this using PowerShell. I chose PowerShell because I’d already come up with an easy way of grabbing the estimated plan for a query, and PowerShell does allow for easy navigation of XML.

I find the most interesting aspect of this as the fact that the Query Optimizer uses the next letter of the alphabet to maintain the SARGability of LIKE. I’m hoping they do something similar for a whole bunch of operations.

Oh, and the fact that you know how to find stuff in the IKEA catalogue.

Footnote:

If you are interested in whether this works in other languages, you might want to consider the following screenshot, which shows that in principle, it should work with Japanese. It might be a bit harder to run this in PowerShell though, as I’m not sure how it translates. In Hiragana, the Japanese alphabet starts あ, ぃ, ぅ, ぇ, ぉ, ...

Inverse Predicates - look both ways before you cross

rob_farley — Mon, 08 Nov 2010 21:53:21 GMT

When I’m at the PASS Summit in Seattle this week, I will need to remember that I can’t just step onto the road if I’m walking along the footpath on the right-hand side. In the UK and Australia, where we drive the correct side, it’s fine (just don’t tell my kids), because the cars that are nearest me are coming towards me – except of course, the idiots who are reading blog posts while they’re driving. They could be anywhere.

I should also learn to stop picking on left-handed people for being ‘sinister’. The word ‘sinister’ comes from the Latin word for left, and is associated with the fact that writing with your left hand is unnatural – some would even use the word ‘evil’. My beautiful wife is left-handed, and she’s definitely not sinister or evil. So really I should just pick on left-handed people for their inability to write on whiteboards, not for their sinisterisity.

You see, the world is designed for right-handed people. Even cars are designed to be driven by right-handed people, and this is why in normal places, the steering wheel is positioned on the right-hand side of the car so that the right-hand can be in control of it all the time, with the left hand being free to change gears, use the indicator, change the radio stations, drink coffee, tweet, etc – all those things that are less important than controlling the car.

And so we consider queries – in particular, the joining of tables. We might include something in our FROM clause like:

FROM dbo.Deliveries AS d
JOIN dbo.Orders AS o
ON d.DeliveryDate = DATEADD(day,1,o.OrderDate)

This aligns nicely with our thoughts around SARGability, which suggests that you leave the left-hand side of predicates untouched. Unfortunately, I don’t tend to write my ON clause predicates this way around, because I like to focus on the table I’ve just introduced into the mix. I write my queries like:

FROM dbo.Deliveries AS d
JOIN dbo.Orders AS o
ON o.OrderDate = DATEADD(day,-1,d.DeliveryDate)

You’ll notice that I’ve inverted the predicate, because I still like the idea of keeping the left-hand side untouched, but at this point, I want to ask you to have a think about what we’re trying to achieve.

I’ve written before about how the point of SARGability is to allow an index to be used nicely. Think of the phone book, and how you can easily find the name you want (also, just for fun, think of the Japanese phone book, and how you can’t find names in it unless you understand how their alphabet is ordered). It’s very similar with our Deliveries and Orders tables – we can find a particular date in it if there is an index on that field.

But which query should we think about? The first one, where we’re trying to find a Delivery, or the second, where we’re trying to find an Order.

Naturally, being a data question, the answer is “It depends”. And that’s right – it depends on what your query is actually doing.

If you’re just creating a query, and have a WHERE clause that contains something like: WHERE o.OrderDate = '20101106', then you’re okay. You know that you can easily find the Orders you want, and need the ON clause in the first example (to help find the Delivery). But if you’re creating a view, and people can use this query in a variety of ways, then you don’t know which side you’re going to start.

When SARGability is working nicely, we probably see the execution plan using an Index Seek, and can notice in that Seek’s properties that there is a Seek Predicate being used to support that. You can also see it in the ToolTip, as I’ve shown in the picture below. I ran the query SELECT * FROM Production.Product WHERE ProductID = 316;

If there are other predicates involved, that aren’t so SARGable (quite probably nothing to do with functions, rather than a choice of index), then we see this reflected in the Predicate property.

Here I’m filtering on the SafetyStockLevel as well as the ProductID. It uses the ProductID for the Seek, but checks all the results of this Seek using the SafetyStockLevel value, before returning anything out of the Seek operator. We’re not doing a scan with SafetyStockLevel, but we are checking every value returned by the Seek Predicate. This could be improved with an index across both columns (together, not individually), but if the Seek is effective, then the regular Predicate won’t have to be applied to many rows anyway.

When thinking about your indexes, do remember that included_columns (rather than key_columns) are not ordered, so any predicates involving them won’t be Seek Predicates. If the phone book were only on LastName, and FirstName was an included columnn, then finding me in there would mean checking all the farleys for Rob, rather than finding the Farleys and then continuing the seek to find the Rob entry.

Back with our orders and deliveries, we see an interesting phenomenon at play.

If I create a view using the first FROM clause, and filter the view on OrderDate, I might get a nice plan, involving Seeks.

This is an excellent plan for this particular query, but if I start with the DeliveryDate, then it’s not so nice.

The cost of this is much larger – probably orders of magnitude larger. But if I use the other ON clause, I see the same behaviour with the columns switched (good performance if I start with the DeliveryDate, bad performance if I start with OrderDate).

Ideally, we can do a Seek to find the records we want, regardless of whether we want to look up the records by DeliveryDate or by OrderDate. This would mean getting a Seek Predicate both times to see SARGability in use.

Having shown you earlier the example that used both a Seek Predicate AND a Predicate in the same query provides the key here...

Use both! (Yes, work out the inverse predicate, and include it)

FROM dbo.Deliveries AS d
JOIN dbo.Orders AS o
ON d.DeliveryDate = DATEADD(day,1,o.OrderDate)
AND o.OrderDate = DATEADD(day,-1,d.DeliveryDate)

The predicate which isn’t suitable for the Seek will be used as a regular Predicate, while the SARGable one gets the effective Seek Predicate. Now you can the best of both worlds, but you will need to work out the inverse of some of your predicates.

It’s not hard, but it may have great reward. In the plans below, I’ve created a view like the notice the fact that when we look up records with a known OrderDate, we can seek for the Order, and then look up the Delivery using the transformed OrderDate. Checking that the OrderDate matches the transformed DeliveryDate falls into the Predicate, not the Seek Predicate.

Conversely, if we have the DeliveryDate, then we can seek to find the Delivery, and then look up the Order using an appropriate Seek Predicate, with the other becoming the regular Predicate.

So now when you want to create views for a variety of uses, you can hopefully see some potential in saying the same thing from both perspectives. Don’t just think left-to-right – consider all the different ways you could approach your data. Just maybe don’t try to write your execution plan on a whiteboard.