Why can't SQL Server find a seek plan? Is this a bug?

Question

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

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

Answer 1

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

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)

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

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).

Answer 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:

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.

Answer 3

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).