Index scan of table with one record with 2.2 billion executions

Question

There's something I'm not sure how to tackle with in the query I have.

First, definitions:

Courier Services table. With one record.

CREATE TABLE [dbo].[CS](
    [ServiceID] [int] IDENTITY(1,1) NOT NULL,
    [CSID] [nvarchar](6) NULL,
    [CSDescription] [varchar](50) NULL,
    [OperatingDays] [int] NULL,
    [DefaultService] [bit] NULL,
 CONSTRAINT [CourierServices_PK] PRIMARY KEY CLUSTERED 
(
    [ServiceID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF,
       ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 90
) ON [PRIMARY]
) ON [PRIMARY]

GO
SET IDENTITY_INSERT [dbo].[CS] ON 

INSERT [dbo].[CS] ([ServiceID], [CSID], [OperatingDays], [DefaultService])
           VALUES (1, N'RM48', 2, 1)
SET IDENTITY_INSERT [dbo].[CS] OFF
SET ANSI_PADDING ON

GO
/****** Object:  Index [ix_CourierServices]    Script Date: 19/04/2017 14:27:03 ******/
CREATE NONCLUSTERED INDEX [ix_CourierServices] ON [dbo].[CS]
(
    [CSID] ASC,
    [DefaultService] ASC,
    [OperatingDays] ASC
)
INCLUDE (   [CSDescription]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON,
ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

Calendar DB and table, code by Genius Jim Horn :

CREATE TABLE [dbo].[days](
    [PKDate] [date] NOT NULL,
    [calendar_year] [smallint] NULL,
    [calendar_quarter] [tinyint] NULL,
    [calendar_quarter_desc] [varchar](10) NULL,
    [calendar_month] [tinyint] NULL,
    [calendar_month_name_long] [varchar](30) NULL,
    [calendar_month_name_short] [varchar](10) NULL,
    [calendar_week_in_year] [tinyint] NULL,
    [calendar_week_in_month] [tinyint] NULL,
    [calendar_day_in_year] [smallint] NULL,
    [calendar_day_in_week] [tinyint] NULL,
    [calendar_day_in_month] [tinyint] NULL,
    [dmy_name_long] [varchar](30) NULL,
    [dmy_name_long_with_suffix] [varchar](30) NULL,
    [day_name_long] [varchar](10) NULL,
    [day_name_short] [varchar](10) NULL,
    [continuous_year] [tinyint] NULL,
    [continuous_quarter] [smallint] NULL,
    [continuous_month] [smallint] NULL,
    [continuous_week] [smallint] NULL,
    [continuous_day] [int] NULL,
    [description] [varchar](100) NULL,
    [is_weekend] [tinyint] NULL,
    [is_holiday] [tinyint] NULL,
    [is_workday] [tinyint] NULL,
    [is_event] [tinyint] NULL,
PRIMARY KEY CLUSTERED 
(
    [PKDate] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF,
 ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

/****** Object:  Index [ix_days]    Script Date: 19/04/2017 14:38:47 ******/
CREATE NONCLUSTERED INDEX [ix_days] ON [dbo].[days]
(
    [PKDate] ASC
)
INCLUDE (   [is_weekend],
    [is_holiday],
    [is_workday],
    [is_event]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
 SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF,
 ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

Now, I'm running a query which references both tables as per bit of code:

Select
    OID
   ,case when
     Cast(o.[CreationDate] as time) > '16:00:00' 
        then (select top 1 [PKDate] from [calendar].[dbo].days
              where is_weekend <> 1 and is_holiday <>1 and 
              PKDate > cast(o.[CreationDate] as date)
              order by PKDate asc)
        else (select top 1 [PKDate] from [calendar].[dbo].days
              where is_weekend <> 1 and is_holiday <>1 and 
              PKDate >= Cast(o.[CreationDate] as date) 
              order by PKDate asc)
        end  OperatingDate
   ,case when
     Cast(o.[CreationDate] as time) > '16:00:00' 
        then (select top 1 [PKDate] from [calendar].[dbo].days
              where is_weekend <> 1 and is_holiday <>1 and 
              PKDate > dateadd(day,isnull(
                  (select top 1 [operatingdays]
                  from [dbo].[CS]
                  where DefaultService = 1)
                 ,2)+1,Cast(o.[CreationDate] as date))
                 order by PKDate asc)
            else (select top 1 [PKDate] from [calendar].[dbo].days
                  where is_weekend <> 1 and is_holiday <>1 and
                  PKDate > dateadd(day,isnull(
                      (select top 1 [operatingdays]
                       from [dbo].[CS]
                       where DefaultService = 1)
                      ,2), Cast(o.[CreationDate] as date))
                      order by PKDate asc)
            end EstimatedDeliveryDate
  ,(select dateadd(day,3,o.[CreationDate])) DeliveryDate
From o

Now the question is, related to index scans and number of executions: why the 2 BILLION? Or 6 Billion? Output of the whole query is, admittedly, 1.7M rows but that doesn't explain the insane numbers shown in the query plan:

https://www.brentozar.com/pastetheplan/?id=H1iahxHAe

If I can hammer flat all those scans I can reduce the query time significantly, but first of all: how do I interpret those numbers to find a solution?

The days table contains 7.6 k rows (to cover years 2000-2020).

Answer 1

Let's start by looking at the top right of the plan. That part calculates the OperatingDate column:

Since we get back 1.72 M rows for the outer row set we can expect around 1.72 M index seeks against ix_days. That is indeed what happens. There are 478k rows for which o.[CreationDate] as time) > '16:00:00' so the CASE statement sends 478k seeks to one branch and the rest to the other.

Note that the index that you have isn't the most efficient one possible for this query. We can only do a seek predicate against PKDate. The rest of the filters are applied as a predicate. This means that the seek might traverse many rows before finding a match. I assume that most days in your calendar table aren't weekends or holidays so it may not make a practical difference for this query. However, you could define an index on is_weekend, is_holiday, PKDate. That should let you immediately seek to the first row that you want.

To make the point more clear let's go through a simple example:

-- does a scan
SELECT TOP 1 PkDate
FROM [Days]
WHERE is_weekend <> 1 AND is_holiday <> 1
AND PkDate >= '2000-04-01'
ORDER BY PkDate;

-- does a seek, reads 3 rows to return 1
SELECT TOP 1 PkDate
FROM [Days]
WHERE is_weekend = 0 AND is_holiday = 0
AND PkDate >= '2000-04-01'
ORDER BY PkDate;

-- create new index
CREATE NONCLUSTERED INDEX [ix_days_2] ON [dbo].[days]
(
    [is_weekend],
    [is_holiday],
    PkDate
)

-- does a seek, reads 1 row to return 1
SELECT TOP 1 PkDate
FROM [Days]
WHERE is_weekend = 0 AND is_holiday = 0
AND PkDate >= '2000-04-01'
ORDER BY PkDate;

DROP INDEX [days].[ix_days_2];

Let's get to the more interesting part which is the branch to calculate the DeliveryDate column. I'll only include half of it:

I suspect that what you hoped the optimizer would do is to calculate this as a scalar:

dateadd(day,isnull(
                  (select top 1 [operatingdays]
                  from [dbo].[CS]
                  where DefaultService = 1)
                 ,2)+1,Cast(o.[CreationDate] as date))

And to use the value of that to do an index seek using ix_days. Unfortunately, the optimizer does not do that. It instead applies a row goal against the index and does a scan. For each row returned from the scan it checks to see if the value matches the filter against [dbo].[CS]. The scan stops as soon as it finds one row that matches. SQL Server estimated that it would only pull back 3.33 rows on average from the scan until it found a match. If that were true then you'd see around 1.5 M executions against [dbo].[CS]. Instead the optimizer did 2 billion executions against the table, so the estimate was off by over 1000 times.

As a general rule you should carefully examine any scans on the inner side of a nested loop. Of course, there are some queries for which that is what you want. And just because you have a seek doesn't mean that the query will be efficient. For example, if a seek returns many rows there may not be that much difference from doing a scan. You didn't post the full query here, but I'll go over a few ideas which could help.

This query is a bit odd:

select top 1 [operatingdays]
from [dbo].[CS]
where DefaultService = 1

It is non-deterministic because you have TOP without ORDER BY. However, the table itself has 1 row and you always pull back the same value for each row from o. If possible, I would just try saving off the value of this query into a local variable and using that in the query instead. That should save you a total of 8 billion scans again [dbo].[CS] and I would expect to see an index seek instead of an index scan against ix_days. I was able to mock up some data on my machine. Here is part of the query plan:

Now we have all seeks and those seeks shouldn't process too many extra rows. However, the real query may be more complicated than that so perhaps you can't use a variable.

Let's say I write a different filter condition that doesn't use TOP. Instead I'll use MIN. SQL Server is able to process that subquery in a more efficient way. TOP can prevent certain query transformations. Here is my subquery:

WHERE PKDate > dateadd(day,isnull(
                      (select MIN([operatingdays])
                       from [dbo].[CS]
                       where DefaultService = 1)
                      ,2), Cast(o.[CreationDate] as date))

Here is what the plan might look like:

Now we'll only do around 1.5 million scans against the CS table. we also get a much more efficient index seek against the ix_days index which is able to use the results of the subquery:

Of course, I'm not saying that you should rewrite your code to use that. It'll probably return incorrect results. The important point is that you can get the index seeks that you want with a subquery. You just need to write your subquery in the right way.

For one more example, let's assume that you absolutely need to keep the TOP operator in the subquery. It might be possible to add a redundant filter against PkDate to get better performance. I'm going to assume that the results of the subquery are non-negative and small. That means that this query will be equivalent:

  PKDate > Cast(o.[CreationDate] as date) AND 
  PKDate > dateadd(day,isnull(
      (select top 1 [operatingdays]
      from [dbo].[CS]
      where DefaultService = 1)
     ,2)+1,Cast(o.[CreationDate] as date))

This changes the plan to use seeks:

It's important to realize that the seeks may return more just one row. The important point is that SQL Server can start seeking at o.[CreationDate]. If there's a large gap in the dates then the index seek will process many extra rows and the query will not be as efficient.

Answer 2

Now the question is, related to index scans and number of executions: why the 2 BILLION? Or 6 Billion?

You are getting those numbers from nested loop join.

In its simplest form, a nested loops join compares each row from one

table (known as the outer table) to each row from the other table (known as the inner table) looking for rows that satisfy the join predicate. (Note that the terms “inner” and “outer” are overloaded; their meaning must be inferred from context. “Inner table” and “outer table” refer to the inputs to the join. “Inner join” and “outer join” refer to the logical operations.)

We can express the algorithm in pseudo-code as:

for each row R1 in the outer table for each row R2 in the inner table if R1 joins with R2 return (R1, R2)

It’s the nesting of the for loops in this algorithm that gives nested loops join its name.

The total number of rows compared and, thus, the cost of this algorithm is proportional to the size of the outer table multiplied by the size of the inner table. Since this cost grows quickly as the size of the input tables grow, in practice we try to minimize the cost by reducing the number of inner rows that we must consider for each outer row.]1

In your this is one example how you get about 2B records.

Another one how you get 5B+.

Few links about how you can avoid large nested loop join:

1. How to optimize a query that's running slow on Nested Loops (Inner Join)
2. https://stackoverflow.com/questions/28441468/why-are-nested-loops-chosen-causing-long-execution-time-for-self-join
3. https://www.littlekendra.com/2016/09/06/estimated-vs-actual-number-of-rows-in-nested-loop-operators/

Answer 3

The information that both other answers try to convey but fail (only partly due to assumptions that I understand exactly what they say) is this:

With the query written the way it was in the question the observed performance was inevitable.

While it was fancy and mostly easy to see the purpose it was simply too heavy for the optimizer to work magic on it. It wasn't quite the nested loop problem SqlWorldWide indicated, but the subqueries simply had to be executed for each row and since they were index seeks and scans they multiplied, and multiplied... and multiplied.

What I ended up having was this:

Select
    OID
   ,case when
     Cast(o.[CreationDate] as time) > '16:00:00' 
        then (select top 1 [PKDate] from [calendar].[dbo].days
              where is_workday = 1 and continuous_day > da.continuous_day
              and continuous_day < da.continuous_day+7 order by PKDate asc)
        else (select top 1 [PKDate] from [calendar].[dbo].days
              where is_workday = 1 and continuous_day >= da.continuous_day
              and continuous_day < da.continuous_day+7 order by PKDate asc)
        end  OperatingDate
   ,case when
     Cast(o.[CreationDate] as time) > '16:00:00' 
        then (select top 1 d.[PKDate] from [calendar].[dbo].days d
              where is_workday = 1 and
              continuous_day > (da.continuous_day+isnull(dt.DeliveryDays,2)) and 
              d.continuous_day < da.continuous_day+7 order by PKDate asc)
            else (select top 1 d.[PKDate] from [calendar].[dbo].days d
              where is_workday = 1 and
              continuous_day >= (da.continuous_day+isnull(dt.DeliveryDays,2)) and 
              d.continuous_day < da.continuous_day+7 order by PKDate asc)
            end EstimatedDeliveryDate
  ,(select dateadd(day,3,o.[CreationDate])) DeliveryDate
From o
left join deliverytype dt on o.deliverytypeid = dt.deliverytypeid
join calendar.dbo.days da on (cast o.creationdate as date) = da.pkdate

In addition to streamlining the query - which still is not optimal - I've also reworked the calendar.dbo.days table's indexes. Dropped the constraint (which I really didn't have to, but what the hell, it might cause more problems further down the line) and added this:

/****** Object:  Index [ixc_days]    Script Date: 20/04/2017 10:40:58 ******/
CREATE UNIQUE CLUSTERED INDEX [ixc_days] ON [dbo].[days]
(
    [PKDate] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF,
IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF,
ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

SET ANSI_PADDING ON

GO

/****** Object:  Index [ix_days]    Script Date: 20/04/2017 10:40:58 ******/
CREATE NONCLUSTERED INDEX [ix_days] ON [dbo].[days]
(
    [is_workday] ASC,
    [PKDate] ASC,
    [continuous_day] ASC
)
INCLUDE (   [calendar_year],
    [calendar_month],
    [calendar_week_in_year],
    [calendar_week_in_month],
    [calendar_day_in_year],
    [calendar_day_in_week],
    [calendar_day_in_month],
    [dmy_name_long],
    [description]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON,
ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

I admit it is mostly so that I can more fully utilize the calendar table (did I mention that Jim Horn is a genius?), but the moment my accounts people saw it they want more and more of the goodies it stores... everywhere.

SO, to bottom line is that while it is important to look at all aspects of the query: logic, indexes, predicates etc., sometimes the only sensible way to improve things is to change the code. In my case the execution time of the full query (several inserts, updates and CTEs) now finishes in about 2 mins, compared to 15 min before.