T-SQL Querying (2015)

---

When you’re done, run the following code for cleanup:

IF OBJECT_ID(N'dbo.V', N'V') IS NOT NULL DROP VIEW dbo.V;
IF OBJECT_ID(N'dbo.T3', N'U') IS NOT NULL DROP TABLE dbo.T3;
IF OBJECT_ID(N'dbo.T2', N'U') IS NOT NULL DROP TABLE dbo.T2;
IF OBJECT_ID(N'dbo.T1', N'U') IS NOT NULL DROP TABLE dbo.T1;

Inline table-valued functions

Suppose you need a reusable table expression like a view, but you also need to be able to pass input parameters to the table expression. Views do not support input parameters. For this purpose, SQL Server provides you with inline table-valued functions (TVFs). As an example, the following code creates an inline TVF called GetTopOrders that accepts as inputs a customer ID and a number and returns the requested number of most-recent orders for the input customer:

IF OBJECT_ID(N'dbo.GetTopOrders', N'IF') IS NOT NULL DROP FUNCTION dbo.GetTopOrders;
GO
CREATE FUNCTION dbo.GetTopOrders(@custid AS INT, @n AS BIGINT) RETURNS TABLE
AS
RETURN
SELECT TOP (@n) orderid, orderdate, empid
FROM Sales.Orders
WHERE custid = @custid
ORDER BY orderdate DESC, orderid DESC;
GO

The following code queries the function to return the three most recent orders for customer 1:

SELECT orderid, orderdate, empid
FROM dbo.GetTopOrders(1, 3) AS O;

SQL Server inlines the inner query and performs parameter embedding, meaning that it replaces the parameters with constants. After inlining and embedding, the query that actually gets optimized is the following:

SELECT TOP (3) orderid, orderdate, empid
FROM Sales.Orders
WHERE custid = 1
ORDER BY orderdate DESC, orderid DESC;

I find inline TVFs to be a great tool, allowing for the encapsulation of the logic and reusability without any performance penalties. I’m afraid I cannot say the same thing about the other types of user-defined functions (UDFs). I elaborate on performance problems of UDFs in Chapter 9, “Programmable objects.”

Generating numbers

One of my favorite tools in T-SQL, if not the favorite, is a function that returns a sequence of integers in a requested range. Such a function has so many practical uses that I’m surprised SQL Server doesn’t provide it as a built-in tool. Fortunately, by employing a few magical tricks, you can create a very efficient version of such a function yourself as an inline TVF.

Before looking at my version, I urge you to try and come up with yours. It’s a great challenge. Create a function called GetNums that accepts the inputs @low and @high and returns a sequence of integers in the requested range. The goal is best-possible performance. You will use the function to generate millions of rows in some cases, so naturally you will want it to perform well.

There are three critical things I rely on to get a performant solution:

Generating a large number of rows with cross joins

Generating row numbers efficiently without sorting

Short-circuiting the work with TOP when the requested number of rows is reached

The first step is to generate a large number of rows. It doesn’t really matter what you will have in those rows because eventually you’ll produce the numbers with the ROW_NUMBER function. A great way in T-SQL to generate a large number of rows is to apply cross joins. But you need a table with at least two rows as a starting point. You can create such a table as a virtual one by using the VALUES clause, like so:

SELECT c FROM (VALUES(1),(1)) AS D(c);

This query generates the following output showing that the virtual table has two rows:

c
-----------
1
1

The next move is to define a CTE based on the last query (call it L0, for level 0), and apply a self-cross join between two instances of L0 to get four rows, like so:

WITH
L0 AS (SELECT c FROM (VALUES(1),(1)) AS D(c))
SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B;

This query generates the following output:

c
-----------
1
1
1
1

The next move is to define a CTE called L1 based on the last query, and then join two instances of L1 to get 16 rows. Repeating this pattern, by the time you get to L5, you have potentially 4,294,967,296 rows! Here’s the expression to compute this number:

SELECT POWER(2., POWER(2., 5));

The next step is to query L5 and compute row numbers (call the column rownum) without causing a sort operation to take place. This is done by specifying ORDER BY (SELECT NULL). You define a CTE called Nums based on this query.

Finally, the last step is to query Nums, and with the TOP option filter @high – @low + 1 rows, ordered by rownum. You compute the result number column (call it n) as @low + rownum – 1.

Here’s the complete solution code applied to the sample input range 11 through 20:

DECLARE @low AS BIGINT = 11, @high AS BIGINT = 20;

WITH
L0 AS (SELECT c FROM (VALUES(1),(1)) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n
FROM Nums
ORDER BY rownum;

This code generates the following output:

n
--------------------
11
12
13
14
15
16
17
18
19
20

For reusability, encapsulate the solution in an inline TVF called GetNums, like so:

IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;
GO
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (VALUES(1),(1)) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n
FROM Nums
ORDER BY rownum;
GO

Use the following code to test the function:

SELECT n FROM dbo.GetNums(11, 20);

My friend Laurent Martin refers to this function as the harp function. This nickname might seem puzzling until you look at the query plan, which is shown in Figure 3-13.

FIGURE 3-13 The harp function.

The beauty of this plan is that the Top operator is the one requesting the rows from the branch to the right of it, and it short-circuits as soon as the requested number of rows is achieved. The Sequence Project and Nested Loops operators, which handle the row-number calculation and cross joins, respectively, respond to the request for rows from the Top operator. As soon as the Top operator stops requesting rows, they stop producing rows. In other words, even though potentially this solution can generate over four billion rows, in practice it generates only the requested number and then short-circuits. Testing the performance of the function on my laptop, it finished generating 10,000,000 numbers in four seconds, with results discarded. That’s not so bad.

The APPLY operator

The APPLY operator is one of the most powerful tools I know of in T-SQL, and yet, it seems to be unnoticed by many. Often when I teach about T-SQL, I ask the students who’s using APPLY and, in many cases, I get only a small percent saying they do. What’s interesting about this operator is that it can be used in very creative ways to solve all kinds of querying tasks.

There are three flavors of APPLY: CROSS APPLY, OUTER APPLY, and implicit APPLY. The following sections describe these flavors.

The CROSS APPLY operator

One way to think of the CROSS APPLY operator is as a hybrid of a cross join and a correlated subquery. Think for a moment of a regular cross join. The inputs can be tables or table expressions, but then the table expressions have to be self-contained. The inner queries are not allowed to be correlated ones. The CROSS APPLY operator is similar to a cross join, only the inner query in the right input is allowed to have correlations to elements from the left input. The left input, like in a cross join, has to be self-contained.

So, T1 CROSS JOIN T2 is equivalent to T1 CROSS APPLY T2. Also, T1 CROSS JOIN (self_contained_query) AS Q is equivalent to T1 CROSS APPLY (self_contained_query) AS Q. However, unlike a cross join, CROSS APPLY allows the right input to be a correlated table subquery, as in T1 CROSS APPLY (SELECT ... FROM T2 WHERE T2.col1 = T1.col1) AS Q. This means that for every row in T1, Q is evaluated separately based on the current value in T1.col1.

Interestingly, standard SQL doesn’t support the APPLY operator but has a similar feature called a lateral derived table. The standard’s parallel to T-SQL’s CROSS APPLY is a CROSS JOIN with a lateral derived table, allowing the right table expression to be a correlated one. So what in T-SQL is expressed as T1 CROSS APPLY (SELECT ... FROM T2 WHERE T2.col1 = T1.col1) AS Q, in standard SQL is expressed as T1 CROSS JOIN LATERAL (SELECT ... FROM T2 WHERE T2.col1 = T1.col1) AS Q.

To demonstrate a practical use case for CROSS APPLY, recall the earlier discussion in this chapter about the top N per group task. The specific example was filtering the most recent orders per customer. The order for the filter was based on orderdate descending with orderid descending used as the tiebreaker. I suggested creating the following POC index to support your solution:

CREATE UNIQUE INDEX idx_poc
ON Sales.Orders(custid, orderdate DESC, orderid DESC)
INCLUDE(empid);

I used the following solution based on a regular correlated subquery:

SELECT orderid, orderdate, custid, empid
FROM Sales.Orders
WHERE orderid IN
(SELECT
(SELECT TOP (1) orderid
FROM Sales.Orders AS O
WHERE O.custid = C.custid
ORDER BY orderdate DESC, orderid DESC)
FROM Sales.Customers AS C);

The problem with a regular subquery is that it’s limited to returning only one column. So this solution used a subquery to return the qualifying order ID per customer, but then another layer was needed with a query against Orders to retrieve the rest of the order information per qualifying order ID. So the plan for this solution shown earlier in Figure 3-3 involved a seek in the POC index per customer to retrieve the qualifying order ID, and another seek per customer in the POC index to retrieve the rest of the order information.

Because CROSS APPLY allows you to apply a correlated table expression, you’re not limited to returning only one column. So you can simplify the solution by removing the need for the extra layer, and instead of doing two seeks per customer, do only one. Here’s what the solution using the CROSS APPLY operator looks like (this time requesting the three most recent orders per customer):

SELECT C.custid, A.orderid, A.orderdate, A.empid
FROM Sales.Customers AS C
CROSS APPLY ( SELECT TOP (3) orderid, orderdate, empid
FROM Sales.Orders AS O
WHERE O.custid = C.custid
ORDER BY orderdate DESC, orderid DESC ) AS A;

It’s both simpler than the previous one and more efficient, as can be seen in the query plan shown in Figure 3-14.

FIGURE 3-14 Plan for a query with the CROSS APPLY operator.

In this example, the inner query is quite simple, so it’s no big deal to embed it directly. But in cases where the inner query is more complex, you would probably want to encapsulate it in an inline TVF, like so:

IF OBJECT_ID(N'dbo.GetTopOrders', N'IF') IS NOT NULL DROP FUNCTION dbo.GetTopOrders;
GO
CREATE FUNCTION dbo.GetTopOrders(@custid AS INT, @n AS BIGINT)
RETURNS TABLE
AS
RETURN
SELECT TOP (@n) orderid, orderdate, empid
FROM Sales.Orders
WHERE custid = @custid
ORDER BY orderdate DESC, orderid DESC;
GO

Then you can replace the correlated table expression with a call to the function, passing C.custid as the input customer ID (the correlation) and 3 as the number of rows to filter per customer, like so:

SELECT C.custid, A.orderid, A.orderdate, A.empid
FROM Sales.Customers AS C
CROSS APPLY dbo.GetTopOrders( C.custid, 3 ) AS A;

You can find a more extensive coverage of efficient handling of the top N per group task in Chapter 5.

The OUTER APPLY operator

The CROSS APPLY operator has something in common with an inner join in that left rows that don’t have matches on the right side are discarded. So, in the previous query, customers who didn’t place orders were discarded. Similar to a left outer join operator, which preserves all left rows, there’s an OUTER APPLY operator that preserves all left rows. Like with an outer join, the OUTER APPLY operator uses NULLs as placeholders for nonmatches on the right side.

As an example, to alter the last query to preserve all customers, replace CROSS APPLY with OUTER APPLY, like so:

SELECT C.custid, A.orderid, A.orderdate, A.empid
FROM Sales.Customers AS C
OUTER APPLY dbo.GetTopOrders( C.custid, 3 ) AS A;

This time, the output includes customers who didn’t place orders:

custid orderid orderdate empid
----------- ----------- ---------- -----------
1 11011 2015-04-09 3
1 10952 2015-03-16 1
1 10835 2015-01-15 1
2 10926 2015-03-04 4
2 10759 2014-11-28 3
2 10625 2014-08-08 3
...
22 NULL NULL NULL
...
57 NULL NULL NULL
58 11073 2015-05-05 2
58 10995 2015-04-02 1
58 10502 2014-04-10 2
...

As mentioned, standard SQL’s parallel to the T-SQL-specific APPLY operator is called a lateral derived table. I described the parallel to the CROSS APPLY operator in the previous section. As for the parallel to OUTER APPLY, what in T-SQL is expressed as T1 OUTER APPLY (SELECT ... FROM T2 WHERE T2.col1 = T1.col1) AS Q, in standard SQL is expressed as T1 LEFT OUTER JOIN LATERAL (SELECT ... FROM T2 WHERE T2.col1 = T1.col1) AS Q ON 1 = 1.

Implicit APPLY

The documented variations of the APPLY operator are the aforementioned CROSS APPLY and OUTER APPLY ones. There is another variation that involves doing something similar to what you do with the explicit APPLY operator, but without using the APPLY keyword in your code. I refer to this variation as implicit APPLY. An implicit APPLY involves using a subquery and, within it, querying a table function to which you pass columns from the outer table as inputs. This is probably best explained through an example.

Consider the GetTopOrders function you used in the previous sections to return the requested number of most recent orders for the requested customer. Suppose you want to compute for each customer from the Customers table the distinct count of employees who handled the customer’s 10 most recent orders. You want to reuse the logic encapsulated in the GetTopOrders function, so you do the following: you query the Customers table; you use a subquery to apply the function to the outer customer to return its 10 most recent orders; finally, you compute the distinct count of employees who handled those orders. Here’s the implementation of this logic in T-SQL:

SELECT C.custid,
( SELECT COUNT(DISTINCT empid) FROM dbo.GetTopOrders( C.custid, 10 ) ) AS numemps
FROM Sales.Customers AS C;

Notice that nowhere does the code mention the APPLY keyword explicitly, but clearly the code in the subquery applies the table function to each outer customer. This code generates the following output:

custid numemps
----------- -----------
1 4
2 3
3 4
4 4
5 6
6 5
7 6
8 2
9 7
11 7
...

It’s easy to see why the term implicit APPLY is appropriate here. Interestingly, before the explicit APPLY operator was added to SQL Server, you couldn’t use the implicit APPLY functionality, either. In other words, the implicit functionality was added thanks to the addition of the explicit operator.

Reuse of column aliases

As discussed in Chapter 1, one of the annoying things about SQL is that if you define a column alias in the SELECT clause of a query, you’re not allowed to refer to it in most query clauses. The only exception is the ORDER BY clause because it’s the only clause that is logically evaluated after the SELECT clause.

There is an elegant trick you can do when using the APPLY operator that solves the problem. Remember that APPLY is a table operator, and table operators are evaluated in the FROM clause of the query. Because the FROM clause is the first clause to be evaluated logically, any aliases you create in it become visible to the rest of the query clauses. Furthermore, because each table operator starts a new series of logical query-processing steps, aliases defined by one table operator are visible to subsequent table operators.

With this in mind, using the APPLY operator you can apply a derived table that defines aliases for expressions based on columns from the left table. The derived table can be based on a SELECT query without a FROM clause, or the VALUES clause, like so:

FROM T1 APPLY ( VALUES(<expressions_based_on_columns_in_T1>) ) AS A(<aliases>)

As an example, consider the following query:

SELECT orderid, orderdate
FROM Sales.Orders
CROSS APPLY ( VALUES( YEAR(orderdate) ) ) AS A1(orderyear)
CROSS APPLY ( VALUES( DATEFROMPARTS(orderyear, 1, 1),
DATEFROMPARTS(orderyear, 12, 31) )
) AS A2(beginningofyear, endofyear)
WHERE orderdate IN (beginningofyear, endofyear);

This query is issued against the Orders table. It is supposed to return only orders placed at the beginning or end of the year. The query uses one CROSS APPLY operator to define the alias orderyear for the expression YEAR(orderdate). It then uses a second CROSS APPLY operator to define the aliases beginningofyear and endofyear for the expressions DATEFROMPARTS(orderyear, 1, 1) and DATEFROMPARTS(orderyear, 12, 31), respectively. The query then filters only the rows where the orderdate value is equal to either the beginningofyear value or the endofyearvalue.

This query generates the following output:

orderid orderdate
----------- ----------
10399 2013-12-31
10400 2014-01-01
10401 2014-01-01
10806 2014-12-31
10807 2014-12-31
10808 2015-01-01
10809 2015-01-01
10810 2015-01-01

From an optimization perspective, this trick doesn’t have a negative performance impact because the expressions in the derived tables get inlined. Internally, after inlining the expressions, the preceding query becomes equivalent to the following query:

SELECT orderid, orderdate
FROM Sales.Orders
WHERE orderdate IN
(DATEFROMPARTS(YEAR(orderdate), 1, 1), DATEFROMPARTS(YEAR(orderdate), 12, 31));

The plans for both queries are the same.

Note that this particular example is pretty simple and is used mainly for illustration purposes. It’s so simple that the benefit in reusing column aliases here is questionable. But this trick becomes extremely handy when the computations are much longer and more complex.

As mentioned, you can use the APPLY operator in creative ways to solve a wide variety of problems. You can find examples in the Microsoft Virtual Academy (MVA) seminar “Boost Your T-SQL with the APPLY Operator” here: http://www.microsoftvirtualacademy.com/training-courses/boost-your-t-sql-with-the-apply-operator.

When you’re done practicing with the APPLY examples, run the following code for cleanup:

DROP INDEX idx_poc ON Sales.Orders;

Joins

The join is by far the most frequently used type of table operator and one of the most commonly used features in SQL in general. Most queries involve combining data from multiple tables, and one of the main tools used for this purpose is a join.

This section covers the fundamental join types (cross, inner, and outer), self, equi, and nonequi joins. It also covers logical and optimization aspects of multi-join queries, semi joins, and anti semi joins, as well as join algorithms. The section concludes with coverage of a common task called separating elements and demonstrates an efficient solution for the task based on joins.

Cross join

Between the three fundamental join types (cross, inner, and outer), the first is the simplest, although it is less commonly used than the others. A cross join produces a Cartesian product of the two input tables. If one table contains M rows and the other N rows, you get a result with M × Nrows.

In terms of syntax, standard SQL (as well as T-SQL) supports two syntaxes for cross joins. One is an older syntax in which you specify a comma between the table names, like so:

SELECT E1.firstname AS firstname1, E1.lastname AS lastname1,
E2.firstname AS firstname2, E2.lastname AS lastname2
FROM HR.Employees AS E1, HR.Employees AS E2;

Another is a newer syntax that was added in the SQL-92 standard, in which you specify a keyword indicating the join type (CROSS, in our case) followed by the JOIN keyword between the table names, like so:

SELECT E1.firstname AS firstname1, E1.lastname AS lastname1,
E2.firstname AS firstname2, E2.lastname AS lastname2
FROM HR.Employees AS E1
CROSS JOIN HR.Employees AS E2;

Both syntaxes are standard, and both are supported by T-SQL. There’s neither a logical difference nor an optimization difference between the two. You might wonder, then, why did standard SQL bother creating two different syntaxes if they have the same meaning? The reason for this doesn’t really have anything to do with cross and inner joins; rather, it is related to outer joins. Recall from the discussions in Chapter 1 that an outer join involves a matching predicate, which has a very different role than a filtering predicate. The former defines only which rows from the nonpreserved side of the join match to rows from the preserved side, but it cannot filter out rows from the preserved side. The latter is used as a basic filter and can certainly discard rows from both sides.

The SQL standards committee decided to add support for outer joins in the SQL-92 standard, but they figured that the traditional comma-based syntax doesn’t lend itself to supporting the new type of join. That’s because this syntax doesn’t allow you to define a matching predicate as part of the join table operator, which as mentioned, is supposed to play a different role than the filtering predicate that you specify in the WHERE clause. So they ended up creating the newer syntax with the JOIN keyword with a designated ON clause where you indicate the matching predicate. This newer syntax with the JOIN keyword is commonly referred to as the SQL-92 syntax, and the older comma-based syntax is referred to as the SQL-89 syntax.

To allow a consistent coding style for the different types of joins, the SQL-92 standard also added support for a similar JOIN-keyword-based syntax for cross and inner joins. That’s the history explaining why you now have two standard syntaxes for cross and inner joins and only one standard syntax for outer joins. It is strongly recommended that you stick to using the JOIN-keyword-based syntax across the board. One reason is that it results in a consistent coding style that is so much easier to maintain than a mixed style. Furthermore, the comma-based syntax is more prone to errors, as I will demonstrate later when discussing inner joins.

I’ll demonstrate a couple examples of use cases of cross joins. One is generating sample data, and the other is circumventing an optimization problem related to subqueries.

Suppose you need to generate sample data representing orders. An order has an order ID, was placed on a certain date, was placed by a certain customer, and was handled by a certain employee. You get as inputs the range of order dates as well as the number of distinct customers and employees you need to support. Using the GetNums function in the sample database, you can generate sets of dates, customer IDs, and employee IDs. You perform cross joins between those sets to get all possible combinations and, using a ROW_NUMBER function, compute the order IDs, like so:

DECLARE @s AS DATE = '20150101', @e AS DATE = '20150131',
@numcusts AS INT = 50, @numemps AS INT = 10;

SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS orderid,
DATEADD(day, D.n, @s) AS orderdate, C.n AS custid, E.n AS empid
FROM dbo.GetNums(0, DATEDIFF(day, @s, @e)) AS D
CROSS JOIN dbo.GetNums(1, @numcusts) AS C
CROSS JOIN dbo.GetNums(1, @numemps) AS E;

The unusual order specification ORDER BY (SELECT NULL) in the ROW_NUMBER function is a trick used to compute row numbers based on an arbitrary order. I use this trick when I need to generate unique values and I don’t care about the order in which they are generated.

Note that usually when you generate sample data, you need a more sophisticated solution that results in a more realistic distribution of the data. In reality, you typically don’t have even distribution of order dates, customer IDs, and employee IDs. But sometimes you need a very basic form of sample data for certain tests, and this simple technique can be sufficient for you.

Another use case for cross joins has to do with a certain optimization shortcoming in SQL Server related to subqueries. Consider the following query:

SELECT orderid, val,
val / (SELECT SUM(val) FROM Sales.OrderValues) AS pct,
val - (SELECT AVG(val) FROM Sales.OrderValues) AS diff
FROM Sales.OrderValues;

This query is issued against the OrderValues view. It returns for each order the percent of the current order value out of the grand total as well as the difference from the grand average. The grand total and grand average are computed by scalar aggregate subqueries. It is true that the query refers to the OrderValues view three times, but clearly both subqueries need to operate on the exact same set of values. Unfortunately, currently there’s no logic in the optimizer to avoid the duplication of work by collapsing all matching subqueries into one activity that will feed the same set of values to all aggregate calculations. In our case, the problem is even further magnified because OrderValues is a view. The view joins the Orders and OrderDetails tables, and it groups and aggregates the data to produce order-level information. All of this work is repeated three times in the execution plan for our query, as you can see in Figure 3-15.

FIGURE 3-15 Work is repeated for every subquery.

The branches marked as 1 and 2 represent the work for the two subqueries feeding the values to the two aggregate calculations. The branch marked as 3 represents the reference to the view in the outer query to obtain the order information—in other words, the detail. As you can imagine, the more aggregates you have, the worse this solution performs. Imagine you had 10 different aggregates to compute. This would require 11 repetitions of the work—10 for the aggregates and one for the detail.

Fortunately, there is a way to avoid the unnecessary repetition of the work. To achieve this, you use one query to compute all aggregates that you need. SQL Server will optimize this query by applying the work only once, feeding the same values to all aggregate calculations. You define a table expression based on that query (call it Aggs) and perform a cross join between the OrderValues view and Aggs. Then, in the SELECT list, you perform all your calculations involving the detail and the aggregates. Here’s the complete solution query:

SELECT orderid, val,
val / sumval AS pct,
val - avgval AS diff
FROM Sales.OrderValues
CROSS JOIN (SELECT SUM(val) AS sumval, AVG(val) AS avgval
FROM Sales.OrderValues) AS Aggs;

Observe the execution plan for this query shown in Figure 3-16.

FIGURE 3-16 Avoiding repetition of work with a join.

Notice that this time the work represented by the view happens only once for all aggregates (branch 1) and once for the detail (branch 2). The nice thing with this solution is that it doesn’t matter how many aggregates you have—you will still have only one activity that collects the values for all of them.

You will face a similar problem when you need the calculation to be partitioned. For example, suppose that instead of grand aggregates, you need customer aggregates. In other words, you need to compute the percent of the current order value out of the customer total (not the grand total) and the difference from the customer average. Using the subquery approach, you add correlations, like so:

SELECT orderid, val,
val / (SELECT SUM(val) FROM Sales.OrderValues AS I
WHERE I.custid = O.custid) AS pct,
val - (SELECT AVG(val) FROM Sales.OrderValues AS I
WHERE I.custid = O.custid) AS diff
FROM Sales.OrderValues AS O;

But again, because you’re using subqueries, the work represented by the view will be repeated three times. The solution is similar to the previous one, only instead of using a cross join, you use an inner join and match the customer IDs between the OrderValues view and Aggs, like so:

SELECT orderid, val,
val / sumval AS pct,
val - avgval AS diff
FROM Sales.OrderValues AS O
INNER JOIN (SELECT custid, SUM(val) AS sumval, AVG(val) AS avgval
FROM Sales.OrderValues
GROUP BY custid) AS Aggs
ON O.custid = Aggs.custid;

Inner join

From a logical query-processing perspective, an inner join involves two steps. It starts with a Cartesian product between the two input tables, like in a cross join. It then applies a filter that usually involves matching elements from both sides. From a physical query-processing perspective, of course things can be done differently, provided that the output is correct.

Like with cross joins, inner joins currently have two standard syntaxes. One is the SQL-89 syntax, where you specify commas between the table names and then apply all filtering predicates in the WHERE clause, like so:

SELECT C.custid, C.companyname, O.orderid
FROM Sales.Customers AS C, Sales.Orders AS O
WHERE C.custid = O.custid
AND C.country = N'USA';

As you can see, the syntax doesn’t really distinguish between a cross join and an inner join; rather, it expresses an inner join as a cross join with a filter.

The other syntax is the SQL-92 one, which is more compatible with the standard outer join syntax. You specify the INNER JOIN keywords between the table names (or just JOIN because INNER is the default) and the join predicate in the mandatory ON clause. If you have any additional filters, you can specify them either in the join’s ON clause or in the usual WHERE clause, like so:

SELECT C.custid, C.companyname, O.orderid
FROM Sales.Customers AS C
INNER JOIN Sales.Orders AS O
ON C.custid = O.custid
WHERE C.country = N'USA';

Despite the fact that the ON clause is mandatory in the SQL-92 syntax for inner joins, there is no distinction between a matching predicate and a filtering predicate like in outer joins. Both predicates are treated as filtering predicates. So, even though from a logical query-processing perspective, the WHERE clause is supposed to be evaluated after the FROM clause with all of its joins, the optimizer might very well decide to process the predicates from the WHERE clause before it starts processing the joins in the FROM clause. In fact, if you examine the plans for the two queries just shown, you will notice that in both cases the plan starts with a scan of the clustered index on the Customers table and applies the country filter as part of the scan.

I mentioned earlier that it’s recommended to stick to the SQL-92 syntax for joins and avoid the SQL-89 syntax even though it’s standard for cross and inner joins. I already provided one reason for this recommendation—using one consistent style for all types of joins. Another reason is that the SQL-89 syntax is more prone to errors; specifically, it is more likely you will miss a join predicate and for such a mistake to go unnoticed. With the SQL-92 syntax, you usually specify each join predicate right after the respective join, like so:

FROM T1
INNER JOIN T2
ON T2.col1 = T1.col1
INNER JOIN T3
ON T3.col2 = T2.col2
INNER JOIN T4
ON T4.col3 = T3.col3

With this syntax, the likelihood that you will miss a join predicate is low, and even if you do, the parser will generate an error because the ON clause is mandatory with inner (and outer) joins. Conversely, with the SQL-89 syntax, you specify all table names separated by commas in the FROM clause, and all predicates as a conjunction in the WHERE clause, like so:

FROM T1, T2, T3, T4
WHERE T2.col1 = T1.col1 AND T3.col2 = T2.col2 AND T4.col3 = T3.col3

Clearly the likelihood that you will miss a predicate by mistake is higher, and if you do, you end up with an unintentional cross join.

A common question I get is whether there’s a difference between using the keywords INNER JOIN and just JOIN. There’s none. Standard SQL made inner joins the default because it’s probably the most commonly used type of join. In a similar way, standard SQL made the keyword OUTER optional in outer joins. For example, LEFT OUTER JOIN and LEFT JOIN are equivalent. As for what’s recommended to use, some prefer the full syntax finding it to be clearer. Others prefer the missing syntax because it results in shorter code. I think that what’s more important than whether to use the full or missing syntax is to be consistent between the members of the development team. When different people use different styles, it can be hard to maintain each other’s code. A good idea is to have meetings to discuss styling choices like full versus missing syntax, indentation, casing, and so on, and to come up with a coding style document that everyone must follow. Sometimes people have strong opinions about certain styling aspects based on their personal preferences, so when conflicts arise you can vote to determine which option will prevail. Once everyone starts using a consistent style, it becomes so much easier for different people to maintain the same code.

Outer join

From a logical query-processing perspective, outer joins start with the same two steps as inner joins. But in addition, they have a third logical step that ensures that all rows from the table or tables that you mark as preserved are returned, even if they don’t have any matches in the other table based on the join predicate. Using the keywords LEFT (or LEFT OUTER), RIGHT, or FULL, you mark the left table, right table, or both tables as preserved. Output rows representing nonmatches (aka outer rows) have NULLs used as placeholders in the nonpreserved side’s columns.

As an example, the following query returns customers and their orders, including customers with no orders:

SELECT C.custid, C.companyname, C.country,
O.orderid, O.shipcountry
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
ON C.custid = O.custid;

In outer joins, the role of the predicate in the ON clause is different than in inner joins. With the latter, it serves as a simple filtering tool, whereas with the former it serves as a more sophisticated matching tool. All rows from the preserved side will be returned whether they find matching rows based on the predicate or not. If you need any simple filters to be applied, you specify those in the WHERE clause. For example, a classic way to identify only nonmatches is to use an outer join and add a WHERE clause that filters only the rows that have a NULL in a column from the nonpreserved side that doesn’t allow NULLs normally. The primary key column is a good choice for this purpose. For example, the following query returns only customers who didn’t place orders:

SELECT C.custid, C.companyname, O.orderid
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
ON C.custid = O.custid
WHERE O.orderid IS NULL;

It’s far more common to see people using left outer joins than right outer ones. It could be because most people tend to specify referenced tables before referencing ones in the query, and usually the referenced table is the one that can have rows with no matches in the referencing one. It’s true that in a single join case such as T1 LEFT OUTER JOIN T2 you can express the same thing with a symmetric T2 RIGHT OUTER JOIN T1. However, in certain more complex cases with multiple joins involved, you will find that using a right outer join enables a simpler solution than using left outer joins. I’ll demonstrate such a case shortly in the “Multi-join queries” section.

Self join

A self join is a join between multiple instances of the same table. As an example, the following query matches employees with their managers, who are also employees:

SELECT E.firstname + ' ' + E.lastname AS emp, M.firstname + ' ' + M.lastname AS mgr
FROM HR.Employees AS E
LEFT OUTER JOIN HR.Employees AS M
ON E.mgrid = M.empid;

What’s special about self joins is that it’s mandatory to alias the instances of the table differently; otherwise, you end up with duplicate column names, including the table prefixes.

From an optimization perspective, the optimizer looks at the two instances as two different tables. For example, it can use different indexes for each of the instances. In the query plan, you can identify in each physical object that is accessed which instance it represents based on the table alias you assigned to it.

Equi and non-equi joins

The terms equi joins and non-equi joins refer to the kind of operator you use in the join predicate. When you use an equality operator, like in the vast majority of the queries, the join is referred to as an equi join. When you use an operator other than equality, the join is referred to as a non-equi join.

As an example, the following query uses a non-equi join with a less than (<) operator to identify unique pairs of employees:

SELECT E1.empid, E1.lastname, E1.firstname, E2.empid, E2.lastname, E2.firstname
FROM HR.Employees AS E1
INNER JOIN HR.Employees AS E2
ON E1.empid < E2.empid;

If you’re wondering why you should use a non-equi join here rather than a cross join, that’s because you don’t want to get the self-pairs (same employee x, x on both sides) and you don’t want to get mirrored pairs (x, y and also y, x). If you want to produce unique triples, simply add another non-equi join to a third instance of the table (call it E3), with the join predicate E2.empid < E3.empid.

From an optimization perspective, there’s relevance to identifying the join as an equi or non-equi one. Later, the chapter covers the optimization of joins with the join algorithms nested loop, merge, and hash. Nested loops is the only algorithm supported with non-equi joins. Merge and hash require an equi-join or, more precisely, at least one predicate that is based on an equality operator.

Multi-join queries

Multi-join queries are queries with multiple joins (what a surprise). There are a number of interesting considerations concerning such queries, some optimization related and others related to the logical treatment.

As an example, the following query joins five tables to return customer-supplier pairs that had activity together:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
INNER JOIN Sales.Orders AS O
ON O.custid = C.custid
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid;

The customer company name is obtained from the Customers table. The Customers table is joined with the Orders table to find the headers of the orders that the customers placed. The result is joined with OrderDetails to find the order lines within those orders. The order lines contain the IDs of the products that were ordered. The result is joined with Products, where the IDs of the suppliers of those products are found. Finally, the result is joined with Suppliers to get the supplier company name.

Because the same customer-supplier pair can appear more than once in the result, the query has a DISTINCT clause to eliminate duplicates. Here there was a good reason to use DISTINCT. Note, however, that if you see excessive use of DISTINCT in someone’s join queries, it could indicate that they don’t correctly understand the relationships in the data model. When joining tables based on incorrect relationships, you can end up with duplicates, and the use of DISTINCT in such a case could be an attempt to hide those.

The following sections discuss aspects of the physical and logical processing of this query.

Controlling the physical-join evaluation order

When discussing logical query processing in Chapter 1, I explained that table operators are evaluated from left to right. That’s the case from a logical-processing standpoint. However, from a physical-processing standpoint, under certain conditions the order can be altered without changing the meaning of the query. With outer joins, changing the order can change the meaning, and this is something the optimizer isn’t allowed to do. But with inner and cross joins, changing the order doesn’t change the meaning. So, with those, the optimizer will apply join-ordering optimization. It will explore different join orders and pick the one from those that according to its estimates is supposed to be the fastest.

As an example, our multi-join query got the plan in Figure 3-17, showing that the physical join order is different than the logical one.

FIGURE 3-17 Plan for a multi-join query.

Observe the order in the plan is as follows: Customers join ( Orders join ( ( Suppliers join Products ) join OrderDetails ) ). For illustration purposes, the following query applies logical join ordering that reflects the physical ordering in Figure 3-17:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
INNER JOIN ( Sales.Orders AS O
INNER JOIN ( Production.Suppliers AS S
INNER JOIN Production.Products AS P
ON P.supplierid = S.supplierid
INNER JOIN Sales.OrderDetails AS OD
ON OD.productid = P.productid )
ON OD.orderid = O.orderid )
ON O.custid = C.custid;

There are a number of reasons that could lead the optimizer to choose a suboptimal join order. Like with other suboptimal choices, join ordering choices can be affected by inaccurate cardinality estimates.

Furthermore, the theoretical number of possible join orders, or join trees, can be very large even with a small number of tables. Benjamin Nevarez explains this in “Optimizing Join Orders” here: http://www.benjaminnevarez.com/2010/06/optimizing-join-orders/. With N tables, the number of possible trees is (2N – 2)! / (N – 1)!, where ! is factorial. As an example, in our case we have 5 tables resulting in 1,680 possible trees. With 10 tables, the number is 17,643,225,600! Here the ! is for amazement, not to represent factorial, thank goodness. As you might realize, if the optimizer actually tried to explore all possible join trees, the optimization process would take too long and become counterproductive. So the optimizer does a number of things to reduce the optimization time. It computes cost-based and time-based thresholds based on the sizes of the tables involved, and if one of them is reached, optimization stops. The optimizer also normally doesn’t consider bushy join trees, where results of joins are joined; such trees represent the majority of the trees. What all this means is that the optimizer might not come up with the truly optimal join order.

If you suspect that’s the case and want to force the optimizer to use a certain order, you can do so by typing the joins in the order you think is optimal and adding the FORCE ORDER query hint, like so:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
INNER JOIN Sales.Orders AS O
ON O.custid = C.custid
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid
OPTION (FORCE ORDER);

This hint is certainly good as a troubleshooting tool because you can use it to test the performance of different orders and see if the optimizer, indeed, made a suboptimal choice. The problem with using such a hint in production code is that it makes this part of optimization static. Normally, changes in indexing, data characteristics, and other factors can result in a change in the optimizer’s join ordering choice, but obviously not when the hint is used. So the hint is good to use as a troubleshooting tool and sometimes as a short, temporary solution in production in critical cases. However, it’s usually not good to use as a long-term solution. For example, suppose the cause for the suboptimal join-ordering choice was a bad cardinality estimate. When you have the time to do more thorough research of the problem, I hope you can find ways to help the optimizer come up with more accurate estimates that naturally lead to a more optimal plan.

Controlling the logical-join evaluation order

You just saw how to control physical join ordering. There are also cases where you need to control logical join ordering to achieve a certain change in the meaning of the query. As an example, consider the query that returns customer-supplier pairs from the previous section:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
INNER JOIN Sales.Orders AS O
ON O.custid = C.custid
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid;

This query returns 1,236 rows. All joins in the query are inner joins. This means that customers who didn’t place any orders aren’t returned. There are two such customers in our sample data. Suppose you need to change the solution to include customers without orders. The intuitive thing to do is change the type of join between Customers and Orders to a left outer join, like so:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
ON O.custid = C.custid
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid;

However, if you run the query, you will notice that it still returns the same result as before. Logically, the left outer join between Customers and Orders returns the two customers who didn’t place orders with NULLs in the order attributes. Then when joining the result with OrderDetails using an inner join, those outer rows are eliminated. That’s because when comparing the NULL marks in the O.orderid column in those rows with any OD.orderid value, the result is the logical value unknown. You can generalize this case and say that any left outer join that is subsequently followed by an inner join or a right outer join causes the left outer join to effectively become an inner join. That’s assuming that you compare the NULL elements from the nonpreserved side of the left outer join with elements from another table. In fact, if you look at the execution plan of the query, you will notice that, indeed, the optimizer converted the left outer join to an inner join.

A common way for people to attempt to solve the problem is to make all joins left outer joins, like so:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
ON O.custid = C.custid
LEFT OUTER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
LEFT OUTER JOIN Production.Products AS P
ON P.productid = OD.productid
LEFT OUTER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid;

There are two problems with this solution. One problem is that you actually changed the meaning of the query from the intended one. You were after a left outer join between Customers and the result of the inner joins between the remaining tables. Rows without matches in the remaining tables aren’t supposed to be preserved; however, with this solution, if they are left rows, they will be preserved. The other problem is that the optimizer has less flexibility in altering the join order when dealing with outer joins. Pretty much the only flexibility that it does have is to change T1 LEFT OUTER JOIN T2 to T2 RIGHT OUTER JOIN T1.

A better solution is to start with the inner joins between the tables besides Customers and then to apply a right outer join with Customers, like so:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Orders AS O
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid
RIGHT OUTER JOIN Sales.Customers AS C
ON C.custid = O.custid;

Now the solution is both semantically correct and leaves more flexibility to the optimizer to apply join-ordering optimization. This query returns 1,238 rows, which include the two customers who didn’t place orders.

There’s an even more elegant solution that allows you to express the joins in a manner similar to the way you think of the task. Remember you want to apply a left outer join between Customers and a unit representing the result of the inner joins between the remaining tables. To define such a unit, simply enclose the inner joins in parentheses and move the join predicate that relates Customers and that unit after the parentheses, like so:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
LEFT OUTER JOIN
( Sales.Orders AS O
INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid
INNER JOIN Production.Products AS P
ON P.productid = OD.productid
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid)
ON O.custid = C.custid;

Curiously, the parentheses are not really required. If you remove them and run the code, you will see it runs successfully and returns the correct result. What really makes the difference is the parentheses-like arrangement of the units and the placement of the ON clauses reflecting this arrangement. Simply make sure that the ON clause that is supposed to relate two units appears right after them; otherwise, the query will not be a valid one. With this in mind, following is another valid arrangement of the units, achieving the desired result for our task:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
INNER JOIN Sales.OrderDetails AS OD
INNER JOIN Production.Products AS P
INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid
ON P.productid = OD.productid
ON OD.orderid = O.orderid
ON O.custid = C.custid;

I find that using parentheses accompanied with adequate indentation results in much clearer code, so I recommend using them even though they are not required.

Earlier I mentioned that one of the heuristics the optimizer uses to reduce optimization time is to not consider bushy plans that involve joins between results of joins. If you suspect that such a bushy plan is the most efficient and want the optimizer to use it, you need to force it. The way you achieve this is by defining two units, each based on a join with the respective ON clause, followed by an ON clause that relates the two units. You also need to specify the FORCE ORDER query option.

Following is an example of forcing such a bushy plan:

SELECT DISTINCT C.companyname AS customer, S.companyname AS supplier
FROM Sales.Customers AS C
INNER JOIN
(Sales.Orders AS O INNER JOIN Sales.OrderDetails AS OD
ON OD.orderid = O.orderid)
INNER JOIN
(Production.Products AS P INNER JOIN Production.Suppliers AS S
ON S.supplierid = P.supplierid)
ON P.productid = OD.productid
ON O.custid = C.custid
OPTION (FORCE ORDER);

Here you have one unit (call it U1) based on a join between Orders and OrderDetails. You have another unit (call it U2) based on a join between Products and Suppliers. Then you have a join between the two units (call the result U1-2). Then you have a join between Customers and U1-2. The execution plan for this query is shown in Figure 3-18.

FIGURE 3-18 Bushy plan.

Observe that the desired bushy layout was achieved in the plan.

Semi and anti semi joins

Normally, a join matches rows from two tables and returns elements from both sides. What makes a join a semi join is that you return elements from only one of the sides. The side you return the elements from determines whether it’s a left or right semi join.

As an example, consider a request to return the customer ID and company name of customers who placed orders. You return information only from the Customers table, provided that a matching row is found in the Orders table. Considering the Customers table as the left table, the operation is a left semi join. There are a number of ways to implement the task. One is to use an inner join and apply a DISTINCT clause to remove duplicate customer info, like so:

SELECT DISTINCT C.custid, C.companyname
FROM Sales.Customers AS C
INNER JOIN Sales.Orders AS O
ON O.custid = C.custid;

Another is to use the EXISTS predicate, like so:

SELECT custid, companyname
FROM Sales.Customers AS C
WHERE EXISTS(SELECT *
FROM Sales.Orders AS O
WHERE O.custid = C.custid);

Both queries get the same plan. Of course, there are more ways to achieve the task.

An anti semi join is one in which you return elements from one table if a matching row cannot be found in a related table. Also here, depending on whether you return information from the left table or the right one, the join is either a left or right anti semi join. As an example, a request to return customers who did not place orders is fulfilled with a left anti semi join operation.

There are a number of classic ways to achieve such an anti semi join. One is to use a left outer join between Customers and Orders and filter only outer rows, like so:

SELECT C.custid, C.companyname
FROM Sales.Customers AS C
LEFT OUTER JOIN Sales.Orders AS O
ON O.custid = C.custid
WHERE O.orderid IS NULL;

Another is to use the NOT EXISTS predicate, like so:

SELECT custid, companyname
FROM Sales.Customers AS C
WHERE NOT EXISTS(SELECT *
FROM Sales.Orders AS O
WHERE O.custid = C.custid);

Curiously, it appears that currently the optimizer doesn’t have logic to detect the outer join solution as actually applying an anti semi join, but it does with the NOT EXISTS solution. This can be seen in the execution plans for these queries shown in Figure 3-19.

FIGURE 3-19 Plans for anti semi join solutions.

Of course, there are a number of additional ways to implement anti semi joins. The ones I showed are two classic ones.

Join algorithms

Join algorithms are the physical join strategies SQL Server uses to process joins. SQL Server supports three join algorithms: nested loops, merge, and hash. Nested loops is the oldest of the three algorithms and the fallback when the others can’t be used. For example, cross join can be processed only with nested loops. Merge and hash require the join to be an equi join or, more precisely, to have at least one join predicate that is based on an equality operator.

In the graphical query plan, the join operator has a distinct icon for each algorithm. In addition, the Physical Operation property indicates the join algorithm (Nested Loops, Hash Match, or Merge Join), and the Logical Operation property indicates the logical join type (Inner Join, Left Outer Join, Left Anti Semi Join, and so on). Also, the physical algorithm name appears right below the operator, and the logical join type appears below the algorithm name in parentheses.

The following sections describe the individual join algorithms, the circumstances in which they tend to be efficient, and indexing guidelines to support them.

Nested loops

The nested loops algorithm is pretty straightforward. It executes the outer (top) input only once and, using a loop, it executes the inner (bottom) input for each row from the outer input to identify matches.

Nested loops tends to perform well when the outer input is small and the inner input has an index with the key list based on the join column plus any additional filtered columns, if relevant. Whether it’s critical for the index to be a covering one depends on how many matches you get in total. If the total number of matches is small, a few lookups are not too expensive and therefore the index doesn’t have to be a covering one. If the number of matches is large, the lookups become expensive, and then it becomes more critical to avoid them by making the index a covering one.

As an example, consider the following query:

USE PerformanceV3;

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER JOIN dbo.Orders AS O
ON O.custid = C.custid
WHERE C.custname LIKE 'Cust_1000%'
AND O.orderdate >= '20140101'
AND O.orderdate < '20140401';

Currently, the tables don’t have good indexing to support an efficient nested loops join. Because the smaller side (Customers, in our case) is usually used as the outer input and is executed only once, it’s not that critical to support it with a good index. In the worst case, the small table gets fully scanned. The far more critical index here is on the bigger side (Orders, in our case). Nevertheless, if you want to avoid a full scan of the Customers table, you can prepare an index on the filtered column custname as the key and include the custid column for coverage. As for the ideal index on the Orders table, think of the work involved in a single iteration of the loop for some customer X. It’s like submitting the following query:

SELECT orderid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE custid = X
AND orderdate >= '20140101'
AND orderdate < '20140401';

Because you have one equality predicate and one range predicate, it’s quite straightforward to come up with an ideal index here. You define the index with the key list based on custid and orderdate, and you include the remaining columns (orderid, empid, and shipperid) for coverage. Remember the discussions about multiple range predicates in Chapter 2? When you have both an equality predicate and a range predicate, you need to define the index key list with the equality column first. This way, qualifying rows will appear in a consecutive range in the index leaf. That’s not going to be the case if you define the key list with the range column first.

Run the following code to create optimal indexing for our query:

CREATE INDEX idx_nc_cn_i_cid ON dbo.Customers(custname) INCLUDE(custid);

CREATE INDEX idx_nc_cid_od_i_oid_eid_sid
ON dbo.Orders(custid, orderdate) INCLUDE(orderid, empid, shipperid);

Now run the query and examine the query plan shown in Figure 3-20.

FIGURE 3-20 Plan with a nested loops algorithm.

As you can see, the optimizer chose to use the nested loops algorithm with the smaller table, Customers, as the outer input and the bigger table, Orders, as the inner input. The plan performs a seek and a range scan in the covering index on Customers to retrieve qualifying customers. (There are 11 in our case.) Then, using a loop, the plan performs for each customer a seek and a range scan in the covering index on Orders to retrieve matching orders for the current customer. There are 30 matching orders in total.

Next, I’ll discuss the effects that different changes to the query will have on its optimization.

As mentioned, if you have a small number of matches in total, it’s not that critical for the index on the inner table to be a covering one. You can test such a case by adding O.filler to the query’s SELECT list. The plan will still use the nested loops algorithm, but it will add key lookups to retrieve the column filler from the clustered index because it’s not part of the index idx_nc_cid_od_i_oid_eid_sid. When you’re done testing, make sure you remove the column O.filler from the query before applying the next change.

When enough rows are returned from the outer input, the optimizer usually applies a prefetch (a read-ahead) to speed up the executions of inner input. Usually, the optimizer considers a prefetch when it estimates that more than a couple of dozen rows will be returned from the outer input. The plan for our current query doesn’t involve a prefetch because the optimizer estimates that only a few rows will be returned from Customers. But if you change the query filter against Customers from C.custname LIKE ‘Cust_1000%’ to C.custname LIKE ‘Cust_100%’, it will use a prefetch. After applying the change, you will find that the Nested Loops operator has a property called WithUnorderedPrefetch, which is set to True. The reason it’s an unordered prefetch is that there’s no relevance to returning the rows sorted by the customer IDs. If you add ORDER BY custid to the query, the property will change to WithOrderedPrefetch. When you’re done testing, make sure to revert back to the original query before applying the next change.

I mentioned that the Nested Loops operator is usually efficient when the outer input is small. Change the filter against Customers to C.custname LIKE ‘Cust_10%’. Now the estimated number of matches from Customers increases from just a few to over a thousand, and the optimizer changes its choice of the join algorithm to hash.

There’s an interesting technique the optimizer can use when the plan is a parallel one but there are only a few outer rows. In such a case, without optimizer intervention the work could be unevenly distributed to the different threads. Therefore, when the optimizer detects a case of a few outer rows, it adds a Redistribute Streams operator after obtaining the rows from the outer input. This operator redistributes the rows between the threads more evenly.

Merge

The merge algorithm requires both inputs to be sorted by the join column. It then merges the two like a zipper. If the join is a one-to-many one, as is likely to be the case in most queries, there’s only one pass over each input. If the join type is a many-to-many one, one input is scanned once and the other involves rewinds.

Generally, there are two ways for the optimizer to get a sorted input. If the data is already sorted in an index, the optimizer can use an index order scan. The other way is by adding an explicit sort operation to the plan, but then there’s the extra cost that is associated with sorting.

Consider the following query as an example of obtaining sorted data from indexes:

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER JOIN dbo.Orders AS O
ON O.custid = C.custid;

The PK_Customers index on the Customers table is a clustered index defined on custid as the key. So the data from Customers is covered by the index and sorted like the merge join algorithm requires. The nonclustered index idx_nc_cid_od_i_oid_eid_sid on Orders that you created for the example in the “Nested loops” section is quite efficient for a merge join. It has the data sorted by custid as the leading key, and it covers the elements in the query from Orders. The conditions are optimal for a merge join algorithm; therefore, the optimizer uses this strategy, as you can see in the plan for our query shown in Figure 3-21.

FIGURE 3-21 Plan with a merge algorithm.

As an example for a merge join involving explicit sorting, consider the following query:

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER JOIN dbo.Orders AS O
ON O.custid = C.custid
WHERE O.orderdate >= '20140101'
AND O.orderdate < '20140102';

The data can be obtained sorted by custid from the clustered index on the Customers table. However, with the extra range filter against Orders, it’s impossible to create an index that sorts the data primarily by both orderdate to support the filter and custid to support a merge join. Still, the date range filter is selective—there are only a few hundred qualifying rows. Furthermore, the clustered index on Orders is defined with orderdate as the key. So the optimizer figures that it can use a seek and a range scan against the clustered index on Orders to retrieve the qualifying orders, and then with an explicit sort operation order the rows by custid. With a small number of rows, the cost of sorting is quite low. The plan for our query, indeed, implements this strategy as you can see in Figure 3-22.

FIGURE 3-22 Plan with a sort operator and merge algorithm.

Observe the small cost percent associated with the sort operation.

Note that such a plan is sensitive to inaccuracies in the cardinality estimate of the activity leading to the Sort operator. That’s especially the case when the estimate is for a small number of rows but the actual is a large number, because sorting doesn’t scale well. For one, a more accurate estimate could lead the optimizer to use a different join algorithm altogether. For two, the low estimate could result in an insufficient memory grant for the sort activity, and this could result in spills to tempdb. You need to be attentive to such problems and, if you spot one, try to figure out ways to help the optimizer come up with a more accurate estimate.

Hash

The hash algorithm involves the creation of a hash table based on one of the inputs—usually the smaller. The reason that the small side is preferred as the build input is that the memory footprint is usually smaller this way. If the hash table fits in memory, it’s ideal. If not, the hash table can be partitioned, but the swapping of partitions in and out of memory makes the algorithm less efficient. The items from the build input are arranged in hash buckets based on the chosen hash function. For illustration purposes, suppose that the join column is an integer one and the optimizer chooses a modulo 50 function as the hash function. Up to 50 hash buckets will be created, with all items that got the same result from the hash function organized in a linked list in the same bucket. Then the other input (known as the probe input) is probed, the hash function is applied to the join column values, and based on the result, the algorithm scans the respective hash bucket to look for matches.

The hash algorithm excels in data-warehouse queries, which tend to involve large amounts of data in the fact table and much smaller dimension tables. It tends to scale well with such queries, benefiting greatly from parallelized processing. Note, though, that the hash table requires a memory grant, and hence this algorithm is sensitive to inaccuracies with cardinality estimates. If there’s an insufficient memory grant, the hash table will spill to tempdb, and this results in less efficient processing.

When using columnstore indexes, the hash algorithm can use batch-execution mode, which is described in Chapter 2. In SQL Server 2012, only inner joins processed with a hash algorithm could use batch execution. Also, if the operator spilled to tempdb, the execution mode switched to row mode. In SQL Server 2014, outer joins processed with a hash algorithm can use batch execution, and so do operators that spill to tempdb.

Besides the classic data warehouse queries, there’s another interesting case where the optimizer tends to choose the hash algorithm—when there aren’t good indexes to support the other algorithms. If you think about it, a hash table is an alternative searching structure to a B-tree. When there are no good existing indexes, it is usually more efficient overall to create a hash table, use it, and drop it in every query execution compared to doing the same thing with a B-tree. As an example, run the following code to drop the two indexes you created earlier to support previous examples:

DROP INDEX idx_nc_cn_i_cid ON dbo.Customers;
DROP INDEX idx_nc_cid_od_i_oid_eid_sid ON dbo.Orders;

Then run the same query you ran earlier in the “Nested loops” section:

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER JOIN dbo.Orders AS O
ON O.custid = C.custid
WHERE C.custname LIKE 'Cust_1000%'
AND O.orderdate >= '20140101'
AND O.orderdate < '20140401';

This time, as a result of the absence of efficient indexes to support a nested loops algorithm, the optimizer chooses to use a hash join with a hash table based on the qualifying customers. The plan for this query is shown in Figure 3-23.

FIGURE 3-23 Plan with a hash algorithm.

So, when you see the optimizer using a hash join in cases where it doesn’t seem natural, ask yourself if you’re missing important indexes—especially if the query is a frequent one in the system.

Forcing join strategy

If you suspect that the optimizer chose a suboptimal join algorithm, you can try a couple of methods for forcing the one you think is more optimal. One is using a join hint where you specify the join algorithm (LOOP, MERGE, or HASH) right before the JOIN keyword, using the full join syntax (INNER <hint> JOIN, LEFT OUTER <hint> JOIN, and so on). Here’s an example for forcing a nested loops algorithm:

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER LOOP JOIN dbo.Orders AS O
ON O.custid = C.custid;

Note that with this method you also force the join order. The left table is used as the outer input, and the right table is used as the inner one.

Another method is to use query hints in the query OPTION clause. The advantage of this method is that you can specify more than one algorithm. Because there are only three supported algorithms, by listing two you are excluding the third. For example, suppose you want to prevent the optimizer from choosing the merge algorithm but you want to leave it with some flexibility to choose between nested loops and hash. You achieve this like so:

SELECT C.custid, C.custname, O.orderid, O.empid, O.shipperid, O.orderdate
FROM dbo.Customers AS C
INNER JOIN dbo.Orders AS O
ON O.custid = C.custid
OPTION(LOOP JOIN, HASH JOIN);

Note, though, that by using this method, all joins in the query are affected. There is no form of a hint that I know of that allows indicating more than one algorithm for a single join. Also note that, unlike the join hint, the query hints for join algorithms don’t affect join ordering. If you want to force the join order, you need to add the FORCE ORDER query hint.

Remember the usual disclaimer concerning performance hints. Such hints are handy as a performance troubleshooting tool; however, using them in production queries removes the dynamic nature of optimization that can normally react to changing circumstances by changing optimization choices. If you do find yourself using such hints in production code to solve critical burning problems, you should consider them a temporary solution. When you have the time, you can more thoroughly research the problem and find a fix that will help the optimizer naturally make more optimal choices.

Separating elements

Separating elements is a classic T-SQL challenge. It involves a table called Arrays with strings holding comma-separated lists of values in a column called arr. Run the following code to create the Arrays table, and populate it with sample data:

SET NOCOUNT ON;
USE tempdb;

IF OBJECT_ID(N'dbo.Arrays', N'U') IS NOT NULL DROP TABLE dbo.Arrays;

CREATE TABLE dbo.Arrays
(
id VARCHAR(10) NOT NULL PRIMARY KEY,
arr VARCHAR(8000) NOT NULL
);
GO

INSERT INTO dbo.Arrays VALUES('A', '20,223,2544,25567,14');
INSERT INTO dbo.Arrays VALUES('B', '30,-23433,28');
INSERT INTO dbo.Arrays VALUES('C', '12,10,8099,12,1200,13,12,14,10,9');
INSERT INTO dbo.Arrays VALUES('D', '-4,-6,-45678,-2');

The challenge is to come up with an efficient solution in T-SQL that splits each string into the individual elements, returned in separate rows along with the id, the position, and the element itself. The desired result looks like the following.

id pos element
---- ---- --------
A 1 20
A 2 223
A 3 2544
A 4 25567
A 5 14
B 1 30
B 2 -23433
B 3 28
...

Note that this task can be solved using .NET more efficiently than with T-SQL—either by using the System.String.Split method or by implementing your own iterative solution. However, our challenge is to implement an efficient solution using T-SQL.

One intuitive approach is to implement an iterative solution as a table function operating on a single string and a separator as inputs and returning a table variable. The function would extract one element in each iteration and insert it into the result table variable. The problem with this approach is that iterative solutions in T-SQL tend to be inefficient.

The challenge, therefore, is to find an efficient set-based solution using T-SQL. To implement such a solution, you will want to split the task into three steps:

1. Generate copies.

2. Extract an element.

3. Calculate the position.

The first step is to generate copies from the original rows—as many as the number of elements in the string. The second step is to extract the relevant element from each copy. The third step is to compute the ordinal position of the element within the string.

For the first step, you will find the auxiliary table Nums from the TSQLV3 database very handy. This table has a column called n that holds a sequence of integers starting with 1. You can think of the numbers as representing character positions in the string. Namely, n = 1 represents character position 1, n = 2 represents character position 2, and so on. To generate copies, you join Arrays and Nums. As the join predicate, use the following expression, which says that the nth character is a comma: SUBSTRING(arr, n, 1) = ‘,’. To avoid extracting a character beyond the end of the string, limit the numbers to the length of the string with the predicate n <= LEN(arr). Here’s the code implementing this logic:

SELECT id, arr, n
FROM dbo.Arrays
INNER JOIN TSQLV3.dbo.Nums
ON n <= LEN(arr)
AND SUBSTRING(arr, n, 1) = ',';

This code generates the following output:

id arr n
----- --------------------- ----
A 20,223,2544,25567,14 3
A 20,223,2544,25567,14 7
A 20,223,2544,25567,14 12
A 20,223,2544,25567,14 18
B 30,-23433,28 3
B 30,-23433,28 10
...

Observe that the output is missing one copy for each string. The reason is that, for a string with X elements, there are X – 1 separators. If you think of the separators as preceding the elements, what’s missing is the separator before the first element. To fix this problem, simply plant a separator at the beginning of the string and pass the result as the first input to the SUBSTRING function. Also, make sure you increase the limit of the number of characters you extract by one to account for the extra character. After these two modifications, the query looks like this:

SELECT id, arr, n
FROM dbo.Arrays
INNER JOIN TSQLV3.dbo.Nums
ON n <= LEN(arr) + 1
AND SUBSTRING(',' + arr, n, 1) = ',';

This query generates the following output:

id arr n
---- --------------------- ----
A 20,223,2544,25567,14 1
A 20,223,2544,25567,14 4
A 20,223,2544,25567,14 8
A 20,223,2544,25567,14 13
A 20,223,2544,25567,14 19
B 30,-23433,28 1
B 30,-23433,28 4
B 30,-23433,28 11
...

This time, you get the right number of copies. In addition, observe that the modifications to the query had an interesting side effect; the character positions where a separator was found increased by one because the whole string shifted one character to the right. This side effect is actually convenient for us because with respect to the original string (without the separator at the beginning), n actually already represents the starting position of the element. So the first step in the solution for the task is accomplished.

The second step is to extract the element that the current copy represents. For this, you will use the SUBSTRING function. You need to pass the string, the starting position, and the length to extract as inputs. You know that the element starts at position n. For the length, you will need to find the position of the next separator and subtract n from it. You can use the CHARINDEX function for this purpose. The first two inputs are the separator you’re looking for and the string where you are looking for it. As the third input, specify n as the starting position to look for the separator. You get the following: CHARINDEX(‘,’, arr, n). The tricky thing here is that there’s no separator after the last element; in such a case, the function returns a 0. To fix this problem, plant a separator at the end of the string, like so: CHARINDEX(‘,’, arr + ‘,’, n). The complete expression extracting the element then becomes: SUBSTRING(arr, n, CHARINDEX(‘,’, arr + ‘,’, n) – n).

The third and last step in the solution is to compute the ordinal position of the element in the string. For this purpose, use the ROW_NUMBER function, partitioned by id and ordered by n.

Here’s the complete solution query:

SELECT id,
ROW_NUMBER() OVER(PARTITION BY id ORDER BY n) AS pos,
SUBSTRING(arr, n, CHARINDEX(',', arr + ',', n) - n) AS element
FROM dbo.Arrays
INNER JOIN TSQLV3.dbo.Nums
ON n <= LEN(arr) + 1
AND SUBSTRING(',' + arr, n, 1) = ',';

If you need to deal with individual input strings, you can encapsulate this logic in an inline table function, like so:

CREATE FUNCTION dbo.Split(@arr AS VARCHAR(8000), @sep AS CHAR(1)) RETURNS TABLE
AS
RETURN
SELECT
ROW_NUMBER() OVER(ORDER BY n) AS pos,
SUBSTRING(@arr, n, CHARINDEX(@sep, @arr + @sep, n) - n) AS element
FROM TSQLV3.dbo.Nums
WHERE n <= LEN(@arr) + 1
AND SUBSTRING(@sep + @arr, n, 1) = @sep;
GO

It’s the same logic, only it operates on a single string instead of a whole table of strings.

As an example, suppose you have a string holding a comma-separated list of order IDs. To split those into a table of elements, use the Split function, like so:

SELECT * FROM dbo.Split('10248,10249,10250', ',') AS S;

You get the following output:

pos element
---- --------
1 10248
2 10249
3 10250

To return further information about the orders in the input string, join the table returned by the function with the Orders table like so:

SELECT O.orderid, O.orderdate, O.custid, O.empid
FROM dbo.Split('10248,10249,10250', ',') AS S
INNER JOIN TSQLV3.Sales.Orders AS O
ON O.orderid = S.element
ORDER BY S.pos;

Observe that the query orders the rows by the ordinal position of the element in the input string. This query generates the following output:

orderid orderdate custid empid
----------- ---------- ----------- -----------
10248 2013-07-04 85 5
10249 2013-07-05 79 6
10250 2013-07-08 34 4

There’s an excellent set of papers written by SQL Server MVP Erland Sommarskog covering the topic of arrays and lists in great depth. You can find those papers here: http://www.sommarskog.se/arrays-in-sql.html.

The UNION, EXCEPT, and INTERSECT operators

The UNION, EXCEPT, and INTERSECT operators are relational operators that combine rows from the result sets of two queries. The general form of code using these operators is shown here:

<query 1>
<operator>
<query 2>
[ORDER BY <order_by_list>];

The UNION operator unifies the rows from the two inputs. The INTERSECT operator returns only the rows that are common to both inputs. The EXCEPT operator returns the rows that appear in the first input but not the second.

The input queries are not allowed to have an ORDER BY clause because they are supposed to return a relational result. However, an ORDER BY clause is allowed against the result of the operator.

The schemas of the input queries need to be compatible. The number of columns has to be the same, and the types need to be implicitly convertible from the one with the lower data type precedence to the higher. The names of the result columns are defined by the first query.

When comparing rows between the inputs, these operators implicitly use the standard distinct predicate. Based on this predicate, one NULL is not distinct from another NULL, and a NULL is distinct from a non-NULL value. Conversely, based on the equality operator, comparing two NULLs results in the logical value unknown, and the same applies when comparing a NULL with a non-NULL value. This fact makes these operators simple and intuitive to use, even when NULLs are possible in the data.

When multiple operators are used in a query without parentheses, INTERSECT precedes UNION and EXCEPT. The last two have the same precedence, so they are evaluated based on appearance order. You can always force your desired evaluation order using parentheses.

The following sections provide more details about these operators.

The UNION ALL and UNION operators

The UNION operator unifies the rows from the two inputs. Figure 3-24 illustrates graphically what the operator does. It shows the result of the operator with a darker background.

FIGURE 3-24 The UNION operator.

T-SQL supports two variations of the UNION operator: UNION (implied DISTINCT) and UNION ALL. Both unify the rows from the two inputs, but only the former removes duplicates from the result; the latter doesn’t. Standard SQL actually supports the explicit form UNION DISTINCT for the former, but T-SQL supports only the implied form.

As an example for UNION, the following code returns distinct unified employee and customer locations:

USE TSQLV3;

SELECT country, region, city FROM HR.Employees
UNION
SELECT country, region, city FROM Sales.Customers;

This query returns 71 distinct locations.

If you want to keep duplicates, use the UNION ALL variation, like so:

SELECT country, region, city FROM HR.Employees
UNION ALL
SELECT country, region, city FROM Sales.Customers;

This query returns 100 rows because it unifies 9 employee rows with 91 customer rows. Usually, it’s not meaningful to return a result with duplicates, but it could be that you need to apply some further logic against the result. For instance, suppose you need to count how many employees plus customers there are in each location. For this, you define a table expression based on the code with the UNION ALL operator and apply the grouping and aggregation in the outer query.

In terms of performance, UNION is usually more expensive than UNION ALL because it involves an extra step that removes duplicates. Figure 3-25 shows the plans for the last UNION and UNION ALL queries demonstrating this.

FIGURE 3-25 UNION versus UNION ALL.

The plan for the UNION query uses a Sort (Distinct Sort) operator to remove duplicates. Another option is to use a hash-based algorithm for this purpose. Either way, you can see that there’s more work involved than with the UNION ALL query.

When you unify disjoint inputs, such as data for different years that includes a date column, UNION and UNION ALL become logically equivalent. Unfortunately, many use the UNION operator in such a case because the code involves fewer keystrokes, not realizing the unnecessary extra work taking place. So it’s important to use the UNION ALL operator as your default and reserve the UNION operator only for cases where the result can have duplicates and you need to remove them.

Interestingly, if you use UNION to unify rows from tables and those tables have CHECK constraints defining disjoint intervals, the optimizer can detect this and help you avoid the extra work of removing duplicates. As an example, the following code creates separate tables to store data for different years, with CHECK constraints enforcing the disjoint year intervals:

USE tempdb;
IF OBJECT_ID(N'dbo.T2014', N'U') IS NOT NULL DROP TABLE dbo.T2014;
IF OBJECT_ID(N'dbo.T2015', N'U') IS NOT NULL DROP TABLE dbo.T2015;
GO
CREATE TABLE dbo.T2014
(
keycol INT NOT NULL CONSTRAINT PK_T2014 PRIMARY KEY,
dt DATE NOT NULL CONSTRAINT CHK_T2014_dt CHECK(dt >= '20140101' AND dt < '20150101')
);

CREATE TABLE dbo.T2015
(
keycol INT NOT NULL CONSTRAINT PK_T2015 PRIMARY KEY,
dt DATE NOT NULL CONSTRAINT CHK_T2015_dt CHECK(dt >= '20150101' AND dt < '20160101')
);

Ignoring best practices, you use the following code to unify the rows from the tables with the UNION operator:

SELECT keycol, dt FROM dbo.T2014
UNION
SELECT keycol, dt FROM dbo.T2015;

Fortunately, thanks to the existence of the constraints, the optimizer figures that duplicates cannot exist in the result and therefore optimizes this query the same as it would UNION ALL. The plan for this query is shown in Figure 3-26.

FIGURE 3-26 UNION and CHECK constraints.

It’s still recommended to follow the best practice and stick with UNION ALL as your default for the sake of cases where the optimizer won’t figure out that the inputs are disjoint.

When you’re done testing, run the following code for cleanup:

IF OBJECT_ID(N'dbo.T2014', N'U') IS NOT NULL DROP TABLE dbo.T2014;
IF OBJECT_ID(N'dbo.T2015', N'U') IS NOT NULL DROP TABLE dbo.T2015;

The INTERSECT operator

The INTERSECT operator returns only distinct rows that are common to both inputs. Figure 3-27 illustrates graphically what this operator returns.

FIGURE 3-27 The INTERSECT operator.

As an example, the following query returns locations that are both employee locations and customer locations:

USE TSQLV3;

SELECT country, region, city FROM HR.Employees
INTERSECT
SELECT country, region, city FROM Sales.Customers;

This query generates the following output:

country region city
--------------- --------------- ---------------
UK NULL London
USA WA Kirkland
USA WA Seattle

Observe in the output that the row with UK, NULL, London was returned because there are both employees and customers in this location. Because the operator uses the distinct predicate implicitly to compare rows, when comparing the NULLs on both sides, it got true and not unknown. If you want to implement the intersection operation with an inner join, you need to add special logic for NULL treatment (with Employees aliased as E and Customers as C):

E.region = C.region OR E.region IS NULL AND C.region IS NULL

Like the UNION operator, INTERSECT returns distinct rows. If a row appears at least once in each of the inputs, it’s returned once in the output. Interestingly, standard SQL supports an operator called INTERSECT ALL, which returns as many occurrences of a row in the result as the minimum number of occurrences between the two inputs. Say that a row R appears X times in the first input and Y times in the second input, the INTERSECT ALL operator returns the row MIN(X, Y) times in the output. It’s as if the operator looks for a separate match for each row. So if you have four occurrences of R in one input and six in the other, you will get R four times in the output.

T-SQL doesn’t support the standard INTERSECT ALL operator, but it’s quite easy to implement your own solution. You achieve this by adding row numbers to both input queries, marking duplicate numbers. You apply the supported INTERSECT operator to the queries with the row numbers. You then define a CTE based on the intersection code, and then in the outer query return the attributes without the row numbers. Here’s the complete solution code:

WITH INTERSECT_ALL
AS
(
SELECT
ROW_NUMBER()
OVER(PARTITION BY country, region, city
ORDER BY (SELECT 0)) AS rn,
country, region, city
FROM HR.Employees

INTERSECT

SELECT
ROW_NUMBER()
OVER(PARTITION BY country, region, city
ORDER BY (SELECT 0)) AS rn,
country, region, city
FROM Sales.Customers
)
SELECT country, region, city
FROM INTERSECT_ALL;

This code generates the following output:

country region city
--------------- --------------- ---------------
UK NULL London
USA WA Kirkland
USA WA Seattle
UK NULL London
UK NULL London
UK NULL London

There are four employees from UK, NULL, London and six customers; doing one-to-one matching, four of them intersect. Therefore, the result has four occurrences of the row.

The EXCEPT operator

The EXCEPT operator returns only distinct rows that appear in the first input but not the second. Figure 3-28 illustrates graphically what this operator returns.

FIGURE 3-28 The EXCEPT operator.

As an example, the following code returns distinct employee locations that are not customer locations:

SELECT country, region, city FROM HR.Employees
EXCEPT
SELECT country, region, city FROM Sales.Customers;

This query generates the following output:

country region city
--------------- --------------- ---------------
USA WA Redmond
USA WA Tacoma

In terms of optimization, like with NOT EXISTS, also with EXCEPT the optimizer can detect that the logical operation is an anti semi join. You can see this if you examine the execution plan for this query.

As it does with INTERSECT ALL, standard SQL supports an operator called EXCEPT ALL, which wasn’t implemented in T-SQL. If a row R appears X times in the first input and Y times in the second input, and X is greater than Y, the operator returns the row X – Y times in the output. The logic behind this is that it’s as if you’re looking for a match for each of the rows and then return only the nonmatches.

To implement your own solution for EXCEPT ALL, you use the same technique you used for INTERSECT ALL. Namely, compute row numbers, marking duplicate numbers in both input queries, and then use the EXCEPT operator. Only the rows from the first input with row numbers that don’t have matches in the second input will be returned. You then define a CTE based on the code with the EXCEPT operator, and in the outer query you return the attributes without the row numbers. Here’s the complete solution code:

WITH EXCEPT_ALL
AS
(
SELECT
ROW_NUMBER()
OVER(PARTITION BY country, region, city
ORDER BY (SELECT 0)) AS rn,
country, region, city
FROM HR.Employees

EXCEPT

SELECT
ROW_NUMBER()
OVER(PARTITION BY country, region, city
ORDER BY (SELECT 0)) AS rn,
country, region, city
FROM Sales.Customers
)
SELECT country, region, city
FROM EXCEPT_ALL;

This code generates the following output:

country region city
--------------- --------------- ---------------
USA WA Redmond
USA WA Tacoma
USA WA Seattle

USA, NULL, Seattle appears twice in Employees and once in Customers; therefore, it is returned once in the output.

As a tip, recall the discussion about finding an efficient solution for the minimum missing value problem earlier in the section “The EXISTS predicate.” Here’s a much simpler and highly efficient solution for the same task using the EXCEPT operator:

SELECT TOP (1) missingval
FROM (SELECT col1 + 1 AS missingval FROM dbo.T1
EXCEPT
SELECT col1 FROM dbo.T1) AS D
ORDER BY missingval;

As with the previously discussed efficient solutions, here also the optimizer uses a Top operator that short-circuits the scans as soon as the first missing value is found.

Conclusion

This chapter covered a lot of ground discussing different tools you use to combine data from multiple tables. It covered subqueries, table expressions, the powerful APPLY operator, joins, and the relational operators UNION, EXCEPT, and INTERSECT. The chapter described both logical considerations for using these tools as well as how to use them optimally.