Argthtjtr

Long story short, we're updating small tables of people with values from a very large table of people. In a recent test, this update takes ca 5 minutes to run.

We stumbled upon what seems like the silliest optimization possible, that seemingly works perfectly! The same query now runs in less than 2 minutes and produces the same results, perfectly.

Here is the query. The last line is added as "the optimization". Why the intense decrease in query time? Are we missing something? Could this lead to problems in the future?

UPDATE smallTbl

SET smallTbl.importantValue = largeTbl.importantValue

FROM smallTableOfPeople smallTbl

JOIN largeTableOfPeople largeTbl

    ON largeTbl.birth_date = smallTbl.birthDate

    AND DIFFERENCE(TRIM(smallTbl.last_name),TRIM(largeTbl.last_name)) = 4

    AND DIFFERENCE(TRIM(smallTbl.first_name),TRIM(largeTbl.first_name)) = 4

WHERE smallTbl.importantValue IS NULL

-- The following line is "the optimization"

AND LEFT(TRIM(largeTbl.last_name), 1) IN ('a','à','á','b','c','d','e','è','é','f','g','h','i','j','k','l','m','n','o','ô','ö','p','q','r','s','t','u','ü','v','w','x','y','z','æ','ä','ø','å')

Technical notes: We are aware that the list of letters to test might need a few more letters. We are also aware of the obvious margin for error when using "DIFFERENCE".

Query plan (regular): https://www.brentozar.com/pastetheplan/?id=rypV84y7V
Query plan (with "optimization"): https://www.brentozar.com/pastetheplan/?id=r1aC2my7E

It depends on the data in your tables, your indexes, .... Hard to say without being able to compare the execution plans / the io + time statistics.

The difference I would expect is the extra filtering happening before the JOIN between the two tables.
In my example, I changed the updates to selects to reuse my tables.

The execution plan with "the optimization"

Execution Plan

You clearly see a filter operation happening, in my test data no records where filtered out and as a result no improvements where made.

The execution plan, without "the optimization"

Execution Plan

The filter is gone, which means that we will have to rely on the join to filter out unneeded records.

Other reason(s)
Another reason / consequence of changing the query could be, that a new execution plan was created when changing the query, which happens to be faster.
An example of this is the engine choosing a different Join operator, but that is just guessing at this point.

EDIT:

Clarifying after getting the two query plans:

The query is reading 550M Rows from the big table, and filtering them out.

Meaning that the predicate is the one doing most of the filtering, not the seek predicate. Resulting in the data being read, but way less being returned.

Making sql server use a different index (query plan) / adding an index could resolve this.

So why doesn't the optimize query have this same issue?

Because a different query plan is used, with a scan instead of a seek.

Without doing any seeks, but only returning 4M rows to work with.

Next difference

Disregarding the update difference ( nothing is being updated on the optimized query)
a hash match is used on the optimized query:

Instead of a nested loop join on the non-optimized:

A nested loop is best when one table is small and the other one big. Since they are both close to the same size I would argue that the hash match is the better choice in this case.

Overview

The optimized query

The Optimized query's plan has parallellism, uses a hash match join, and needs to do less residual IO filtering. It also uses a bitmap to eliminate key values that cannot produce any join rows . (Also nothing is being updated)

The non-optimized query

The non-Optimized query's plan has no parallellism, uses a nested loop join, and needs to do residual IO filtering on 550M records. (Also the update is happening)

What could you do to improve the non-optimized query?

• 
  

  Changing the index to have first_name & last_name in the key column
  list:

  
  
  

  CREATE INDEX IX_largeTableOfPeople_birth_date_first_name_last_name
  on dbo.largeTableOfPeople(birth_date,first_name,last_name)
  include(id)

  
  

But due to the use of functions and this table being big this might not be the optimal solution.

• Updating statistics, using recompile to try and get the better plan.


• Adding OPTION(HASH JOIN, MERGE JOIN) to the query


• ...

Test data + Queries used

CREATE TABLE #smallTableOfPeople(importantValue int, birthDate datetime2, first_name varchar(50),last_name varchar(50));

CREATE TABLE #largeTableOfPeople(importantValue int, birth_date datetime2, first_name varchar(50),last_name varchar(50));





set nocount on;

DECLARE @i int = 1

WHILE @i <= 1000

BEGIN

insert into #smallTableOfPeople (importantValue,birthDate,first_name,last_name)

VALUES(NULL, dateadd(mi,@i,'2018-01-18 11:05:29.067'),'Frodo','Baggins');



set @i += 1;

END





set nocount on;

DECLARE @j int = 1

WHILE @j <= 20000

BEGIN

insert into #largeTableOfPeople (importantValue,birth_Date,first_name,last_name)

VALUES(@j, dateadd(mi,@j,'2018-01-18 11:05:29.067'),'Frodo','Baggins');



set @j += 1;

END





SET STATISTICS IO, TIME ON;



SELECT  smallTbl.importantValue , largeTbl.importantValue

FROM #smallTableOfPeople smallTbl

JOIN #largeTableOfPeople largeTbl

    ON largeTbl.birth_date = smallTbl.birthDate

    AND DIFFERENCE(RTRIM(LTRIM(smallTbl.last_name)),RTRIM(LTRIM(largeTbl.last_name))) = 4

    AND DIFFERENCE(RTRIM(LTRIM(smallTbl.first_name)),RTRIM(LTRIM(largeTbl.first_name))) = 4

WHERE smallTbl.importantValue IS NULL

-- The following line is "the optimization"

AND LEFT(RTRIM(LTRIM(largeTbl.last_name)), 1) IN ('a','à','á','b','c','d','e','è','é','f','g','h','i','j','k','l','m','n','o','ô','ö','p','q','r','s','t','u','ü','v','w','x','y','z','æ','ä','ø','å');



SELECT  smallTbl.importantValue , largeTbl.importantValue

FROM #smallTableOfPeople smallTbl

JOIN #largeTableOfPeople largeTbl

    ON largeTbl.birth_date = smallTbl.birthDate

    AND DIFFERENCE(RTRIM(LTRIM(smallTbl.last_name)),RTRIM(LTRIM(largeTbl.last_name))) = 4

    AND DIFFERENCE(RTRIM(LTRIM(smallTbl.first_name)),RTRIM(LTRIM(largeTbl.first_name))) = 4

WHERE smallTbl.importantValue IS NULL

-- The following line is "the optimization"

--AND LEFT(RTRIM(LTRIM(largeTbl.last_name)), 1) IN ('a','à','á','b','c','d','e','è','é','f','g','h','i','j','k','l','m','n','o','ô','ö','p','q','r','s','t','u','ü','v','w','x','y','z','æ','ä','ø','å')









drop table #largeTableOfPeople;

drop table #smallTableOfPeople;

It is not clear that the second query is in fact an improvement.

The execution plans contain QueryTimeStats that show a much less dramatic difference than stated in the question.

The slow plan had an elapsed time of 257,556 ms (4 mins 17 seconds). The fast plan had an elapsed time of 190,992 ms (3 mins 11 seconds) despite running with a degree of parallelism of 3.

Moreover the second plan was running in a database where there was no work to do after the join.

First Plan

Second Plan

So that extra time could well be explained by the work needed to update 3.5 million rows (the work required in the update operator to locate these rows, latch the page, write the update to the page and transaction log is not negligible)

If this is in fact reproducible when comparing like with like then the explanation is that you just got lucky in this case.

The filter with the 37 IN conditions only eliminated 51 rows out of the 4,008,334 in the table but the optimiser considered it would eliminate much more

   LEFT(TRIM(largeTbl.last_name), 1) IN ( 'a', 'à', 'á', 'b',

                                          'c', 'd', 'e', 'è',

                                          'é', 'f', 'g', 'h',

                                          'i', 'j', 'k', 'l',

                                          'm', 'n', 'o', 'ô',

                                          'ö', 'p', 'q', 'r',

                                          's', 't', 'u', 'ü',

                                          'v', 'w', 'x', 'y',

                                          'z', 'æ', 'ä', 'ø', 'å' ) 

Such incorrect cardinality estimations are usually a bad thing. In this case it produced a differently shaped (and parallel) plan which apparently (?) worked better for you despite the hash spills caused by the massive underestimate.

Without the TRIM SQL Server is able to convert this to a range interval in the base column histogram and give much more accurate estimates but with the TRIM it just resorts to guesses.

The nature of the guess can vary but the estimate for a single predicate on LEFT(TRIM(largeTbl.last_name), 1) is in some circumstances ^* just estimated to be table_cardinality/estimated_number_of_distinct_column_values.

_{I'm not sure exactly what circumstances - size of data seems to play a part. I was able to reproduce this with wide fixed length datatypes as here but got a different, higher, guess with varchar (which just used a flat 10% guess and estimated 100,000 rows). @Solomon Rutzky points out that if the varchar(100) is padded with trailing spaces as happens for char the lower estimate is used}

The IN list is expanded out to OR and SQL Server uses exponential backoff with a maximum of 4 predicates considered. So the 219.707 estimate is arrived at as follows.

DECLARE @TableCardinality FLOAT = 4008334, 

        @DistinctColumnValueEstimate FLOAT = 34207



DECLARE @NotSelectivity float = 1 - (1/@DistinctColumnValueEstimate)



SELECT @TableCardinality * ( 1 - (

@NotSelectivity * 

SQRT(@NotSelectivity) * 

SQRT(SQRT(@NotSelectivity)) * 

SQRT(SQRT(SQRT(@NotSelectivity)))

))