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:
FROM dbo.Test AS T
T.FilterMe = 567
OPTION (QUERYTRACEON 9130); -- Not for production systems!
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:
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);
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.