commit e0665b6dcb4b789bc2569d3fff3d4ae09ebadcbb
parent cc3d113e51eb6dab79e3bc8b0ae7687433644f57
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Thu, 20 Jan 2011 00:27:32 +0100
Requêtes SQL pour la création de parties.
Diffstat:
3 files changed, 92 insertions(+), 0 deletions(-)
diff --git a/code/serveur/select/01.random-node b/code/serveur/select/01.random-node
@@ -0,0 +1,44 @@
+// Select random node :
+// Comparaison de plusieurs méthodes :
+
+// Note : calculer un count(*) prend très longtemps, il vaut mieux faire un max(eid).
+
+// rapide, mais ne renvoie rien si on tombe sur un trou dans les eid, probabilité 105/229894 ≈ 1/2000
+select * from node where eid = (abs(random()) % (select max(eid) from node))+1;
+// assez rapide, renvoie le noeud 1 si on tombe sur un trou dans les eid
+select * from node where eid = (abs(random()) % (select max(eid) from node))+1 or eid = (select min(eid) from node where eid > 0) order by eid desc limit 1;
+// peu rapide, trouve toujours un row, aléatoire
+select * from node limit 1 offset (abs(random()) % (select count(*)+1 from node));
+
+// Comparaison des temps d'exécution des méthodes ci-dessus
+// Note : les deux premiers sont sur 10000 exécutions, le dernier sur 100
+
+> time yes "select * from node where eid = (abs(random()) % (select max(eid) from node));" | head -n 10000 | sqlite3 db > /dev/null
+yes 0,01s user 0,00s system 0% cpu 3,272 total
+head -n 10000 0,00s user 0,02s system 0% cpu 3,283 total
+sqlite3 db > /dev/null 2,70s user 0,52s system 89% cpu 3,586 total
+> time yes "select * from node where eid = (abs(random()) % (select max(eid) from node)) or eid = (select min(eid) from node where eid > 0) order by eid desc limit 1;" | head -n 10000 | sqlite3 db > /dev/null
+yes 0,01s user 0,01s system 0% cpu 7,324 total
+head -n 10000 0,01s user 0,02s system 0% cpu 7,340 total
+sqlite3 db > /dev/null 5,94s user 0,62s system 85% cpu 7,645 total
+> time yes "select * from node limit 1 offset (abs(random()) % (select count(*) from node));" | head -n 100 | sqlite3 db > /dev/null
+yes 0,01s user 0,00s system 33% cpu 0,024 total
+head -n 100 0,00s user 0,00s system 37% cpu 0,021 total
+sqlite3 db > /dev/null 7,40s user 5,99s system 89% cpu 14,984 total
+
+// Avec un index sur node(eid), nettement meilleur pour les deux premières méthodes
+// Les deux premières méthodes ne bougent pas, la troisième est pas mal améliorée.
+create index i_node_eid on node(eid);
+
+> time yes "select * from node where eid = (abs(random()) % (select max(eid) from node));" | head -n 10000 | sqlite3 db > /dev/null
+yes 0,01s user 0,01s system 0% cpu 3,421 total
+head -n 10000 0,00s user 0,02s system 0% cpu 3,439 total
+sqlite3 db > /dev/null 2,82s user 0,53s system 89% cpu 3,752 total
+> time yes "select * from node where eid = (abs(random()) % (select max(eid) from node)) or eid = (select min(eid) from node where eid > 0) order by eid desc limit 1;" | head -n 10000 | sqlite3 db > /dev/null
+yes 0,02s user 0,01s system 0% cpu 7,059 total
+head -n 10000 0,02s user 0,02s system 0% cpu 7,076 total
+sqlite3 db > /dev/null 6,10s user 0,54s system 89% cpu 7,390 total
+> time yes "select * from node limit 1 offset (abs(random()) % (select count(*) from node));" | head -n 100 | sqlite3 db > /dev/null
+yes 0,00s user 0,01s system 25% cpu 0,031 total
+head -n 100 0,00s user 0,00s system 27% cpu 0,029 total
+sqlite3 db > /dev/null 5,71s user 3,78s system 86% cpu 10,917 total
diff --git a/code/serveur/select/02.neighbors b/code/serveur/select/02.neighbors
@@ -0,0 +1,27 @@
+// BEAUCOUP plus rapide avec un index
+create index i_relation_start on relation(start);
+create index i_relation_end on relation(end);
+create index i_relation_type on relation(type);
+// Pour les voisins reliés par un end avec filtrage des types
+create index i_relation_end_type on relation(end,type);
+
+// select relations partant d'un noeud
+select * from relation where start = 42;
+
+// select cibles de relations partant d'un noeud
+select end from relation where start = 42;
+
+// Deux sauts
+select * from relation where start in (select end from relation where start = 42);
+
+// Mots qui ont des voisins en commun avec 42 (42->123, 314->123 : on prend 314)
+// Renvoie beaucoup trop de résultats à cause de certains types, il faut donc les exclure.
+select * from relation where end in (select end from relation where start = 42) and type not in (4, 12, 36, 18, 29, 45, 46, 47, 48, 1000, 1001);
+
+// types de relation à éviter :
+4 12 36 18 29 45 46 47 48 1000 1001
+// Liste des types de relation par ordre de plus gros nombre d'arcs entrants de ce type sur n'importe quel noeud :
+select count(end) as c, type, end from relation group by end order by c desc limit 50;
++ pas mal de manips pour avoir un distinct qui garde l'ordre :(
+4 12 666 41 36 18 3 0 6 42 5 15 9 14 28 32 10 17 35 16 23 8 13 34 52 7 50 37 22 49 30 25 31 51 54 20 24 38 39 40 43 21 1 44 19 55 33 11 46 999 27 26 45 48 29 2
+
diff --git a/code/serveur/select/03.partie b/code/serveur/select/03.partie
@@ -0,0 +1,21 @@
+pseudo-parameter : $taille_nuage
+
+// select random node
+select eid from node where eid = (abs(random()) % (select max(eid) from node))+1 or eid = (select max(eid) from node where eid > 0) order by eid desc limit 1;
+
+Difficulté 1 :
+// select neighbors 1 hop
+select end from relation where start = 42 limit $taille_nuage;
+
+Difficulté 2 :
+// select neighbors 2 hops
+select * from relation where start in (select end from relation where start = 42) limit $taille_nuage;
+
+Difficulté 3 :
+// select neighbors relative to the end (one hop start->end, one hop start<-end).
+select * from relation where end in (select end from relation where start = 42) and type not in (4, 12, 36, 18, 29, 45, 46, 47, 48, 1000, 1001) limit $taille_nuage;
+
+// Pour compléter :
+// select random words
+do "select random node" $taille_nuage times
+
