¿Por qué esta estimación de cardinalidad de unión es tan grande?

Estoy experimentando lo que creo que es una estimación de cardinalidad imposiblemente alta para la siguiente consulta:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

El plan estimado está aquí . Estoy trabajando en una copia estadística de las tablas, así que no puedo incluir un plan real. Sin embargo, no creo que sea muy relevante para este problema.

SQL Server estima que se devolverán 481577 filas de la tabla derivada "dm". Luego estima que se devolverán 4528030000 filas después de que se realice la unión a X_LAST_TABLE, pero JOIN_ID es la clave principal de X_LAST_TIME. Esperaría una estimación de cardinalidad de unión entre 0 y 481577 filas. En cambio, la estimación de filas parece ser el 10% del número de filas que obtendría al unir de forma cruzada las tablas externa e interna. La matemática para esto funciona con redondeo: 481577 * 94025 * 0.1 = 45280277425 que se redondea a 4528030000.

Estoy buscando principalmente una causa raíz de este comportamiento. También estoy interesado en soluciones simples, pero no sugiera cambiar el modelo de datos o usar tablas temporales. Esta consulta es una simplificación de la lógica dentro de una vista. Sé que hacer COALESCE en algunas columnas y unirse a ellas no es una buena práctica. Parte del objetivo de esta pregunta es averiguar si necesito recomendar que se rediseñe el modelo de datos.

Estoy probando en Microsoft SQL Server 2014 con el estimador de cardinalidad heredado habilitado. TF 4199 y otros están encendidos. Puedo dar una lista completa de marcas de seguimiento si eso termina siendo relevante.

Aquí está la definición de tabla más relevante:

CREATE TABLE X_LAST_TABLE (
JOIN_ID NUMERIC(18, 0) NOT NULL
    CONSTRAINT PK_X_LAST_TABLE PRIMARY KEY CLUSTERED (JOIN_ID ASC)
);

También escribí todos los scripts de creación de tablas junto con sus estadísticas si alguien quiere reproducir el problema en uno de sus servidores.

Para agregar algunas de mis observaciones, usar TF 2312 corrige la estimación, pero esa no es una opción para mí. TF 2301 no fija la estimación. Eliminar una de las tablas corrige la estimación. Curiosamente, cambiar el orden de unión de X_DETAIL_LINK también corrige la estimación. Al cambiar el orden de unión me refiero a reescribir la consulta y no forzar el orden de unión con una pista. Aquí hay un plan de consulta estimado cuando solo se cambia el orden de las uniones.

Sé que hacer COALESCEalgunas columnas y unirlas no es una buena práctica.

Generar buenas estimaciones de cardinalidad y distribución es bastante difícil cuando el esquema es 3NF + (con claves y restricciones) y la consulta es relacional y principalmente SPJG (select-projection-join-group by). El modelo CE se basa en esos principios. Mientras más características inusuales o no relacionales haya en una consulta, más se acerca a los límites de lo que puede manejar el marco de cardinalidad y selectividad. Vaya demasiado lejos y CE se rendirá y adivinará .

La mayor parte del ejemplo de MCVE es SPJ simple (sin G), aunque con predominantemente equijoins externos (modelados como unión interna más anti-semiunión) en lugar del equijoin interno más simple (o semiunión). Todas las relaciones tienen claves, aunque no claves externas u otras restricciones. Todas menos una de las uniones son de uno a muchos, lo cual es bueno.

La excepción es la unión externa de muchos a muchos entre X_DETAIL_1y X_DETAIL_LINK. La única función de esta unión en MCVE es duplicar potencialmente las filas X_DETAIL_1. Este es un tipo de cosa inusual .

Los predicados de igualdad simples (selecciones) y los operadores escalares también son mejores. Por ejemplo, el atributo compare-equal attribute / constant normalmente funciona bien en el modelo. Es relativamente "fácil" modificar histogramas y estadísticas de frecuencia para reflejar la aplicación de tales predicados.

COALESCEestá construido sobre CASE, que a su vez se implementa internamente como IIF(y esto era cierto mucho antes de que IIFapareciera en el lenguaje Transact-SQL). Los modelos CE IIFcomo UNIONcon dos niños mutuamente excluyentes, cada uno compuesto de un proyecto en una selección de la relación de entrada. Cada uno de los componentes enumerados tiene soporte de modelo, por lo que combinarlos es relativamente sencillo. Aun así, cuanto más capas uno abstracciones, menos preciso tiende a ser el resultado final, razón por la cual los planes de ejecución más grandes tienden a ser menos estables y confiables.

ISNULL, por otro lado, es intrínseco al motor. No se construye utilizando más componentes básicos. Aplicar el efecto de ISNULLun histograma, por ejemplo, es tan simple como reemplazar el paso por NULLvalores (y compactar según sea necesario). Todavía es relativamente opaco, como lo hacen los operadores escalares, y es mejor evitarlo siempre que sea posible. Sin embargo, en general, es más optimista (menos optimista) que una CASEalternativa basada en el optimizador .

El CE (70 y 120+) es muy complejo, incluso para los estándares de SQL Server. No se trata de aplicar una lógica simple (con una fórmula secreta) a cada operador. El CE sabe sobre claves y dependencias funcionales; sabe cómo estimar usando frecuencias, estadísticas multivariadas e histogramas; y hay una tonelada absoluta de casos especiales, refinamientos, controles y equilibrios, y estructuras de soporte. A menudo estima, por ejemplo, las uniones de múltiples maneras (frecuencia, histograma) y decide un resultado o ajuste basado en las diferencias entre los dos.

Una última cosa básica para cubrir: la estimación de cardinalidad inicial se ejecuta para cada operación en el árbol de consulta, de abajo hacia arriba. La selectividad y la cardinalidad se derivan primero para los operadores de hoja (relaciones base). Los histogramas modificados y la información de densidad / frecuencia se derivan para los operadores principales. Cuanto más avanzamos en el árbol, menor es la calidad de las estimaciones, ya que los errores tienden a acumularse.

Esta única estimación integral inicial proporciona un punto de partida, y ocurre mucho antes de que se considere cualquier plan de ejecución final (ocurre mucho antes incluso de la etapa de compilación del plan trivial). El árbol de consultas en este punto tiende a reflejar la forma escrita de la consulta con bastante atención (aunque con las subconsultas eliminadas y las simplificaciones aplicadas, etc.)

Inmediatamente después de la estimación inicial, SQL Server realiza un reordenamiento de la unión heurística, que en términos generales trata de reordenar el árbol para colocar primero las tablas más pequeñas y las uniones de alta selectividad. También trata de colocar uniones internas antes de uniones externas y productos cruzados. Sus capacidades no son extensas; sus esfuerzos no son exhaustivos; y no tiene en cuenta los costos físicos (dado que aún no existen, solo hay información estadística e información de metadatos). El reordenamiento heurístico es más exitoso en los árboles de equijoin internos simples. Existe para proporcionar un "mejor" punto de partida para la optimización basada en costos.

¿Por qué esta estimación de cardinalidad de unión es tan grande?

El MCVE tiene una unión de muchos a muchos "inusual", en su mayoría redundante , y una unión equi COALESCEen el predicado. El árbol del operador también tiene una unión interna al final , cuyo reordenamiento de la unión heurística no pudo mover el árbol a una posición más preferida. Dejando a un lado todos los escalares y proyecciones, el árbol de unión es:

LogOp_Join [ Card=4.52803e+009 ]
    LogOp_LeftOuterJoin [ Card=481577 ]
        LogOp_LeftOuterJoin [ Card=481577 ]
            LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_Get TBL: X_DRIVING_TABLE(alias TBL: dt) [ Card=481577 ]
                LogOp_Get TBL: X_DETAIL_1(alias TBL: d1) [ Card=70 ]
                LogOp_Get TBL: X_DETAIL_LINK(alias TBL: lnk) [ Card=47 ]
            LogOp_Get TBL: X_DETAIL_2(alias TBL: d2) X_DETAIL_2 [ Card=119 ]
        LogOp_Get TBL: X_DETAIL_3(alias TBL: d3) X_DETAIL_3 [ Card=281 ]
    LogOp_Get TBL: X_LAST_TABLE(alias TBL: lst) X_LAST_TABLE [ Card=94025 ]

Tenga en cuenta que la estimación final defectuosa ya está en su lugar. Se imprime Card=4.52803e+009y almacena internamente como el valor de coma flotante de doble precisión 4.5280277425e + 9 (4528027742.5 en decimal).

La tabla derivada en la consulta original se ha eliminado y las proyecciones se han normalizado. Una representación SQL del árbol en el que se realizó la estimación inicial de cardinalidad y selectividad es:

SELECT 
    PRIMARY_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)
FROM X_DRIVING_TABLE dt
LEFT OUTER JOIN X_DETAIL_1 d1
    ON dt.ID = d1.ID
LEFT OUTER JOIN X_DETAIL_LINK lnk 
    ON d1.LINK_ID = lnk.LINK_ID
LEFT OUTER JOIN X_DETAIL_2 d2 
    ON dt.ID = d2.ID
LEFT OUTER JOIN X_DETAIL_3 d3 
    ON dt.ID = d3.ID
INNER JOIN X_LAST_TABLE lst 
    ON lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)

(Como comentario aparte, lo repetido COALESCEtambién está presente en el plan final: una vez en el Escalar de cómputo final y otra en el lado interno de la unión interna).

Observe la unión final. Esta unión interna es (por definición) el producto cartesiano X_LAST_TABLEy la salida de unión anterior, con una selección (predicado de unión) de lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)aplicado. La cardinalidad del producto cartesiano es simplemente 481577 * 94025 = 45280277425.

Para eso, necesitamos determinar y aplicar la selectividad del predicado. La combinación del COALESCEárbol expandido opaco (en términos de , UNIONy IIFrecuerde) junto con el impacto en la información clave, los histogramas y las frecuencias derivadas de la combinación externa de muchos a muchos "inusual" anterior redundante en su mayoría combinada significa que el CE no puede derivar una estimación aceptable en cualquiera de las formas normales.

Como resultado, entra en la lógica de la conjetura. La lógica de conjetura es moderadamente compleja, con capas de conjeturas "educadas" y algoritmos de conjetura "no tan educados" probados. Si no se encuentra una mejor base para una suposición, el modelo utiliza una suposición de último recurso, que para una comparación de igualdad es: sqllang!x_Selectivity_Equal= selectividad 0.1 fija (10% de suposición):

-- the moment of doom
movsd xmm0,mmword ptr [sqllang!x_Selectivity_Equal

El resultado es 0.1 selectividad en el producto cartesiano: 481577 * 94025 * 0.1 = 4528027742.5 (~ 4.52803e + 009) como se mencionó anteriormente.

Reescribe

Cuando se comenta la unión problemática , se produce una mejor estimación porque se evita la "conjetura de último recurso" de selectividad fija (las uniones 1-M retienen la información clave). La calidad de la estimación sigue siendo de baja confianza, porque un COALESCEpredicado de unión no es en absoluto compatible con CE. La estimación revisada al menos parece más razonable para los humanos, supongo.

Cuando la consulta se escribe con la combinación externa en X_DETAIL_LINK último lugar , el reordenamiento heurístico puede intercambiarla con la combinación interna final en X_LAST_TABLE. Al colocar la unión interna justo al lado de la unión externa problemática, las habilidades limitadas de reordenamiento temprano tienen la oportunidad de mejorar la estimación final, ya que los efectos de la unión externa de muchos a muchos "inusual", en su mayoría redundantes, se producen después de la difícil estimación de selectividad para COALESCE. Una vez más, las estimaciones son poco mejores que las conjeturas fijas, y probablemente no resistirían un interrogatorio determinado en un tribunal de justicia.

Reordenar una mezcla de uniones internas y externas es difícil y requiere mucho tiempo (incluso la optimización completa de la etapa 2 solo intenta un subconjunto limitado de movimientos teóricos).

El anidado ISNULLsugerido en la respuesta de Max Vernon se las arregla para evitar la conjetura fija de rescate, pero la estimación final es un cero improbable filas (elevado a una fila por decencia). Esto también podría ser una suposición fija de 1 fila, para toda la base estadística que tiene el cálculo.

Esperaría una estimación de cardinalidad de unión entre 0 y 481577 filas.

Esta es una expectativa razonable, incluso si uno acepta que la estimación de la cardinalidad puede ocurrir en diferentes momentos (durante la optimización basada en el costo) en subárboles físicamente diferentes, pero idénticos lógica y semánticamente, siendo el plan final una especie de lo mejor mejor (por grupo de notas). La falta de una garantía de coherencia en todo el plan no significa que una unión individual deba ser capaz de ignorar la respetabilidad, lo entiendo.

Por otro lado, si terminamos con la suposición de último recurso , la esperanza ya está perdida, entonces, ¿por qué molestarse? Probamos todos los trucos que conocíamos y nos rendimos. Si nada más, la estimación final salvaje es una gran señal de advertencia de que no todo salió bien dentro del CE durante la compilación y optimización de esta consulta.

Cuando probé el MCVE, el CE de más de 120 produjo una estimación final de fila cero (= 1) (como la anidada ISNULL) para la consulta original, que es tan inaceptable para mi forma de pensar.

La solución real probablemente implica un cambio de diseño, para permitir equi-uniones simples sin COALESCEo ISNULL, e idealmente claves foráneas y otras restricciones útiles para la compilación de consultas.

Creo que el Compute Scalaroperador resultante de la COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)unión X_LAST_TABLE.JOIN_IDes la causa principal del problema. Históricamente, los escalares computacionales han sido difíciles de costar con precisión ^{1 , 2} .

Dado que ha proporcionado un ejemplo verificable mínimamente completo (¡gracias!) Con estadísticas precisas, puedo volver a escribir la consulta de modo que la unión ya no requiera la CASEfuncionalidad que COALESCEse expande, lo que resulta en estimaciones de filas mucho más precisas, y aparentemente más costeo exacto general ^{Consulte el anexo al final.} :

SELECT COALESCE(dm.d1ID, dm.d2ID, dm.d3ID)
FROM
(
    SELECT d1ID = d1.JOIN_ID
        , d2ID = d2.JOIN_ID
        , d3ID = d3.JOIN_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst 
    ON (dm.d1ID IS NOT NULL AND dm.d1ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NOT NULL AND dm.d2ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NULL AND dm.d3ID IS NOT NULL AND dm.d3ID = lst.JOIN_ID);

Si bien xID IS NOT NULLno es técnicamente necesario, ya ID = JOIN_IDque no se unirá en valores nulos, los incluí ya que retrata más claramente la intención.

Plan 1 y Plan 2

Plan 1:

Plan 2:

La nueva consulta se beneficia (?) De la paralelización. También cabe destacar que la nueva consulta tiene un número estimado de salida de filas de 1, que de hecho puede ser peor al final del día que la estimación de 4528030000 para la consulta original. El costo del subárbol para el operador seleccionado en la nueva consulta se encuentra en 243210, mientras que el original se registra en 536.535, que es claramente menor. Dicho esto, no creo que la primera estimación esté cerca de la realidad.

Anexo 1.

Después de una consulta adicional con varias personas en The Heap ™ impulsada por una discusión con @Lamak, parece que mi consulta de observación anterior funciona terriblemente, incluso con el paralelismo. Una solución que permite tanto un buen rendimiento como buenas estimaciones de cardinalidad consiste en reemplazar el COALESCE(x,y,z)con un ISNULL(ISNULL(x, y), z), como en:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT ISNULL(ISNULL(d1.JOIN_ID, d2.JOIN_ID), d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

COALESCEse transforma en una CASEdeclaración "debajo de las cubiertas" por el optimizador de consultas. Como tal, el estimador de cardinalidad tiene más dificultades para descubrir estadísticas confiables para columnas enterradas en su interior COALESCE. ISNULLser una función intrínseca es mucho más "abierta" para el estimador de cardinalidad. Tampoco vale nada que ISNULLpueda optimizarse si se sabe que el objetivo no es anulable.

El plan para la ISNULLvariante se ve así:

(Pegue la versión del Plan aquí ).

FYI, apoya a Sentry One por su gran Plan Explorer, que utilicé para producir los planes gráficos anteriores.

Según su condición de unión, la tabla se puede organizar de muchas maneras, eso es "cambiar de una manera particular" para arreglar el resultado.

Supongamos que unir solo una tabla le da el resultado correcto.

SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID

Aquí en lugar de X_DETAIL_1, puede usar cualquiera X_DETAIL_2o X_DETAIL_3.

Por lo tanto, el propósito del descanso 2 tablas no está claro.

Es como si hubieras dividido la mesa X_DETAIL_1en 2 partes más.

Lo más probable " hay un error en el que está completando esas tablas. " Lo ideal X_DETAIL_1, X_DETAIL_2y X_DETAIL_3debe contener la misma cantidad de filas.

Pero una o más tablas contienen un número no deseado de filas.

Lo siento si me equivoco.