Unable to execute query and not even able to generate Estimated execution plan

Question

I am working on SQL Server 2019.

I have a table dbo.AllDates where I have all dates from 1990 to 2050. I have another table dbo.ActualExchangeRates where I have actual exchange rates for certain currencies on the dates when exchange rate is found in given source.

I am trying to write a query to get all currencies for all dates between 2010 and 2020. If rate is found then write the rate otherwise write NULL.

Given this scenario and given code below, can someone please help me understand why the SELECT query is not generating any results or even not able to see estimated execution plan?

CREATE TABLE dbo.AllDates(Date date)
CREATE TABLE dbo.ActualExchangeRates(Date date, Currency char(3), Rate real)

--Query 1: Not generating any results or estimated plan
SELECT      d.Date, m.Currency, c.Rate
FROM        dbo.AllDates d
INNER JOIN  (
    select
      currency,
      '20100101' as mindate,
      '20201231' as maxdate
    from dbo.ActualExchangeRates
    group by currency
) as m on d.date between m.mindate and m.maxdate
LEFT JOIN   dbo.ActualExchangeRates C ON C.Currency = m.Currency and c.Date = d.Date;

I get the following error after the query runs for 9 minutes against empty tables:

Msg 701, Level 17, State 123, Line 5
There is insufficient system memory in resource pool 'default' to run this query.

Seems like it depends upon how much memory is available to SQL server until it reaches the error. To me, looks like a bug in SQL engine given there is no data in the table.

Now, I know that above query can be written in many different ways and other ways can generate results but my question is why SQL Server just hangs up forever on that query even if both tables are empty?

Answer 1

This is certainly a bug.

I can't tell you the nitty gritty details of the exact nature of the bug but some details are below.

Whilst the execution plan is being compiled the Visual Studio performance profiler shows the CPU time for the thread is spent as follows.

So a lot of CPU time was being spent at

... -> sqllang.dll!COptContext::NormalizeQuery -> ... sqllang.dll!COptContext::PexprTransformTopLevel -> sqllang.dll!CSubRuleImpliedPredInnerAndAllLeftJn::BuildSubstitutes -> sqllang.dll!OptimizerUtil::PexprCreateConjOrDisj

and at

... -> sqllang.dll!COptContext::NormalizeQuery -> ... sqllang.dll!COptContext::PexprTransformTopLevel -> sqllang.dll!COptExpr::DeriveGroupProperties

The stack shows the issue is arising during the Query normalization stage of compilation and appears to be associated with a rule RuleImpliedPredInnerAndAllLeftJn.

The issue does indeed go away when that rule is disabled with option(queryruleoff ImpliedPredInnerAndAllLeftJn) but this is not a good solution to the issue (undocumented and can affect performance as it no longer pushes the implied predicate of [C].[Date]>='2010-01-01' AND [C].[Date]<='2020-12-31' to the read of dbo.ActualExchangeRates C).

A simpler workaround was given in a comment on the question by @charlieface in that the issue also goes away when mindate/maxdate are cast to date rather than left as strings.

Adding option(querytraceon 3604, querytraceon 2373) shows that the compilation seems to have entered some sort of circle of deriving properties of LogOp_LeftOuterJoin -> ScaOp_Comp -> ScaOp_Comp -> ScaOp_Logical -> ScaOp_Const -> ScaOp_Comp -> ScaOp_Const -> ScaOp_Comp -> ScaOp_Logical -> ScaOp_Logical -> LogOp_Select -> LogOp_LeftOuterJoin -> ... with memory usage steadily increasing until eventually it runs out of memory and the compilation attempt ends. (Sample output of that showing a couple of circuits)

On my dev machine

select promised
from sys.dm_exec_query_transformation_stats
where name = 'ImpliedPredInnerAndAllLeftJn'

from before and after grows by ~390,000 with each failed run.

Answer 2

This is a product defect as Martin Smith has already answered.

Under certain conditions, the optimizer becomes stuck in a loop adding the same implied predicates to the outer join as it has derived from the earlier join. Eventually, so many duplicate predicates are added that the process runs out of memory.

To encounter this issue you need:

• Multiple joins of different types that do not qualify for treatment as a single n-ary join
• A join predicate specified in the ON clause referencing a constant literal projected column
• A separate simple equijoin of column references without expressions
• The same column reference in both joins allowing predicate inference
• Different base types requiring an explicit conversion before comparison
• Two inequalities in the first join (BETWEEN expands to two inequalities)
• Explicit conversion required at both ends of the implied range
• The conversion must be constant foldable

A simplified example that meets all these conditions:

DECLARE @T1 AS table (i integer NULL);

SELECT NULL
FROM @T1 AS T1
JOIN (VALUES ('1', '9')) AS V (f, t)
    ON T1.i > V.f
    AND T1.i < V.t
LEFT JOIN @T1 AS T2
    ON T2.i = T1.i;

The first join acquires a tree representation with explicit conversions (ScaOp_Convert):

LogOp_Select
LogOp_Join
    LogOp_Get TBL: @T1(alias TBL: T1) @T1
    LogOp_ConstTableGet (1) [empty]
    ScaOp_Const TI(bit,ML=1) XVAR(bit,Not Owned,Value=1)
ScaOp_Logical x_lopAnd
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T1].i
    ScaOp_Convert int,Null,ML=4
        ScaOp_Const TI(varchar collate 53256,Var,Trim,ML=1) XVAR(varchar,Not Owned,Value=Len,Data = (1,1))
    ScaOp_Comp x_cmpLt
    ScaOp_Identifier QCOL: [T1].i
    ScaOp_Convert int,Null,ML=4
        ScaOp_Const TI(varchar collate 53256,Var,Trim,ML=1) XVAR(varchar,Not Owned,Value=Len,Data = (1,9))

The second join acquires implied predicates:

LogOp_Select
LogOp_Get TBL: @T1(alias TBL: T2)
ScaOp_Logical x_lopAnd
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].i
    ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
    ScaOp_Comp x_cmpLt
    ScaOp_Identifier QCOL: [T2].i
    ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
ScaOp_Comp x_cmpEq
ScaOp_Identifier QCOL: [T2].i
ScaOp_Identifier QCOL: [T1].i

The inferred predicates have been constant folded to T2.i > 1 AND T2.i < 9.

This is great, but the optimizer now cannot tell that these predicates exactly match what can be inferred from the other join, which involve an explicit conversion from a string type to integer. There's a little more to it, concerning the way the optimizer reasons about implied constraints and domain ranges, but that's the gist of it.

The result is that the implied predicate rule matches again and produces a duplicate set of inferred predicates:

LogOp_Select
    LogOp_Select
        LogOp_Get TBL: @T1(alias TBL: T2) @T1
        ScaOp_Logical x_lopAnd
        ScaOp_Comp x_cmpGt
            ScaOp_Identifier QCOL: [T2].i
            ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
        ScaOp_Comp x_cmpLt
            ScaOp_Identifier QCOL: [T2].i
            ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
    ScaOp_Logical x_lopAnd
        ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
        ScaOp_Comp x_cmpLt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
    ScaOp_Comp x_cmpEq
    ScaOp_Identifier QCOL: [T2].i
    ScaOp_Identifier QCOL: [T1].i

After the next iteration:

LogOp_Select
LogOp_Select
    LogOp_Select
    LogOp_Get TBL: @T1(alias TBL: T2) @T1
    ScaOp_Logical x_lopAnd
        ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
        ScaOp_Comp x_cmpLt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
    ScaOp_Logical x_lopAnd
    ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
    ScaOp_Comp x_cmpLt
        ScaOp_Identifier QCOL: [T2].i
        ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
ScaOp_Logical x_lopAnd
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].i
    ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=1)
    ScaOp_Comp x_cmpLt
    ScaOp_Identifier QCOL: [T2].i
    ScaOp_Const TI(int,Null,ML=4) XVAR(int,Not Owned,Value=9)
ScaOp_Comp x_cmpEq
ScaOp_Identifier QCOL: [T2].i
ScaOp_Identifier QCOL: [T1].i

...and so on until we run out of memory.

The problem requires a very particular set of unusual circumstances to manifest. It is therefore easy to work around with query rewrites, as noted in the question body. It is also possible to disable the application of implied predicates in this particular case using undocumented trace flag 2324, which can be specified at the query level using QUERYTRACEON.