Table scan instead of index seeks happening when where clause filters across multiple tables in join using OR

Question

We have an application generated query using a view that has two tables joined on a LEFT OUTER join. When filtering by fields from just one table (either table) an index seek happens and it's reasonably fast. When the where clause includes conditions for fields from both tables using an OR the query plan switches to a table scan and doesn't utilize any of the indexes.

All four fields that are being filtered on are indexed on their respective tables.

Fast query plan where I filter on 3 fields from one table: https://www.brentozar.com/pastetheplan/?id=Hym_4PRSO

Slow query plan where I filter on four fields...three from one table and one from another table: https://www.brentozar.com/pastetheplan/?id=r1dVNDRHO

Ideally I would like to understand why this is happening and how to nudge the query engine to utilize all the indexes.

I considered a union but unfortunately this legacy system is using ntext values which can't be unioned. Also note the join between the two tables is one to one so I really expected the optimizer to utilize the indexes, but maybe it doesn't know that?

Answer 1

It looks to me like it’s doing a Scan because it may well need rows from T553 if the condition in T1011 holds. On the other hand, if any of the conditions on T553 hold, it’ll need rows from T1011.

So indexes would have to be able to handle finding rows in T553 and then pulling in the relevant rows from T1011, and also finding rows in T1011 and pulling in the relevant rows from T553. And the Query Optimizer figures that it’s probably best to get a good join happening and to filter the results.

To make it better, use a UNION of the two ways through the query. This should help it decide to do it the preferred way and you can optimise each side of the Union as you need.

Something like:

SELECT *, ROW_NUMBER....
FROM
(
SELECT *
FROM T1617
WHERE
  C1402001100 LIKE @P0
  OR C200000001 LIKE @P2
  OR C200000020 LIKE @P3
UNION
SELECT *
FROM T1617
WHERE C260100004 LIKE @P1
) t

---

Use SELECT CAST(ntextCol as nvarchar(max)), ... for something which can be UNIONed.

One thing to keep in mind is the UNION operator will remove dupes, not only between the two datasets, but within them as well. There are PKs in place here though, based on the objects involved in the seeks. If it did apply here, the answer would be to include something that’s unique in the view on each side of the UNION and then leave it out in the outer query.

Answer 2

We have an application generated query using a view that has two tables joined on a LEFT OUTER join. When filtering by fields from just one table (either table) an index seek happens and it's reasonably fast.

It is valid (= guaranteed to always produce correct results) to push a selection (aka filter, predicate) below an inner join when the selection involves only attributes from one table.

It is also valid to push such a selection down the preserved side of an outer join. A single-table selection that rejects nulls (as yours does) can also be pushed down the non-preserved (null-padded) side of an outer join. This works because rejecting nulls turns the outer join into an inner join, so the previous rule applies.

Once a predicate is below the join, it may be matched to one or more indexes.

Note: SQL Server cannot use a disjunctive ("or") selection over multiple attributes to seek using b-tree indexes directly. It achieves this result via index union transformation. This rewrite locates the set of rows matching any of the individual disjunctive tests, using a separate index per attribute, then removing duplicates. This transform only applies to a single table, and does not apply to attribute-to-attribute comparisons.

When the where clause includes conditions for fields from both tables using an OR the query plan switches to a table scan and doesn't utilize any of the indexes.

A disjunctive selection that references both joined tables cannot be pushed below a join directly — it must be evaluated at, or after the join. There are other valid transformations for conjunctive ("and") predicates, but you do not have those.

---

While it is not possible to push a disjunctive selection referencing both tables directly, it is possible to rewrite the query to achieve the same result. SQL Server does not contain this transformation, so you have to perform it manually. To be clear, it is not a question of cardinality estimation, or any other input to the optimizer's choices — SQL Server just can't do it.

One such manual rewrite is shown in Rob Farley's answer. As noted there, you do have to be careful to preserve all the semantics when using UNION, and the cost of the de-duplicating aspect can be significant.

---

Another valid rewrite is included in Oracle's "or-expansion" feature. This uses UNION ALL rather than UNION, so the problem with ntext not being comparable does not arise. The end result may also be cheaper to execute since duplicate removal is not necessary:

The essential idea is to guarantee the components of the UNION ALL are disjoint by explicitly excluding rows that match any of the preceding conditions.

It can be tricky to get the required negation correct in three-valued logic. Oracle uses the LNNVL built-in for this purpose. LNNVL(test) returns true if the tested predicate is false or unknown, and false if the tested predicate is true. I have simulated LNNVL in SQL Server using IIF.

SELECT *
FROM T1617
WHERE C260100004 LIKE @P1

UNION ALL

SELECT *
FROM T1617
WHERE
    --- Exclude rows found in the previous step
    0 = IIF(C260100004 LIKE @P1, 1, 0)
    -- New tests
    AND
    (
        C1402001100 LIKE @P0
        OR C200000001 LIKE @P2
        OR C200000020 LIKE @P3
    )

Now, the question shows you do not care about preserving the exact semantics of the outer join, so a small improvement is possible by replacing the (correct) IIF test with a simple (but less correct) NOT. This rejects nulls, so the outer join is simplified to an inner join, and the NOT test can be pushed down to the seek on T1011 as a non-sargable predicate:

SELECT *
FROM T1617
WHERE C260100004 LIKE @P1

UNION ALL

SELECT *
FROM T1617
WHERE
    (
        NOT C260100004 LIKE @P1
    )
    AND
    (
        C1402001100 LIKE @P0
        OR C200000001 LIKE @P2
        OR C200000020 LIKE @P3
    )

Online demo

Answer 3

Firstly, thank you for providing the actual execution plans for both cases, that is one of the best things for us to help troubleshoot performance problems.

Secondly, the issue you're facing is due to the difference in Cardinality between the first query and second query, which in a few words is the number of records your query might return relative to how many records are in the tables themselves, for the predicates (conditions in the JOIN, WHERE, and HAVING clauses) specified.

When SQL Server analyzes your query, its Cardinality Estimator uses statistics the server stores about the tables involved to try to make a reasonable estimate on how many rows will be returned from each table in your query. Then the execution plan is generated based on this information, as different operations are more efficient in different situations with different amounts of rows being returned.

For example, if your query results in a high Cardinality (lot of records being returned), generally an index scan is a more performant operation than an index seek because there is a higher likelihood the index scan will encounter a majority of your records sooner (contiguously) than it would've trying to seek out each one individually.

Sometimes the Cardinality Estimator gets confused based on the conditions in your predicates causing it to misestimate the cardinality resulting in performance issues. One way to verify you have a cardinality estimate issue is by comparing the Estimated Number of Rows to the Actual Number of Rows in the actual execution plan. If they are off by a significant amount (e.g. a magnitude or more) then likely there's a cardinality estimate issue.

Finally, sorry to get your hopes up, but your execution plans don't seem to be indicative of a cardinality estimate issue. It does seem to be your second execution plan is estimating the cardinality correctly, and it truly is a case where the conditions of your WHERE clause truly result in enough rows for SQL Server's engine to think an index scan operation will be more performant here than an index seek. As you'll notice both your Estimated Number of Rows and Actual Number of Rows in your second execution plan are now about 1.5 million rows.

That being said, even with accurate statistics and cardinality estimates sometimes the engine is just plain wrong. You can test this by using the FORCESEEK index hint which in your query's case would be appended after the table like FROM T1617 WITH (FORCESEEK), for example.

Fair warning, index hints are only recommended for use in production code after extended testing, as when used incorrectly can lead to worse performance. But FORCESEEK is a relatively benign one when appropriately used, and can help correct some uncommon cases where the engine is wrong about which operation will be faster. Alternatively you can try re-writing the query in a more relationally efficient way, when applicable.