Forzar flujo distintivo

Tengo una mesa como esta:

CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
    ObjectId INT NOT NULL
)

Esencialmente, el seguimiento de las actualizaciones de los objetos con una identificación creciente

El consumidor de esta tabla seleccionará un trozo de 100 ID de objetos distintos, ordenados por UpdateIdy a partir de un específico UpdateId. Esencialmente, hacer un seguimiento de dónde se quedó y luego consultar cualquier actualización.

He encontrado que esto sea un problema de optimización interesante porque sólo he sido capaz de generar un plan de consulta óptimo máximo escribiendo consultas que suceden a hacer lo que quiero, debido a los índices, pero no garantizo lo que quiero:

SELECT DISTINCT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId

Donde @fromUpdateIdes un parámetro de procedimiento almacenado.

Con un plan de:

SELECT <- TOP <- Hash match (flow distinct, 100 rows touched) <- Index seek

Debido a la búsqueda en el UpdateIdíndice que se está utilizando, los resultados ya son agradables y están ordenados de la ID de actualización más baja a la más alta como quiero. Y esto genera un plan de flujo distinto , que es lo que quiero. Pero el orden obviamente no es un comportamiento garantizado, por lo que no quiero usarlo.

Este truco también da como resultado el mismo plan de consulta (aunque con un TOP redundante):

WITH ids AS
(
    SELECT ObjectId
    FROM Updates
    WHERE UpdateId > @fromUpdateId
    ORDER BY UpdateId OFFSET 0 ROWS
)
SELECT DISTINCT TOP 100 ObjectId FROM ids

Sin embargo, no estoy seguro (y sospecho que no) si esto realmente garantiza el pedido.

Una consulta que esperaba que SQL Server fuera lo suficientemente inteligente como para simplificar fue esta, pero termina generando un plan de consulta muy malo:

SELECT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId
GROUP BY ObjectId
ORDER BY MIN(UpdateId)

Con un plan de:

SELECT <- Top N Sort <- Hash Match aggregate (50,000+ rows touched) <- Index Seek

Estoy tratando de encontrar una manera de generar un plan óptimo con una búsqueda de índice UpdateIdy un flujo distinto para eliminar los duplicados ObjectId. ¿Algunas ideas?

Datos de muestra si lo desea. Los objetos rara vez tendrán más de una actualización, y casi nunca deberían tener más de una dentro de un conjunto de 100 filas, por lo que busco un flujo distinto , a menos que haya algo mejor que no conozca. Sin embargo, no hay garantía de que una sola ObjectIdno tenga más de 100 filas en la tabla. La tabla tiene más de 1,000,000 de filas y se espera que crezca rápidamente.

Suponga que el usuario de esto tiene otra forma de encontrar el siguiente apropiado @fromUpdateId. No es necesario devolverlo en esta consulta.

El optimizador de SQL Server no puede producir el plan de ejecución que está buscando con la garantía que necesita, porque el operador Hash Match Flow Distinct no conserva la orden.

Sin embargo, no estoy seguro (y sospecho que no) si esto realmente garantiza el pedido.

Puede observar la preservación del orden en muchos casos, pero este es un detalle de implementación; no hay garantía, por lo que no puede confiar en ella. Como siempre, el orden de presentación solo puede garantizarse mediante una ORDER BYcláusula de nivel superior .

Ejemplo

El siguiente script muestra que Hash Match Flow Distinct no conserva el orden. Configura la tabla en cuestión con números coincidentes 1-50,000 en ambas columnas:

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;

La consulta de prueba es:

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

El plan estimado muestra un índice de búsqueda y flujo distinto:

La salida ciertamente parece ordenada para comenzar con:

... pero más abajo los valores comienzan a faltar:

... y eventualmente:

La explicación en este caso particular, es que el operador hash derrama:

Una vez que se derrama una partición, también se derraman todas las filas que se combinan con la misma partición. Las particiones derramadas se procesan más tarde, rompiendo la expectativa de que se emitirán valores distintos encontrados inmediatamente en la secuencia en que se reciben.

Hay muchas formas de escribir una consulta eficiente para producir el resultado ordenado que desea, como la recursividad o el uso de un cursor. Sin embargo, no se puede hacer usando Hash Match Flow Distinct .

No estoy satisfecho con esta respuesta porque no pude obtener un operador distinto de flujo junto con resultados que se garantizaban que eran correctos. Sin embargo, tengo una alternativa que debería obtener un buen rendimiento junto con resultados correctos. Desafortunadamente, requiere que se cree un índice no agrupado en la tabla.

Abordé este problema tratando de pensar en una combinación de columnas que pudiera ORDER BYy obtener los resultados correctos después de aplicarlas DISTINCT. El valor mínimo de UpdateIdper ObjectIdjunto con ObjectIdes una de esas combinaciones. Sin embargo, pedir directamente el mínimo UpdateIdparece resultar en la lectura de todas las filas de la tabla. En cambio, podemos pedir indirectamente el valor mínimo de UpdateIdcon otra unión a la tabla. La idea es escanear la Updatestabla en orden, tirar cualquier fila para la que UpdateIdno sea el valor mínimo de esa fila ObjectIdy mantener las primeras 100 filas. Según su descripción de la distribución de datos, no deberíamos necesitar tirar muchas filas.

Para la preparación de datos, puse 1 millón de filas en una tabla con 2 filas 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);

El índice no agrupado en Objectidy UpdateIdes importante. Nos permite tirar eficientemente filas que no tienen el mínimo UpdateIdpor Objectid. Hay muchas formas de escribir una consulta que coincida con la descripción anterior. Aquí hay una manera de usar 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;

Aquí hay una imagen del plan de consulta :

En el mejor de los casos, SQL Server solo realizará 100 búsquedas de índice contra el índice no agrupado. Para simular ser muy desafortunado, cambié la consulta para devolver las primeras 5000 filas al cliente. Eso dio como resultado 9999 búsquedas de índice, por lo que es como obtener un promedio de 100 filas por distintivo ObjectId. Aquí está la salida de SET STATISTICS IO, TIME ON:

Tabla 'Actualizaciones'. Cuenta de escaneo 10000, lecturas lógicas 31900, lecturas físicas 0

Tiempos de ejecución de SQL Server: tiempo de CPU = 31 ms, tiempo transcurrido = 42 ms.

Me encanta la pregunta: Flow Distinct es uno de mis operadores favoritos.

Ahora, la garantía es el problema. Cuando piensa en el operador FD que extrae filas del operador Seek de manera ordenada, produciendo cada fila como determina que es única, esto le dará las filas en el orden correcto. Pero es difícil saber si puede haber algunos escenarios en los que el FD no maneja una sola fila a la vez.

Teóricamente, el FD podría solicitar 100 filas de Seek y producirlas en el orden que las necesite.

Las sugerencias de consulta OPTION (FAST 1, MAXDOP 1)podrían ayudar, ya que evitará obtener más filas de las que necesita del operador Seek. Sin embargo, ¿es una garantía ? No exactamente. Todavía podría decidir tirar de una página de filas a la vez, o algo así.

Creo que con OPTION (FAST 1, MAXDOP 1)su OFFSETversión le daría mucha confianza sobre el pedido, pero no es una garantía.