Query Optimizer Deep Dive – Part 3

This is the third in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group, and SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 1 Part 2 Part 4

Storage of Alternative Plans

We saw in part 2 how optimizer rules are used to explore logical alternatives for parts of the query tree, and how implementation rules are used to find physical operations to perform each logical steps.

To keep track of all these options, the cost-based part of the SQL Server query optimizer uses a structure called the Memo. This structure is part of the Cascades general optimization framework developed by Goetz Graefe.

Query Optimizer Deep Dive – Part 2

This is the second in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group, and SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 1 Part 3 Part 4

Cost-Based Optimization Overview

The input to cost-based optimization is a tree of logical operations produced by the previous optimization stages discussed in part one.

Cost-based optimization takes this logical tree, explores logical alternatives (different logical tree shapes that will always produce the same results), generates physical implementations, assigns an estimated cost to each, and finally chooses the cheapest physical option overall.

The goal of cost-based optimization is not to find the best possible physical execution plan by exploring every possible alternative. Rather, the goal is to find a good plan quickly.

Query Optimizer Deep Dive - Part 1

This is the first in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group, and SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 2 Part 3 Part 4

Introduction

The motivation behind writing these sessions is finding that relatively few people have a good intuition for the way the optimizer works. This is partly because the official documentation is rather sparse, and partly because what information is available is dispersed across many books and blog posts.

The content presented here is very much geared to my preferred way of learning. It shows the concepts in what seems to me to be a reasonably logical sequence, and then provides tools to enable the interested reader to explore further, if desired.

Fun with Scalar and Vector Aggregates

There are interesting things to be learned from even the simplest queries.

For example, imagine you are asked to write a query that lists AdventureWorks product names, where the product has at least one entry in the transaction history table, but fewer than ten.

Dynamic Seeks and Hidden Implicit Conversions

A LIKE predicate with only a trailing wildcard can usually use an index seek, as the following AdventureWorks sample database query shows:

SELECT 
    P.[Name]
FROM Production.Product AS P
WHERE 
    P.[Name] LIKE N'D%';

Forcing a Parallel Query Execution Plan

This article is for SQL Server developers who have experienced the special kind of frustration that only comes from spending hours trying to convince the query optimizer to generate a parallel execution plan.

This situation often occurs when making an apparently innocuous change to the text of a moderately complex query — a change which somehow manages to turn a parallel plan that executes in ten seconds, into a five-minute serially-executing monster.

SQL Server Optimizer Bug with JOIN and GROUP BY

I came across a SQL Server optimizer bug recently that made me wonder how on earth I never noticed it before.

As the title of this post suggests, the bug occurs in common JOIN and GROUP BY queries. While it does not cause incorrect results to be returned, it will often cause a poor query plan to be selected by the optimizer.

If you are just interested in the bug itself, you will find a description in the section headed “the bug revealed”. It relates to cardinality estimation for serial partial aggregates.

As the regular reader will be expecting though, I am going to work up to it with a bit of background. The lasting value of this post (once the bug is fixed) is in the background details anyway.

Is Distinct Aggregation Still Considered Harmful?

Back in 2008, Marc Friedman of the SQL Server Query Processor Team wrote a blog entry entitled “Distinct Aggregation Considered Harmful”.

Marc shows a way to work around the poor performance that often results simply from adding the keyword DISTINCT to an otherwise perfectly reasonable aggregate function in a query.

This post is an update to that work, presenting a query optimizer enhancement in SQL Server 2012 that reduces the need to perform the suggested rewrite manually.

Finding the Statistics Used to Compile an Execution Plan

In this post, I show you how to determine the statistics objects used by the query optimizer in producing an execution plan.

Note: This technique only applies to queries compiled using the original (70) cardinality estimation model.

Can a SELECT query cause page splits?

The SQL Server documentation has this to say about page splits:

When a new row is added to a full index page, the Database Engine moves approximately half the rows to a new page to make room for the new row. This reorganization is known as a page split. A page split makes room for new records, but can take time to perform and is a resource intensive operation. Also, it can cause fragmentation that causes increased I/O operations.

Given that, how can a SELECT statement be responsible for page splits?

Well, I suppose we could SELECT from a function that adds rows to a table variable as part of its internal implementation, but that would clearly be cheating, and no fun at all from a blogging point of view.

SQL Server, Seeks, and Binary Search

The following table summarizes the results from my last two articles, Enforcing Uniqueness for Performance and Avoiding Uniqueness for Performance. It shows the CPU time used when performing 5 million clustered index seeks into a unique or non-unique index:

In test 1, making the clustered index unique improved performance by around 40%.

In test 2, making the same change reduced performance by around 70% (on 64-bit systems – more on that later).

Avoiding Uniqueness for Performance

In my last post, Enforcing Uniqueness for Performance, I showed how using a unique index could speed up equality seeks by around 40%.

Enforcing Uniqueness for Performance

A little while back, I posted a short series on seeks and scans:

• When is a Seek not a Seek?
• So…is it a Seek or a Scan?
• Seeking Without Indexes

One of the things I highlighted in the middle post was the difference between a singleton seek and a range scan:

• A singleton equality seek always retrieves exactly one row, and is guaranteed to do so because a unique index exists to enforce it.

• A range scan seeks down the B-tree to a starting (or ending) point, and scans forward (or backward) from that point using the next or previous page pointers.

Today’s short post shows how much faster a singleton seek is, compared with a range scan, even when both return exactly the same number of records.

Join Performance, Implicit Conversions, and Residuals

Introduction

You probably already know that it’s important to be aware of data types when writing queries, and that implicit conversions between types can lead to poor query performance.

Some people have gone so far as to write scripts to search the plan cache for CONVERT_IMPLICIT elements, and others routinely inspect plans for that type of thing when tuning.

Now, that’s all good, as far as it goes. It may surprise you to learn that not all implicit conversions are visible in query plans, and there are other important factors to consider too.

Bitmap Magic (or… how SQL Server uses bitmap filters)

Question

Can a parallel query use less CPU than the same serial query, while executing faster?

The answer is yes! To demonstrate, I’ll use the following two (heap) tables, each containing a single column typed as integer:

Undocumented Query Plans: The ANY Aggregate

As usual, here’s a sample table:

CREATE TABLE #Example
(
    pk numeric IDENTITY PRIMARY KEY NONCLUSTERED,
    col1 sql_variant NULL,
    col2 sql_variant NULL,
    thing sql_variant NOT NULL,
);

Some sample data:

And an index that will be useful shortly:

CREATE INDEX nc1 
ON #Example
    (col1, col2, thing);

There’s a complete script to create the table and add the data at the end of this post. There’s nothing special about the table or the data (except that I wanted to have some fun with values and data types).

Undocumented Query Plans: Equality Comparisons

The diagram below shows two data sets, with differences highlighted:

To find changed rows using T-SQL, we might write a query like this:

The logic is clear: Join rows from the two sets together on the primary key column, and return rows where a change has occurred in one or more data columns.

Unfortunately, this query only finds one of the expected four rows:

The problem is that our query does not correctly handle NULLs.

How Parallelism Works in SQL Server

You might have noticed that January was a quiet blogging month for me.

Part of the reason was that I was working on an article for Simple Talk, looking at how parallel query execution really works. The first part is published today at:

Understanding and Using Parallelism in SQL Server.

This introductory piece is not quite as technical as normal, but I hope there be enough interesting material there to make it worth a read.

© Paul White
email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

SQL Server Bug: Slow T-SQL Sums and Averages

It’s a curious thing about SQL that the SUM or AVG of no items (an empty set) is not zero, it’s NULL.

In this post, you’ll see how this means your SUM and AVG calculations might run at half speed, or worse. As usual though, this entry is not so much about the result, but the journey we take to get there.

Advanced TSQL Tuning: Why Internals Knowledge Matters

There is much more to query tuning than reducing logical reads and adding covering nonclustered indexes. Query tuning is not complete as soon as the query returns results quickly in the development or test environments.

In production, your query will compete for memory, CPU, locks, I/O, and other resources on the server. Today’s post looks at some tuning considerations that are often overlooked, and shows how deep internals knowledge can help you write better T-SQL.

I see no LOBs!

Is it possible to see LOB (large object) logical reads from STATISTICS IO output on a table with no LOB columns?

I was asked this question today by someone who had spent a good fraction of their afternoon trying to work out why this was occurring — even going so far as to re-run DBCC CHECKDB to see if corruption was the cause.

The table in question wasn’t particularly pretty. It had grown somewhat organically over time, with new columns being added every so often as the need arose.

Nevertheless, it remained a simple structure with no LOB columns — no text or image, no xml, no max types — nothing aside from ordinary integer, money, varchar, and datetime types.

To add to the air of mystery, not every query that ran against the table would report LOB logical reads — just sometimes — but when it did, the query often took much longer to execute.

Seeking Without Indexes

A seek can contain one or more seek predicates, each of which can either identify (at most) one row in a unique index (a singleton lookup) or a range of values (a range scan).

When looking at an execution plan, we often need to look at the details of the seek operator in the Properties window to see how many operations it is performing, and what type of operation each one is.

As seen in the first post of this mini-series, When is a Seek not a Seek? the number of hidden seeking operations can have an appreciable impact on performance.

So…is it a Seek or a Scan?

You might be most familiar with the terms ‘Seek’ and ‘Scan’ from the graphical plans produced by SQL Server Management Studio (SSMS). You might look to the SSMS tool-tip descriptions to explain the differences between them:

Both mention scans and ranges (nothing about seeks) and the Index Seek description maybe implies that it will not scan the index entirely (which isn’t necessarily true). Not massively helpful.

When is a Seek not a Seek?

The following script creates a single-column clustered table containing the integers from 1 to 1,000 inclusive.

IF OBJECT_ID(N'tempdb..#Test', N'U') IS NOT NULL
BEGIN
    DROP TABLE #Test
END;
GO
CREATE TABLE #Test
(
    id integer PRIMARY KEY CLUSTERED
);
INSERT #Test
    (id)
SELECT
    V.number
FROM master.dbo.spt_values AS V
WHERE
    V.[type] = N'P'
    AND V.number BETWEEN 1 AND 1000;

Let’s say we are given the following task:

Find the rows with values from 100 to 170, excluding any values that divide exactly by 10.

Beware Sneaky Reads with Unique Indexes

I saw a question asked recently on the #sqlhelp hash tag:

Might SQL Server retrieve (out-of-row) LOB data from a table, even if the column isn’t referenced in the query?

Leaving aside trivial cases like selecting a computed column that does reference the LOB data, one might be tempted to say that no, SQL Server does not read data you haven’t asked for.

In general, that is correct; however, there are cases where SQL Server might sneakily read a LOB column.