UNION ALL Optimization

UNION ALL Optimization

The following examples use two tables with identical contents: A million rows of integers from one to a million. One table is a heap with no nonclustered indexes; the other has a unique clustered index:

No Row Goal

The following query looks for the same rows in each table, and returns the concatenation of the two sets:

The execution plan produced by the query optimizer is:

UNION ALL without a row goal

The warning on the root SELECT operator is alerting us to the obvious missing index on the heap table. The warning on the Table Scan operator is added by Sentry One Plan Explorer. It is drawing our attention to the I/O cost of the residual predicate hidden within the scan.

The order of the inputs to the Concatenation does not matter here, because we have not set a row goal. Both inputs will be fully read to return all result rows. Of interest (though this is not guaranteed) notice that the order of the inputs follows the textual order of the original query. Observe also that the order of the final result rows is not specified either, since we did not use a top-level ORDER BY clause. We will assume that is deliberate and final ordering is inconsequential to the task at hand.

If we reverse the written order of the tables in the query like so:

The execution plan follows the change, accessing the clustered table first (again, this is not guaranteed):

UNION ALL with reversed inputs

Both queries may be expected to have the same performance characteristics, as they perform the same operations, just in a different order.

With a Row Goal

Clearly, the lack of indexing on the heap table will normally make finding specific rows more expensive, compared with the same operation on the clustered table. If we ask the optimizer for a plan that returns the first row quickly, we would expect SQL Server to reorder the concatenation inputs so the cheap clustered table is consulted first.

Using the query that mentions the heap table first, and using a FAST 1 query hint to specify the row goal:

The estimated execution plan produced on an instance of SQL Server 2008 R2 is:

UNION ALL with a row goal on 2008 R2

Notice that the concatenation inputs have been reordered to reduce the estimated cost of returning the first row. Note also that the missing index and residual I/O warnings have disappeared. Neither issue is of consequence with this plan shape when the goal is to return a single row as quickly as possible.

The same query executed on SQL Server 2016 (using either cardinality estimation model) is:

UNION ALL with a row goal on 2016

SQL Server 2016 has not reordered the concatenation inputs. The Plan Explorer I/O warning has returned, but sadly the optimizer has not produced a missing index warning this time (though it is relevant).

General reordering

As mentioned, the post-optimization rewrite that reorders concatenation inputs is only effective for:

  • SQL Server 2008 R2 and earlier
  • A row goal of exactly one

If we genuinely only want one row returned, rather than a plan optimized to return the first row quickly (but which will ultimately still return all rows), we can use a TOP clause with a derived table or common table expression (CTE):

On SQL Server 2008 R2 or earlier, this produces the optimal reordered-input plan:

UNION ALL with TOP on 2008 R2

On SQL Server 2012, 2014, and 2016 no post-optimization reordering occurs:

UNION ALL with TOP on 2012-2016

If we want more than one row returned, for example using TOP (2), the desired rewrite will not be applied on SQL Server 2008 R2 even if a FAST 1 hint is also used. In that situation, we need to resort to tricks like using TOP with a variable and an OPTIMIZE FOR hint:

The query hint is sufficient to set a row goal of one, while the runtime value of the variable ensures the desired number of rows (2) is returned.

The actual execution plan on SQL Server 2008 R2 is:

UNION ALL with variable and OPTIMIZE FOR on 2008 R2

Both rows returned come from the reordered seek input, and the Table Scan is not executed at all. Plan Explorer shows the row counts in red because the estimate was for one row (due to the hint) whereas two rows were encountered at run time.

Without UNION ALL

This issue is also not limited to queries written explicitly with UNION ALL. Other constructions such as EXISTS and OR can also result in the optimizer introducing a concatenation operator, which may suffer from the lack of input reordering. There was a recent question on Database Administrators Stack Exchange with exactly this issue. Transforming the query from that question to use our example tables:

The execution plan on SQL Server 2016 has the heap table on the first input:

CASE subquery on 2016

On SQL Server 2008 R2 the order of the inputs is optimized to reflect the single row goal of the semi join:

CASE subquery on 2008 R2

In the more optimal plan, the heap scan is never executed.

Hakan AK

Son Yazılar