Inside the SQL Server Query Optimizer - part 3 Cardinality estimation

Hi guys!

After the simplification phase discussed in the last article, today we will speak about another fundamental step called Cardinality Estimation.

During this step the optimizer try to predict the number of rows returned by each node of the execution plan.
As you can imagine this is a step of primary importance because a good prediction generate an accurate execution plan with a lower processing cost to execute.

The statistics

In order to estimate the number of rows returned by a query the Cardinality Estimator use so called statistics.

By default for each column and each index created, SQL Server create it's relative statistic.

But what is a statistic?

A statististic for query optimization is a binary large object called BLOBs that contain statistical information about the distribution of values for one o more columns of a table.

We can observe statistics through the T-SQL command:
       
DBCC SHOW_STATISTICS ( <TABLE> , <FIELD_NAME> )

The execution of this command will show you a grid with a bunch of rows called histogram statistics.




How to read the Histogram above?

For a value in the RANGE_HI_KEY columns (eg."214230003200000") the EQ_ROWS will tell your how much rows there are (eg. 4 rows).

Single Predicate (the simplest case)

Now, we will start with the simplest case.
Estimate the number of rows qualified returned by a single query predicate.
This is an easy case for the Optimizer.

Suppose to execute this following simple query:
       
SELECT * FROM <TABLE> WHERE FIELD_NAME = '214230003200000'
Looking at the execution plan, using the statistics, the optimizer correctly indicate an estimated Number of Rows equal to 4.







Multiple predicates

As we have just seen, if we have a Query where the WHERE clause has only one predicate everything is simple!

If instead we have more than one predicate? ...what happens? 

Suppose having two predicate, we can go back to two extreme cases:
  • One of the two sets generated by the (two) predicates, considered individually, overlaps the other.
  • The two sets are disjoint.

Taking into consideration for the moment only the case in which the two predicates are connected by an AND operator
 
In the first case the result will be the cardinality of the part in common of the two set, while in the second case the result will be the empty set.

What is not known is the cardinality of the elements in common to the two sets.

For this reason, it is also easy to understand that having only statistics for single fields it is not possible to calculate an exact cardinality value.

As we will see below, there are formulas that allow us to estimate this value!
 

An example with two predicates connected by an AND operator

Given a PERSON table with these fields:


 
Suppose to execute this Query with two conditions in the predicate:

       
Select CAP, PIVA from Person where (CAP BETWEEN '10000' AND '400000') AND  PIVA = '00759680218'

A) When I search the CAP field (CAP BETWEEN '10000' AND '400000')

Using statistics, estimated number of row is equal to 111





B) When I search the PIVA field (PIVA = '00759680218')

Using statistics, estimated number of row is equal to 13



And now? ...what is the number of rows estimated when the two conditions are placed in AND?

Well, before SQL Server 2014 the two conditions are considerated independent among them.


So the Optimizer apply this formula:



So, ( 13 * 111 ) / 512 = 2,818

 




Sql Server 2014 introduce a new cardinality estimator (CE) who assume some correlation between the predicates.

New CE adopt a new formula called exponential backoff algorithm:



In this case we have:

So, 512 * ( 13 / 512) * SQRT(111 / 512) =  6,052

And actually: 



And now another question!

What cardinality estimator produced the better rows number estimation?

OLD CE = 2,8
NEW CE = 6,4

Our Query return ….



…. 13 Rows!

 

In this case the NEW CE produce a better estimation for this Query but in general it depends:

If you have data with correlating predicates the new CE is likely to give you a better estimate and therefore a better plan.
However, if your predicates have no correlation, you may find the legacy CE to provide a better estimate.


That's all for today!
I hope  you liked this article.
Look forward to the next part of this series of articles

Luca Biondi @ SQLServerPerformance blog!



 

 

 

 

Next post: SQL Server, Again info about statistics and the "Ascending Key Problem"   

Previous post: Inside the SQL Server Query Optimizer - part 2 All about the Simplification

Comments

Post a Comment

I Post più popolari

SQL Server, execution plan and the lazy spool (clearly explained)

Image
Hi Guys, Welcome back! In one of the last posts we talked about Table Spool . We had explained what Spool are for by telling the somewhat curious story of the halloween problem . Here we specifically talked about a type of spool called Eager Spool   You can look to the execution plan below where the eager Spool is used to avoid the halloween problem in classic query of the "salary increase".. i suggest Well, if the story of the eager spool intrigued you, today instead we will speak about another type of Spool, the Lazy Spool . The Lazy spool Let's take a small step back. So, what is a Spool operation?  As we have already understood a spool operation is simply a temporary storage of data . Data are read from a source table and stored inside a worktable in the Tempdb database . While an Eager Spool is used to prevent the Halloween problem, the Lazy Spool is instead used to store data that will later be needed again when running a query . So, when a Lazy spool is used?    I
Read more

SQL Server, datetime vs. datetime2

Image
Hi guys, This time, in this post we will speak about datetime and datetime2 datatypes. We will talk about the pros and cons. We will talk about all the differences between the two types of data. Write me in the comments which type of data do you prefer between the two. Enjoy the reading!     Datetime Vs. Datetime2 First of all, it must be said that the datatype datetime is certainly the best known native format for storing a date in SQL Server. However, Microsoft has also been introducing a new type of data for many years now, also used to manage dates. It is in fact from SQL server 2008 that it is present in datetime2 data type. This "new" type of data was born primarily to have higher accuracy . Let's in fact talk about ... precision ! Datetime Certainly the datetime data type is not very precise and certainly there are many cases in which its precision is simply not sufficient. Let's see it with an example. Open the SQL Management studio (SSMS) and write the fo
Read more

La clausola NOLOCK. Approfondiamo e facciamo chiarezza!

Image
Ehi ragazzi! La domanda è di quelle importanti! Siete pronti per scoprire tutto ma proprio tutto sulla clausola NOLOCK?   Se la riposta è si, allora seguitemi! Oggi ne spiegheremo il funzionamento in maniera approfondita. Faremo una introduzione al concetto di tipi di LOCK Ed infine vedremo come mai una SELECT ne può bloccare un'altra. Non vi nascondo che il motivo di questo articolo è fare chiarezza. Su questo argomento si sentono spesso affermazioni “curiose” ma tra le tante questa è la prima: “ uso la SELECT con l’opzione WITH(LOCK) così non blocco le altre tabelle ”.   Ma, è proprio vero quanto affermato? Beh oggi facciamo il punto!   Buona lettura!     La clausola NOLOCK Diciamo subito per iniziare che cos’è la NOLOCK. NOLOCK è il nome di una clausola che è possibile specificare all’interno di uno statement di tipo SELECT utilizzando la seguente sintassi: SELECT * FROM TABELLA WITH (NOLOCK) Si noti che non possiamo utilizzare questa cl
Read more