28

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

Sol B

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.

5
  • 16
    Ordering is only guaranteed if you use ORDER BY.
    – alroc
    Dec 17, 2014 at 18:55
  • 8
    "Am I right that it will guarantee the order in this case without an order by clause" - no, absolutely not.
    – user1822
    Dec 17, 2014 at 19:01
  • 3
    Here is an article which does a great job explaining this. blogs.msdn.com/b/conor_cunningham_msft/archive/2008/08/27/…
    – Sean Lange
    Dec 17, 2014 at 19:04
  • @SeanLange: Like you and others, I not comfortable with leaving out the order by for all the same reasons. However, a) I cannot find a query with the same performance as Solution A that uses ORDER BY, and b) I don't know of any way it could order them incorrectly. Do you? I'm not saying there isn't a way, I just don't know of one, and was hoping someone could articulate one if it existed. Even the examples in the article you referenced only applies to scans not seeks.
    – JohnnyM
    Dec 17, 2014 at 20:14
  • UPDATE: I changed the amount data type & calculation method to avoid having so many duplicates. The principles all still apply. Although in this problem I don't care who wins when there is a tie, having so many ties made it hard to see what was happening when looking at the data. It is much more clear now that except for ties, Solution A and B produce the same results.
    – JohnnyM
    Dec 17, 2014 at 21:40

2 Answers 2

24
  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. 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

(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

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:

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;
    }
}
0
6

Without an ORDER BY a lot of things can go wrong. You have excluded all possible problems that I can think of, but that does not mean that there is no problem nor will there be one in a future release.

This should work:

Pull batches of 500 rows from the table in a loop and stop when you've got 500 distinct customer IDs. The fetch query could look like this:

select TOP (500) Amount, CustID
into #fetchedOrders
from Orders
where StoreID = 1234 and Amount <= @lastAmountFetched
order by Amount DESC

This will perform an ordered range scan on the index. The Amount <= @lastAmountFetched predicate is there to incrementally pull more records. Each query will only physically touch 500 records. That means it is O(1). It does not become more expensive the farther you get into the index.

You have to maintain the variable @lastAmountFetched to decrease to the smallest value that you fetched in that statement.

This way you will incrementally scan the index in an ordered way. You will read at most (500 - 1) rows more than the optimal amount would have been.

This will be a lot faster than always aggregating 100000 or so orders for a particular store. Probably, only a few iterations of 500 rows each will be needed.

Essentially, this is a manually coded flow distinct operator.

Alternatively, use a cursor to fetch as few rows as possible. This will be a lot slower because executing 500 single-row queries most often is slower than executing a batch of 500 rows.

Alternatively, simply query all rows without DISTINCT in an ordered way and make the client application terminate the query once enough rows have been returned (using SqlCommand.Cancel).

3
  • 1
    This is lacking a crucial detail -- how are you going to ensure #fetchedOrders doesn't contain customers we've already seen? Presumably this involves an index seek on the temp table, which is not quite the same thing as a "flow distinct" and does get more expensive the more rows we've seen (although it will still beat solution B in all but the worst case of having to scan all rows because there's only one customer, for which A and B will perform identically).
    – Jeroen Mostert
    Dec 17, 2014 at 23:08
  • 2
    @JeroenMostert - IGNORE_DUP_KEY could do that. Dec 17, 2014 at 23:15
  • @usr: Thanks for this. I coded it using IGNORE_DUP_KEY & ran the numbers & got cpu time =31ms, elapsed time = 27ms. Although way faster than Solution B, it is nowhere near Solution A (cpu=0, ms=1), which for my purposes it needs to be. When you said "You have excluded all possible problems that I can think of", I'm wondering if I've excluded all the problems anyone can think of. Frustrating thing is, I can envision what SQL needs to do to get A's perf, I just don't know how to tell it using an ORDER BY.
    – JohnnyM
    Dec 17, 2014 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.