Symptoms
Assume that you run a query involving a join or aggregation on a column that's covered by both single column and multiple column statistics (in which this column is not the leading column). If you are using default Cardinality Estimator (CE) in SQL Server 2016, it may underestimate number of distinct rows. This leads to a sub-optimal query execution plan (for example: low estimation may cause insufficient memory grant for a hash operator, which cause the query to spill to tempdb).
Status
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.
Resolution
This issue is fixed in the following cumulative update for SQL Server:
Note In order for this fix to take effect, you have to enable Query Optimizer Hotfixes using Trace Flag (TF) 4199 or corresponding database scoped configuration or query hint option.
About cumulative updates for SQL Server:
Each new cumulative update for SQL Server contains all the hotfixes and all the security fixes that were included with the previous cumulative update. Check out the latest cumulative updates for SQL Server:
Workaround
This issue can be fixed by adding the following query hint:
USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION')
References
Learn about the terminology that Microsoft uses to describe software updates.