Pourquoi cette estimation de cardinalité jointe est-elle si importante?

Je ressens ce que je pense être une estimation de cardinalité incroyablement élevée pour la requête suivante:

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;

Le plan estimé est ici . Je travaille sur une copie des statistiques des tableaux, donc je ne peux pas inclure un plan réel. Cependant, je ne pense pas que ce soit très pertinent pour ce problème.

SQL Server estime que 481577 lignes seront renvoyées à partir de la table dérivée "dm". Il estime ensuite que 4528030000 lignes seront retournées une fois la jointure à X_LAST_TABLE effectuée, mais JOIN_ID est la clé primaire de X_LAST_TIME. Je m'attendrais à une estimation de cardinalité de jointure entre 0 et 481577 lignes. Au lieu de cela, l'estimation des lignes semble représenter 10% du nombre de lignes que j'obtiendrais en joignant les tables externe et interne. Le calcul pour cela fonctionne avec l'arrondissement: 481577 * 94025 * 0,1 = 45280277425 qui est arrondi à 4528030000.

Je recherche principalement une cause profonde de ce comportement. Je suis également intéressé par des solutions de contournement simples, mais veuillez ne pas suggérer de modifier le modèle de données ou d'utiliser des tables temporaires. Cette requête est une simplification de la logique dans une vue. Je sais que faire COALESCE sur quelques colonnes et les rejoindre n'est pas une bonne pratique. Une partie de l'objectif de cette question est de déterminer si je dois recommander que le modèle de données soit repensé.

Je teste sur Microsoft SQL Server 2014 avec l'estimateur de cardinalité hérité activé. TF 4199 et d'autres sont allumés. Je peux donner une liste complète des indicateurs de trace si cela s'avère pertinent.

Voici la définition de table la plus pertinente:

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

J'ai également écrit tous les scripts de création de table ainsi que leurs statistiques si quelqu'un veut reproduire le problème sur l'un de leurs serveurs.

Pour ajouter quelques-unes de mes observations, l'utilisation du TF 2312 corrige l'estimation, mais ce n'est pas une option pour moi. TF 2301 ne fixe pas l'estimation. La suppression de l'un des tableaux corrige l'estimation. Bizarrement, la modification de l'ordre de jointure de X_DETAIL_LINK corrige également l'estimation. En changeant l'ordre de jointure, je veux dire réécrire la requête et ne pas forcer l'ordre de jointure avec un indice. Voici un plan de requête estimé lorsque vous modifiez simplement l'ordre des jointures.

Je sais que faire COALESCEsur quelques colonnes et les rejoindre n'est pas une bonne pratique.

La génération de bonnes estimations de cardinalité et de distribution est déjà assez difficile lorsque le schéma est 3NF + (avec clés et contraintes) et que la requête est relationnelle et principalement SPJG (selection-projection-join-group by). Le modèle CE est construit sur ces principes. Plus une fonction est inhabituelle ou non relationnelle dans une requête, plus on se rapproche des limites de ce que le cadre de cardinalité et de sélectivité peut gérer. Allez trop loin et CE abandonnera et devinera .

La plupart de l'exemple MCVE est un SPJ simple (pas de G), bien que les équijoines soient principalement externes (modélisées comme jointure interne plus anti-semi-jointure) plutôt que l'équijoin interne plus simple (ou semi-jointure). Toutes les relations ont des clés, mais pas de clés étrangères ou d'autres contraintes. Toutes les jointures sauf une sont un à plusieurs, ce qui est bien.

L'exception est la jointure externe plusieurs-à-plusieurs entre X_DETAIL_1et X_DETAIL_LINK. La seule fonction de cette jointure dans le MCVE est de potentiellement dupliquer des lignes X_DETAIL_1. C'est une sorte de chose inhabituelle .

Les prédicats d'égalité simples (sélections) et les opérateurs scalaires sont également meilleurs. Par exemple, l' attribut comparaison-égal attribut / constante fonctionne normalement bien dans le modèle. Il est relativement "facile" de modifier les histogrammes et les statistiques de fréquence pour refléter l'application de ces prédicats.

COALESCEest construit sur CASE, qui est à son tour implémenté en interne comme IIF(et cela était vrai bien avant d' IIFapparaître dans le langage Transact-SQL). Les modèles CE IIFcommeUNION avec deux enfants mutuellement exclusifs, chacun consistant en un projet sur une sélection sur la relation d'entrée. Chacun des composants répertoriés prend en charge les modèles, il est donc relativement simple de les combiner. Même ainsi, plus il y a d'abstractions d'une couche, moins le résultat final a tendance à être précis - une raison pour laquelle les plans d'exécution plus grands ont tendance à être moins stables et fiables.

ISNULL, d'autre part, est intrinsèque au moteur. Il n'est pas construit en utilisant des composants plus basiques. L'application de l'effet de ISNULLà un histogramme, par exemple, est aussi simple que de remplacer l'étape des NULLvaleurs (et de la compacter si nécessaire). Il est encore relativement opaque, comme le font les opérateurs scalaires, et il vaut donc mieux éviter autant que possible. Néanmoins, il est généralement plus convivial pour l'optimiseur (moins hostile à l'optimiseur) qu'un système CASEalternatif.

Le CE (70 et 120+) est très complexe, même selon les normes SQL Server. Il ne s'agit pas d'appliquer une logique simple (avec une formule secrète) à chaque opérateur. Le CE connaît les clés et les dépendances fonctionnelles; il sait estimer à l'aide de fréquences, de statistiques multivariées et d'histogrammes; et il y a une tonne absolue de cas spéciaux, de raffinements, de freins et contrepoids et de structures de support. Il estime souvent par exemple les jointures de plusieurs manières (fréquence, histogramme) et décide d'un résultat ou d'un ajustement en fonction des différences entre les deux.

Une dernière chose de base à couvrir: l'estimation de cardinalité initiale s'exécute pour chaque opération dans l'arbre de requête, de bas en haut. La sélectivité et la cardinalité sont d'abord dérivées pour les opérateurs feuille (relations de base). Des histogrammes modifiés et des informations de densité / fréquence sont dérivés pour les opérateurs parents. Plus nous montons dans l'arbre, plus la qualité des estimations tend à être faible, car les erreurs ont tendance à s'accumuler.

Cette estimation globale initiale unique fournit un point de départ et se produit bien avant que toute considération ne soit donnée à un plan d'exécution final (elle se produit bien avant même l'étape de compilation du plan trivial). L'arbre de requête à ce stade a tendance à refléter assez étroitement la forme écrite de la requête (bien que les sous-requêtes soient supprimées et les simplifications appliquées, etc.)

Immédiatement après l'estimation initiale, SQL Server effectue un réordonnancement des jointures heuristiques, qui essaie de réorganiser l'arborescence pour placer les tables plus petites et les jointures à haute sélectivité en premier. Il essaie également de positionner les jointures internes avant les jointures externes et les produits croisés. Ses capacités ne sont pas étendues; ses efforts ne sont pas exhaustifs; et il ne prend pas en compte les coûts physiques (car ils n'existent pas encore - seules des informations statistiques et des métadonnées sont présentes). Le réordonnancement heuristique est plus efficace sur les équijoins internes simples. Il existe pour fournir un «meilleur» point de départ pour une optimisation basée sur les coûts.

Pourquoi cette estimation de cardinalité jointe est-elle si importante?

Le MCVE a une jointure plusieurs-à-plusieurs "inhabituelle" pour la plupart redondante , et une jointure équi avec COALESCEdans le prédicat. L'arborescence des opérateurs a également une jointure interne en dernier , ce qui réordonne la jointure heuristique n'a pas pu déplacer l'arborescence vers une position plus préférée. Laissant de côté tous les scalaires et les projections, l'arbre de jointure est:

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 ]

Notez que l'estimation finale erronée est déjà en place. Il est imprimé Card=4.52803e+009et stocké en interne en tant que valeur à virgule flottante double précision 4,5280277425e + 9 (4528027742,5 en décimal).

La table dérivée de la requête d'origine a été supprimée et les projections normalisées. Une représentation SQL de l'arbre sur lequel la cardinalité et l'estimation de sélectivité initiales ont été effectuées est:

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)

(En passant, la répétition COALESCEest également présente dans le plan final - une fois dans le calcul final scalaire, et une fois sur le côté intérieur de la jointure intérieure).

Remarquez la jointure finale. Cette jointure interne est (par définition) le produit cartésien de X_LAST_TABLEet la sortie de jointure précédente, avec une sélection (prédicat de jointure) lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)appliquée. La cardinalité du produit cartésien est simplement 481577 * 94025 = 45280277425.

Pour cela, nous devons déterminer et appliquer la sélectivité du prédicat. La combinaison de l' COALESCEarbre étendu opaque (en termes de, UNIONet IIFrappelez-vous) ainsi que l'impact sur les informations clés, les histogrammes dérivés et les fréquences de la jointure externe plusieurs-à-plusieurs "inhabituelle" principalement-redondante combinée signifie que le CE est incapable de dériver une estimation acceptable de l'une des manières normales.

En conséquence, il entre dans la logique Guess. La logique de la supposition est modérément complexe, avec des couches d'algorithmes de supposition «éduqués» et «moins instruits» essayés. Si aucune meilleure base pour une estimation n'est trouvée, le modèle utilise une estimation de dernier recours, qui pour une comparaison d'égalité est: sqllang!x_Selectivity_Equal= sélectivité fixe de 0,1 (estimation de 10%):

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

Le résultat est une sélectivité de 0,1 sur le produit cartésien: 481577 * 94025 * 0,1 = 4528027742,5 (~ 4,52803e + 009) comme mentionné précédemment.

Réécrit

Lorsque la jointure problématique est commentée , une meilleure estimation est produite car la sélectivité fixe "deviner le dernier recours" est évitée (les informations clés sont conservées par les jointures 1-M). La qualité de l'estimation est encore peu fiable, car un COALESCEprédicat de jointure n'est pas du tout compatible CE. L'estimation révisée fait au moins apparence plus raisonnable pour les humains, je suppose.

Lorsque la requête est écrite avec la jointure externe X_DETAIL_LINK placée en dernier , le réordonnancement heuristique peut l'échanger avec la jointure interne finale vers X_LAST_TABLE. Placer la jointure interne juste à côté du joint externe problématique donne aux capacités limitées de réorganisation précoce la possibilité d'améliorer l'estimation finale, car les effets de la jointure externe plusieurs-à-plusieurs "inhabituelle" pour la plupart redondante surviennent après l'estimation délicate de la sélectivité. pour COALESCE. Encore une fois, les estimations ne valent guère mieux que les suppositions fixes et ne résisteraient probablement pas à un contre-interrogatoire déterminé devant un tribunal.

La réorganisation d'un mélange de jointures internes et externes est difficile et prend du temps (même l'optimisation complète de l'étape 2 ne tente qu'un sous-ensemble limité de mouvements théoriques).

La ISNULLsuggestion imbriquée dans la réponse de Max Vernon parvient à éviter la supposition fixe du renflouement, mais l'estimation finale est une improbable ligne zéro (élevée à une ligne pour la décence). Cela pourrait aussi bien être une estimation fixe de 1 ligne, pour toute la base statistique du calcul.

Je m'attendrais à une estimation de cardinalité de jointure entre 0 et 481577 lignes.

C'est une attente raisonnable, même si l'on admet que l'estimation de la cardinalité peut se produire à différents moments (lors de l'optimisation basée sur les coûts) sur des sous-arbres physiquement différents, mais logiquement et sémantiquement identiques - le plan final étant une sorte de meilleur assemblé meilleur (par groupe de mémos). L'absence d'une garantie de cohérence à l'échelle du plan ne signifie pas qu'une jointure individuelle devrait pouvoir bafouer la respectabilité, je comprends.

D'un autre côté, si nous finissons par deviner le dernier recours , l'espoir est déjà perdu, alors pourquoi s'embêter. Nous avons essayé toutes les astuces que nous connaissions et avons abandonné. Si rien d'autre, l'estimation finale sauvage est un grand signe d'avertissement que tout ne s'est pas bien passé à l'intérieur du CE pendant la compilation et l'optimisation de cette requête.

Lorsque j'ai essayé le MCVE, le 120+ CE a produit une estimation finale de ligne zéro (= 1) (comme le niché ISNULL) pour la requête d'origine, ce qui est tout aussi inacceptable pour ma façon de penser.

La vraie solution implique probablement un changement de conception, pour permettre des équi-jointures simples sans COALESCEou ISNULL, et idéalement des clés étrangères et d'autres contraintes utiles pour la compilation de requêtes.

Je crois que l' Compute Scalaropérateur résultant de l' COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)adhésion X_LAST_TABLE.JOIN_IDest à l'origine du problème. Historiquement, les scalaires de calcul ont été difficiles à chiffrer avec précision ^{1 , 2} .

Étant donné que vous avez fourni un exemple vérifiable minimalement complet (merci!) Avec des statistiques précises, je suis en mesure de réécrire la requête de telle sorte que la jointure ne nécessite plus la CASEfonctionnalité qui COALESCEest développée, ce qui entraîne des estimations de ligne beaucoup plus précises, et apparemment plus chiffrage global précis ^{Voir l'addendum à la fin.} :

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

Bien que la xID IS NOT NULLtechnique ne soit pas requise,ID = JOIN_ID ne se joindra pas aux valeurs nulles, je les ai incluses car il décrit plus clairement l'intention.

Plan 1 et Plan 2

Plan 1:

Plan 2:

La nouvelle requête bénéficie (?) De la parallélisation. Il convient également de noter que la nouvelle requête a un nombre de sortie estimé de lignes de 1, ce qui peut en fait être pire à la fin de la journée que l'estimation de 4528030000 pour la requête d'origine. Le coût de la sous-arborescence pour l'opérateur de sélection sur la nouvelle requête est de 243210, tandis que celui de l'horloge d'origine est de 536,535, ce qui est clairement moins. Cela dit, je ne pense pas que la première estimation soit proche de la réalité.

Addendum 1.

Après de nouvelles consultations avec diverses personnes sur The Heap ™, stimulées par une discussion avec @Lamak, il semble que ma requête d'observation ci-dessus fonctionne terriblement, même avec le parallélisme. Une solution qui permet à la fois de bonnes performances et de bonnes estimations de cardinalité consiste à remplacer le COALESCE(x,y,z)par un ISNULL(ISNULL(x, y), z), comme dans:

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;

COALESCEest transformé en une CASEdéclaration "sous les couvertures" par l'optimiseur de requête. En tant que tel, l'estimateur de cardinalité a plus de mal à découvrir des statistiques fiables pour les colonnes enfouies à l'intérieur COALESCE. ISNULLêtre une fonction intrinsèque est beaucoup plus «ouvert» pour l'estimateur de cardinalité. Cela ne vaut également rien qui ISNULLpuisse être optimisé si la cible est connue pour être non nulle.

Le plan de la ISNULLvariante ressemble à:

(Collez la version Plan ici ).

Pour info, les accessoires de Sentry One pour leur grand Plan Explorer, que j'ai utilisé pour produire les plans graphiques ci-dessus.

Selon votre condition de jointure, la table peut être arrangée de nombreuses manières, c'est "changer d'une manière particulière" pour corriger le résultat.

Supposons que joindre une seule table vous donne un résultat correct.

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

Ici , à la place X_DETAIL_1, vous pouvez utiliser X_DETAIL_2ouX_DETAIL_3 .

Par conséquent, le but des tables de repos 2 n'est pas clair.

C'est comme si vous aviez divisé le tableau X_DETAIL_1en 2 parties supplémentaires.

Très probablement « il y a erreur où vous peuplez ces tables. » Idéalement X_DETAIL_1, X_DETAIL_2et X_DETAIL_3doit contenir une quantité égale de lignes.

Mais une ou plusieurs tables contiennent un nombre non souhaité de lignes.

Désolé si je me trompe.