Forçando fluxo distinto

O otimizador do SQL Server não pode produzir o plano de execução desejado com a garantia necessária, porque o operador Hash Match Flow Distinct não preserva a ordem.

No entanto, não tenho certeza (e suspeito que não) se isso realmente garante o pedido.

Você pode observar a preservação da ordem em muitos casos, mas este é um detalhe de implementação; não há garantia, então você não pode confiar nele. Como sempre, a ordem de apresentação só pode ser garantida por uma ORDER BYcláusula de nível superior.

Exemplo

O script abaixo mostra que Hash Match Flow Distinct não preserva a ordem. Ele configura a tabela em questão com números correspondentes de 1 a 50.000 em ambas as colunas:

IF OBJECT_ID(N'dbo.Updates', N'U') IS NOT NULL
    DROP TABLE dbo.Updates;
GO
CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1),
    ObjectId INT NOT NULL,

    CONSTRAINT PK_Updates_UpdateId PRIMARY KEY (UpdateId)
);
GO
INSERT dbo.Updates (ObjectId)
SELECT TOP (50000)
    ObjectId =
        ROW_NUMBER() OVER (
            ORDER BY C1.[object_id]) 
FROM sys.columns AS C1
CROSS JOIN sys.columns AS C2
ORDER BY
    ObjectId;

A consulta de teste é:

DECLARE @Rows bigint = 50000;

-- Optimized for 1 row, but will be 50,000 when executed
SELECT DISTINCT TOP (@Rows)
    U.ObjectId 
FROM dbo.Updates AS U
WHERE 
    U.UpdateId > 0
OPTION (OPTIMIZE FOR (@Rows = 1));

O plano estimado mostra um índice de busca e fluxo distinto:

A saída certamente parece ordenada para começar:

...mas os valores mais abaixo começam a 'faltar':

...e eventualmente:

A explicação, neste caso específico, é que o operador de hash derrama:

Uma vez que uma partição se espalha, todas as linhas que fazem hash para a mesma partição também se espalham. As partições derramadas são processadas posteriormente, quebrando a expectativa de que valores distintos encontrados sejam emitidos imediatamente na sequência em que são recebidos.

Há muitas maneiras de escrever uma consulta eficiente para produzir o resultado ordenado que você deseja, como recursão ou usando um cursor. No entanto, isso não pode ser feito usando Hash Match Flow Distinct .

Estou insatisfeito com esta resposta porque não consegui obter um operador distinto de fluxo junto com resultados que eram garantidos como corretos. No entanto, tenho uma alternativa que deve obter um bom desempenho junto com resultados corretos. Infelizmente, isso requer que um índice não clusterizado seja criado na tabela.

Abordei esse problema tentando pensar em uma combinação de colunas que pudesse ORDER BYe obter os resultados corretos depois de aplicar DISTINCTa elas. O valor mínimo de UpdateIdper ObjectIdjunto com ObjectIdé uma dessas combinações. No entanto, pedir diretamente o mínimo UpdateIdparece resultar na leitura de todas as linhas da tabela. Em vez disso, podemos solicitar indiretamente o valor mínimo de UpdateIdcom outra junção à tabela. A ideia é varrer a Updatestabela em ordem, descartar todas as linhas para as quais UpdateIdnão é o valor mínimo para essa linha ObjectIde manter as primeiras 100 linhas. Com base em sua descrição da distribuição de dados, não deveríamos precisar descartar muitas linhas.

Para preparação de dados, coloquei 1 milhão de linhas em uma tabela com 2 linhas para cada ObjectId distinto:

INSERT INTO Updates WITH (TABLOCK)
SELECT t.RN / 2
FROM 
(
    SELECT TOP 1000000 -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) t;

CREATE INDEX IX On Updates (Objectid, UpdateId);

O índice não clusterizado em Objectide UpdateIdé importante. Ele nos permite descartar com eficiência linhas que não têm o mínimo UpdateIdpor Objectid. Há muitas maneiras de escrever uma consulta que corresponda à descrição acima. Aqui está uma maneira usando NOT EXISTS:

DECLARE @fromUpdateId INT = 9999;
SELECT ObjectId
FROM (
    SELECT DISTINCT TOP 100 u1.UpdateId, u1.ObjectId
    FROM Updates u1
    WHERE UpdateId > @fromUpdateId
    AND NOT EXISTS (
        SELECT 1
        FROM Updates u2
        WHERE u2.UpdateId > @fromUpdateId
        AND u1.ObjectId = u2.ObjectId
        AND u2.UpdateId < u1.UpdateId
    )
    ORDER BY u1.UpdateId, u1.ObjectId
) t;

Aqui está uma imagem do plano de consulta :

Na melhor das hipóteses, o SQL Server fará apenas 100 buscas de índice em relação ao índice não clusterizado. Para simular ter muito azar eu mudei a consulta para retornar as primeiras 5000 linhas para o cliente. Isso resultou em 9.999 buscas de índice, então é como obter uma média de 100 linhas por ObjectId. Aqui está a saída de SET STATISTICS IO, TIME ON:

Tabela 'Atualizações'. Contagem de varredura 10.000, leituras lógicas 31.900, leituras físicas 0

Tempos de execução do SQL Server: tempo de CPU = 31 ms, tempo decorrido = 42 ms.

Eu amo a pergunta - Flow Distinct é um dos meus operadores favoritos.

Agora, a garantia é o problema. Quando você pensa no operador FD puxando linhas do operador Seek de forma ordenada, produzindo cada linha conforme determina que ela seja única, isso lhe dará as linhas na ordem correta. Mas é difícil saber se pode haver alguns cenários em que o FD não lida com uma única linha de cada vez.

Teoricamente, o FD poderia solicitar 100 linhas do Seek e produzi-las na ordem que precisar.

As dicas de consulta OPTION (FAST 1, MAXDOP 1)podem ajudar, porque evitarão obter mais linhas do que o necessário do operador Seek. Mas é uma garantia ? Não exatamente. Ele ainda pode decidir puxar uma página de linhas de cada vez, ou algo assim.

Acho que com OPTION (FAST 1, MAXDOP 1), sua OFFSETversão lhe daria muita confiança sobre o pedido, mas não é uma garantia.