Por que essa estimativa de cardinalidade de junção é tão grande?

Eu sei que fazer COALESCEem algumas colunas e juntar nelas não é uma boa prática.

Gerar boas estimativas de cardinalidade e distribuição é bastante difícil quando o esquema é 3NF+ (com chaves e restrições) e a consulta é relacional e principalmente SPJG (seleção-projeção-junção-grupo por). O modelo CE é construído sobre esses princípios. Quanto mais características incomuns ou não relacionais houver em uma consulta, mais próximo se chega dos limites do que a estrutura de cardinalidade e seletividade pode lidar. Vá longe demais e o CE desistirá e adivinhará .

A maior parte do exemplo MCVE é simples SPJ (sem G), embora com equijoins predominantemente externos (modelado como junção interna mais anti-semijoin) em vez do equijoin interno mais simples (ou semijoin). Todas as relações possuem chaves, embora nenhuma chave estrangeira ou outras restrições. Todas as junções, exceto uma, são um-para-muitos, o que é bom.

A exceção é a junção externa muitos-para-muitosX_DETAIL_1 entre e X_DETAIL_LINK. A única função dessa junção no MCVE é potencialmente duplicar linhas em arquivos X_DETAIL_1. Este é um tipo incomum de coisa.

Predicados de igualdade simples (seleções) e operadores escalares também são melhores. Por exemplo , o atributo/constante de comparação de atributos normalmente funciona bem no modelo. É relativamente "fácil" modificar histogramas e estatísticas de frequência para refletir a aplicação de tais predicados.

COALESCEé construído em CASE, que por sua vez é implementado internamente como IIF(e isso era verdade bem antes IIFde aparecer na linguagem Transact-SQL). O CE modela IIFcomo um UNIONcom dois filhos mutuamente exclusivos, cada um consistindo em um projeto em uma seleção na relação de entrada. Cada um dos componentes listados tem suporte de modelo, então combiná-los é relativamente simples. Mesmo assim, quanto mais camadas de abstrações, menos preciso o resultado final tende a ser - uma razão pela qual planos de execução maiores tendem a ser menos estáveis ​​e confiáveis.

ISNULL, por outro lado, é intrínseco ao motor. Não é construído usando quaisquer componentes mais básicos. Aplicar o efeito de ISNULLa um histograma, por exemplo, é tão simples quanto substituir o passo por NULLvalores (e compactar conforme necessário). Ainda é relativamente opaco, no que diz respeito aos operadores escalares e, portanto, é melhor evitá-lo sempre que possível. No entanto, em geral, é mais amigável ao otimizador (menos hostil ao otimizador) do que uma CASEalternativa baseada em.

O CE (70 e 120+) é muito complexo, mesmo para os padrões do SQL Server. Não se trata de aplicar uma lógica simples (com uma fórmula secreta) a cada operador. O CE conhece chaves e dependências funcionais; sabe estimar usando frequências, estatísticas multivariadas e histogramas; e há uma tonelada absoluta de casos especiais, refinamentos, verificações e balanços e estruturas de suporte. Ele geralmente estima, por exemplo, junções de várias maneiras (frequência, histograma) e decide sobre um resultado ou ajuste com base nas diferenças entre os dois.

Uma última coisa básica a ser abordada: a estimativa de cardinalidade inicial é executada para cada operação na árvore de consulta, de baixo para cima. A seletividade e a cardinalidade são derivadas primeiro para os operadores de folha (relações de base). Histogramas modificados e informações de densidade/frequência são derivados para operadores principais. Quanto mais subimos na árvore, menor tende a ser a qualidade das estimativas, pois os erros tendem a se acumular.

Essa única estimativa abrangente inicial fornece um ponto de partida e ocorre bem antes de qualquer consideração ser dada a um plano de execução final (acontece muito antes mesmo do estágio trivial de compilação do plano). A árvore de consulta neste ponto tende a refletir a forma escrita da consulta bastante próxima (embora com subconsultas removidas e simplificações aplicadas etc.)

Imediatamente após a estimativa inicial, o SQL Server executa a reordenação de junção heurística, que de forma geral tenta reordenar a árvore para colocar tabelas menores e junções de alta seletividade primeiro. Ele também tenta posicionar as junções internas antes das junções externas e dos produtos cruzados. Suas capacidades não são extensas; seus esforços não são exaustivos; e não considera custos físicos (pois ainda não existem - apenas informações estatísticas e informações de metadados). A reordenação heurística é mais bem-sucedida em árvores equijoin internas simples. Ele existe para fornecer um ponto de partida "melhor" para otimização baseada em custo.

Por que essa estimativa de cardinalidade de junção é tão grande?

O MCVE tem uma junção muitos-para-muitos "incomum" quase redundante e uma junção equivalente com COALESCEno predicado. A árvore do operador também possui uma junção interna por último , cujo reordenamento de junção heurística não foi capaz de mover a árvore para uma posição mais preferencial. Deixando de lado todos os escalares e projeções, a árvore de junção é:

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 ]

Observe que a estimativa final incorreta já está em vigor. Ele é impresso Card=4.52803e+009e armazenado internamente como o valor de ponto flutuante de precisão dupla 4,5280277425e+9 (4528027742,5 em decimal).

A tabela derivada na consulta original foi removida e as projeções normalizadas. Uma representação SQL da árvore na qual a estimativa inicial de cardinalidade e seletividade foi realizada é:

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 um aparte, o repetido COALESCEtambém está presente no plano final - uma vez no Compute Scalar final e uma vez no lado interno da junção interna).

Observe a junção final. Essa junção interna é (por definição) o produto cartesiano de X_LAST_TABLEe a saída da junção anterior, com uma seleção (predicado de junção) de lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)aplicado. A cardinalidade do produto cartesiano é simplesmente 481577 * 94025 = 45280277425.

Para isso, precisamos determinar e aplicar a seletividade do predicado. A combinação da árvore expandida opaca COALESCE(em termos de UNIONe IIF, lembre-se) junto com o impacto nas informações-chave, histogramas derivados e frequências da junção externa muitos-para-muitos redundante "incomum" anterior combinada significa que o CE é incapaz de derivar uma estimativa aceitável em qualquer uma das formas normais.

Como resultado, ele entra na lógica de adivinhação. A lógica de palpite é moderadamente complexa, com camadas de palpites "instruídos" e algoritmos de palpites "não tão educados" testados. Se nenhuma base melhor para uma suposição for encontrada, o modelo usa uma suposição de último recurso, que para uma comparação de igualdade é: sqllang!x_Selectivity_Equal= seletividade fixa de 0,1 (10% de suposição):

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

O resultado é 0,1 seletividade no produto cartesiano: 481577 * 94025 * 0,1 = 4528027742,5 (~4,52803e+009) conforme mencionado anteriormente.

reescreve

Quando a junção problemática é comentada , uma estimativa melhor é produzida porque a "suposição de último recurso" de seletividade fixa é evitada (as informações principais são retidas pelas junções 1-M). A qualidade da estimativa ainda é de baixa confiança, porque um COALESCEpredicado de junção não é compatível com o CE. A estimativa revisada pelo menos parece mais razoável para os humanos, suponho.

Quando a consulta é escrita com a junção externa para X_DETAIL_LINK colocada por último , a reordenação heurística é capaz de trocá-la pela junção interna final para X_LAST_TABLE. Colocar a junção interna ao lado do problema da junção externa dá às habilidades limitadas de reordenar cedo a oportunidade de melhorar a estimativa final, uma vez que os efeitos da junção externa muitos-para-muitos "incomum" e redundante vêm após a estimativa de seletividade complicada para COALESCE. Mais uma vez, as estimativas são pouco melhores do que suposições fixas e provavelmente não resistiriam a um determinado interrogatório em um tribunal.

Reordenar uma mistura de junções internas e externas é difícil e demorado (mesmo a otimização completa do estágio 2 tenta apenas um subconjunto limitado de movimentos teóricos).

O aninhado ISNULLsugerido na resposta de Max Vernon consegue evitar o palpite fixo de salvamento, mas a estimativa final é um improvável zero linhas (elevado para uma linha por decência). Isso também pode ser um palpite fixo de 1 linha, para toda a base estatística que o cálculo possui.

Eu esperaria uma estimativa de cardinalidade de junção entre 0 e 481577 linhas.

Essa é uma expectativa razoável, mesmo se aceitarmos que a estimativa de cardinalidade pode ocorrer em momentos diferentes (durante a otimização baseada em custo) em subárvores fisicamente diferentes, mas lógica e semanticamente idênticas - com o plano final sendo uma espécie de melhor costurado entre os melhor (por grupo de memorandos). A falta de uma garantia de consistência em todo o plano não significa que uma junção individual deva ser capaz de desrespeitar a respeitabilidade, eu entendo.

Por outro lado, se acabarmos no palpite de último recurso , a esperança já está perdida, então por que se preocupar. Tentamos todos os truques que conhecíamos e desistimos. No mínimo, a estimativa final selvagem é um grande sinal de alerta de que nem tudo correu bem dentro do CE durante a compilação e otimização desta consulta.

Quando tentei o MCVE, o 120+ CE produziu uma estimativa final de linha zero (= 1) (como o aninhado ISNULL) para a consulta original, o que é igualmente inaceitável para minha maneira de pensar.

A solução real provavelmente envolve uma mudança de design, para permitir uniões de equivalência simples sem COALESCEou ISNULL, e, idealmente, chaves estrangeiras e outras restrições úteis para a compilação de consultas.

Acredito que o Compute Scalaroperador resultante da COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)associação X_LAST_TABLE.JOIN_IDseja a causa raiz do problema. Historicamente, os escalares de computação têm sido difíceis de estimar com precisão ^{1 , 2} .

Como você forneceu um exemplo verificável minimamente completo (obrigado!) com estatísticas precisas, posso reescrever a consulta para que a junção não exija mais a CASEfuncionalidade COALESCEexpandida, resultando em estimativas de linha muito mais precisas e, aparentemente , custeio geral preciso ^{Veja o adendo no 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);

Embora o xID IS NOT NULLnão seja tecnicamente necessário, já que o ID = JOIN_IDnão se juntará em valores nulos, eu os incluí, pois retrata mais claramente a intenção.

Plano 1 e Plano 2

Plano 1:

Plano 2:

A nova consulta se beneficia(?) da paralelização. Também digno de nota, a nova consulta tem um número de saída estimado de linhas de 1, o que pode, de fato, ser pior no final do dia do que a estimativa de 4528030000 para a consulta original. O custo da subárvore para o operador select na nova consulta chega a 243210, enquanto o original chega a 536,535, o que é claramente menor. Dito isto, não acredito que a primeira estimativa esteja perto da realidade.

Adendo 1.

Após mais consultas com várias pessoas no The Heap™ estimuladas por uma discussão com @Lamak, parece que minha consulta observacional acima tem um desempenho terrível, mesmo com o paralelismo. Uma solução que permite boas estimativas de desempenho e de cardinalidade consiste em substituir o COALESCE(x,y,z)por um ISNULL(ISNULL(x, y), z), como em:

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;

COALESCEé transformado em uma CASEdeclaração "nos bastidores" pelo otimizador de consulta. Como tal, o estimador de cardinalidade tem mais dificuldade em descobrir estatísticas confiáveis ​​para colunas escondidas dentro de COALESCE. ISNULLsendo uma função intrínseca é muito mais "aberta" para o estimador de cardinalidade. Também não vale nada que ISNULLpossa ser otimizado se o alvo for conhecido por não ser anulável.

O plano para a ISNULLvariante se parece com:

(Cole a versão do plano aqui ).

Para sua informação, parabéns ao Sentry One por seu excelente Plan Explorer, que usei para produzir os planos gráficos acima.