Dans le premier article, nous avons vu combien il était facile de solutionner des grilles de sudoku avec une seule requête SQL. Malheureusement, c’était trop beau pour être vrai…
Avant de poursuivre, voici un outil utile pour se faciliter la tâche. Pour ceux qui utilisent Smalltalk, vous pouvez vous aider du script suivant :
| uneTableOuVue uneStringSudoku stream estLePremier | uneTableOuVue := 'sudoku_rows_view'. uneStringSudoku := '.........134825697759364182397182564.........581476239825641973976538421.........'. stream := ReadWriteStream on: String new. stream nextPutAll: 'SELECT * '; cr; nextPutAll: 'FROM '; nextPutAll: uneTableOuVue; space; cr; nextPutAll: 'WHERE'; cr. estLePremier := false. 1 to: 9 do: [:r | 1 to: 9 do: [:c | | i | i := (r-1)*9 + c. ((uneStringSudoku at: i) ~= $. and: [(uneStringSudoku at: i) ~= 0]) ifTrue: [ estLePremier ifTrue: [stream nextPutAll: ' AND ';cr]. estLePremier := true. stream nextPutAll: '(r'; nextPutAll: r asString; nextPutAll: 'c'; nextPutAll: c asString; nextPutAll: ' = '; nextPutAll: (uneStringSudoku at: i) asString; nextPutAll: ')'. ].]]. Transcript cr;show: stream contents
Ce script génère les requêtes SQL à partir d’une chaîne de caractères (uneStringSudoku) représentant une grille de sudoku pour une table/vue précise (uneTableOuVue) en affichant le résultat dans le Transcript.
1. Problème majeur
Il y a une faille majeure et évidente dans la solution telle que présentée : elle repose totalement sur la capacité de MySQL de faire correspondre les révélés (givens en anglais) de la grille à des lignes. Que se passerait-il si une ligne (ou pire encore, plusieurs lignes) dans le sudoku ne contenait pas de révélés (ou pas assez)? Sans index à utiliser, une lecture séquentielle de la table nous attend sans doute! Prenons, par exemple, la grille suivante:
Ce sudoku contient 54 révélés (la première grille n’en comptait que 30, près de la moitié de celle-ci) et 6 de ses lignes seront rapidement récupérées avec les index. De plus, il y a suffisamment de révélés pour éliminer rapidement un bon nombre de lignes candidates avec les contraintes du puzzle incluses dans la vue sudoku_rows_view.
Cependant les lignes vides (1, 5 et 9) causeront probablement une lecture séquentielle (table scan) de la table. Nous faisons face à un problème majeur avec les lignes 1, 5 et 9 étant vides! Examinons la requête pour ce sudoku :
EXPLAIN SELECT * FROM sudoku_rows_view WHERE (r2c1 = 1) AND (r2c2 = 3) AND (r2c3 = 4) AND (r2c4 = 8) AND (r2c5 = 2) AND (r2c6 = 5) AND (r2c7 = 6) AND (r2c8 = 9) AND (r2c9 = 7) AND (r3c1 = 7) AND (r3c2 = 5) AND (r3c3 = 9) AND (r3c4 = 3) AND (r3c5 = 6) AND (r3c6 = 4) AND (r3c7 = 1) AND (r3c8 = 8) AND (r3c9 = 2) AND (r4c1 = 3) AND (r4c2 = 9) AND (r4c3 = 7) AND (r4c4 = 1) AND (r4c5 = 8) AND (r4c6 = 2) AND (r4c7 = 5) AND (r4c8 = 6) AND (r4c9 = 4) AND (r6c1 = 5) AND (r6c2 = 8) AND (r6c3 = 1) AND (r6c4 = 4) AND (r6c5 = 7) AND (r6c6 = 6) AND (r6c7 = 2) AND (r6c8 = 3) AND (r6c9 = 9) AND (r7c1 = 8) AND (r7c2 = 2) AND (r7c3 = 5) AND (r7c4 = 6) AND (r7c5 = 4) AND (r7c6 = 1) AND (r7c7 = 9) AND (r7c8 = 7) AND (r7c9 = 3) AND (r8c1 = 9) AND (r8c2 = 7) AND (r8c3 = 6) AND (r8c4 = 5) AND (r8c5 = 3) AND (r8c6 = 8) AND (r8c7 = 4) AND (r8c8 = 2) AND (r8c9 = 1);
Le résultat du EXPLAIN :
+----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+--------+----------------------------------------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+--------+----------------------------------------------------------------------------------+ | 1 | SIMPLE | r2 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i29 | 2,2 | NULL | 68 | Using intersect(i37,i29); Using where | | 1 | SIMPLE | r3 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i28 | 2,2 | NULL | 68 | Using intersect(i37,i28); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r4 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i56,i29 | 2,2 | NULL | 68 | Using intersect(i56,i29); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r6 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12,i35 | 2,2 | NULL | 68 | Using intersect(i12,i35); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r7 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12,i68 | 2,2 | NULL | 68 | Using intersect(i12,i68); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r8 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i79,i38 | 2,2,2 | NULL | 78 | Using intersect(i37,i79,i38); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r1 | range | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23 | 1 | NULL | 40012 | Using index condition; Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r5 | ALL | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | NULL | NULL | NULL | 362880 | Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r9 | ALL | NULL | NULL | NULL | NULL | 362880 | Using where; Using join buffer (Block Nested Loop) | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+--------+----------------------------------------------------------------------------------+ 9 rows in set (13.39 sec)
Les lignes vides (lignes 1, 5 et 9) nous feront payer très chèrement le fait que nous ne pouvons pas utiliser pleinement les index! Il n’y a qu’à constater le nombre de lignes à potentiellement examiner pour joindre les tables r1, r5 et r9 (40012 x 362880 x 362880 = 5268855958732800) ainsi que le type de jointure utilisé (range, ALL et ALL).
Vérifions en combien de temps la requête s’exécute :
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ | r1c1 | r1c2 | r1c3 | r1c4 | r1c5 | r1c6 | r1c7 | r1c8 | r1c9 | r2c1 | r2c2 | r2c3 | r2c4 | r2c5 | r2c6 | r2c7 | r2c8 | r2c9 | r3c1 | r3c2 | r3c3 | r3c4 | r3c5 | r3c6 | r3c7 | r3c8 | r3c9 | r4c1 | r4c2 | r4c3 | r4c4 | r4c5 | r4c6 | r4c7 | r4c8 | r4c9 | r5c1 | r5c2 | r5c3 | r5c4 | r5c5 | r5c6 | r5c7 | r5c8 | r5c9 | r6c1 | r6c2 | r6c3 | r6c4 | r6c5 | r6c6 | r6c7 | r6c8 | r6c9 | r7c1 | r7c2 | r7c3 | r7c4 | r7c5 | r7c6 | r7c7 | r7c8 | r7c9 | r8c1 | r8c2 | r8c3 | r8c4 | r8c5 | r8c6 | r8c7 | r8c8 | r8c9 | r9c1 | r9c2 | r9c3 | r9c4 | r9c5 | r9c6 | r9c7 | r9c8 | r9c9 | +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ | 2 | 6 | 8 | 7 | 1 | 9 | 3 | 4 | 5 | 1 | 3 | 4 | 8 | 2 | 5 | 6 | 9 | 7 | 7 | 5 | 9 | 3 | 6 | 4 | 1 | 8 | 2 | 3 | 9 | 7 | 1 | 8 | 2 | 5 | 6 | 4 | 6 | 4 | 2 | 9 | 5 | 3 | 7 | 1 | 8 | 5 | 8 | 1 | 4 | 7 | 6 | 2 | 3 | 9 | 8 | 2 | 5 | 6 | 4 | 1 | 9 | 7 | 3 | 9 | 7 | 6 | 5 | 3 | 8 | 4 | 2 | 1 | 4 | 1 | 3 | 2 | 9 | 7 | 8 | 5 | 6 | +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ 1 row in set (6.17 sec)
Ouf! Nous sommes passés de 0.39 seconde (grille 01) à 6.17 secondes (grille 02) malgré le fait que la grille 02 comporte près de 2 fois plus de révélés que la grille 01! Cet exemple démontre clairement que les choses peuvent rapidement mal tourner à un rythme alarmant (même exponentiel) quand nous sommes confrontés à une grille contenant des lignes vides ou presque vides!
2. Changer de point de vue!
Imaginons maintenant que nous faisons effectuer une rotation à notre grille et que les colonnes deviennent des lignes. Dans ce cas, chaque nouvelle ligne pourrait dès lors bénéficier des index!
Voyons cette nouvelle grille :
La requête aurait désormais l’air de ceci :
SELECT * FROM sudoku_rows_view WHERE (r1c2 = 1) AND (r1c3 = 7) AND (r1c4 = 3) AND (r1c6 = 5) AND (r1c7 = 8) AND (r1c8 = 9) AND (r2c2 = 3) AND (r2c3 = 5) AND (r2c4 = 9) AND (r2c6 = 8) AND (r2c7 = 2) AND (r2c8 = 7) AND (r3c2 = 4) AND (r3c3 = 9) AND (r3c4 = 7) AND (r3c6 = 1) AND (r3c7 = 5) AND (r3c8 = 6) AND (r4c2 = 8) AND (r4c3 = 3) AND (r4c4 = 1) AND (r4c6 = 4) AND (r4c7 = 6) AND (r4c8 = 5) AND (r5c2 = 2) AND (r5c3 = 6) AND (r5c4 = 8) AND (r5c6 = 7) AND (r5c7 = 4) AND (r5c8 = 3) AND (r6c2 = 5) AND (r6c3 = 4) AND (r6c4 = 2) AND (r6c6 = 6) AND (r6c7 = 1) AND (r6c8 = 8) AND (r7c2 = 6) AND (r7c3 = 1) AND (r7c4 = 5) AND (r7c6 = 2) AND (r7c7 = 9) AND (r7c8 = 4) AND (r8c2 = 9) AND (r8c3 = 8) AND (r8c4 = 6) AND (r8c6 = 3) AND (r8c7 = 7) AND (r8c8 = 2) AND (r9c2 = 7) AND (r9c3 = 2) AND (r9c4 = 4) AND (r9c6 = 9) AND (r9c7 = 3) AND (r9c8 = 1);
Le résultat du EXPLAIN correspondant :
+----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+------+----------------------------------------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+------+----------------------------------------------------------------------------------+ | 1 | SIMPLE | r3 | index_merge | i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i67,i68,i69,i78,i79,i89 | i23,i38,i48 | 2,2,2 | NULL | 64 | Using intersect(i23,i38,i48); Using where | | 1 | SIMPLE | r9 | index_merge | i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i67,i68,i69,i78,i79,i89 | i78,i68,i48 | 2,2,2 | NULL | 65 | Using intersect(i78,i68,i48); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r1 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i67 | 2,2 | NULL | 68 | Using intersect(i23,i67); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r2 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r4 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i78,i46 | 2,2 | NULL | 68 | Using intersect(i78,i46); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r5 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r6 | index_merge | i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i67,i68,i69,i78,i79,i89 | i23,i67 | 2,2 | NULL | 68 | Using intersect(i23,i67); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r7 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer (Block Nested Loop) | | 1 | SIMPLE | r8 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i24 | 2,2 | NULL | 68 | Using intersect(i37,i24); Using where; Using join buffer (Block Nested Loop) | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+------+------+----------------------------------------------------------------------------------+ 9 rows in set (42.98 sec)
Et combien de temps la requête prendrait-elle à s’exécuter?
SELECT * FROM sudoku_rows_view WHERE (r1c2 = 1) AND (r1c3 = 7) AND (r1c4 = 3) AND (r1c6 = 5) AND (r1c7 = 8) AND (r1c8 = 9) AND (r2c2 = 3) AND (r2c3 = 5) AND (r2c4 = 9) AND (r2c6 = 8) AND (r2c7 = 2) AND (r2c8 = 7) AND (r3c2 = 4) AND (r3c3 = 9) AND (r3c4 = 7) AND (r3c6 = 1) AND (r3c7 = 5) AND (r3c8 = 6) AND (r4c2 = 8) AND (r4c3 = 3) AND (r4c4 = 1) AND (r4c6 = 4) AND (r4c7 = 6) AND (r4c8 = 5) AND (r5c2 = 2) AND (r5c3 = 6) AND (r5c4 = 8) AND (r5c6 = 7) AND (r5c7 = 4) AND (r5c8 = 3) AND (r6c2 = 5) AND (r6c3 = 4) AND (r6c4 = 2) AND (r6c6 = 6) AND (r6c7 = 1) AND (r6c8 = 8) AND (r7c2 = 6) AND (r7c3 = 1) AND (r7c4 = 5) AND (r7c6 = 2) AND (r7c7 = 9) AND (r7c8 = 4) AND (r8c2 = 9) AND (r8c3 = 8) AND (r8c4 = 6) AND (r8c6 = 3) AND (r8c7 = 7) AND (r8c8 = 2) AND (r9c2 = 7) AND (r9c3 = 2) AND (r9c4 = 4) AND (r9c6 = 9) AND (r9c7 = 3) AND (r9c8 = 1); +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ | r1c1 | r1c2 | r1c3 | r1c4 | r1c5 | r1c6 | r1c7 | r1c8 | r1c9 | r2c1 | r2c2 | r2c3 | r2c4 | r2c5 | r2c6 | r2c7 | r2c8 | r2c9 | r3c1 | r3c2 | r3c3 | r3c4 | r3c5 | r3c6 | r3c7 | r3c8 | r3c9 | r4c1 | r4c2 | r4c3 | r4c4 | r4c5 | r4c6 | r4c7 | r4c8 | r4c9 | r5c1 | r5c2 | r5c3 | r5c4 | r5c5 | r5c6 | r5c7 | r5c8 | r5c9 | r6c1 | r6c2 | r6c3 | r6c4 | r6c5 | r6c6 | r6c7 | r6c8 | r6c9 | r7c1 | r7c2 | r7c3 | r7c4 | r7c5 | r7c6 | r7c7 | r7c8 | r7c9 | r8c1 | r8c2 | r8c3 | r8c4 | r8c5 | r8c6 | r8c7 | r8c8 | r8c9 | r9c1 | r9c2 | r9c3 | r9c4 | r9c5 | r9c6 | r9c7 | r9c8 | r9c9 | +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ | 2 | 1 | 7 | 3 | 6 | 5 | 8 | 9 | 4 | 6 | 3 | 5 | 9 | 4 | 8 | 2 | 7 | 1 | 8 | 4 | 9 | 7 | 2 | 1 | 5 | 6 | 3 | 7 | 8 | 3 | 1 | 9 | 4 | 6 | 5 | 2 | 1 | 2 | 6 | 8 | 5 | 7 | 4 | 3 | 9 | 9 | 5 | 4 | 2 | 3 | 6 | 1 | 8 | 7 | 3 | 6 | 1 | 5 | 7 | 2 | 9 | 4 | 8 | 4 | 9 | 8 | 6 | 1 | 3 | 7 | 2 | 5 | 5 | 7 | 2 | 4 | 8 | 9 | 3 | 1 | 6 | +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ 1 row in set (0.22 sec)
Nous sommes passés de 6.17 secondes à 0.22 seconde! Un gain imposant!
3. Les vues combinées
Alors pourquoi ne tenterions-nous pas de résoudre nos sudokus en effectuant la recherche par ligne ET par colonne à la fois?
Nous allons donc construire une seconde vue (sudoku_columns_view) qui sera basée sur les colonnes de la grille. Pour faire résoudre les sudokus, il nous faudra une troisième vue (sudoku_combined_view) qui combinera la vue par lignes (sudoku_rows_view) avec la vue par colonne (sudoku_columns_view). De cette façon, nous serons à l’abri des grilles avec des lignes vides et des grilles avec des colonnes vides. L’optimisateur de requête aura dorénavant tout le luxe de choisir la « méthode » la plus efficace!
Construisons la vue par colonnes en exécutant cette requête :
USE sudoku; CREATE VIEW sudoku_columns_view AS SELECT col1.c1 as r1c1, col1.c2 as r2c1, col1.c3 as r3c1, col1.c4 as r4c1, col1.c5 as r5c1,col1.c6 as r6c1, col1.c7 as r7c1, col1.c8 as r8c1, col1.c9 as r9c1, col2.c1 as r1c2, col2.c2 as r2c2, col2.c3 as r3c2, col2.c4 as r4c2, col2.c5 as r5c2, col2.c6 as r6c2,col2.c7 as r7c2, col2.c8 as r8c2, col2.c9 as r9c2, col3.c1 as r1c3, col3.c2 as r2c3, col3.c3 as r3c3, col3.c4 as r4c3, col3.c5 as r5c3, col3.c6 as r6c3, col3.c7 as r7c3,col3.c8 as r8c3, col3.c9 as r9c3, col4.c1 as r1c4, col4.c2 as r2c4, col4.c3 as r3c4, col4.c4 as r4c4, col4.c5 as r5c4, col4.c6 as r6c4, col4.c7 as r7c4, col4.c8 as r8c4,col4.c9 as r9c4, col5.c1 as r1c5, col5.c2 as r2c5, col5.c3 as r3c5, col5.c4 as r4c5, col5.c5 as r5c5, col5.c6 as r6c5, col5.c7 as r7c5, col5.c8 as r8c5, col5.c9 as r9c5,col6.c1 as r1c6, col6.c2 as r2c6, col6.c3 as r3c6, col6.c4 as r4c6, col6.c5 as r5c6, col6.c6 as r6c6, col6.c7 as r7c6, col6.c8 as r8c6, col6.c9 as r9c6, col7.c1 as r1c7,col7.c2 as r2c7, col7.c3 as r3c7, col7.c4 as r4c7, col7.c5 as r5c7, col7.c6 as r6c7, col7.c7 as r7c7, col7.c8 as r8c7, col7.c9 as r9c7, col8.c1 as r1c8, col8.c2 as r2c8,col8.c3 as r3c8, col8.c4 as r4c8, col8.c5 as r5c8, col8.c6 as r6c8, col8.c7 as r7c8, col8.c8 as r8c8, col8.c9 as r9c8, col9.c1 as r1c9, col9.c2 as r2c9, col9.c3 as r3c9,col9.c4 as r4c9, col9.c5 as r5c9, col9.c6 as r6c9, col9.c7 as r7c9, col9.c8 as r8c9, col9.c9 as r9c9 FROM positions col1, positions col2, positions col3,positions col4, positions col5, positions col6,positions col7, positions col8, positions col9 WHERE -- Nombres uniques dans chaque rangee (col1.c1 <> col2.c1) AND (col1.c1 <> col3.c1) AND (col1.c1 <> col4.c1) AND (col1.c1 <> col5.c1) AND (col1.c1 <> col6.c1) AND (col1.c1 <> col7.c1) AND (col1.c1 <> col8.c1) AND (col1.c1 <> col9.c1) AND (col1.c2 <> col2.c2) AND (col1.c2 <> col3.c2) AND (col1.c2 <> col4.c2) AND (col1.c2 <> col5.c2) AND (col1.c2 <> col6.c2) AND (col1.c2 <> col7.c2) AND (col1.c2 <> col8.c2) AND (col1.c2 <> col9.c2) AND (col1.c3 <> col2.c3) AND (col1.c3 <> col3.c3) AND (col1.c3 <> col4.c3) AND (col1.c3 <> col5.c3) AND (col1.c3 <> col6.c3) AND (col1.c3 <> col7.c3) AND (col1.c3 <> col8.c3) AND (col1.c3 <> col9.c3) AND (col1.c4 <> col2.c4) AND (col1.c4 <> col3.c4) AND (col1.c4 <> col4.c4) AND (col1.c4 <> col5.c4) AND (col1.c4 <> col6.c4) AND (col1.c4 <> col7.c4) AND (col1.c4 <> col8.c4) AND (col1.c4 <> col9.c4) AND (col1.c5 <> col2.c5) AND (col1.c5 <> col3.c5) AND (col1.c5 <> col4.c5) AND (col1.c5 <> col5.c5) AND (col1.c5 <> col6.c5) AND (col1.c5 <> col7.c5) AND (col1.c5 <> col8.c5) AND (col1.c5 <> col9.c5) AND (col1.c6 <> col2.c6) AND (col1.c6 <> col3.c6) AND (col1.c6 <> col4.c6) AND (col1.c6 <> col5.c6) AND (col1.c6 <> col6.c6) AND (col1.c6 <> col7.c6) AND (col1.c6 <> col8.c6) AND (col1.c6 <> col9.c6) AND (col1.c7 <> col2.c7) AND (col1.c7 <> col3.c7) AND (col1.c7 <> col4.c7) AND (col1.c7 <> col5.c7) AND (col1.c7 <> col6.c7) AND (col1.c7 <> col7.c7) AND (col1.c7 <> col8.c7) AND (col1.c7 <> col9.c7) AND (col1.c8 <> col2.c8) AND (col1.c8 <> col3.c8) AND (col1.c8 <> col4.c8) AND (col1.c8 <> col5.c8) AND (col1.c8 <> col6.c8) AND (col1.c8 <> col7.c8) AND (col1.c8 <> col8.c8) AND (col1.c8 <> col9.c8) AND (col1.c9 <> col2.c9) AND (col1.c9 <> col3.c9) AND (col1.c9 <> col4.c9) AND (col1.c9 <> col5.c9) AND (col1.c9 <> col6.c9) AND (col1.c9 <> col7.c9) AND (col1.c9 <> col8.c9) AND (col1.c9 <> col9.c9) AND (col2.c1 <> col3.c1) AND (col2.c1 <> col4.c1) AND (col2.c1 <> col5.c1) AND (col2.c1 <> col6.c1) AND (col2.c1 <> col7.c1) AND (col2.c1 <> col8.c1) AND (col2.c1 <> col9.c1) AND (col2.c2 <> col3.c2) AND (col2.c2 <> col4.c2) AND (col2.c2 <> col5.c2) AND (col2.c2 <> col6.c2) AND (col2.c2 <> col7.c2) AND (col2.c2 <> col8.c2) AND (col2.c2 <> col9.c2) AND (col2.c3 <> col3.c3) AND (col2.c3 <> col4.c3) AND (col2.c3 <> col5.c3) AND (col2.c3 <> col6.c3) AND (col2.c3 <> col7.c3) AND (col2.c3 <> col8.c3) AND (col2.c3 <> col9.c3) AND (col2.c4 <> col3.c4) AND (col2.c4 <> col4.c4) AND (col2.c4 <> col5.c4) AND (col2.c4 <> col6.c4) AND (col2.c4 <> col7.c4) AND (col2.c4 <> col8.c4) AND (col2.c4 <> col9.c4) AND (col2.c5 <> col3.c5) AND (col2.c5 <> col4.c5) AND (col2.c5 <> col5.c5) AND (col2.c5 <> col6.c5) AND (col2.c5 <> col7.c5) AND (col2.c5 <> col8.c5) AND (col2.c5 <> col9.c5) AND (col2.c6 <> col3.c6) AND (col2.c6 <> col4.c6) AND (col2.c6 <> col5.c6) AND (col2.c6 <> col6.c6) AND (col2.c6 <> col7.c6) AND (col2.c6 <> col8.c6) AND (col2.c6 <> col9.c6) AND (col2.c7 <> col3.c7) AND (col2.c7 <> col4.c7) AND (col2.c7 <> col5.c7) AND (col2.c7 <> col6.c7) AND (col2.c7 <> col7.c7) AND (col2.c7 <> col8.c7) AND (col2.c7 <> col9.c7) AND (col2.c8 <> col3.c8) AND (col2.c8 <> col4.c8) AND (col2.c8 <> col5.c8) AND (col2.c8 <> col6.c8) AND (col2.c8 <> col7.c8) AND (col2.c8 <> col8.c8) AND (col2.c8 <> col9.c8) AND (col2.c9 <> col3.c9) AND (col2.c9 <> col4.c9) AND (col2.c9 <> col5.c9) AND (col2.c9 <> col6.c9) AND (col2.c9 <> col7.c9) AND (col2.c9 <> col8.c9) AND (col2.c9 <> col9.c9) AND (col3.c1 <> col4.c1) AND (col3.c1 <> col5.c1) AND (col3.c1 <> col6.c1) AND (col3.c1 <> col7.c1) AND (col3.c1 <> col8.c1) AND (col3.c1 <> col9.c1) AND (col3.c2 <> col4.c2) AND (col3.c2 <> col5.c2) AND (col3.c2 <> col6.c2) AND (col3.c2 <> col7.c2) AND (col3.c2 <> col8.c2) AND (col3.c2 <> col9.c2) AND (col3.c3 <> col4.c3) AND (col3.c3 <> col5.c3) AND (col3.c3 <> col6.c3) AND (col3.c3 <> col7.c3) AND (col3.c3 <> col8.c3) AND (col3.c3 <> col9.c3) AND (col3.c4 <> col4.c4) AND (col3.c4 <> col5.c4) AND (col3.c4 <> col6.c4) AND (col3.c4 <> col7.c4) AND (col3.c4 <> col8.c4) AND (col3.c4 <> col9.c4) AND (col3.c5 <> col4.c5) AND (col3.c5 <> col5.c5) AND (col3.c5 <> col6.c5) AND (col3.c5 <> col7.c5) AND (col3.c5 <> col8.c5) AND (col3.c5 <> col9.c5) AND (col3.c6 <> col4.c6) AND (col3.c6 <> col5.c6) AND (col3.c6 <> col6.c6) AND (col3.c6 <> col7.c6) AND (col3.c6 <> col8.c6) AND (col3.c6 <> col9.c6) AND (col3.c7 <> col4.c7) AND (col3.c7 <> col5.c7) AND (col3.c7 <> col6.c7) AND (col3.c7 <> col7.c7) AND (col3.c7 <> col8.c7) AND (col3.c7 <> col9.c7) AND (col3.c8 <> col4.c8) AND (col3.c8 <> col5.c8) AND (col3.c8 <> col6.c8) AND (col3.c8 <> col7.c8) AND (col3.c8 <> col8.c8) AND (col3.c8 <> col9.c8) AND (col3.c9 <> col4.c9) AND (col3.c9 <> col5.c9) AND (col3.c9 <> col6.c9) AND (col3.c9 <> col7.c9) AND (col3.c9 <> col8.c9) AND (col3.c9 <> col9.c9) AND (col4.c1 <> col5.c1) AND (col4.c1 <> col6.c1) AND (col4.c1 <> col7.c1) AND (col4.c1 <> col8.c1) AND (col4.c1 <> col9.c1) AND (col4.c2 <> col5.c2) AND (col4.c2 <> col6.c2) AND (col4.c2 <> col7.c2) AND (col4.c2 <> col8.c2) AND (col4.c2 <> col9.c2) AND (col4.c3 <> col5.c3) AND (col4.c3 <> col6.c3) AND (col4.c3 <> col7.c3) AND (col4.c3 <> col8.c3) AND (col4.c3 <> col9.c3) AND (col4.c4 <> col5.c4) AND (col4.c4 <> col6.c4) AND (col4.c4 <> col7.c4) AND (col4.c4 <> col8.c4) AND (col4.c4 <> col9.c4) AND (col4.c5 <> col5.c5) AND (col4.c5 <> col6.c5) AND (col4.c5 <> col7.c5) AND (col4.c5 <> col8.c5) AND (col4.c5 <> col9.c5) AND (col4.c6 <> col5.c6) AND (col4.c6 <> col6.c6) AND (col4.c6 <> col7.c6) AND (col4.c6 <> col8.c6) AND (col4.c6 <> col9.c6) AND (col4.c7 <> col5.c7) AND (col4.c7 <> col6.c7) AND (col4.c7 <> col7.c7) AND (col4.c7 <> col8.c7) AND (col4.c7 <> col9.c7) AND (col4.c8 <> col5.c8) AND (col4.c8 <> col6.c8) AND (col4.c8 <> col7.c8) AND (col4.c8 <> col8.c8) AND (col4.c8 <> col9.c8) AND (col4.c9 <> col5.c9) AND (col4.c9 <> col6.c9) AND (col4.c9 <> col7.c9) AND (col4.c9 <> col8.c9) AND (col4.c9 <> col9.c9) AND (col5.c1 <> col6.c1) AND (col5.c1 <> col7.c1) AND (col5.c1 <> col8.c1) AND (col5.c1 <> col9.c1) AND (col5.c2 <> col6.c2) AND (col5.c2 <> col7.c2) AND (col5.c2 <> col8.c2) AND (col5.c2 <> col9.c2) AND (col5.c3 <> col6.c3) AND (col5.c3 <> col7.c3) AND (col5.c3 <> col8.c3) AND (col5.c3 <> col9.c3) AND (col5.c4 <> col6.c4) AND (col5.c4 <> col7.c4) AND (col5.c4 <> col8.c4) AND (col5.c4 <> col9.c4) AND (col5.c5 <> col6.c5) AND (col5.c5 <> col7.c5) AND (col5.c5 <> col8.c5) AND (col5.c5 <> col9.c5) AND (col5.c6 <> col6.c6) AND (col5.c6 <> col7.c6) AND (col5.c6 <> col8.c6) AND (col5.c6 <> col9.c6) AND (col5.c7 <> col6.c7) AND (col5.c7 <> col7.c7) AND (col5.c7 <> col8.c7) AND (col5.c7 <> col9.c7) AND (col5.c8 <> col6.c8) AND (col5.c8 <> col7.c8) AND (col5.c8 <> col8.c8) AND (col5.c8 <> col9.c8) AND (col5.c9 <> col6.c9) AND (col5.c9 <> col7.c9) AND (col5.c9 <> col8.c9) AND (col5.c9 <> col9.c9) AND (col6.c1 <> col7.c1) AND (col6.c1 <> col8.c1) AND (col6.c1 <> col9.c1) AND (col6.c2 <> col7.c2) AND (col6.c2 <> col8.c2) AND (col6.c2 <> col9.c2) AND (col6.c3 <> col7.c3) AND (col6.c3 <> col8.c3) AND (col6.c3 <> col9.c3) AND (col6.c4 <> col7.c4) AND (col6.c4 <> col8.c4) AND (col6.c4 <> col9.c4) AND (col6.c5 <> col7.c5) AND (col6.c5 <> col8.c5) AND (col6.c5 <> col9.c5) AND (col6.c6 <> col7.c6) AND (col6.c6 <> col8.c6) AND (col6.c6 <> col9.c6) AND (col6.c7 <> col7.c7) AND (col6.c7 <> col8.c7) AND (col6.c7 <> col9.c7) AND (col6.c8 <> col7.c8) AND (col6.c8 <> col8.c8) AND (col6.c8 <> col9.c8) AND (col6.c9 <> col7.c9) AND (col6.c9 <> col8.c9) AND (col6.c9 <> col9.c9) AND (col7.c1 <> col8.c1) AND (col7.c1 <> col9.c1) AND (col7.c2 <> col8.c2) AND (col7.c2 <> col9.c2) AND (col7.c3 <> col8.c3) AND (col7.c3 <> col9.c3) AND (col7.c4 <> col8.c4) AND (col7.c4 <> col9.c4) AND (col7.c5 <> col8.c5) AND (col7.c5 <> col9.c5) AND (col7.c6 <> col8.c6) AND (col7.c6 <> col9.c6) AND (col7.c7 <> col8.c7) AND (col7.c7 <> col9.c7) AND (col7.c8 <> col8.c8) AND (col7.c8 <> col9.c8) AND (col7.c9 <> col8.c9) AND (col7.c9 <> col9.c9) AND (col8.c1 <> col9.c1) AND (col8.c2 <> col9.c2) AND (col8.c3 <> col9.c3) AND (col8.c4 <> col9.c4) AND (col8.c5 <> col9.c5) AND (col8.c6 <> col9.c6) AND (col8.c7 <> col9.c7) AND (col8.c8 <> col9.c8) AND (col8.c9 <> col9.c9) AND -- Nombres uniques dans chaque maison de 3x3 (col1.c1 <> col1.c2) AND (col1.c1 <> col1.c3) AND (col1.c1 <> col2.c2) AND (col1.c1 <> col2.c3) AND (col1.c1 <> col3.c2) AND (col1.c1 <> col3.c3) AND (col1.c2 <> col1.c3) AND (col1.c2 <> col2.c1) AND (col1.c2 <> col2.c3) AND (col1.c2 <> col3.c1) AND (col1.c2 <> col3.c3) AND (col1.c3 <> col2.c1) AND (col1.c3 <> col2.c2) AND (col1.c3 <> col3.c1) AND (col1.c3 <> col3.c2) AND (col1.c4 <> col1.c5) AND (col1.c4 <> col1.c6) AND (col1.c4 <> col2.c5) AND (col1.c4 <> col2.c6) AND (col1.c4 <> col3.c5) AND (col1.c4 <> col3.c6) AND (col1.c5 <> col1.c6) AND (col1.c5 <> col2.c4) AND (col1.c5 <> col2.c6) AND (col1.c5 <> col3.c4) AND (col1.c5 <> col3.c6) AND (col1.c6 <> col2.c4) AND (col1.c6 <> col2.c5) AND (col1.c6 <> col3.c4) AND (col1.c6 <> col3.c5) AND (col1.c7 <> col1.c8) AND (col1.c7 <> col1.c9) AND (col1.c7 <> col2.c8) AND (col1.c7 <> col2.c9) AND (col1.c7 <> col3.c8) AND (col1.c7 <> col3.c9) AND (col1.c8 <> col1.c9) AND (col1.c8 <> col2.c7) AND (col1.c8 <> col2.c9) AND (col1.c8 <> col3.c7) AND (col1.c8 <> col3.c9) AND (col1.c9 <> col2.c7) AND (col1.c9 <> col2.c8) AND (col1.c9 <> col3.c7) AND (col1.c9 <> col3.c8) AND (col2.c1 <> col2.c2) AND (col2.c1 <> col2.c3) AND (col2.c1 <> col3.c2) AND (col2.c1 <> col3.c3) AND (col2.c2 <> col2.c3) AND (col2.c2 <> col3.c1) AND (col2.c2 <> col3.c3) AND (col2.c3 <> col3.c1) AND (col2.c3 <> col3.c2) AND (col2.c4 <> col2.c5) AND (col2.c4 <> col2.c6) AND (col2.c4 <> col3.c5) AND (col2.c4 <> col3.c6) AND (col2.c5 <> col2.c6) AND (col2.c5 <> col3.c4) AND (col2.c5 <> col3.c6) AND (col2.c6 <> col3.c4) AND (col2.c6 <> col3.c5) AND (col2.c7 <> col2.c8) AND (col2.c7 <> col2.c9) AND (col2.c7 <> col3.c8) AND (col2.c7 <> col3.c9) AND (col2.c8 <> col2.c9) AND (col2.c8 <> col3.c7) AND (col2.c8 <> col3.c9) AND (col2.c9 <> col3.c7) AND (col2.c9 <> col3.c8) AND (col3.c1 <> col3.c2) AND (col3.c1 <> col3.c3) AND (col3.c2 <> col3.c3) AND (col3.c4 <> col3.c5) AND (col3.c4 <> col3.c6) AND (col3.c5 <> col3.c6) AND (col3.c7 <> col3.c8) AND (col3.c7 <> col3.c9) AND (col3.c8 <> col3.c9) AND (col4.c1 <> col4.c2) AND (col4.c1 <> col4.c3) AND (col4.c1 <> col5.c2) AND (col4.c1 <> col5.c3) AND (col4.c1 <> col6.c2) AND (col4.c1 <> col6.c3) AND (col4.c2 <> col4.c3) AND (col4.c2 <> col5.c1) AND (col4.c2 <> col5.c3) AND (col4.c2 <> col6.c1) AND (col4.c2 <> col6.c3) AND (col4.c3 <> col5.c1) AND (col4.c3 <> col5.c2) AND (col4.c3 <> col6.c1) AND (col4.c3 <> col6.c2) AND (col4.c4 <> col4.c5) AND (col4.c4 <> col4.c6) AND (col4.c4 <> col5.c5) AND (col4.c4 <> col5.c6) AND (col4.c4 <> col6.c5) AND (col4.c4 <> col6.c6) AND (col4.c5 <> col4.c6) AND (col4.c5 <> col5.c4) AND (col4.c5 <> col5.c6) AND (col4.c5 <> col6.c4) AND (col4.c5 <> col6.c6) AND (col4.c6 <> col5.c4) AND (col4.c6 <> col5.c5) AND (col4.c6 <> col6.c4) AND (col4.c6 <> col6.c5) AND (col4.c7 <> col4.c8) AND (col4.c7 <> col4.c9) AND (col4.c7 <> col5.c8) AND (col4.c7 <> col5.c9) AND (col4.c7 <> col6.c8) AND (col4.c7 <> col6.c9) AND (col4.c8 <> col4.c9) AND (col4.c8 <> col5.c7) AND (col4.c8 <> col5.c9) AND (col4.c8 <> col6.c7) AND (col4.c8 <> col6.c9) AND (col4.c9 <> col5.c7) AND (col4.c9 <> col5.c8) AND (col4.c9 <> col6.c7) AND (col4.c9 <> col6.c8) AND (col5.c1 <> col5.c2) AND (col5.c1 <> col5.c3) AND (col5.c1 <> col6.c2) AND (col5.c1 <> col6.c3) AND (col5.c2 <> col5.c3) AND (col5.c2 <> col6.c1) AND (col5.c2 <> col6.c3) AND (col5.c3 <> col6.c1) AND (col5.c3 <> col6.c2) AND (col5.c4 <> col5.c5) AND (col5.c4 <> col5.c6) AND (col5.c4 <> col6.c5) AND (col5.c4 <> col6.c6) AND (col5.c5 <> col5.c6) AND (col5.c5 <> col6.c4) AND (col5.c5 <> col6.c6) AND (col5.c6 <> col6.c4) AND (col5.c6 <> col6.c5) AND (col5.c7 <> col5.c8) AND (col5.c7 <> col5.c9) AND (col5.c7 <> col6.c8) AND (col5.c7 <> col6.c9) AND (col5.c8 <> col5.c9) AND (col5.c8 <> col6.c7) AND (col5.c8 <> col6.c9) AND (col5.c9 <> col6.c7) AND (col5.c9 <> col6.c8) AND (col6.c1 <> col6.c2) AND (col6.c1 <> col6.c3) AND (col6.c2 <> col6.c3) AND (col6.c4 <> col6.c5) AND (col6.c4 <> col6.c6) AND (col6.c5 <> col6.c6) AND (col6.c7 <> col6.c8) AND (col6.c7 <> col6.c9) AND (col6.c8 <> col6.c9) AND (col7.c1 <> col7.c2) AND (col7.c1 <> col7.c3) AND (col7.c1 <> col8.c2) AND (col7.c1 <> col8.c3) AND (col7.c1 <> col9.c2) AND (col7.c1 <> col9.c3) AND (col7.c2 <> col7.c3) AND (col7.c2 <> col8.c1) AND (col7.c2 <> col8.c3) AND (col7.c2 <> col9.c1) AND (col7.c2 <> col9.c3) AND (col7.c3 <> col8.c1) AND (col7.c3 <> col8.c2) AND (col7.c3 <> col9.c1) AND (col7.c3 <> col9.c2) AND (col7.c4 <> col7.c5) AND (col7.c4 <> col7.c6) AND (col7.c4 <> col8.c5) AND (col7.c4 <> col8.c6) AND (col7.c4 <> col9.c5) AND (col7.c4 <> col9.c6) AND (col7.c5 <> col7.c6) AND (col7.c5 <> col8.c4) AND (col7.c5 <> col8.c6) AND (col7.c5 <> col9.c4) AND (col7.c5 <> col9.c6) AND (col7.c6 <> col8.c4) AND (col7.c6 <> col8.c5) AND (col7.c6 <> col9.c4) AND (col7.c6 <> col9.c5) AND (col7.c7 <> col7.c8) AND (col7.c7 <> col7.c9) AND (col7.c7 <> col8.c8) AND (col7.c7 <> col8.c9) AND (col7.c7 <> col9.c8) AND (col7.c7 <> col9.c9) AND (col7.c8 <> col7.c9) AND (col7.c8 <> col8.c7) AND (col7.c8 <> col8.c9) AND (col7.c8 <> col9.c7) AND (col7.c8 <> col9.c9) AND (col7.c9 <> col8.c7) AND (col7.c9 <> col8.c8) AND (col7.c9 <> col9.c7) AND (col7.c9 <> col9.c8) AND (col8.c1 <> col8.c2) AND (col8.c1 <> col8.c3) AND (col8.c1 <> col9.c2) AND (col8.c1 <> col9.c3) AND (col8.c2 <> col8.c3) AND (col8.c2 <> col9.c1) AND (col8.c2 <> col9.c3) AND (col8.c3 <> col9.c1) AND (col8.c3 <> col9.c2) AND (col8.c4 <> col8.c5) AND (col8.c4 <> col8.c6) AND (col8.c4 <> col9.c5) AND (col8.c4 <> col9.c6) AND (col8.c5 <> col8.c6) AND (col8.c5 <> col9.c4) AND (col8.c5 <> col9.c6) AND (col8.c6 <> col9.c4) AND (col8.c6 <> col9.c5) AND (col8.c7 <> col8.c8) AND (col8.c7 <> col8.c9) AND (col8.c7 <> col9.c8) AND (col8.c7 <> col9.c9) AND (col8.c8 <> col8.c9) AND (col8.c8 <> col9.c7) AND (col8.c8 <> col9.c9) AND (col8.c9 <> col9.c7) AND (col8.c9 <> col9.c8) AND (col9.c1 <> col9.c2) AND (col9.c1 <> col9.c3) AND (col9.c2 <> col9.c3) AND (col9.c4 <> col9.c5) AND (col9.c4 <> col9.c6) AND (col9.c5 <> col9.c6) AND (col9.c7 <> col9.c8) AND (col9.c7 <> col9.c9) AND (col9.c8 <> col9.c9);
Maintenant, chers lecteurs, patientez un peu!
ATTENTION : n’allez surtout pas essayer de solutionner une grille avant de passer au prochain point!
Pour l’instant, contentez-vous seulement de créer la nouvelle vue sudoku_combined_view :
USE sudoku; CREATE VIEW sudoku_combined_view AS SELECT t1.* FROM sudoku_rows_view t1 INNER JOIN sudoku_columns_view t2 ON -- Jointures entre représentation-colonnes et représentation-rangées (t1.r1c1 = t2.r1c1) AND (t1.r1c2 = t2.r1c2) AND (t1.r1c3 = t2.r1c3) AND (t1.r1c4 = t2.r1c4) AND (t1.r1c5 = t2.r1c5) AND (t1.r1c6 = t2.r1c6) AND (t1.r1c7 = t2.r1c7) AND (t1.r1c8 = t2.r1c8) AND (t1.r1c9 = t2.r1c9) AND (t1.r2c1 = t2.r2c1) AND (t1.r2c2 = t2.r2c2) AND (t1.r2c3 = t2.r2c3) AND (t1.r2c4 = t2.r2c4) AND (t1.r2c5 = t2.r2c5) AND (t1.r2c6 = t2.r2c6) AND (t1.r2c7 = t2.r2c7) AND (t1.r2c8 = t2.r2c8) AND (t1.r2c9 = t2.r2c9) AND (t1.r3c1 = t2.r3c1) AND (t1.r3c2 = t2.r3c2) AND (t1.r3c3 = t2.r3c3) AND (t1.r3c4 = t2.r3c4) AND (t1.r3c5 = t2.r3c5) AND (t1.r3c6 = t2.r3c6) AND (t1.r3c7 = t2.r3c7) AND (t1.r3c8 = t2.r3c8) AND (t1.r3c9 = t2.r3c9) AND (t1.r4c1 = t2.r4c1) AND (t1.r4c2 = t2.r4c2) AND (t1.r4c3 = t2.r4c3) AND (t1.r4c4 = t2.r4c4) AND (t1.r4c5 = t2.r4c5) AND (t1.r4c6 = t2.r4c6) AND (t1.r4c7 = t2.r4c7) AND (t1.r4c8 = t2.r4c8) AND (t1.r4c9 = t2.r4c9) AND (t1.r5c1 = t2.r5c1) AND (t1.r5c2 = t2.r5c2) AND (t1.r5c3 = t2.r5c3) AND (t1.r5c4 = t2.r5c4) AND (t1.r5c5 = t2.r5c5) AND (t1.r5c6 = t2.r5c6) AND (t1.r5c7 = t2.r5c7) AND (t1.r5c8 = t2.r5c8) AND (t1.r5c9 = t2.r5c9) AND (t1.r6c1 = t2.r6c1) AND (t1.r6c2 = t2.r6c2) AND (t1.r6c3 = t2.r6c3) AND (t1.r6c4 = t2.r6c4) AND (t1.r6c5 = t2.r6c5) AND (t1.r6c6 = t2.r6c6) AND (t1.r6c7 = t2.r6c7) AND (t1.r6c8 = t2.r6c8) AND (t1.r6c9 = t2.r6c9) AND (t1.r7c1 = t2.r7c1) AND (t1.r7c2 = t2.r7c2) AND (t1.r7c3 = t2.r7c3) AND (t1.r7c4 = t2.r7c4) AND (t1.r7c5 = t2.r7c5) AND (t1.r7c6 = t2.r7c6) AND (t1.r7c7 = t2.r7c7) AND (t1.r7c8 = t2.r7c8) AND (t1.r7c9 = t2.r7c9) AND (t1.r8c1 = t2.r8c1) AND (t1.r8c2 = t2.r8c2) AND (t1.r8c3 = t2.r8c3) AND (t1.r8c4 = t2.r8c4) AND (t1.r8c5 = t2.r8c5) AND (t1.r8c6 = t2.r8c6) AND (t1.r8c7 = t2.r8c7) AND (t1.r8c8 = t2.r8c8) AND (t1.r8c9 = t2.r8c9) AND (t1.r9c1 = t2.r9c1) AND (t1.r9c2 = t2.r9c2) AND (t1.r9c3 = t2.r9c3) AND (t1.r9c4 = t2.r9c4) AND (t1.r9c5 = t2.r9c5) AND (t1.r9c6 = t2.r9c6) AND (t1.r9c7 = t2.r9c7) AND (t1.r9c8 = t2.r9c8) AND (t1.r9c9 = t2.r9c9);
4. L’optimisateur de plan
Avant de tenter d’exécuter la requête de la grille présentée au point 1 de cet article, quelques explications sont de mise. Il appert que notre nouvelle façon de faire change radicalement les choses!
En effet, au lieu de joindre seulement 9 tables comme c’était le cas avec sudoku_rows_view, notre nouvelle solution joint 9 tables une première fois (sudoku_rows_view), encore une fois 9 tables (sudoku_columns_view) puis regroupe les résultats de ces 2 vues dans sudoku_combined_view.
Il faut savoir que l’optimisateur de requêtes de MySQL, par défaut, énumère toutes les jointures possibles pour déterminer le plan d’accès qu’il considère comme optimal. Dans le cas qui nous intéresse, l’optimisateur détecte donc 18 tables indirectement référencées par la vue sudoku_combined_view et aura donc à examiner 18! (18 factorielle) jointures possibles, c’est-à-dire un total de 6402373705728000 jointures! Si par malheur vous tentiez d’exécuter la requête sur la vue sudoku_combined_view, il vous faudrait attendre une éternité avant que MySQL détermine un plan d’accès! Pour vérifier, j’ai laissé rouler une requête de EXPLAIN sur la vue sudoku_combined_view pendant 2 jours avant de l’arrêter…
Heureusement, il existe une variable système nous permettant de contrôler le zèle de l’optimisateur de requêtes! Cette variable s’appelle optimizer_search_depth. Elle détermine la profondeur d’analyse de l’optimisateur quand celui-ci essaie de trouver le plan d’accès optimal. À quoi bon un plan d’accès optimal si celui-ci prend 3 semaines à être généré ? En ce qui nous concerne, un plan d’accès non optimal mais généré rapidement, compte tenu des 18 tables, est ce que nous recherchons!
La variable optimizer_search_depth peut être changée dans les fichiers de configuration de MySQL ou dynamiquement au beau milieu d’une session. Prenez garde toutefois! Si vous changez cette variable dans une session et non au niveau des fichiers de configuration, la nouvelle valeur de la variable ne s’applique qu’à la session!
Réglons cette valeur à 3 pour l’instant (plus de détails quant à cette valeur dans le prochain article) :
set @@optimizer_search_depth = 3;
Maintenant, nous pouvons exécuter notre requête :
SELECT * FROM sudoku_combined_view WHERE (r2c1 = 1) AND (r2c2 = 3) AND (r2c3 = 4) AND (r2c4 = 8) AND (r2c5 = 2) AND (r2c6 = 5) AND (r2c7 = 6) AND (r2c8 = 9) AND (r2c9 = 7) AND (r3c1 = 7) AND (r3c2 = 5) AND (r3c3 = 9) AND (r3c4 = 3) AND (r3c5 = 6) AND (r3c6 = 4) AND (r3c7 = 1) AND (r3c8 = 8) AND (r3c9 = 2) AND (r4c1 = 3) AND (r4c2 = 9) AND (r4c3 = 7) AND (r4c4 = 1) AND (r4c5 = 8) AND (r4c6 = 2) AND (r4c7 = 5) AND (r4c8 = 6) AND (r4c9 = 4) AND (r6c1 = 5) AND (r6c2 = 8) AND (r6c3 = 1) AND (r6c4 = 4) AND (r6c5 = 7) AND (r6c6 = 6) AND (r6c7 = 2) AND (r6c8 = 3) AND (r6c9 = 9) AND (r7c1 = 8) AND (r7c2 = 2) AND (r7c3 = 5) AND (r7c4 = 6) AND (r7c5 = 4) AND (r7c6 = 1) AND (r7c7 = 9) AND (r7c8 = 7) AND (r7c9 = 3) AND (r8c1 = 9) AND (r8c2 = 7) AND (r8c3 = 6) AND (r8c4 = 5) AND (r8c5 = 3) AND (r8c6 = 8) AND (r8c7 = 4) AND (r8c8 = 2) AND (r8c9 = 1);
Fantastique! 1.08 seconde! Est-il possible d’extraire plus de jus de ce citron?
Voyons ce que le EXPLAIN a à nous dire :
+----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+-------------------------------+------+--------------------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+-------------------------------+------+--------------------------------------------------------------+ | 1 | SIMPLE | col3 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i38,i48 | 2,2,2 | NULL | 64 | Using intersect(i23,i38,i48); Using where | | 1 | SIMPLE | col9 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i78,i68,i48 | 2,2,2 | NULL | 65 | Using intersect(i78,i68,i48); Using where; Using join buffer | | 1 | SIMPLE | r2 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i29 | 2,2 | NULL | 68 | Using intersect(i37,i29); Using where; Using join buffer | | 1 | SIMPLE | r3 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i28 | 2,2 | NULL | 68 | Using intersect(i37,i28); Using where; Using join buffer | | 1 | SIMPLE | r4 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i56,i29 | 2,2 | NULL | 68 | Using intersect(i56,i29); Using where; Using join buffer | | 1 | SIMPLE | r6 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12,i35 | 2,2 | NULL | 68 | Using intersect(i12,i35); Using where; Using join buffer | | 1 | SIMPLE | r7 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12,i68 | 2,2 | NULL | 68 | Using intersect(i12,i68); Using where; Using join buffer | | 1 | SIMPLE | col1 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i67 | 2,2 | NULL | 68 | Using intersect(i23,i67); Using where; Using join buffer | | 1 | SIMPLE | col2 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer | | 1 | SIMPLE | col4 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i78,i46 | 2,2 | NULL | 68 | Using intersect(i78,i46); Using where; Using join buffer | | 1 | SIMPLE | col5 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer | | 1 | SIMPLE | col6 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i67 | 2,2 | NULL | 68 | Using intersect(i23,i67); Using where; Using join buffer | | 1 | SIMPLE | r8 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i79,i38 | 2,2,2 | NULL | 78 | Using intersect(i37,i79,i38); Using where; Using join buffer | | 1 | SIMPLE | col8 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i37,i24 | 2,2 | NULL | 68 | Using intersect(i37,i24); Using where; Using join buffer | | 1 | SIMPLE | col7 | index_merge | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i23,i68 | 2,2 | NULL | 68 | Using intersect(i23,i68); Using where; Using join buffer | | 1 | SIMPLE | r1 | ref | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12 | 2 | sudoku.col1.c1,sudoku.col2.c1 | 5040 | Using where | | 1 | SIMPLE | r5 | ref | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12 | 2 | sudoku.col1.c5,sudoku.col2.c5 | 5040 | Using where | | 1 | SIMPLE | r9 | ref | i12,i13,i14,i15,i16,i17,i18,i19,i23,i24,i25,i26,i27,i28,i29,i34,i35,i36,i37,i38,i39,i45,i46,i47,i48,i49,i56,i57,i58,i59,i67,i68,i69,i78,i79,i89,i9 | i12 | 2 | sudoku.col1.c9,sudoku.col2.c9 | 5040 | Using where | +----+-------------+-------+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------+-------------+---------+-------------------------------+------+--------------------------------------------------------------+ 18 rows in set (0.28 sec)
5. Optimisation de la table
Il existe quelques trucs d’optimisation de table que nous avons omis de faire. C’est peut-être le temps d’y songer pour extraire chaque milliseconde et chaque octet possible!
Bien que la table positions ne subisse jamais de UPDATE, de INSERT ou de DELETE, sommes-nous certains que les pages d’index sont triées ? Pour ce faire, nous pourrions exécuter un OPTIMIZE TABLE sur la table positions. Ce serait inutile dans notre cas. Pourquoi? Parce que les permutations générées pour créer les requêtes d’insertion dans la table positions ont été générées dans l’ordre des index.
D’autre part, comme la table n’a connu aucune modification, un ANALYZE TABLE serait, lui aussi, totalement inutile!
Changer la définition de la table avec un ALTER TABLE pour y inclure AVG_ROW_LENGTH et MAX_ROWS ? Pas plus utile. Comme le format des lignes dans la table positions est Fixed et que la table est de format MyISAM, ces deux valeurs n’ont pas à être forcées puisque MySQL les détermine sans notre aide!
6. Impossible n’est pas français!
Est-ce possible de faire mieux? En éternel optimiste et têtu que je suis, je répondrai « oui » ! Mais comment?
Seulement, avons-nous tout prévu? Que faire avec une grille contenant des lignes vides et des colonnes vides comme la grille suivante :
Suite au prochain article!
L'endormitoire 