sql-server add tag
johnnym (imported from SE)
**Update 2014-12-18** 

With the overwhelming response to the main question being "No", the more interesting responses have focused on part 2, how to solve the performance puzzle with an explicit `ORDER BY`.  Although I've marked an answer already, I wouldn't be surprised if there were an even better performing solution.

**Original**

This question arose because the only extremely fast solution I could find to a particular problem only works without an `ORDER BY` clause. Below is the full T-SQL needed to produce the problem, along with my proposed solution (I am using SQL Server 2008 R2, if that matters.)

    --Create Orders table
    IF OBJECT_ID('tempdb..#Orders') IS NOT NULL DROP TABLE #Orders
    CREATE TABLE #Orders
    (  
           OrderID    INT NOT NULL IDENTITY(1,1)
         , CustID     INT NOT NULL
         , StoreID    INT NOT NULL       
         , Amount     FLOAT NOT NULL
    )
    CREATE CLUSTERED INDEX IX ON #Orders (StoreID, Amount DESC, CustID)
    
    --Add 1 million rows w/ 100K Customers each of whom had 10 orders
    ;WITH  
        Cte0 AS (SELECT 1 AS C UNION ALL SELECT 1), --2 rows  
        Cte1 AS (SELECT 1 AS C FROM Cte0 AS A, Cte0 AS B),--4 rows  
        Cte2 AS (SELECT 1 AS C FROM Cte1 AS A ,Cte1 AS B),--16 rows 
        Cte3 AS (SELECT 1 AS C FROM Cte2 AS A ,Cte2 AS B),--256 rows 
        Cte4 AS (SELECT 1 AS C FROM Cte3 AS A ,Cte3 AS B),--65536 rows 
        Cte5 AS (SELECT 1 AS C FROM Cte4 AS A ,Cte2 AS B),--1048576 rows 
        FinalCte AS (SELECT  ROW_NUMBER() OVER (ORDER BY C) AS Number FROM   Cte5)
    INSERT INTO #Orders (CustID, StoreID, Amount)
    SELECT CustID = Number / 10
         , StoreID    = Number % 4
         , Amount     = 1000 * RAND(Number)
    FROM  FinalCte
    WHERE Number <= 1000000
    
    SET STATISTICS IO ON
    SET STATISTICS TIME ON
    
    --For StoreID = 1, find the top 500 customers ordered by their most expensive purchase (Amount)
    
    --Solution A: Without ORDER BY
    DECLARE @Top INT = 500
    SELECT DISTINCT TOP (@Top) CustID
    FROM #Orders WITH(FORCESEEK)
    WHERE StoreID = 1
    OPTION(OPTIMIZE FOR (@Top = 1), FAST 1);
    --9 logical reads, CPU Time = 0 ms, elapsed time = 1 ms
    GO
    --Solution B: With ORDER BY
    DECLARE @Top INT = 500
    SELECT TOP (@Top) CustID
    FROM #Orders
    WHERE StoreID = 1
    GROUP BY CustID
    ORDER BY MAX(Amount) DESC
    OPTION(MAXDOP 1)
    --745 logical reads, CPU Time = 141 ms, elapsed time = 145 ms
    --Uses Sort operator
    
    GO

Here are the execution plans for Solution A and B, respectively:

![Sol A][1]

![Sol B][2]

Solution A gives the performance I need, but I couldn't get it to work with the same performance when adding any kind ORDER BY clause (e.g., see Solution B).  And it certainly seems like Solution A would have to deliver its results in order, since 1) the table has only one index on it, 2) a seek is forced, thus eliminating the possibility of its using an allocation order scan based on IAM pages.  

So my questions are:

1. Am I right that it will guarantee the order in this case without an order by clause?

2. If not, is there another method to force a plan that is as fast as Solution A, preferably one that avoids sorts? Note that it would have to solve the exact same problem (for `StoreID = 1`, find the top 500 customers ordered by their most expensive purchase amount). It would also have to still use the `#Orders` table, but different indexing schemes would be OK.


  [1]: http://i.stack.imgur.com/PhZLn.jpg
  [2]: http://i.stack.imgur.com/K3kZJ.jpg
Top Answer
Paul White
>1. Am I right that it will guarantee the order in this case without an order by clause?

**No.** A *Flow Distinct* that preserves order (allowing `ORDER BY` without a sort) is not implemented in SQL Server today. It is possible to do in principle, but then many things are possible if we are allowed to change the SQL Server source code. If you can make a good case for this development work, you could [suggest it to Microsoft][1].

>2. If not, is there another method to force a plan that is as fast as Solution A, preferably one that avoids sorts?

**Yes.** (Table & query hints only required when using the pre-2014 cardinality estimator):

    -- Additional index
    CREATE UNIQUE NONCLUSTERED INDEX i 
    ON #Orders (StoreID, CustID, Amount, OrderID);

    -- Query
    SELECT TOP (500) 
    	O.CustID, 
    	O.Amount
    FROM #Orders AS O
        WITH (FORCESEEK(IX (StoreID)))
    WHERE O.StoreID = 1
    AND NOT EXISTS
    (
    	SELECT NULL
    	FROM #Orders AS O2
            WITH (FORCESEEK(i (StoreID, CustID, Amount)))
    	WHERE 
    		O2.StoreID = O.StoreID
    		AND O2.CustID = O.CustID
    		AND O2.Amount >= O.Amount
    		AND
    		(
    			O2.Amount > O.Amount
    			OR
    			(
    				O2.Amount = O.Amount
    				AND O2.OrderID > O.OrderID
    			)
    		)
    )
    ORDER BY
    	O.Amount DESC
    OPTION (MAXDOP 1);

![Actual Execution Plan][2]

    (500 row(s) affected)
    
     SQL Server Execution Times:
       CPU time = 0 ms,  elapsed time = 4 ms.

### SQL CLR solution

The following script shows using a SQL CLR table-valued function to meet the stated requirements. I am not a C# expert, so the code may bear improvement:

    USE Sandpit;
    GO
    -- Ensure SQLCLR is enabled
    EXECUTE sys.sp_configure
    	@configname = 'clr enabled',
        @configvalue = 1;
    RECONFIGURE;
    GO
    -- Lazy, but effective to allow EXTERNAL_ACCESS
    ALTER DATABASE Sandpit
    SET TRUSTWORTHY ON;
    GO
    -- The CLR assembly
    CREATE ASSEMBLY FlowDistinctOrder
    AUTHORIZATION dbo
    FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C010300881F94540000000000000000E00002210B010B000010000000060000000000004E2F0000002000000040000000000010002000000002000004000000000000000400000000000000008000000002000000000000030040850000100000100000000010000010000000000000100000000000000000000000FC2E00004F00000000400000C802000000000000000000000000000000000000006000000C000000C42D00001C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000540F0000002000000010000000020000000000000000000000000000200000602E72737263000000C8020000004000000004000000120000000000000000000000000000400000402E72656C6F6300000C0000000060000000020000001600000000000000000000000000004000004200000000000000000000000000000000302F00000000000048000000020005009C210000280C000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001B300300CB00000001000011280700000A730800000A730900000A0A730A00000A0B071F0A6F0B00000A07026F0C00000A07166F0D00000A07036F0E00000A07176F0F00000A076F1000000A731100000A0C086F1200000A086F1300000A0D0972010000706F1400000A096F1500000A13062B321106166F1600000A13041106176F1700000A13050611056F1800000A2D1406110511046F1900000A066F1A00000A6A042E0911066F1B00000A2DC5DE0C11062C0711066F1C00000ADCDE0A092C06096F1C00000ADCDE0A082C06086F1C00000ADC062A0001280000020066003FA5000C000000000200530060B3000A000000000200460079BF000A00000000133002001A0000000200001102A50500001B0A031200281D00000A54041200281E00000A572A1E02281F00000A2A3A02281F00000A02037D2000000A2A3A027B2000000A04036F2100000A2A42534A4201000100000000000C00000076322E302E35303732370000000005006C000000EC020000237E000058030000FC03000023537472696E67730000000054070000300200002355530084090000100000002347554944000000940900009402000023426C6F620000000000000002000001571702080906000000FA25330016000001000000160000000300000001000000050000000900000001000000210000000600000002000000060000000100000003000000010000000100000000000A0001000000000006005700500006007B00600006009A0087000A000901EE0006005A013B0106008C0179011B00A00100000600CF01AF010600EF01AF010A000D02EE000600220260000E00390260000A0062024C020A00E702D4020A0016034C020A002403D4020A0036034C020A004F03D4020A0069034C020A008503D4020600C40350000600D80360000000000001000000000001000100010010002000000005000100010003011000350000000500010004002100C60026005020000000009600A600110001005021000000009600B800190004007621000000008618C000220007007E21000000008618C0002E0007008D2100000000E601CF003800080000000100D700000002001B0100000300280100000100300102000200340102000300670100000100C600000001006E01000002007301030006002100C00022002900C00022003100C00053004100C00059004900C00022005100C000220014002D02E1011C00C0002E002400C0002E006900C000220069007D02590069009002F70169009F02FC016900AA02F7016900BD02FC017100010301027900C000F70181003103220079004103050291005903F701890077030A02A10092030F02A1009B0314022400A50319022400B1031F022400B5032702A100BF032B02A900D00322002C00E70349022C00F1034E020900C00022003400C60026000C00CF003800200033005E0024000B0040002E001B0063022E0023006C022E002B00750244000B0040002F0253020A00DB01EA01F00142025C02048000000000000000000000000000000000A600000002000000000000000000000001004700000000000200000000000000000000000100E200000000000200000000000000000000000100500000000000030002000000000006005E000000003C4D6F64756C653E00466C6F7744697374696E63744F726465722E646C6C0055736572446566696E656446756E6374696F6E730052657665727365436F6D70617265726031006D73636F726C69620053797374656D004F626A65637400540053797374656D2E436F6C6C656374696F6E732E47656E657269630049436F6D706172657260310053797374656D2E436F6C6C656374696F6E730049456E756D657261626C6500466C6F7744697374696E63744F726465720046696C6C526F77002E63746F72006F726967696E616C00436F6D70617265005365727665724E616D650053797374656D2E44617461004D6963726F736F66742E53716C5365727665722E5365727665720053716C46616365744174747269627574650044617461626173654E616D65004D6178526F7773006F626A004375737449440053797374656D2E52756E74696D652E496E7465726F705365727669636573004F757441747472696275746500416D6F756E74006C6566740072696768740053797374656D2E446961676E6F73746963730044656275676761626C6541747472696275746500446562756767696E674D6F6465730053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650052756E74696D65436F6D7061746962696C6974794174747269627574650053716C46756E6374696F6E41747472696275746500436F6D70617265726031006765745F44656661756C7400536F7274656444696374696F6E61727960320053797374656D2E446174612E53716C436C69656E740053716C436F6E6E656374696F6E537472696E674275696C646572007365745F436F6E6E65637454696D656F7574007365745F44617461536F75726365007365745F456E6C697374007365745F496E697469616C436174616C6F67007365745F496E746567726174656453656375726974790053797374656D2E446174612E436F6D6D6F6E004462436F6E6E656374696F6E537472696E674275696C646572006765745F436F6E6E656374696F6E537472696E670053716C436F6E6E656374696F6E004462436F6E6E656374696F6E004F70656E0053716C436F6D6D616E6400437265617465436F6D6D616E64004462436F6D6D616E64007365745F436F6D6D616E64546578740053716C4461746152656164657200457865637574655265616465720044624461746152656164657200476574496E74333200476574446F75626C6500436F6E7461696E734B657900416464006765745F436F756E7400526561640049446973706F7361626C6500446973706F7365004B657956616C7565506169726032006765745F56616C7565006765745F4B65790000000000822D0D000A0020002000200020002000200020002000200020002000200020002000200020002000200020002000530045004C004500430054000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E004300750073007400490044002C0020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E0041006D006F0075006E0074000D000A0020002000200020002000200020002000200020002000200020002000200020002000200020002000460052004F004D002000640062006F002E004F007200640065007200730020004100530020004F000D000A00200020002000200020002000200020002000200020002000200020002000200020002000200020005700480045005200450020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E00530074006F00720065004900440020003D002000310020000D000A00200020002000200020002000200020002000200020002000200020002000200020002000200020004F00520044004500520020004200590020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E0041006D006F0075006E00740020004400450053004300008E8B082F3050554B858E01B56306C38B0008B77A5C561934E08906151209011300070003120D0E0E0A080003011C1008100D03200001070615120901130009200101151209011300072002081300130012010001005408074D617853697A658000000005200101111D0420010108817B010004005455794D6963726F736F66742E53716C5365727665722E5365727665722E446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038390A446174614163636573730100000054557F4D6963726F736F66742E53716C5365727665722E5365727665722E53797374656D446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038391053797374656D4461746141636365737300000000540E1146696C6C526F774D6574686F644E616D650746696C6C526F77540E0F5461626C65446566696E6974696F6E2643757374494420696E7465676572204E554C4C2C20416D6F756E7420666C6F6174204E554C4C0515122D010D08000015122D0113000515120C010D06151231020D08042001010E04200101020320000E0420001245042000124D04200108080420010D0805200102130007200201130013010320000803200002120707151231020D081235123D1245080D124D06151159020D0804200013010420001300080701151159020D080615120C0113000801000200000000000801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F77730100000000881F945400000000020000001C010000E02D0000E00F00005253445388411786AC332241BCB71A9315A6D3DD07000000633A5C55736572735C5061756C2057686974655C446F63756D656E74735C56697375616C2053747564696F20323031335C50726F6A656374735C466C6F7744697374696E63744F726465725C466C6F7744697374696E63744F726465725C6F626A5C52656C656173655C466C6F7744697374696E63744F726465722E70646200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000242F000000000000000000003E2F0000002000000000000000000000000000000000000000000000302F0000000000000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF250020001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000018000080000000000000000000000000000001000100000030000080000000000000000000000000000001000000000048000000584000006C02000000000000000000006C0234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000000000000000000000000000000003F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B004CC010000010053007400720069006E006700460069006C00650049006E0066006F000000A801000001003000300030003000300034006200300000002C0002000100460069006C0065004400650073006300720069007000740069006F006E000000000020000000300008000100460069006C006500560065007200730069006F006E000000000030002E0030002E0030002E00300000004C001600010049006E007400650072006E0061006C004E0061006D006500000046006C006F007700440069007300740069006E00630074004F0072006400650072002E0064006C006C0000002800020001004C006500670061006C0043006F0070007900720069006700680074000000200000005400160001004F0072006900670069006E0061006C00460069006C0065006E0061006D006500000046006C006F007700440069007300740069006E00630074004F0072006400650072002E0064006C006C000000340008000100500072006F006400750063007400560065007200730069006F006E00000030002E0030002E0030002E003000000038000800010041007300730065006D0062006C0079002000560065007200730069006F006E00000030002E0030002E0030002E003000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C000000503F00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    WITH PERMISSION_SET = EXTERNAL_ACCESS;
    GO
    -- The CLR TVF with order guarantee
    CREATE FUNCTION dbo.FlowDistinctOrder 
    (
    	@ServerName nvarchar(128), 
    	@DatabaseName nvarchar(128), 
    	@MaxRows bigint
    )
    RETURNS TABLE 
    (
    	CustID integer NULL, 
    	Amount float NULL
    )
    ORDER (Amount DESC)
    AS EXTERNAL NAME FlowDistinctOrder.UserDefinedFunctions.FlowDistinctOrder;
    
Test table and sample data from the question:

    -- Test table
    CREATE TABLE dbo.Orders
    (  
    	OrderID    integer	NOT NULL IDENTITY(1,1),
    	CustID     integer	NOT NULL,
    	StoreID    integer	NOT NULL,
    	Amount     float	NOT NULL
    );
    GO
    -- Sample data
    WITH  
    	Cte0 AS (SELECT 1 AS C UNION ALL SELECT 1), --2 rows  
    	Cte1 AS (SELECT 1 AS C FROM Cte0 AS A, Cte0 AS B),--4 rows  
    	Cte2 AS (SELECT 1 AS C FROM Cte1 AS A ,Cte1 AS B),--16 rows 
    	Cte3 AS (SELECT 1 AS C FROM Cte2 AS A ,Cte2 AS B),--256 rows 
    	Cte4 AS (SELECT 1 AS C FROM Cte3 AS A ,Cte3 AS B),--65536 rows 
    	Cte5 AS (SELECT 1 AS C FROM Cte4 AS A ,Cte2 AS B),--1048576 rows 
    	FinalCte AS (SELECT  ROW_NUMBER() OVER (ORDER BY C) AS Number FROM   Cte5)
    INSERT dbo.Orders 
    	(CustID, StoreID, Amount)
    SELECT 
    	CustID	= Number / 10,
    	StoreID = Number % 4,
    	Amount  = 1000 * RAND(Number)
    FROM FinalCte
    WHERE 
    	Number <= 1000000;
    GO
    -- Index
    CREATE CLUSTERED INDEX IX 
    ON dbo.Orders 
    	(StoreID ASC, Amount DESC, CustID ASC);

Function test:

    -- Test the function
    -- Run several times to ensure connection is cached
    -- and CLR code fully compiled
    DECLARE @Start datetime2 = SYSUTCDATETIME();

    SELECT TOP (500) 
    	FDO.CustID
    FROM dbo.FlowDistinctOrder
    (
    	@@SERVERNAME,	-- For external connection
    	DB_NAME(),		-- For external connection
    	500				-- Number of rows to return
    ) AS FDO 
    ORDER BY 
    	FDO.Amount DESC;
    
    SELECT DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());

Execution plan (note the validation of the `ORDER` guarantee):

![CLR function execution plan][3]

On my laptop, this typically executes in 80-100ms. This is nowhere near as fast as the T-SQL rewrite above, but it should show good performance stability in the face of different data distributions.

Source code:

```cs
using Microsoft.SqlServer.Server;
using System.Collections;
using System.Collections.Generic;
using System.Data.SqlClient;

public partial class UserDefinedFunctions
{
    private sealed class ReverseComparer<T> : IComparer<T>
    {
        private readonly IComparer<T> original;

        public ReverseComparer(IComparer<T> original)
        {
            this.original = original;
        }

        public int Compare(T left, T right)
        {
            return original.Compare(right, left);
        }
    }

    [SqlFunction
        (
        DataAccess = DataAccessKind.Read,
        SystemDataAccess = SystemDataAccessKind.None,
        FillRowMethodName = "FillRow",
        TableDefinition = "CustID integer NULL, Amount float NULL"
        )
    ]
    public static IEnumerable FlowDistinctOrder
        (
        [SqlFacet (MaxSize=128)]string ServerName, 
        [SqlFacet (MaxSize=128)]string DatabaseName,
        long MaxRows
        )
    {
        var list = new SortedDictionary<double, int>
            (new ReverseComparer<double>(Comparer<double>.Default));

        var csb = new SqlConnectionStringBuilder();
        csb.ConnectTimeout = 10;
        csb.DataSource = ServerName;
        csb.Enlist = false;
        csb.InitialCatalog = DatabaseName;
        csb.IntegratedSecurity = true;

        using (var conn = new SqlConnection(csb.ConnectionString))
        {
            conn.Open();
            using (var cmd = conn.CreateCommand())
            {
                cmd.CommandText =
                    @"
                    SELECT
                        O.CustID, 
                        O.Amount
                    FROM dbo.Orders AS O
                    WHERE 
                        O.StoreID = 1 
                    ORDER BY 
                        O.Amount DESC";

                int custid;
                double amount;

                using (var rdr = cmd.ExecuteReader())
                {
                    while (rdr.Read())
                    {
                        custid = rdr.GetInt32(0);
                        amount = rdr.GetDouble(1);

                        if (!list.ContainsKey(amount))
                        {
                            list.Add(amount, custid);
                            if (list.Count == MaxRows)
                            {
                                break;
                            }
                        }
                    }
                }
            }
        }
        return list;
    }

    public static void FillRow(object obj, out int CustID, out double Amount)
    {
        var v = (KeyValuePair<double, int>)obj;
        CustID = v.Value;
        Amount = v.Key;
    }
}
```

  [1]: https://docs.microsoft.com/en-us/sql/sql-server/sql-server-get-help
  [2]: https://i.stack.imgur.com/kMIm2.png
  [3]: https://i.stack.imgur.com/WDkuQ.png

This room is for discussion about this question.

Once logged in you can direct comments to any contributor here.

Enter question or answer id or url (and optionally further answer ids/urls from the same question) from

Separate each id/url with a space. No need to list your own answers; they will be imported automatically.