Search results matching tags 'sql' and 'indexing'

The SQL Query Optimizer – when Logical Order can get it wrong

rob_farley — Sun, 30 Dec 2012 05:32:25 GMT

It’s very easy to get in the habit of imagining the way that a query should work based on the Logical Order of query processing – the idea that the FROM clause gets evaluated first, followed by the WHERE clause, GROUP BY, and so on – finally ending with whatever is in the SELECT clause. We even get in the habit of creating indexes that focus on the WHERE clause, and this is mostly right.

But it’s only mostly right, and it will often depend on statistics.

There are other situations where statistics have to play a major part in choosing the right plan, of course. In fact, almost every query you ever run will use statistics to work out the best plan. What I’m going to show you in this post is an example of how the statistics end up being incredibly vital in choosing the right plan. It also helps demonstrate an important feature of the way that Scans work, and how to read execution plans.

I’m going to use AdventureWorks2012 for this example. I’m going to ask for the cheapest product according to the first letter of the product name. This kind of query:

SELECT MIN(ListPrice)
FROM Production.Product
WHERE Name LIKE 'H%';

Don’t run it yet. I want to ask you how you’d solve it on paper.

Would you prefer I give you a list of the products sorted by name, or would you prefer I give you that list sorted by price?

If you want the ‘sorted by name’ option, then you’ll have to look through all the products that start with H, and work out which is the cheapest (notice that my predicate is not an equality predicate – if I knew what the name had to be exactly, then I could have an index which ordered by name and then price, and very quickly find the cheapest with that name). This approach could be good if you don’t have many products starting with that particular letter. But if you have lots, then finding them all and then looking for the cheapest of them could feel like too much work. Funnily enough, this is the way that most people would imagine this query being run – applying the WHERE clause first, and applying the aggregate function after that.

On the other hand, if you have lots of products with that particular letter, you might be better off with your list sorted by price, looking through for the first product that starts with the right letter.

Let me explain this algorithm a little more.

If you’re at a restaurant and are strapped for cash, you might want to see what the cheapest thing is. You’d pick the “sorted by price” menu, and go to the first item. But then if you saw it had peanut in, and you have an allergy, then you’d skip it and go to the next one. You wouldn’t expect to have to look far to find one that doesn’t have peanut, and because you’ve got the “sorted by price” menu, you have the cheapest one that satisfies your condition after looking through just a few records.

It’s clearly not the same algorithm as finding all the things that satisfy the condition first, but it’s just as valid. If you’re only going to have to look through a handful of products before you find one that starts with the right letter, then great! But what if there are none? You’d end up having to look through the whole list before you realised.

The Query Optimizer faces the same dilemma, but luckily it might have statistics, so it should be able to know which will suit better.

Let’s create the two indexes – one sorted by Name, one sorted by Price. Both will include the other column, so that the query will only need one of them.

CREATE INDEX ixNamePrice ON Production.Product (Name) INCLUDE (ListPrice);
CREATE INDEX ixPriceName ON Production.Product (ListPrice) INCLUDE (Name);

Now let’s consider two queries. Both queries give the same result – $0.00. But that’s not important, I’m only interested in how they run.

SELECT MIN(ListPrice)
FROM Production.Product
WHERE Name LIKE 'I%';

SELECT MIN(ListPrice)
FROM Production.Product
WHERE Name LIKE 'H%';

The two queries are almost identical, but they run quite differently.

Ok, they’re fairly similar – they both use a Stream Aggregate operator, for example. And they have similar cost. But significantly, one is performing a Seek, while the other is doing a Scan. Different indexes, but nevertheless a Scan and a Seek.

People will tell you that Scans are bad and Seeks are good, but it’s not necessarily the case. Here, we see that the Scan plan is no more expensive than the Seek plan – it’s just different. We should consider why.

Those two indexes are the two different stories that I described earlier. There are very few products that start with the letter ‘I’, and quite a number than start with ‘H’, and so the Query Optimizer has chosen differently.

There are exactly 10 products that start with I. From a total of 504. That’s less than 2% of the products.

There are 91 products that start with H. That’s 18%. You might not have expected it to be that high, but that’s okay – if SQL has been maintaining statistics for you on this, it hopefully won’t be as surprised as you.

18% – nearly 1 in 5. So by the time you’ve looked at, oh, a dozen records, you will have almost certainly found one that starts with an H. (Actually, the chance of NOT finding one in the first 12 would be power(.82, 12), which is 0.09. That’s just 9%.) If I do a bit of digging into the internals, I can discover that the pages in my index typically have over a hundred records on them each. The chance of not finding a product that starts with an H on that first page – you’d need lottery-scale luck (1 in 444 million).

On the other hand, the cost of finding the cheapest value from 91 records is a lot more expensive than finding the cheapest from just 10. And getting all 10 records should be a small number of reads too.

But a Scan! Really? It has to look through the whole table, right?

No. That’s not how it works.

You see, execution plans go from left to right. If you start reading these plans from the right, you’ll start thinking that the whole index has been scanned, when it’s simply not the case. That Top operator asks for a single row from the index, and that’s all it provides. Once that row has been found, the Scan operation stops.

For this information, I don’t even need to pull up the Properties window for the Scan (but I would recommend you get in the habit of doing that). No – this is all available in the Tool Tip. Look at the number of “Actual number of rows” – it’s just one.

A predicate is applied – it looks through the index for rows that start with H – but it’s doing this in Order (see Ordered = True), and it’s stopping after the first row is found. Remember I mentioned that there are actually 91 rows that satisfy the predicate? The Scan doesn’t care – it only needs one and it stops right then.

You might figure this is because we are using MIN. What if we needed the MAX though? Well, that’s just the same, except that the Direction of the Scan is BACKWARD (you’ll need F4 for that one).

MIN goes forward, because it’s most interested in the ‘smallest’ ones, MAX will go backward because it wants the ‘largest’. (And as you’d probably expect, if you’d created your index to be descending, then it would be reversed.)

But again – being able to tell which is the better algorithm depends entirely on your statistics being known.

I see so many systems have bad statistics for one reason or another, and typically because the data most frequently queried is the newest data, and that makes up such a small percentage of the table. The statistics will think that there is almost no data for ‘today’, as they probably haven’t been updated since at least some number of hours ago.

When you look at how a query is running, always have a think about you’d solve it on paper, and remember that you might actually have a better (or worse) picture of the statistics than what the Query Optimizer has.

And remember that a Scan is not necessarily bad. I might do another post on that soon as well.

@rob_farley

Joins in single-table queries

rob_farley — Tue, 11 Dec 2012 00:05:17 GMT

Tables are only metadata. They don’t store data.

I’ve written something about this before, but I want to take a viewpoint of this idea around the topic of joins, especially since it’s the topic for T-SQL Tuesday this month. Hosted this time by Sebastian Meine (@sqlity), who has a whole series on joins this month. Good for him – it’s a great topic.

In that last post I discussed the fact that we write queries against tables, but that the engine turns it into a plan against indexes. My point wasn’t simply that a table is actually just a Clustered Index (or heap, which I consider just a special type of index), but that data access always happens against indexes – never tables – and we should be thinking about the indexes (specifically the non-clustered ones) when we write our queries.

I described the scenario of looking up phone numbers, and how it never really occurs to us that there is a master list of phone numbers, because we think in terms of the useful non-clustered indexes that the phone companies provide us, but anyway – that’s not the point of this post.

So a table is metadata. It stores information about the names of columns and their data types. Nullability, default values, constraints, triggers – these are all things that define the table, but the data isn’t stored in the table. The data that a table describes is stored in a heap or clustered index, but it goes further than this.

All the useful data is going to live in non-clustered indexes. Remember this. It’s important. Stop thinking about tables, and start thinking about indexes.

So let’s think about tables as indexes. This applies even in a world created by someone else, who doesn’t have the best indexes in mind for you.

I’m sure you don’t need me to explain Covering Index bit – the fact that if you don’t have sufficient columns “included” in your index, your query plan will either have to do a Lookup, or else it’ll give up using your index and use one that does have everything it needs (even if that means scanning it). If you haven’t seen that before, drop me a line and I’ll run through it with you. Or go and read a post I did a long while ago about the maths involved in that decision.

So – what I’m going to tell you is that a Lookup is a join.

When I run SELECT CustomerID FROM Sales.SalesOrderHeader WHERE SalesPersonID = 285; against the AdventureWorks2012 get the following plan:

I’m sure you can see the join. Don’t look in the query, it’s not there. But you should be able to see the join in the plan. It’s an Inner Join, implemented by a Nested Loop. It’s pulling data in from the Index Seek, and joining that to the results of a Key Lookup.

It clearly is – the QO wouldn’t call it that if it wasn’t really one. It behaves exactly like any other Nested Loop (Inner Join) operator, pulling rows from one side and putting a request in from the other. You wouldn’t have a problem accepting it as a join if the query were slightly different, such as

SELECT sod.OrderQty
FROM Sales.SalesOrderHeader AS soh
JOIN Sales.SalesOrderDetail as sod
on sod.SalesOrderID = soh.SalesOrderID
WHERE soh.SalesPersonID = 285;

Amazingly similar, of course. This one is an explicit join, the first example was just as much a join, even thought you didn’t actually ask for one.

You need to consider this when you’re thinking about your queries.

But it gets more interesting.

Consider this query:

SELECT SalesOrderID
FROM Sales.SalesOrderHeader
WHERE SalesPersonID = 276
AND CustomerID = 29522;

It doesn’t look like there’s a join here either, but look at the plan.

That’s not some Lookup in action – that’s a proper Merge Join. The Query Optimizer has worked out that it can get the data it needs by looking in two separate indexes and then doing a Merge Join on the data that it gets. Both indexes used are ordered by the column that’s indexed (one on SalesPersonID, one on CustomerID), and then by the CIX key SalesOrderID. Just like when you seek in the phone book to Farley, the Farleys you have are ordered by FirstName, these seek operations return the data ordered by the next field. This order is SalesOrderID, even though you didn’t explicitly put that column in the index definition. The result is two datasets that are ordered by SalesOrderID, making them very mergeable.

Another example is the simple query

SELECT CustomerID
FROM Sales.SalesOrderHeader
WHERE SalesPersonID = 276;

This one prefers a Hash Match to a standard lookup even! This isn’t just ordinary index intersection, this is something else again! Just like before, we could imagine it better with two whole tables, but we shouldn’t try to distinguish between joining two tables and joining two indexes.

The Query Optimizer can see (using basic maths) that it’s worth doing these particular operations using these two less-than-ideal indexes (because of course, the best indexese would be on both columns – a composite such as (SalesPersonID, CustomerID – and it would have the SalesOrderID column as part of it as the CIX key still).

You need to think like this too.

Not in terms of excusing single-column indexes like the ones in AdventureWorks2012, but in terms of having a picture about how you’d like your queries to run. If you start to think about what data you need, where it’s coming from, and how it’s going to be used, then you will almost certainly write better queries.

…and yes, this would include when you’re dealing with regular joins across multiples, not just against joins within single table queries.

Covering, schmuvvering – when a covering index is actually rubbish

rob_farley — Thu, 19 May 2011 04:11:34 GMT

Take a look at this query plan.

Yes, that arrow indicates a single row. This is an Index Seek, returning a single row. And yet it’s rubbish. That’s right – it’s rubbish!

In fact, I had to provide a hint for it to use this index. A table scan would’ve been better, and this is what happens without the index hint.

Let’s look at the query. I can promise you there’s no bug here.

SELECT Name, ProductNumber
FROM Production.Product
WHERE DaysToManufacture < 4
AND ReorderPoint < 100
AND Color = 'Red';

And the covering index is defined as follows:

CREATE INDEX rf_ix_Covering ON Production.Product(DaysToManufacture)
INCLUDE (Name, ProductNumber, Size, ReorderPoint, Color)
WITH (FILLFACTOR=30);

Try it yourself on AdventureWorks, you should see the same.

Of course, there’s a bit of trickery going on. For example, I purposely spaced out the NCIX using FILLFACTOR=30. But despite that, most DBAs would tell you that the first plan is better than the second. But they’d be wrong.

Let’s look at the tooltip of each of those Index operations. First, the Clustered Index Scan.

There’s no real surprise here. We know there’s only one row being returned, I told you that before. There’s a predicate listed which is tested on every row, and the Name and ProductNumber are the two fields which are being outputted. Estimated Subtree Cost of 0.0127253.

How about that Seek then, which the Query Optimizer only chose when its hand was forced by a hint?

You’ll probably notice immediately that the Estimated Subtree Cost is higher! 0.0141 instead of 0.0127. The reason why is in the Predicate and Seek Predicate sections. Sure, it can do a Seek – it can seek on the first key column of the index, on DaysToManufacture. But having found those records, the data is still very much in DaysToManufacture order. We can’t search on those predicates very easily at all, and we’re left with them being handled as a Residual Predicate.

To use a phone-book example, this is like searching for people called “Rob F.” – I can easily find people whose last name starts with F, but would then have to go through all of them looking for people called Rob. That residual check could be painful. Actually, this particular example is more like saying “Find me anyone called Rob whose surname is < Z”, as the Seek Predicate involved returns most of the table.

Unfortunately, the query plan doesn’t show us how many rows go through the Residual Predicate check. If it did, we’d be able to see that it’s over 400 rows (in a table of 504 rows), and we might rethink our indexing strategy.

In fact, I can easily make an index which causes the same query to perform a full Index Scan, plus Lookup, and which is half the cost of either of the plans we’ve seen so far.

CREATE INDEX rf_ix_NotCovering ON Production.Product(DaysToManufacture)
WHERE DaysToManufacture < 4
AND ReorderPoint < 100
AND Color = 'Red';

Of course, now I’m really cheating, by using a Filtered Index which would only contain a single row. And I could’ve eliminated the Lookup by including the other columns, halving the cost yet again.

CREATE INDEX rf_ix_Covering2 ON Production.Product(DaysToManufacture)
INCLUDE (Name, ProductNumber)
WHERE DaysToManufacture < 4
AND ReorderPoint < 100
AND Color = 'Red';

Interestingly, the tooltips for both of these Filtered Index operations don’t show the predicates – the Query Optimizer knows that the index has already done the necessary filtering, and in this case, it doesn’t need to apply any further predicates, whether Seek or Residual.

So… just because an index is covering a query, doesn't mean it’s necessarily the right choice. The better question is “Is this index good for this query?”

(Incidentally, this is the kind of thing that I’d go through in my pre-conference seminar at SQLPASS if chosen, and in the talk on “Joins, SARGability and the Evils of Residualiciousness” if that one gets picked)

@rob_farley

Function Invertability for SARGability

rob_farley — Thu, 24 Mar 2011 00:42:07 GMT

My good friend Simon Sabin used the term ‘invertability’ on a Connect item he logged today.

Essentially, Simon’s noticed that there are lots of people that use year(someDate), but that the system doesn’t understand that this function doesn’t affect the order of the items in the index. month(someDate) does, but if you’re already using year(someDate), then the combination of the two doesn’t change.

This is one of the keys to SARGability, which I’ve written about before, like at http://bit.ly/sargability. I’ve also raised a Connect item myself about it.

However, the term ‘invertability’ is interesting, and ties into the Inverse Predicates concept that I’ve also used before, like at http://bit.ly/inversepredicates. The idea is that you might have applied a function to a column, creating a predicate that isn’t sargable, but if you (or the system) can tell how to invert it, then you can make a predicate that can be easily handled by the Query Optimizer. Currently, the system doesn’t understand the invertability of all the functions (even easy ones like the YEAR function), but it’s something which would make SQL a lot faster if it did.

I’m going to let you read those various posts yourself, and encourage you to vote for Simon’s connect item. But as well as that, I’m going to encourage you to consider the SARGability of the predicates in your query.

Edit: Simon’s written a post on this now.

Probe Residual when you have a Hash Match – a hidden cost in execution plans

rob_farley — Mon, 21 Mar 2011 22:58:44 GMT

No, this post has nothing to do with airport security, and nothing to do with marijuana.

Being honest, this post is only half about Hash Matches and Probe Residuals. It’s more about the types of predicates you can see mentioned in a SQL Server Execution Plan (or Query Plan, but I prefer to call them Execution Plans) – but you may well see some described as a Probe Residual when you look at the properties of a Hash Match operator.

The main point of this post is: Some of these predicates can be really bad, even if they’re part of things which seem really good (like Seeks or Merge Joins).

Let’s consider a join. Two streams of data, of which matching rows must be found. These matching rows will be the ones that satisfy the join conditions, expressed through predicates listed in the ON clause and/or the WHERE clause. In fact, these predicates might only involve one side of the join, such as OrderDate <= '2011-03-22T00:00:00.000'. There are plenty of times when a join condition will incorporate a one-sided predicate like this – imagine a scenario in which matching rows can be easily located in an index, but only those that match an additional condition are allowed to be included.

In a join (ha!) there are these two streams of data, joined by one of a few different operators. This operator could be a Hash Match; it could be a Merge Join. It could even be a Nested Loop, although then the predicates are (generally) handled in the second (lower) data source. In fact, let’s start with that scenario.

When a Seek is performed, there are two main kinds of predicates that can be included. One is the Seek Predicate, and one is simply listed as Predicate. I prefer to call this second one the Residual Predicate. It’s the leftover one, after the Seek has been performed. This often happens when SARGability isn’t possible. SARGability is about being able to use an index effectively (with a seek), so if you have a predicate which doesn’t allow SARGability (for example, being able to consider the last letter of a character string.

You’ll see here that for each Product we find, we look up the Subcategory name for it. We have [s].[ProductSubcategoryID] before the Seek is done (the Nested Loop calls the Seek operator using each one), but although it can quickly seek to the right row(s) involved, it performs an additional check, making sure that the Product Name ends in a 'y'.

To get this plan, I used the query:

CREATE INDEX rf_ix_Product_SubCat_inc_Name ON
Production.Product(ProductSubcategoryID) INCLUDE (Name);

SELECT s.Name, COUNT(*)
FROM Production.ProductSubcategory s
INNER JOIN Production.Product p
ON s.ProductSubcategoryID = p.ProductSubcategoryID
WHERE p.Name like '%y'
GROUP BY s.Name;

The index lets the system immediately search for the rows needed. It can seek to the rows in rf_ix_Product_Subcat_inc that match the SubcategoryID, but this is only half the story. Having applied this Seek Predicate, there’s still the matter of the last letter of the Product Name, which isn’t something that can be checked easily with the index. The values are there, but each row that the Seek finds must be checked individually, with this leftover, or Residual, Predicate.

Hopefully this helps show why I want to call the Predicate here a Residual Predicate.

But this Residual Predicate must be tested on every row that is fetched by the Seek. That could well be a lot of rows, if the Seek isn’t particularly selective.

The Seek might feel really nice, and might be returning very few rows. But the effort could be a lot larger than you expect if most of the work is being done in the Residual Predicate.

The Nested Loop operator pulls rows from the first stream of data, and passes the required values down to the next row of operators, pulling a stream of data which is then simply joined. All the rows that come in from the second stream of data are known to be matches with the row that provided the values, so that there is relatively little work in doing the actual join.

In a Merge Join or Hash Match, things are slightly different. The predicate checking happens in the actual join operator. However, there are still two types of predicates – the main ones and the residuals.

In a Merge Join, the two data streams are ordered by columns appropriate for the join, but there could still be a leftover predicate.

Consider this query (but I’ve dropped the extra index at this point). It’s a very similar query to before, but I’m forcing a Merge Join with a Join Hint, and I’ve thrown in a predicate which is non-SARGable from the perspective of either table. This is part of the clue to the problem – it’s a non-SARGable predicate. Mind you, it could seem perfectly SARGable. It might simply be that the stream of data being used for the Merge Join isn’t ordered by all the columns involved in the join.

SELECT s.Name, COUNT(*)
FROM Production.ProductSubcategory s
INNER MERGE JOIN Production.Product p
ON s.ProductSubcategoryID = p.ProductSubcategoryID
WHERE RIGHT(p.Name, LEN(s.Name)) = 'blah'
GROUP BY s.Name;

When hovering over the Merge Join operator in this query’s plan, we see this tooltip. You’ll notice that it has a section called “Where (join columns)” which shows that the join is being done on the ProductSubcategoryID.

However, the other predicate isn’t mentioned. It’s nowhere in the tooltip. Hitting F4 shows the Properties window, and this is where we find it, in a property called Residual.

Residual: [AdventureWorks].[Production].[Product].[ProductSubcategoryID] as [p].[ProductSubcategoryID]=[AdventureWorks].[Production].[ProductSubcategory].[ProductSubcategoryID] as [s].[ProductSubcategoryID] AND right([AdventureWorks].[Production].[Product].[Name] as [p].[Name],len([AdventureWorks].[Production].[ProductSubcategory].[Name] as [s].[Name]))=N'blah'

Interestingly, it re-checks that the ProductSubcategoryID columns match, but the important thing is that it’s here (and only here) that Residual Predicate is tested.

This Residual Predicate must be tested on every combination of rows that match the ‘Where (join columns)’ predicate. That could well be a lot of rows, if those rows aren’t particularly selective.

With a Hash Match, the join is done by first applying a Hash function to columns involved in the join, using the resultant Hash Key to populate the data (including all the required columns) into a Hash Table. Once that has been done for one stream of data, the second stream is pulled in, and the Hash function applied to the columns from the second stream. The result of each row from the second stream is used in a Probe of the Hash Table. However, predicates which don’t work nicely with the Hash Key concept (such as the ‘blah’ predicate I used earlier) are considered residual.

SELECT s.Name, COUNT(*)
FROM Production.ProductSubcategory s
INNER JOIN Production.Product p
ON s.ProductSubcategoryID = p.ProductSubcategoryID
WHERE RIGHT(p.Name, LEN(s.Name)) = 'blah'
GROUP BY s.Name;

So when candidate rows are identified via the Probe, the Probe Residual still needs to be tested. Just like the Predicate after the Seek Predicate was done, and the Residual after the Where (join columns) are handled.

This Probe Residual must be tested on every combination of rows that satisfies the Hash Key Probe. That could well be a lot of rows, if that probe isn’t particularly selective.

When you’re trying to tune your query, you need to consider how many rows are being matched by each section of the join.

Imagine with me that you have a Merge Join (or a Hash Match), in which you have a predicate such as p1.ListPrice - p2.Listprice = 0

SELECT p1.Product
FROM Production.Product p1
JOIN Production.Product p2
ON p1.ProductSubcategoryID = p2.ProductSubcategoryID
AND p1.ListPrice - p2.ListPrice = 0

(Incidentally, this query could use any of the three joins, depending on indexes and other filters. Put an index on ProductSubcategoryID including ListPrice, and then run the query with either no WHERE clause (Hash Match), a WHERE clause for ProductSubcategoryID < 2 (Nested Loop) or < 5 (Merge Join).)

The predicate featuring the ListPrice column is always going to be treated as residual. It’s something that can only be tested once both values are known, and is considered a non-SARGable predicate. Regardless of what type of join is done, the ListPrice predicate is handled as a Residual.

For this query, the answer is hopefully obvious. Rewriting the predicate as p1.ListPrice = p2.ListPrice will resolve it nicely, but an example you have might not be so straightforward.

Residual predicates can be expensive, and the bottleneck of your query might not be obvious from looking at the plan. The mere fact that a Residual in a Merge Join is not shown in the tooltip could mean you miss it significantly. Don’t worry – you’ll be in good company. Plenty of proper experts miss this.

Luckily, the answer is simple. Look at your Seek Predicates, your Where (join columns) and your Hash Keys Probes, and compare this to the Residuals. If the Residuals are needing to be checked for a lot more rows that you’d like, then you have a tuning opportunity you can leverage. Ideally, Residuals only need to be applied on a tiny number of rows.

Remember, a Residual Predicate will feel like a Scan, because it’s not using the Index nicely. Scanning a tiny table might be fine, but scanning a large one could be horrible.

@rob_farley

The SSIS tuning tip that everyone misses

rob_farley — Thu, 17 Feb 2011 06:19:09 GMT

I know that everyone misses this, because I’m yet to find someone who doesn’t have a bit of an epiphany when I describe this.

When tuning Data Flows in SQL Server Integration Services, people see the Data Flow as moving from the Source to the Destination, passing through a number of transformations. What people don’t consider is the Source, getting the data out of a database.

Remember, the source of data for your Data Flow is not your Source Component. It’s wherever the data is, within your database, probably on a disk somewhere. You need to tune your query to optimise it for SSIS, and this is what most people fail to do.

I’m not suggesting that people don’t tune their queries – there’s plenty of information out there about making sure that your queries run as fast as possible. But for SSIS, it’s not about how fast your query runs. Let me say that again, but in bolder text:

The speed of an SSIS Source is not about how fast your query runs.

If your query is used in a Source component for SSIS, the thing that matters is how fast it starts returning data. In particular, those first 10,000 rows to populate that first buffer, ready to pass down the rest of the transformations on its way to the Destination.

Let’s look at a very simple query as an example, using the AdventureWorks database:

We’re picking the different Weight values out of the Product table, and it’s doing this by scanning the table and doing a Sort. It’s a Distinct Sort, which means that the duplicates are discarded.

It'll be no surprise to see that the data produced is sorted. Obvious, I know, but I'm making a comparison to what I'll do later.

Before I explain the problem here, let me jump back into the SSIS world...

If you’ve investigated how to tune an SSIS flow, then you’ll know that some SSIS Data Flow Transformations are known to be Blocking, some are Partially Blocking, and some are simply Row transformations.

Take the SSIS Sort transformation, for example. I’m using a larger data set for this, because my small list of Weights won’t demonstrate it well enough.

Seven buffers of data came out of the source, but none of them could be pushed past the Sort operator, just in case the last buffer contained the data that would be sorted into the first buffer. This is a blocking operation.

Back in the land of T-SQL, we consider our Distinct Sort operator. It’s also blocking. It won’t let data through until it’s seen all of it.

If you weren’t okay with blocking operations in SSIS, why would you be happy with them in an execution plan?

The source of your data is not your OLE DB Source. Remember this. The source of your data is the NCIX/CIX/Heap from which it’s being pulled.

Picture it like this... the data flowing from the Clustered Index, through the Distinct Sort operator, into the SELECT operator, where a series of SSIS Buffers are populated, flowing (as they get full) down through the SSIS transformations.

Alright, I know that I’m taking some liberties here, because the two queries aren’t the same, but consider the visual.

The data is flowing from your disk and through your execution plan before it reaches SSIS, so you could easily find that a blocking operation in your plan is just as painful as a blocking operation in your SSIS Data Flow.

Luckily, T-SQL gives us a brilliant query hint to help avoid this.

OPTION (FAST 10000)

This hint means that it will choose a query which will optimise for the first 10,000 rows – the default SSIS buffer size. And the effect can be quite significant.

First let’s consider a simple example, then we’ll look at a larger one.

Consider our weights. We don’t have 10,000, so I’m going to use OPTION (FAST 1) instead.

You’ll notice that the query is more expensive, using a Flow Distinct operator instead of the Distinct Sort. This operator is consuming 84% of the query, instead of the 59% we saw from the Distinct Sort. But the first row could be returned quicker – a Flow Distinct operator is non-blocking.

The data here isn’t sorted, of course. It’s in the same order that it came out of the index, just with duplicates removed.

As soon as a Flow Distinct sees a value that it hasn’t come across before, it pushes it out to the operator on its left. It still has to maintain the list of what it’s seen so far, but by handling it one row at a time, it can push rows through quicker. Overall, it’s a lot more work than the Distinct Sort, but if the priority is the first few rows, then perhaps that’s exactly what we want.

The Query Optimizer seems to do this by optimising the query as if there were only one row coming through:

This 1 row estimation is caused by the Query Optimizer imagining the SELECT operation saying “Give me one row” first, and this message being passed all the way along. The request might not make it all the way back to the source, but in my simple example, it does.

I hope this simple example has helped you understand the significance of the blocking operator. Now I’m going to show you an example on a much larger data set.

This data was fetching about 780,000 rows, and these are the Estimated Plans. The data needed to be Sorted, to support further SSIS operations that needed that.

First, without the hint.

...and now with OPTION (FAST 10000):

A very different plan, I’m sure you’ll agree. In case you’re curious, those arrows in the top one are 780,000 rows in size. In the second, they’re estimated to be 10,000, although the Actual figures end up being 780,000.

The top one definitely runs faster. It finished several times faster than the second one. With the amount of data being considered, these numbers were in minutes. Look at the second one – it’s doing Nested Loops, across 780,000 rows! That’s not generally recommended at all. That’s “Go and make yourself a coffee” time. In this case, it was about six or seven minutes. The faster one finished in about a minute.

But in SSIS-land, things are different.

The particular data flow that was consuming this data was significant. It was being pumped into a Script Component to process each row based on previous rows, creating about a dozen different flows. The data flow would take roughly ten minutes to run – ten minutes from when the data first appeared.

The query that completes faster – chosen by the Query Optimizer with no hints, based on accurate statistics (rather than pretending the numbers are smaller) – would take a minute to start getting the data into SSIS, at which point the ten-minute flow would start, taking eleven minutes to complete.

The query that took longer – chosen by the Query Optimizer pretending it only wanted the first 10,000 rows – would take only ten seconds to fill the first buffer. Despite the fact that it might have taken the database another six or seven minutes to get the data out, SSIS didn’t care. Every time it wanted the next buffer of data, it was already available, and the whole process finished in about ten minutes and ten seconds.

When debugging SSIS, you run the package, and sit there waiting to see the Debug information start appearing. You look for the numbers on the data flow, and seeing operators going Yellow and Green. Without the hint, I’d sit there for a minute. With the hint, just ten seconds. You can imagine which one I preferred.

By adding this hint, it felt like a magic wand had been waved across the query, to make it run several times faster. It wasn’t the case at all – but it felt like it to SSIS.

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.

SARGability isn’t about the left-hand side

rob_farley — Tue, 12 Oct 2010 22:10:12 GMT

This month’s T-SQL Tuesday has me caught slightly unawares. I’m in the UK, having come over for SQLBits, and I’m left writing this with only a few hours to go.

The theme this time is on misconceptions in SQL, and this fits nicely with SARGability – one of the topics that I presented on at SQLBits a week and a half ago. I often see people refer to SARGability as making sure that the left-hand side of the predicate is untouched. In other words, suggesting that something like this would be fine:

WHERE someColumn = someFunction(someValue)

whereas something like this would not:

WHERE someOtherFunction(someColumn) = someValue

As with most misconceptions, there’s an element of truth to this, but it definitely doesn’t tell the whole story.

If you have an index on someColumn, then great – the first predicate should let you find the value you want in that index nicely. Then you have other questions about whether the index is suitable or not, but that’s for a different post. On the other hand, if you don’t have an index, then the system is going to scan the table (or at least some less suitable index) in both scenarios. Applying the function to each column is painful in the second one, but SARGability is about producing seeks instead of scans, and these would both cause scans.

But how often do you write predicates like this. Normally, we have something more like:

ON x.someColum = y.someOtherColumn

…and this naturally causes a question. Do we want to be looking up the values in x, or in y? What needs to be SARGable here, the left or the right? It’s very easy to assume the left, but is it really going to be best for you? SQL Server doesn’t care which way around you’ve written your predicate, so don’t hold onto the ‘left-hand side’ idea longer than the end of this post. In fact, think about the way you want your query to be executed, and ask yourself where your SARGability should actually be looking.

It’s all a matter of perspective…

Table? No such thing…

rob_farley — Mon, 13 Sep 2010 23:48:00 GMT

No really – hear me out.

Of course you create tables, and you query tables, and we say that data is stored in tables. The table is (rightly) a fundamental part of relational theory. But I find that when I think about queries and how they run, I need to approach the system thinking about the indexes that I’m querying, not the tables.

When you decide to find someone’s phone number, you have to make a decision about where you’re going to look that up. Do you pick up the White Pages, the Yellow Pages, your little black book, your kids’ school’s parent directory, or something else? In fact, this is a question that you ask yourself before you even consider whether the particular information is accessible or not. If you had no other option but to scan the entire White Pages (starting at page 1), you would probably just consider the information unobtainable.

And yet all these different sources of data are just different non-clustered indexes on the master set. They’re generally filtered, ordered in an appropriate way, and don’t contain all the information. The Yellow Pages is just businesses, ordered by business type. The White Pages doesn’t include the business type at all, and maybe the school’s parent directory doesn’t include the address. Each of them is designed for a particular type of use. The cost of maintaining them is considered (and presumably it’s understood that the benefits of having the index far outweighs of cost).

I know some of you will be telling me that not all tables have indexes – but every table in SQL Server is either a Heap or a Clustered Index, and if you consider that a Heap is simply an unordered index, then hopefully my points can stand.

When you write a query, you have the option of forcing a particular index to be used with a Hint. This is the kind of hint where you don’t get a choice. I’m sure you all know times when someone has “hinted” that a particular task needs doing, or that you should avoid telling a particular kind of joke, or etc. The kind of hint that if you can’t obey, an error situation will occur. So if you “hint” that a particular index should be used but that index isn’t there, you’ll get an error. So I try not to use index hints if possible.

But my dislike for index hints doesn’t stop me from wanting to consider indexes rather than tables. If I think about what data I want, I really ought to be thinking about the ideal index for my query, and expect to see that index being used in the execution plan. If it’s not being used, or it’s being used in a way that I didn’t expect, then I really ought to ask myself why and investigate the situation (and consider whether or not the way that the query is being run is acceptable or not – remember the analogy of not wanting to start on page one of the White Pages). Hopefully I’ll realise that the index I imagined wasn’t actually ideal when considering the statistics involved, or that the Query Optimizer has found some clever way to answer my query in a way that I didn’t expect, but sometimes you find that the way you’ve written the query is actually persuading the Query Optimizer to create a plan that’s not actually what you want. Correct, valid, but not necessarily ideal.

It’s very easy to just think in terms of tables. You need to reference tables in your query, which ultimately is a logical construct – but the plan that gets produced is what determines the performance, the locking, the cache use, etc, and the plan doesn’t talk about tables (and if it does, the word Table means Heap). By all means you should remember that two indexes that are based on the same ‘table’ may refer to the same data, and a perfectly valid plan could use a different index to what you’re expecting – but this doesn’t mean you shouldn’t give thought to what you consider the ‘correct’ index to be.

So move on from tables, and think in terms of indexes. You’ll learn more about how your queries get executed, and your indexing techniques will improve wildly. More importantly though, your queries will almost certainly run faster.

But to complete the story, it's also completely valid to think of every index as a table. Each non-clustered index could be thought of as a table which the key is like the table's clustered index, and the NCIX's included columns are like the rest of the columns in the table. This helps you think about the cost associated with maintaining your indexes, and also helps you plan them. I'm not saying that you should create different tables instead of indexes by any means, but when you consider the idea that a table is an index, also consider that each index is a table - just to complete the picture.