Return to Answer

I'm not sure if there's a way to avoid the sort without changing the query, but thought I'd add some information that might be helpful in answering this question:

Is this intentional?

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm
  • changing the indexes and joins to only have 5 keys removes the sort for the second query (6, 7, and 8 keys all have the sort).
  • This implies that the search space with 8 keys is so large that the optimizer just doesn't have time to identify the non-sort solution as a viable option before it terminates early with the "good enough plan found" reason
  • it does seem a little buggy to me that the order of the join conditions influences the optimizer's search process this much, but really that's a bit over my head
• the sort is required in order to ensure correctness in the results
  • this one seems unlikely, since the query can run without the sort when there are fewer keys, or the keys are specified in a different order

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.

Can I eliminate the sort without changing the query (which is vendor code, so I'd really rather not...). I can change the table and indexes.

If you can change the indexes, then changing the order of the index on #right to match the order of the filters in the join removes the sort (for me):

CREATE CLUSTERED INDEX IX ON #right (c, a, b, d, e, f, g, h)

Surprisingly (to me, at least), this results in neither query ending up with a sort.

Is this intentional?

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm
  • changing the indexes and joins to only have 5 keys removes the sort for the second query (6, 7, and 8 keys all have the sort).
  • This implies that the search space with 8 keys is so large that the optimizer just doesn't have time to identify the non-sort solution as a viable option before it terminates early with the "good enough plan found" reason
  • it does seem a little buggy to me that the order of the join conditions influences the optimizer's search process this much, but really that's a bit over my head
• the sort is required in order to ensure correctness in the results
  • this one seems unlikely, since the query can run without the sort when there are fewer keys, or the keys are specified in a different order

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.

I'm not sure if there's a way to avoid the sort without changing the query, but thought I'd add some information that might be helpful in answering this question:

Is this intentional?

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm, or
• the sort is required in order to ensure correctness in the results

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.

I'm not sure if there's a way to avoid the sort without changing the query, but thought I'd add some information that might be helpful in answering this question:

Is this intentional?

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm
  • changing the indexes and joins to only have 5 keys removes the sort for the second query (6, 7, and 8 keys all have the sort).
  • This implies that the search space with 8 keys is so large that the optimizer just doesn't have time to identify the non-sort solution as a viable option before it terminates early with the "good enough plan found" reason
  • it does seem a little buggy to me that the order of the join conditions influences the optimizer's search process this much, but really that's a bit over my head
• the sort is required in order to ensure correctness in the results
  • this one seems unlikely, since the query can run without the sort when there are fewer keys, or the keys are specified in a different order

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm, or
• the sort is required in order to ensure correctness in the results

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.

I'm not sure if there's a way to avoid the sort without changing the query, but thought I'd add some information that might be helpful in answering this question:

Is this intentional?

Looking at the output from some weird trace flags, there's an interesting difference in the final Memo structure:

As you can see in the "Root Group" at the top, both queries have the option to use a Merge Join as the main physical operation to execute this query.

Good query

The join without the sort is driven by group 29 option 1 and group 31 option 1 (each of which are range scans on the indexes involved). It's filtered by group 27 (not shown), which is the series of logical comparison operations that filter the join.

Bad query

The one with the sort is driven by the (new) options 3 that each of those two groups (29 and 31) has. Option 3 performs a physical sort on the results of the range scans mentioned previously (option 1 of each of those groups).

Why?

For some reason, the option to use 29.1 and 31.1 directly as sources for the merge join is not even available to the optimizer in the second query. Otherwise, I think it would be listed under the root group among the other options. If it were available at all, then it would definitely pick those over the massively more expensive sort operations.

I can only conclude that either:

• this is a bug (or more likely a limitation) in the optimizer's search algorithm, or
• the sort is required in order to ensure correctness in the results

Hopefully someone can come along and explain why the sort is required, but I thought the difference in the Memo building was interesting enough to post as an answer.