SQL Server – Excessive Sort Memory Grant

execution-planmemory-grantsql server

Why is this simple query granted so much memory?

-- Demo table
CREATE TABLE dbo.Test
(
    TID integer IDENTITY NOT NULL,
    FilterMe integer NOT NULL,
    SortMe integer NOT NULL,
    Unused nvarchar(max) NULL,

    CONSTRAINT PK_dbo_Test_TID
    PRIMARY KEY CLUSTERED (TID)
);
GO
-- 100,000 example rows
INSERT dbo.Test WITH (TABLOCKX)
    (FilterMe, SortMe)
SELECT TOP (100 * 1000)
    CHECKSUM(NEWID()) % 1000,
    CHECKSUM(NEWID())
FROM sys.all_columns AS AC1
CROSS JOIN sys.all_columns AS AC2;
GO    
-- Query
SELECT
    T.TID,
    T.FilterMe,
    T.SortMe,
    T.Unused
FROM dbo.Test AS T 
WHERE 
    T.FilterMe = 567
ORDER BY 
    T.SortMe;

For an estimated 50 rows, the optimizer reserves almost 500 MB for the sort:

Estimated plan

Best Answer

This is a bug in SQL Server (from 2008 to 2014 inclusive).

My bug report is here.

The filtering condition is pushed down into the scan operator as a residual predicate, but the memory granted for the sort is erroneously calculated based on the pre-filter cardinality estimate.

To illustrate the issue, we can use (undocumented and unsupported) trace flag 9130 to prevent the Filter from being pushed down into the scan operator. The memory granted to the sort is now correctly based on the estimated cardinality of the Filter output, not the scan:

SELECT
    T.TID,
    T.FilterMe,
    T.SortMe,
    T.Unused
FROM dbo.Test AS T 
WHERE 
    T.FilterMe = 567
ORDER BY 
    T.SortMe
OPTION (QUERYTRACEON 9130); -- Not for production systems!

Estimated plan

For a production system, steps will need to be taken to avoid the problematic plan shape (a filter pushed into a scan with a sort on another column). One way to do this is to provide an index on the filter condition and/or to provide the required sort order.

-- Index on the filter condition only
CREATE NONCLUSTERED INDEX IX_dbo_Test_FilterMe
ON dbo.Test (FilterMe);

With this index in place, the desired memory grant for the sort is only 928KB:

With filter index

Going further, the following index can avoid the sort completely (zero memory grant):

-- Provides filtering and sort order
-- nvarchar(max) column deliberately not INCLUDEd
CREATE NONCLUSTERED INDEX IX_dbo_Test_FilterMe_SortMe
ON dbo.Test (FilterMe, SortMe);

With filter and sort index

Tested and bug confirmed on the following builds of SQL Server x64 Developer Edition:

2014   : 12.00.2430 (RTM CU4)
2012   : 11.00.5556 (SP2 CU3)
2008R2 : 10.50.6000 (SP3)
2008   : 10.00.6000 (SP4)

This was fixed in SQL Server 2016 Service Pack 1. The release notes include the following:

VSTS bug number 8024987
Table scans and index scans with push down predicate tend to overestimate memory grant for the parent operator.

Tested and confirmed fixed on:

  • Microsoft SQL Server 2016 (SP1) - 13.0.4001.0 (X64) Developer Edition
  • Microsoft SQL Server 2014 (SP2-CU3) 12.0.5538.0 (X64) Developer Edition

Both CE models.

Related Question