No SQL Server, posso garantir um pedido sem uma cláusula ORDER BY explícita quando uma pesquisa de índice é forçada em uma tabela com apenas um índice em cluster?

24

Atualização 18/12/2014

Com a resposta esmagadora à pergunta principal sendo "Não", as respostas mais interessantes se concentraram na parte 2, como resolver o quebra-cabeça do desempenho de forma explícita ORDER BY. Embora eu já tenha marcado uma resposta, não ficaria surpreso se houvesse uma solução com desempenho ainda melhor.

Original

Essa questão surgiu porque a única solução extremamente rápida que eu poderia encontrar para um problema em particular só funciona sem uma ORDER BYcláusula. Abaixo está o T-SQL completo necessário para produzir o problema, juntamente com a minha solução proposta (estou usando o SQL Server 2008 R2, se isso for importante).

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

Aqui estão os planos de execução para as soluções A e B, respectivamente:

Sol A

Sol B

A solução A fornece o desempenho necessário, mas não consegui fazê-lo funcionar com o mesmo desempenho ao adicionar qualquer cláusula ORDER BY (por exemplo, consulte a Solução B). E certamente parece que a Solução A teria que entregar seus resultados em ordem, pois 1) a tabela possui apenas um índice, 2) uma busca é forçada, eliminando assim a possibilidade de usar uma verificação de ordem de alocação com base nas páginas do IAM .

Então, minhas perguntas são:

  1. Estou certo de que garantirá a ordem neste caso sem uma ordem por cláusula?

  2. Caso contrário, existe outro método para forçar um plano tão rápido quanto a Solução A, preferencialmente um método que evite classificações? Observe que ele precisaria resolver exatamente o mesmo problema (para StoreID = 1encontrar os 500 principais clientes pedidos pelo valor de compra mais caro). Também seria necessário usar a #Orderstabela, mas diferentes esquemas de indexação seriam aceitáveis.

sql-server JohnnyM
fonte
16
O pedido só é garantido se você usar ORDER BY.
Alroc
8
" Estou certo de que garantirá a ordem neste caso sem uma ordem por cláusula " - não, absolutamente não.
a_horse_with_no_name
3
Aqui está um artigo que faz um ótimo trabalho explicando isso. blogs.msdn.com/b/conor_cunningham_msft/archive/2008/08/27/…
Sean Lange
@SeanLange: Como você e outras pessoas, não me sinto à vontade para deixar de fora o pedido pelas mesmas razões. No entanto, a) não consigo encontrar uma consulta com o mesmo desempenho que a Solução A que usa ORDER BY eb) não conheço nenhuma maneira de ordená-las incorretamente. Você? Não estou dizendo que não há uma maneira, apenas não conheço uma, e esperava que alguém pudesse articular uma, se ela existisse. Mesmo os exemplos no artigo que você referenciou se aplicam apenas a verificações não solicitadas.
JohnnyM
ATUALIZAÇÃO: alterei o tipo de dados da quantia e o método de cálculo para evitar tantas duplicatas. Todos os princípios ainda se aplicam. Embora neste problema eu não me importo com quem ganha quando há um empate, ter tantos empates dificultou a visualização do que estava acontecendo ao observar os dados. É muito mais claro agora que, exceto pelos empates, as soluções A e B produzem os mesmos resultados.
precisa

Respostas:

23
  1. Estou certo de que garantirá a ordem neste caso sem uma ordem por cláusula?

Não. Um fluxo distinto que preserva a ordem (permitindo ORDER BYsem classificação) não está implementado no SQL Server hoje. É possível fazer isso em princípio, mas muitas coisas serão possíveis se tivermos permissão para alterar o código-fonte do SQL Server. Se você pode defender esse trabalho de desenvolvimento, sugira-o à Microsoft .

  1. Caso contrário, existe outro método para forçar um plano tão rápido quanto a Solução A, preferencialmente um método que evite classificações?

Sim. (Dicas de tabela e consulta necessárias apenas ao usar o estimador de cardinalidade anterior a 2014):

-- 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);

Plano de execução real

(500 row(s) affected)

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 4 ms.

Solução SQL CLR

O script a seguir mostra o uso de uma função com valor de tabela do SQL CLR para atender aos requisitos declarados. Como eu não sou especialista em C #, o código pode ter melhorias:

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;

Tabela de teste e dados de amostra da pergunta:

-- 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);

Teste de funcionamento:

-- 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());

Plano de execução (observe a validação da ORDERgarantia):

Plano de execução da função CLR

No meu laptop, isso geralmente é executado em 80-100ms. Isso não chega nem perto da velocidade da reescrita do T-SQL acima, mas deve mostrar boa estabilidade de desempenho diante das diferentes distribuições de dados.

Código fonte:

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;
    }
}
Paul White diz que a GoFundMonica
fonte
6

Sem ORDER BYmuitas coisas podem dar errado. Você excluiu todos os problemas possíveis em que consigo pensar, mas isso não significa que não há nenhum problema nem haverá um em uma versão futura.

Isso deve funcionar:

Puxe lotes de 500 linhas da tabela em um loop e pare quando tiver 500 IDs de clientes distintos. A consulta de busca pode ficar assim:

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

Isso executará uma verificação de intervalo ordenada no índice. O Amount <= @lastAmountFetchedpredicado está lá para extrair incrementalmente mais registros. Cada consulta toca apenas fisicamente em 500 registros. Isso significa que é O (1). Não fica mais caro quanto mais você entra no índice.

É necessário manter a variável @lastAmountFetchedpara diminuir para o menor valor que você buscou nessa instrução.

Dessa forma, você fará a varredura incremental do índice de maneira ordenada. Você lerá no máximo (500 - 1) linhas mais do que a quantidade ideal seria.

Isso será muito mais rápido do que sempre agregar mais de 100000 pedidos para uma loja específica. Provavelmente, apenas algumas iterações de 500 linhas cada serão necessárias.

Essencialmente, este é um operador distinto de fluxo codificado manualmente.

Como alternativa, use um cursor para buscar o menor número possível de linhas. Isso será muito mais lento porque a execução de 500 consultas de linha única na maioria das vezes é mais lenta do que a execução de um lote de 500 linhas.

Como alternativa, basta consultar todas as linhas sem DISTINCTuma ordem ordenada e fazer com que o aplicativo cliente encerre a consulta assim que retornar linhas suficientes (usando SqlCommand.Cancel).

usr
fonte
11
Falta um detalhe crucial - como você garantirá #fetchedOrdersque não contenha clientes que já vimos? Presumivelmente, isso envolve uma busca de índice na tabela temporária, que não é exatamente a mesma coisa que um "fluxo distinta" e não ficar mais caros os mais linhas que vimos (embora ainda vai bater solução B em todos, mas o pior caso de ter que verificar todas as linhas porque há apenas um cliente, para o qual A e B terão desempenho idêntico).
2
@JeroenMostert - IGNORE_DUP_KEYpoderia fazer isso.
Martin Smith
@usr: Obrigado por isso. Eu o codifiquei usando IGNORE_DUP_KEY e corri os números e obtive o tempo da CPU = 31ms, tempo decorrido = 27ms. Embora seja muito mais rápido que a Solução B, não está nem perto da Solução A (cpu = 0, ms = 1), que, para meus propósitos, precisa ser. Quando você disse: "Você excluiu todos os problemas possíveis em que consigo pensar", fico imaginando se excluí todos os problemas em que alguém possa pensar. O mais frustrante é que eu posso imaginar o que o SQL precisa fazer para obter o desempenho de A, só não sei como contar isso usando um ORDER BY.
JohnnyM