Why is my Nested Loops join showing inaccurate row estimates in SQL Server?

Question

I have the following execution plan:

As you can see, the row estimates for the Clustered Index Scan and Index Seek operators are accurate. However, the Nested Loops join has a significant discrepancy: the actual row count is 6,420, while the estimated row count is only 72.

My questions are:

1. How is the row count estimated for a Nested Loops join in SQL Server?
2. What factors could lead to such an inaccurate row estimate in this case?
3. Is there anything I can do to improve or correct the estimate?

Thank you for any insights!

Answer 1

1. How is the row count estimated for a Nested Loops join in SQL Server?

No differently from a hash or merge join. The display in SSMS often looks different for nested loops because the inner side is per execution (when looking at a pre-execution (estimated) plan).

Fundamentally, you are asking how SQL Server estimates the selectivity of a join. The logical selectivity remains the same whatever physical implementation (nested loops, apply, hash, merge) is chosen.

The broad answer to that question is SQL Server may use one of several techniques based on histogram or frequency (distinct values) information for the join predicate column(s).

There isn't one single formula for either histogram- or frequency-based estimates. There are several modelling variations that may come into play depending on the predicates involved, the available information and database configuration.

The most important configuration factors are which cardinality estimation (CE) model you are using ('default' or 'legacy'), the database compatibility level setting, and whether you have query optimizer hotfixes enabled. That is not a complete list.

The question is exceptionally light on detail—not even providing the join predicates—so I'm not even going to speculate on a specific cause here.

2. What factors could lead to such an inaccurate row estimate in this case?

Estimates are calculated based on statistical information using SQL Server's proprietary modelling assumptions and algorithms. Given representative statistics, the most frequent cause of inaccurate estimations is a disconnect between the data and SQL Server's modelling assumptions.

3. Is there anything I can do to improve or correct the estimate?

First, ensure statistics are up to date and of good quality. Do not rely on default sampled statistics alone. You may need a higher sampling rate or even FULLSCAN to provide accurate enough information. You may also need to create additional statistics or indexes, depending on the exact nature of the join.

Once that has been established, the main things you can try are:

1. Use a different cardinality estimation model

   FORCE_DEFAULT_CARDINALITY_ESTIMATION
   FORCE_LEGACY_CARDINALITY_ESTIMATION
   

2. Use documented model variations

    ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS
    ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES
    ASSUME_FULL_INDEPENDENCE_FOR_FILTER_ESTIMATES
    ASSUME_PARTIAL_CORRELATION_FOR_FILTER_ESTIMATES
   

3. Use a different optimizer compatibility level if the estimates used to be better

    QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_n
   

The above options are all specified as a USE HINT query hint.

Resources

• Existing Q & A: What Method / Formula does a Nested Loops Operator use for row estimation?.

If you're really interested in the underlying join selectivity process or how multiple predicates are combined:

• Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator - Microsoft
• Join Estimation Internals by Dmitry Piliugin
• Join Cardinality Estimation using Histogram Coarse Alignment by me
• Cardinality Estimation for Multiple Predicates by me
• Cardinality Estimation for Disjunctive (OR) Predicates by me

Answer 2

SQL Server maintains statistics on column cardinalities and value distribution histograms, so it is able to estimate with some level of accuracy how many rows might match a particular predicate against a column, or a set of columns, of a single table. It does not, however, know how many values in a column might match a certain value in a column of a different table, i.e. it does not have the column correlation statistics.

One possible mechanism to generate and use such statistics is to allow statistics collection on plain (not materialized and not indexed) views. You would then create a view joining your two (or more) tables, and the engine would calculate a histogram of the correlated column values.

SQL Server doesn't appear to have the capability to maintain statistics on regular views, though it allows you to generate statistics on an indexed view, which one would hope might produce a similar effect, so you could try that. There will be, of course, a performance penalty of having to maintain the corresponding physical index, plus additional storage utilisation.

Answer 3

For the Nested Loops operator the "estimated" is per row from the outer table, ie per "loop", and the "actual" is the total across all loops.

See eg: https://kendralittle.com/2016/09/06/estimated-vs-actual-number-of-rows-in-nested-loop-operators/