Je posterai une réponse pour commencer. Ma première pensée a été qu'il devrait être possible de profiter de la nature préservant l'ordre d'une jointure en boucle imbriquée avec quelques tables auxiliaires qui ont une ligne pour chaque lettre. La partie délicate allait boucler de manière à ce que les résultats soient classés par longueur tout en évitant les doublons. Par exemple, lors de l'adhésion croisée à un CTE qui comprend les 26 majuscules avec '', vous pouvez finir par générer 'A' + '' + 'A'
et'' + 'A' + 'A'
qui est bien sûr la même chaîne.
La première décision a été de savoir où stocker les données d'assistance. J'ai essayé d'utiliser une table temporaire mais cela a eu un impact étonnamment négatif sur les performances, même si les données tiennent sur une seule page. Le tableau temporaire contient les données ci-dessous:
SELECT 'A'
UNION ALL SELECT 'B'
...
UNION ALL SELECT 'Y'
UNION ALL SELECT 'Z'
Par rapport à l'utilisation d'un CTE, la requête a pris 3 fois plus de temps avec une table en cluster et 4 fois plus avec un tas. Je ne crois pas que le problème soit que les données soient sur disque. Il doit être lu en mémoire sur une seule page et traité en mémoire pour l'ensemble du plan. Peut-être que SQL Server peut travailler avec les données d'un opérateur Constant Scan plus efficacement qu'avec des données stockées dans des pages de magasin de lignes typiques.
Fait intéressant, SQL Server choisit de placer les résultats ordonnés d'une table tempdb d'une seule page avec les données ordonnées dans une bobine de table:
SQL Server place souvent les résultats de la table interne d'une jointure croisée dans une bobine de table, même si cela semble absurde de le faire. Je pense que l'optimiseur a besoin d'un peu de travail dans ce domaine. J'ai exécuté la requête avec leNO_PERFORMANCE_SPOOL
pour éviter la perte de performances.
Un problème avec l'utilisation d'un CTE pour stocker les données d'assistance est que les données ne sont pas garanties d'être ordonnées. Je ne vois pas pourquoi l'optimiseur choisirait de ne pas le commander et dans tous mes tests, les données ont été traitées dans l'ordre où j'ai écrit le CTE:
Cependant, mieux vaut ne pas prendre de risques, surtout s'il existe un moyen de le faire sans une surcharge de performances importante. Il est possible de classer les données dans une table dérivée en ajoutant un TOP
opérateur superflu . Par exemple:
(SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR)
Cet ajout à la requête devrait garantir que les résultats seront renvoyés dans le bon ordre. Je m'attendais à ce que tous les types aient un grand impact négatif sur les performances. L'optimiseur de requêtes s'y attendait également en fonction des coûts estimés:
De manière très surprenante, je n'ai pu observer aucune différence statistiquement significative dans le temps ou le temps d'exécution du processeur avec ou sans classement explicite. Si quoi que ce soit, la requête semble s'exécuter plus rapidement avec leORDER BY
! Je n'ai aucune explication à ce comportement.
La partie délicate du problème était de savoir comment insérer des caractères vides aux bons endroits. Comme mentionné précédemment, un simple CROSS JOIN
entraînerait la duplication des données. Nous savons que la chaîne 100000000th aura une longueur de six caractères car:
26 + 26 ^ 2 + 26 ^ 3 + 26 ^ 4 + 26 ^ 5 = 914654 <100000000
mais
26 + 26 ^ 2 + 26 ^ 3 + 26 ^ 4 + 26 ^ 5 + 26 ^ 6 = 321272406> 100000000
Par conséquent, nous devons seulement adhérer à la lettre CTE six fois. Supposons que nous nous joignions au CTE six fois, prenions une lettre de chaque CTE et les concaténions tous ensemble. Supposons que la lettre la plus à gauche ne soit pas vide. Si l'une des lettres suivantes est vide, cela signifie que la chaîne comporte moins de six caractères, il s'agit donc d'un doublon. Par conséquent, nous pouvons éviter les doublons en trouvant le premier caractère non vide et en exigeant que tous les caractères après lui ne soient pas non plus vides. J'ai choisi de suivre cela en attribuant une FLAG
colonne à l'un des CTE et en ajoutant une vérification à la WHERE
clause. Cela devrait être plus clair après avoir examiné la requête. La dernière requête est la suivante:
WITH FIRST_CHAR (CHR) AS
(
SELECT 'A'
UNION ALL SELECT 'B'
UNION ALL SELECT 'C'
UNION ALL SELECT 'D'
UNION ALL SELECT 'E'
UNION ALL SELECT 'F'
UNION ALL SELECT 'G'
UNION ALL SELECT 'H'
UNION ALL SELECT 'I'
UNION ALL SELECT 'J'
UNION ALL SELECT 'K'
UNION ALL SELECT 'L'
UNION ALL SELECT 'M'
UNION ALL SELECT 'N'
UNION ALL SELECT 'O'
UNION ALL SELECT 'P'
UNION ALL SELECT 'Q'
UNION ALL SELECT 'R'
UNION ALL SELECT 'S'
UNION ALL SELECT 'T'
UNION ALL SELECT 'U'
UNION ALL SELECT 'V'
UNION ALL SELECT 'W'
UNION ALL SELECT 'X'
UNION ALL SELECT 'Y'
UNION ALL SELECT 'Z'
)
, ALL_CHAR (CHR, FLAG) AS
(
SELECT '', 0 CHR
UNION ALL SELECT 'A', 1
UNION ALL SELECT 'B', 1
UNION ALL SELECT 'C', 1
UNION ALL SELECT 'D', 1
UNION ALL SELECT 'E', 1
UNION ALL SELECT 'F', 1
UNION ALL SELECT 'G', 1
UNION ALL SELECT 'H', 1
UNION ALL SELECT 'I', 1
UNION ALL SELECT 'J', 1
UNION ALL SELECT 'K', 1
UNION ALL SELECT 'L', 1
UNION ALL SELECT 'M', 1
UNION ALL SELECT 'N', 1
UNION ALL SELECT 'O', 1
UNION ALL SELECT 'P', 1
UNION ALL SELECT 'Q', 1
UNION ALL SELECT 'R', 1
UNION ALL SELECT 'S', 1
UNION ALL SELECT 'T', 1
UNION ALL SELECT 'U', 1
UNION ALL SELECT 'V', 1
UNION ALL SELECT 'W', 1
UNION ALL SELECT 'X', 1
UNION ALL SELECT 'Y', 1
UNION ALL SELECT 'Z', 1
)
SELECT TOP (100000000)
d6.CHR + d5.CHR + d4.CHR + d3.CHR + d2.CHR + d1.CHR
FROM (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d6
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d5
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d4
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d3
CROSS JOIN (SELECT TOP (27) FLAG, CHR FROM ALL_CHAR ORDER BY CHR) d2
CROSS JOIN (SELECT TOP (26) CHR FROM FIRST_CHAR ORDER BY CHR) d1
WHERE (d2.FLAG + d3.FLAG + d4.FLAG + d5.FLAG + d6.FLAG) =
CASE
WHEN d6.FLAG = 1 THEN 5
WHEN d5.FLAG = 1 THEN 4
WHEN d4.FLAG = 1 THEN 3
WHEN d3.FLAG = 1 THEN 2
WHEN d2.FLAG = 1 THEN 1
ELSE 0 END
OPTION (MAXDOP 1, FORCE ORDER, LOOP JOIN, NO_PERFORMANCE_SPOOL);
Les CTE sont tels que décrits ci-dessus. ALL_CHAR
est joint à cinq fois car il comprend une ligne pour un caractère vide. Le caractère final de la chaîne ne doit jamais être vide si on définit un CTE séparé pour elle, FIRST_CHAR
. La colonne d'indicateur supplémentaire dans ALL_CHAR
est utilisée pour éviter les doublons comme décrit ci-dessus. Il existe peut-être un moyen plus efficace d'effectuer cette vérification, mais il existe certainement des moyens plus inefficaces de le faire. Une tentative de ma part avec LEN()
etPOWER()
fait exécuter la requête six fois plus lentement que la version actuelle.
Les astuces MAXDOP 1
et FORCE ORDER
sont essentielles pour garantir que l'ordre est conservé dans la requête. Un plan estimé annoté peut être utile pour voir pourquoi les jointures sont dans leur ordre actuel:
Les plans de requête sont souvent lus de droite à gauche, mais les demandes de ligne se produisent de gauche à droite. Idéalement, SQL Server demandera exactement 100 millions de lignes à l' d1
opérateur d'analyse constante. Lorsque vous vous déplacez de gauche à droite, je m'attends à ce que moins de lignes soient demandées à chaque opérateur. Nous pouvons voir cela dans le plan d'exécution réel . En outre, ci-dessous est une capture d'écran de SQL Sentry Plan Explorer:
Nous avons obtenu exactement 100 millions de lignes de d1, ce qui est une bonne chose. Notez que le rapport des lignes entre d2 et d3 est presque exactement 27: 1 (165336 * 27 = 4464072), ce qui est logique si vous pensez au fonctionnement de la jointure croisée. Le rapport des rangées entre d1 et d2 est de 22,4, ce qui représente du travail gaspillé. Je crois que les lignes supplémentaires proviennent de doublons (en raison des caractères vides au milieu des chaînes) qui ne dépassent pas l'opérateur de jointure de boucle imbriquée qui effectue le filtrage.
L' LOOP JOIN
astuce est techniquement inutile car a CROSS JOIN
ne peut être implémenté qu'en tant que jointure en boucle dans SQL Server. leNO_PERFORMANCE_SPOOL
est d'empêcher la mise en file d'attente de table inutile. L'omission de l'indicateur de bobine a rendu la requête 3 fois plus longue sur ma machine.
La requête finale a un temps processeur d'environ 17 secondes et un temps total écoulé de 18 secondes. C'était lors de l'exécution de la requête via SSMS et de la suppression du jeu de résultats. Je suis très intéressé à voir d'autres méthodes de génération des données.