3
create table Test1 (Id int not null, H char, primary key (Id), index i1 unique (H))
create table Test2 (Id int not null, H char, primary key (Id), index i2 unique (H))
insert into Test1 values (1, 'A'), (2, 'B')
insert into Test2 values (1, 'A'), (2, 'C')

this query fails Query processor could not produce a query plan because of the hints defined in this query. (if I remove the forceseek hints then it runs but it will scan one of the two tables - even if it's extremely large)

select * from Test1 a with (forceseek)
join Test2 b with (forceseek) on a.Id = b.Id
where a.H = 'A' or b.H = 'C'

this equivalent query runs fine:

select * from Test1 a with (forceseek)
join Test2 b with (forceseek) on a.Id = b.Id
where a.H = 'A'
union
select * from Test1 a with (forceseek)
join Test2 b with (forceseek) on a.Id = b.Id
where b.H = 'C'

and gives plan

enter image description here

..I don't understand why SQL Server doesn't run the first query optimally. Is this a known issue? Does it have a name?

3
  • 4
    "Does it have a name?" for an OR on a single index. This is index union. but even that is often not considered - your case is an OR on two different columns in different tables not sure if there is a general name for transforming or to UNION Apr 18, 2020 at 0:11
  • @MartinSmith the linked answer is interesting thanks! it seems to indicate that with forceseek hints SQL Server ought to have found the seek plan rather than fail to execute. I tried the (undocumented) traceflag 8726 and got the same results.
    – gordy
    Apr 18, 2020 at 0:42
  • 1
    The linked answer is talking about index union. Which is a much more specific case. It combines seeks on the same index under a union, not on different indexes/sub trees Apr 18, 2020 at 0:51

3 Answers 3

4

For the original query in question optimizer considers(*) two main alternatives normally (when FORCESEEK hints aren't used on any of the tables).

First one is simple join

plan 1

when indexes from both tables are scanned entirely (without predicates), and predicate a.Id = b.Id AND (a.H = 'A' OR b.H = 'C') is tested at join node.

Second one is apply form (more about it here)

plan 2

when index on one of the tables is scanned on the outer side of the Nested Loops join, and then index data is used on the inner side to seek into clustered index on the other table using b.Id = a.Id seek predicate and additional a.H = 'A' OR b.H = 'C' predicate. It can be expressed in T-SQL as

SELECT *
FROM Test1 a
    CROSS APPLY (
        SELECT *
        FROM Test2 b
        WHERE b.Id = a.Id AND (a.H = 'A' OR b.H = 'C')
    ) appl

When FORCESEEK is used on one of the tables, simple join alternative falls out from consideration, but optimizer additionally considers modified form of apply

plan 3

which unions two seeks into clustered index on the other table. One with b.Id = a.Id seek predicate and additional b.H = 'C' predicate. And the other with b.Id = a.Id seek predicate beyond Filter with a.H = 'A' startup predicate. It can be expressed in T-SQL as

SELECT *
FROM Test1 a
    CROSS APPLY (
        SELECT DISTINCT u.Id, u.H
        FROM (
            SELECT b.Id, b.H
            FROM Test2 b
            WHERE b.Id = a.Id AND a.H = 'A'
            UNION ALL
            SELECT b.Id, b.H
            FROM Test2 b
            WHERE b.Id = a.Id AND b.H = 'C'
        ) u
    ) appl

There are more alternatives actually (that use spooling on the inner side of the apply, for example, or different physical join implementation for simple join, or non-clustered index scan instead of clustered index scan, or vice versa, etc.), but above execution plans shapes are quite representative.

When FORCESEEK is used on both tables, no new alternatives appear. Moreover, apply alternatives become rejected after consideration due to seek requirement on both tables.

So, I think we can say, that possible implementations of the original written form of the query require FORCESEEK requirement to be relaxed for at least one of the tables.

You have another equivalent query, but discovering such alternative is not implemented in the current version of query optimizer unfortunately. This is not a bug though, just imperfection.

Notice also that you add FORCESEEK to convince optimizer to seek in the non-clustered index, but in the above cases optimizer understands it in its own way and performs seek over clustered index instead. Rewriting query, when its performance is not satisfactory, is one of the first (and right) things to try often.


(*) One may find it out by analyzing final memo structure and applied transformations (using undocumented trace flags 8615, 8619 and 8621).

2

I don't understand why SQL Server doesn't run the first query optimally. Is this a known issue?

It's not that SQL Server is not runnig the first query optimally, it's just that it can't run at all. The Hints doc says:

  • If FORCESEEK causes no plan to be found, error 8622 is returned.

To understand the problem caused with that query let's observe the query plan of part of the query that executed the way you wanted:

select * from Test1 a with (forceseek)
join Test2 b with (forceseek) on a.Id = b.Id
where a.H = 'A'

And here's the query plan generated:

Execution Plan

Notice that SQL Server did the first seek on the nonclustered index i1 to find a.H = 'A' and with that result the second seek (the one related with the join clause on a.Id = b.Id) could occur on the clustered index of the table Test2.

The problem when we have where a.H = 'A' or b.H = 'C' is that if SQL Server did the first seek on the nonclustered index i1 to find a.H = 'A' and with that result proceeded to do a second seek for the join on a.Id = b.Id, it would eliminate the rows that didn't match the clause on a.Id = b.Id and with that the predicate b.H = 'C' could not be correctly verified because some rows that would match it could already have been discarded by a forced join seek. Since it can't risk to generate a wrong resultset, SQL Server throws 8622 error.

On the Optimizer not choosing index union plan mentioned by Martin Smith, Paul White says:

Joins with multiple conditions separated with OR have long been problematic. Over the years, the optimizer has added new tricks like converting them to equivalent UNION forms, but the transformations available are limited, so it is quite easy to come unstuck. (emphasis added)

So it's possible that the convertion you desired is not on the list and without that possibility, it doesn't have an option at all. A case for 8622 error.

3
  • 1
    It would not be impossible for it to come up with an execution plan that both respected the index seek hints and returned the correct results - as shown in the manual rewrite with UNION. Apr 18, 2020 at 16:44
  • @MartinSmith , I agree. The doc says: Specifying FORCESEEK with parameters limits the number of plans that can be considered by the optimizer more than when specifying FORCESEEK without parameters. This may cause a Plan cannot be generated error to occur in more cases., so it's possible that the hint limited that union plan (that wasn't beeing chosen for it's not guaranteed that the Optimizer will pick the best of all plans, but one that's satisfying).
    – Ronaldo
    Apr 18, 2020 at 17:14
  • I'm using forceseek here to demonstrate SQL Server not finding the seek plan - it will execute the query without the hints but it will scan one of the tables (to devastating effect when they are large - not at all satisfying).
    – gordy
    Apr 18, 2020 at 19:12
0

Your first query is "Give me all rows from Test1 and Test2 with the same Id, where either Test1 has a value in a column, OR Test2 has a value in a column". SQL Server cannot do a seek on both these tables, because it cannot filter out rows from either side due to the OR in the where clause.

Your second query is "Give me all Test1-Test2 pairs were Test1 has A, combined with all Test1-Test2 pairs where Test2 has C". The UNION will produce equivalent results, however it appears that the query optimizer is not smart enough to see that it's the same as the JOIN + OR).

11
  • ah thanks, I'm not going to accept this answer because I meant "union" - edited
    – gordy
    Apr 17, 2020 at 23:53
  • How large are your tables? - SQLServer will tend to scan tables where the scan is cheaper than the aggregate seeks.
    – geofftnz
    Apr 17, 2020 at 23:57
  • 10's of millions in production, but the issue is reproducible with two rows and forceseek hints
    – gordy
    Apr 17, 2020 at 23:58
  • 1
    it's the plan for the 2nd query which is equivalent
    – gordy
    Apr 18, 2020 at 0:04
  • 1
    @MartinSmith, UNItoDISonUNIA is about A UNION B to DISTINCT (A UNION ALL B), it is considered for the 2nd query.
    – i-one
    Apr 18, 2020 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.