Common Query Plan Patterns For Joins: OR Clauses

Least Favorite


This is one of my least favorite query patterns, because even with appropriate indexes, performance often isn’t very good without additional interventions.

Without indexes in place, or when “indexes aren’t used”, then the query plans will often look like one of these.

Maybe not always, but there are pretty common.

Merge Interval


SELECT
    COUNT_BIG(*) AS records
FROM dbo.Users AS u
JOIN dbo.Posts AS p 
    ON (p.OwnerUserId = u.Id
        OR p.LastEditorUserId = u.Id);
SQL Server Query Plan
here comes the pain

We start off with a scan of the Posts table, and a Nested Loops Join to a… Nested Loops Join? That’s weird.

SQL Server Query Plan
work it

From the Merge Interval to the right, there’s a lot of additional operators. Those two Constant Scan operators represent virtual tables containing the two columns from Posts being used in the join.

One for OwnerUserId, and one for LastEditorUserId. The Sort and Merge interval are a pseudo-attempt at ordering the concatenated results and removing duplicate ranges. I don’t think I’ve ever seen them be terribly effective.

This plan takes on this shape because the Users table has a seekable index on the Users table on the Id column.

Loops and Lazy Spools


With no usable indexes on either side, the plan will often take on a shape like this.

SELECT
    COUNT_BIG(*) AS records
FROM dbo.Comments AS c
JOIN dbo.Posts AS p 
    ON (p.OwnerUserId = c.UserId
        OR p.LastEditorUserId = c.UserId);
SQL Server Query Plan
rebort

This is an admittedly weird plan. Weird because usually when there’s a Lazy Spool on the inner side of a Nested Loops Join, there’s some Sorting of data on the outer side.

The Nested Loops Join here is not Optimized, and does not do an Ordered Prefetch. It’s odd to me that the Hash Match Aggregate on the outer side isn’t a Sort > Stream Aggregate.

This is usually done to maximize the Spool’s efficiency, and cut down on the Spool needing to execute child operators.

For example, let’s say the numbers 1 through 10 came out of the Comments table, and there were 10 of each. If they were in order, the Spool would initially fill with the values from Posts for  1, and then the contents of the Spool would get used for the next 9 duplicate values of 1.

The process would repeat for the rest of the numbers, with the Spool truncating itself when it sees a new value.

Let’s Add Indexes


You may have noticed that I’ve only been using estimated plans up until now. That’s because both of these queries run way too slowly to deal with actual plans for.

The optimal indexes we need to make that not the case any more look like this:

CREATE INDEX po
ON dbo.Posts
    (OwnerUserId);

CREATE INDEX pl
ON dbo.Posts
    (LastEditorUserId);

CREATE INDEX cu
ON dbo.Comments
    (UserId);

ORnery


If we don’t change the queries at all, both plans will use the Merge Interval shape. It’s only somewhat beneficial to the Users/Posts query, which now finishes in about 40 seconds. The Comments/Posts query runs for… I dunno. I let it go for three hours and my CPUs were maxed out the whole time and things got unusable.

If you’re going to leave the OR in, you need to use a FORCESEEK hint. More specifically, you need to use the hint on the table that has different columns in the OR clause. Otherwise, the plan shape goes all to crap (Merge Interval).

SELECT
    COUNT_BIG(*) AS records
FROM dbo.Users AS u  
JOIN dbo.Posts AS p WITH(FORCESEEK)
    ON (p.OwnerUserId = u.Id
        OR p.LastEditorUserId = u.Id);
GO 

SELECT
    COUNT_BIG(*) AS records
FROM dbo.Comments AS c
JOIN dbo.Posts AS p WITH(FORCESEEK)
    ON (p.OwnerUserId = c.UserId
        OR p.LastEditorUserId = c.UserId);
GO

With that hint in place, both queries will take on a similar, non-disastrous shape.

SQL Server Query Plan
oh hey seeks

Both queries will take around 5 seconds.

Leaving The Or Out


The usually-better rewrite is to use UNION ALL to separate the OR out, especially if you don’t have good indexes in place.

With good indexes in place (like above), both benefit from the FORCESEEK hint as well

SELECT
    SUM(x.x) AS records
FROM 
(
    SELECT
        COUNT_BIG(*) AS x
    FROM dbo.Comments AS c
    JOIN dbo.Posts AS p WITH(FORCESEEK)
        ON p.OwnerUserId = c.UserId
    
    UNION ALL

    SELECT
        COUNT_BIG(*) AS x
    FROM dbo.Comments AS c
    JOIN dbo.Posts AS p WITH(FORCESEEK)
        ON p.LastEditorUserId = c.UserId
    AND p.OwnerUserId <> c.UserId
) AS x;

SELECT
    SUM(x.x) AS records
FROM 
(
    SELECT
        COUNT_BIG(*) AS x
    FROM dbo.Users AS u
    JOIN dbo.Posts AS p WITH(FORCESEEK)
        ON p.OwnerUserId = u.Id
    
    UNION ALL

    SELECT
        COUNT_BIG(*) AS x
    FROM dbo.Users AS u
    JOIN dbo.Posts AS p WITH(FORCESEEK)
        ON p.LastEditorUserId = u.Id
    AND p.OwnerUserId <> u.Id
) AS x;

Not All ORs


I am usually not a fan of OR predicates in JOINs. There often isn’t great indexing in place to make things fast, or support the FORCESEEK hints.

If you see query plans with these patterns in them, you should keep an eye out for them. You may have a pretty easy performance win on your hands, either via indexing and hints, or rewriting to a UNION ALL.

Thanks for reading!

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.

Common Query Plan Patterns For Windowing Functions: Ranges, Rows, and Spills

What Why


Certain windowing functions allow you to specify more precise windows to perform calculations on, and many of them allow you to specify an empty OVER() clause to get a global aggregate for a result set.

The performance difference between RANGE and ROWS is fairly well-documented, and I’m mostly covering it here to show you the difference in execution plans.

There’s also some different behavior when Batch Mode shows up around memory usage, which I was amused by.

We’re going to be using this index to help our queries move along faster.

CREATE INDEX c
ON dbo.Comments
(
    UserId,
    CreationDate,
    Score
);

RANGEr Zone


If you don’t specify the type of window you want, by default you’ll use RANGE. I’m using it here to be clear about which I’m covering.

WITH Comments AS 
(
    SELECT
        SUM(c.Score) OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
            RANGE BETWEEN UNBOUNDED PRECEDING 
                      AND CURRENT ROW
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n < 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

Even with an index to help us along, this query runs for a very long time. In fact it’s been running for the entire time I’ve been writing this particular blog post.

The longer it runs, the more space-filler I have to type, and the more post quality suffers. If this post is terrible, you can blame the above query. Or SQL Server.

Whatever.

Three minutes later:

SQL Server Query Plan
cpu hound

In my experience, this is the query plan pattern that shows up when you use the RANGE/default specification.

SQL Server Query Plan
emergency

The first Segment is for the Partition By elements, and the second Segment is for both Partition By and Order By.

Depending on your ideas about our time on Earth, and the afterlife, this query could be considered a poor use of finite time.

ROW Boat


Switching over to the ROWS specification, performance is much different, and we get a different execution plan.

WITH Comments AS 
(
    SELECT
        SUM(c.Score) OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
            ROWS BETWEEN UNBOUNDED PRECEDING 
                     AND CURRENT ROW
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n < 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

I only have to wait about 10 seconds for this one, with some efficiency gained by the query going parallel. Even if I force the query to run at DOP 1, it runs in about 25 seconds. Is 15 seconds of duration worth the 7 additional threads? I don’t know.

Again, it depends largely on your belief system. You may find this to be a good way to kill time until you end up somewhere better. You might not.

SQL Server Query Plan
wisdumb

The relevant difference in the query plan here (again, based on my observations over the years) is that rather than two consecutive Segment operators, we have Segment > Sequence Project > Segment > Window Spool.

In this case, the Segment operators only list UserId in the “Group By” portion of the query plan. The Sequence Project uses ROW_NUMBER to define the frame.

SQL Server Query Plan
gifts!

The reason for the performance difference is that the RANGE/default specification uses an on-disk worktable for the Window Spool, and the ROWS specification uses one in-memory. If you were to compare memory grant details for the two query plans, you’d see the RANGE/default query had 0 for all memory grant categories, and the ROWS specification asks for a ~6GB memory grant.

There is a limit here though. If you go beyond 10,000 rows, an on-disk table will be used. This query will run for just about a minute:

WITH Comments AS 
(
    SELECT
        SUM(c.Score) OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
            ROWS BETWEEN 9999 PRECEDING 
                     AND CURRENT ROW
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n < 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

Unfortunately, details of the Window Spool don’t indicate that any I/O was done. This seems a little bit weird, since Many to Many Merge Joins will show I/O details for the worktable.

Anyway. What about that Batch Mode?

Batcher Up


In Batch Mode, the window specification doesn’t tend to make a lot of difference when it comes to performance.

SQL Server Query Plan
bangers

Both of these queries ask for 1MB of memory, but take ~3 seconds to scan the table single-threaded.

Again, your trade-off here will be deciding whether or not it’s worth scanning the table faster with parallel threads but incurring additional memory grant with the Sort.

Even though you’re Sorting Sorted data.

Go figure.

OVER It


If you use an empty OVER() clause, you can’t specify rows or ranges. You use the default/RANGE specification. That typically means queries using that in Row Mode vs Batch Mode will be much slower.

WITH Comments AS 
(
    SELECT
        COUNT_BIG(*) OVER () AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n < 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

Also, the query plans are atrocious looking.

SQL Server Query Plan
take your time

Batch Mode does solve a lot of the issues with them, but at the cost of additional memory usage, and the potential for spilling.

SQL Server Query Plan
scampi

Batch Mode Memory Grant Feedback will fix the spill, and the query will run about 2-3 seconds faster.

Thanks, probably.

Some Grants Are Bigger Than Others


The non-spilling memory grant for the COUNT query is about 800MB.

SQL Server Memory Grant
one right here

The non-spilling grant for the SUM query is about 1100MB:

SQL Server Memory Grant
friendly

Apparently the reason for the additional memory is because behind the scenes sum also does a count, and returns NULL if it’s zero.

SELECT
    SUM(x.x) AS the_sum,
    COUNT_BIG(x.x) AS the_x_count,
    COUNT_BIG(*) AS the_full_count
FROM 
(
    SELECT CONVERT(int, NULL) AS x
) AS x;

Thanks for reading!

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.

Common Query Plan Patterns For Windowing Functions: Column Selection Matters

Not A Doctor


All of our previous queries looked about like this:

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c 
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0;

The only columns that we were really selecting from the Comments table were UserId and CreationDate, which are an integer and a datetime.

Those are relatively easy columns to deal with, both from the perspective of reading and sorting.

In order to show you how column selection can muck things up, we need to create a more appropriate column store index, add columns to the select list, and use a where clause to  restrict the number of rows we’re sorting. Otherwise, we’ll get a 16GB memory grant for every query.

Starting Point


Selecting no additional columns:

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
    WHERE c.CreationDate >= '20131201'
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0;

On a second run of the query, after a memory grant feedback correction, we end up with a plan with these details:

SQL Server Query Plan
burgers

It takes us 3 milliseconds to scan the column store index, and we get a 24MB memory grant. This is good. I like this.

Darn Strings


Our second query looks like this. We’re selecting all the columns from the Comments table.

WITH Comments AS 
(
    SELECT
        c.Id, 
        c.CreationDate, 
        c.PostId, 
        c.Score, 
        c.Text, 
        c.UserId,
        ROW_NUMBER() OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
    WHERE c.CreationDate >= '20131201'
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0;

A first run of the query, before memory grant feedback fixes things for us, asks for a 16GB memory grant. Without this mechanism in place, we’ll keep asking for the same unproductive grant. If you don’t have batch mode and enterprise edition, this is the scenario you’ll face over and over again.

When memory grant correction kicks in, we end up with a 456MB memory grant.

Quite an adjustment, eh?

SQL Server Query Plan
kick me

We also end up taking 125ms to scan the table with parallel threads, up from 3 milliseconds with a single thread. Of course, the issue here is mostly the Text column.

Strings were a mistake.

No Strings Attached


If we select all the columns other than the string, we’ll end up with a very similar set of metrics as the first plan.

SQL Server Query Plan
mexico

If we want to maintain those metrics, but still show the Text column, we’ll need to do something like this:

WITH Comments AS 
(
    SELECT
        c.Id, 
        c.CreationDate, 
        c.PostId, 
        c.Score,  
        c.UserId,
        ROW_NUMBER() OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
    WHERE c.CreationDate >= '20131201'
)
SELECT 
    c.*,
    c2.Text
FROM Comments AS c
JOIN dbo.Comments AS c2
    ON c.Id = c2.Id
WHERE c.n = 0;
SQL Server Query Plan
big hands

Using a self-join, and getting the initial set of columns we care about,  then getting the Text column at the end means we avoid some of the the knuckle-headedness of strings in databases.

Deep Drink


This pattern applies to more than just windowing functions, but it’s a performance issue I have to tune pretty often for people using paging queries.

In tomorrow’s post, we’ll look at another rather unfortunate thing that I see people messing up with windowing functions, and how you can spot it looking at query plans.

Thanks for reading!

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.

Common Query Plan Patterns For Windowing Functions: Row Store vs Column Store Indexes

Headed Serial


Getting it out of the way, yes, we can create this nonclustered row store index to store our data in oh-so-perfect order for the windowing function:

CREATE INDEX row_store 
ON dbo.Comments
(
    UserId, 
    CreationDate
);

Keeping in mind that sort direction matters in how you write your query and define your index, this particular topic has, in my mind, been done to death.

SQL Server Query Plan
pasty

Look ma, no Sort! Whoopie.

We also get serial plans. For the row store query, it’s about twice as fast, even single-threaded.

For the column store query, it’s about twice as slow.

Headed Parallel


Here are some interesting things. You’re going to want to speak to the manager.

Let’s force these to go parallel. For science.

SQL Server Query Plan
longer

Not only is the parallel version of the row mode plan a full second slower, but… look at that batch mode plan.

Look at it real close. There’s a sort before the Window Aggregate, despite reading from the same nonclustered index that the row mode plan uses.

But the row mode plan doesn’t have a Sort in it. Why? Because it reads ordered data from the index, and the batch mode plan doesn’t.

This must be hard to do, with all the support added for Batch Mode stuff, to still not be able to do an ordered scan of the data.

For those of you keeping track at home: yes, we are sorting sorted data.

Column-Headed


Let’s try an equivalent column store index:

CREATE COLUMNSTORE INDEX column_store_ordered 
ON dbo.Comments
(
    UserId, 
    CreationDate
)
SQL Server Query Plan
tiny dragons

Both have to sort, but both are fast and parallel. Yes, Sorting is annoying. Unfortunately, we can’t do this Sort in the application.

But hey, look how fast those index scans are. Choo-choo, as a wise man once said.

And of course, since we have to sort anyway, we’d be better off creating a wide nonclustered column store index on the table, so it would be more generally useful to more queries. You only get one per table, so it’s important to choose wisely.

If you have queries using window functions where performance is suffering, it might be wise to considered nonclustered column store indexes as a data source for them. Beyond just tricking the optimizer into using Batch Mode, the data compression really helps.

Elsewise


But there’s something else to consider, here: the plans with Sorts in them require memory.

It’s not much here — about 570MB — but in situations where more columns are needed for the query, they could get much larger.

And you know what can happen then. We’ll look at that in tomorrow’s post.

Thanks for reading!

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.

Common Query Plan Patterns For Windowing Functions: Partition By Parallelism

Ramble On


Prior to SQL Server 2012, this blog post would be wrong. If you’re still on a version prior to 2012, ignore this blog post.

In fact, ignore every blog post and go upgrade those servers. Go on. Get out of here. Show’s over.

After SQL Server 2012, AKA the only versions that currently matter, this blog post is largely correct, and leans more towards correctness as you get to closer to SQL Server 2019.

Sliding scale correctness. Get on board.

Say It Slow


When windowing functions don’t have a Partition By, the parallel zone ends much earlier on than it does with one.

That doesn’t mean it’s always slower, though. My general experience is the opposite, unless you have a good supporting index.

But “good supporting index” is for tomorrow. You’re just going to have to deal with that.

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

With just an Order By in the windowing function, our query plan looks about like so:

SQL Server Query Plan
ripper

Immediately after sorting data, our parallel streams are gathered. This is the end of our parallel zone, and it will occur regardless of if you’re filtering on the windowing function or now. I’m filtering on it here because I don’t want to spend any time retuning rows to SSMS.

Here’s an example of when a parallel zone is started again later:

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n > 100000000
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));
SQL Server Query Plan
innuendo

Note that there’s no Top in this plan prior to the Filter.

You’ll see a Top generally when you filter on the windowing function with an equality or less-than predicate. Greater than seems to most often not end up with a Top in the plan.

Margaret Batcher


If we let Batch Mode run free, things turn out a little bit different.

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0;
SQL Server Query Plan
branded!

The Window Aggregate operator is within the parallel zone, unlike the Segment and Sequence Project operators in the Row Mode plan.

If we reuse the greater-than query from above while allowing Batch Mode to be used, we get a fully parallel plan.

SQL Server Query Plan
science can’t explain it

Paddington


Of course, Partition By adds work, especially in Row Mode, and especially without a supporting index.

SQL Server Query Plan
boulevard

The nearly 11 second Row Mode plan compared to the 1.6 second Batch Mode plan doesn’t leave a lot of room for arguing.

It’s also worth noting here that Batch Mode Sorts (at least currently) will always sort on a single thread, unless it’s the child of a Window Aggregate operator, like in the above plan.

Tomorrow, we’ll look at how indexing can improve things, but not just row store indexes!

Everyone knows about those P(artition By) O(rder By) C(overing) indexes, but does that attention to ordering matter as much with column store indexes?

Tune in to find out!

Thanks for reading.

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.

Common Query Plan Patterns For Windowing Functions: Row vs Batch Mode

Kickball


To start things off, we’re going to talk about query plan patterns related to windowing functions.

There are several things to consider with windowing function query plans:

  • Row vs Batch mode
  • With and Without Partition By
  • Index Support for Partition and Order By
  • Column SELECTion
  • Rows vs Range/Global aggregates

We’ll get to them in separate posts, because there are particulars about them that would make covering them all in a single post unwieldy.

Anyway, the first one is pretty simple, and starting simple is about my speed.

Row Mode


I’m doing all of this work in SQL Server 2019, with the database in compatibility level 150. It makes my life easier.

First, here’s the query we’ll be using. The only difference will be removing the hint to allow for Batch Mode later on.

WITH Comments AS 
(
    SELECT
        ROW_NUMBER() OVER
        (
            PARTITION BY
                c.UserId
            ORDER BY 
                c.CreationDate
        ) AS n
    FROM dbo.Comments AS c
)
SELECT 
    c.*
FROM Comments AS c
WHERE c.n = 0
OPTION(USE HINT('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_140'));

Part of the row mode query plan will look like this:

The two operators that generate the numbering are the Segment and Sequence Project.

SQL Server Query Plan
shotted

We’ll talk about the Sort later on. For now, we can see the segment “grouping” by UserId, and the Sequence Project description notes that it works over an ordered set.

You can probably guess why we need the Sort here.

SQL Server Query Plan
consider surgery

Group is in quotes up there, because technically there’s no grouping. The “Segment1002” column in the Output List of the Segment is a computed column that marks the beginning and ending of each set of values. Likewise, the Sequence Project outputs “Expr1001”, which in this case is the calculated row number.

Batch Mode


In Batch Mode, there are three operators associated with windowing functions that get replaced with a single operator: the Window Aggregate.

The operators that get replaced are two we’ve already seen — Segment and Sequence Project, along with one we’ll see in a future post, the Window Spool.

SQL Server Query Plan
richie rich

We still need to Sort data for it without a supporting index. Gosh, those indexes sure are magickal.

The details of the Window Aggregate do still show a sequence generated, but we no longer see the “grouping”.

SQL Server Query Plan
a society

Baby Steps


Batch Mode kicks the pantalones off of Row Mode when it comes to window functions, but that’s not really the point of the post.

If you’re using a relatively modern version of SQL Server and also windowing functions, you should look at various ways to get Batch Mode processing alongside them.

Unless you’re on Standard Edition, probably.

In the next entry in this series, we’ll look at how the absence and presence of Partition By changes parallelism.

Thanks for reading!

Going Further


If this is the kind of SQL Server stuff you love learning about, you’ll love my training. I’m offering a 75% discount on to my blog readers if you click from here. I’m also available for consulting if you just don’t have time for that and need to solve performance problems quickly.