Join 2 grosses tables

Version imprimable

Bonjour,
je recherche un moyen de joindre ces 2 grosses tables dans un temps raisonnable.
Les 2 tables :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mysql> describe databases.ancestral;
+--------+-----------------------------------------------+------+-----+---------+-------+
| Field  | Type                                          | Null | Key | Default | Extra |
+--------+-----------------------------------------------+------+-----+---------+-------+
| chr    | tinyint(4) unsigned                           | NO   | MUL | NULL    |       |
| pos    | int(11) unsigned                              | NO   |     | NULL    |       |
| allele | enum('A','C','T','G','a','c','t','g','N','-') | NO   |     | NULL    |       |
+--------+-----------------------------------------------+------+-----+---------+-------+
mysql> describe data.get_ancestral;
+-----------+---------------------------------------------------+------+-----+---------+-------+
| Field     | Type                                              | Null | Key | Default | Extra |
+-----------+---------------------------------------------------+------+-----+---------+-------+
| chr       | tinyint(3) unsigned                               | NO   | MUL | NULL    |       |
| pos       | int(10) unsigned                                  | NO   |     | NULL    |       |
| ancestral | enum('.','A','C','T','G','a','c','t','g','N','-') | NO   |     | NULL    |       |
+-----------+---------------------------------------------------+------+-----+---------+-------+

ancestral contient 2 786 295 961 enregristrement (50GO)
get_ancestral contient 1 623 542 enregistrement (26.3MO)

J'ai essayé avec ou sans index, et le temps est toujours tres elevé.
Voici le describe des requetes ou :

ancestral a 'chr' pour index
ancestral2 a 'chr, pos' pour index
ancestral3 a aucun index

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
mysql> explain select count(*) from databases.ancestral natural join data.get_ancestral;
+----+-------------+---------------+------+---------------+------+---------+------------------------+---------+-------------+
| id | select_type | table         | type | possible_keys | key  | key_len | ref                    | rows    | Extra       |
+----+-------------+---------------+------+---------------+------+---------+------------------------+---------+-------------+
|  1 | SIMPLE      | get_ancestral | ALL  | chr           | NULL | NULL    | NULL                   | 1623542 |             |
|  1 | SIMPLE      | ancestral     | ref  | chr           | chr  | 1       | data.get_ancestral.chr |    2206 | Using where |
+----+-------------+---------------+------+---------------+------+---------+------------------------+---------+-------------+
2 rows in set (0.00 sec)
 
mysql> explain select count(*) from databases.ancestral2 natural join data.get_ancestral;
+----+-------------+---------------+------+---------------+------+---------+-----------------------------------------------+---------+-------------+
| id | select_type | table         | type | possible_keys | key  | key_len | ref                                           | rows    | Extra       |
+----+-------------+---------------+------+---------------+------+---------+-----------------------------------------------+---------+-------------+
|  1 | SIMPLE      | get_ancestral | ALL  | chr           | NULL | NULL    | NULL                                          | 1623542 |             |
|  1 | SIMPLE      | ancestral2    | ref  | chr           | chr  | 5       | data.get_ancestral.chr,data.get_ancestral.pos |    2206 | Using index |
+----+-------------+---------------+------+---------------+------+---------+-----------------------------------------------+---------+-------------+
2 rows in set (0.00 sec)
 
mysql> explain select count(*) from databases.ancestral3 natural join data.get_ancestral;
+----+-------------+---------------+------+---------------+------+---------+--------------------------+------------+-------------+
| id | select_type | table         | type | possible_keys | key  | key_len | ref                      | rows       | Extra       |
+----+-------------+---------------+------+---------------+------+---------+--------------------------+------------+-------------+
|  1 | SIMPLE      | ancestral3    | ALL  | NULL          | NULL | NULL    | NULL                     | 2786295961 |             |
|  1 | SIMPLE      | get_ancestral | ref  | chr           | chr  | 1       | databases.ancestral3.chr |         15 | Using where |
+----+-------------+---------------+------+---------------+------+---------+--------------------------+------------+-------------+
2 rows in set (0.00 sec)

Ma grande question :
Est ce qu'il y a quelque chose a améliorer, ou est ce que j'essaie de faire une requête impossible?
Merci de votre aide
Z.

23/02/2013, 03h42
ericd69

salut,

ah la bio informatique et le séquençage adn...

rien n'est impossible mais une question de compromis souvent...:zoubi:

c'est quoi ta requête exactement? tu joins sur quoi car natural join prend toutes les colonnes avec un nom commun... donc tu recherches tous les tuples communs (chr,pos) c'est ça?... mais bon natural join c'est un peu le MAL... il vau mieux faire un jointure explicite (left ou inner join) sur les colonnes voulues...

qu'est ce que tu cherches à faire vraiment? si c'est bien sur (chr,pos) un index sur chr ou chr,pos doit éviter d'aller lire l'autre colonne restante pour la jointure et donc permettre de gagner un peu...

pour info, int(11) c'est int (le nombre entre parentèse ne sert qu'à dire le nombre de chiffres significatifs pas la taille stockée) donc entier signé sur 4 octets (4 giga combinaisons)

enum stocke une forme numérique de type int à la place de chaque valeur texte de l'énumération... vu le nombre de tuple il peut être utile d'utiliser une table supplémentaire pour lister les variante d’allèles, en utilisant un tinyint ou mieux tinyint unsigned... histoire de compacter les colonnes correspondantes

selon le traitement, on peut envisager un partitionnement (mysql le supporte selon la version que tu as) de la grosse table mais sans plus d'info dur de dire si ça fera gagner...

l'index servira peu si tu n'a que ces colonnes mais si ça limite à une seule ou 2 de ces colonnes la recherche et/ou qu'il y en a d'autres (au cas où tu aurais "simplifié") c'est alors fort utile... là encore sans plus de détails...

selon le type des tables (mysam ou innodb) tu peux booster les valeurs dans le fichier de configuration de mysql qui touchent aux buffer d'index ou du buffer de données ou les buffers servant au classement si nécessaire avec sort dans leur nom (attention de ne jamais dépasser 75% de la valeur maximale possible sous peine de voir apparaitre une baisse de performance potentielle)

après y pas de secret tu ne feras jamais tenir tes tables en mémoire donc ça va forcément ramer...

pas besoin de te dire qu'il vaut mieux un serveur ou ordi costaud et si possible que tu destines à faire que ça... histoire de pas être parasité par d'autres processus...

bref tu vois y a certaines marges de manœuvre mais là encore faut partir sur le fait de bien dimensionner la machine puis configurer mysql en conséquence puis construire des tables les plus compactes possibles (ça limitera les besoin d'accès disque) et généralement indexer correctement (ou pas dans certains cas extrême)...
23/02/2013, 05h23
Zwiter

Merci de ta réponse.
Oui... le sequencage ADN, ARN, et encore ce n'est pas tout...
Je sais que NJ, enum et set font grincer des dents les experts en BDD, mais je ne vois pas de contrindications a leur usage.

Ma requete est exactement ce que c'est : je cherche a recuperer allele de la table ancestral pour chaque position contenue dans la table get_ancestral. Donc le natural join fait bien ce qu'il doit faire : jointure sur chr et pos.

int(10) et int(11) sont involontaires. Je sais que ca ne prendra pas moins de place. Je comprends pas comment ca c'est retrouvé comme ca, j'ai créé ces 2 tables ce matin sans specifié de taille a int. Peut etre le passage de signé a non signé alors que la table était déjà crée.

Par contre, enum (doc mysql): 1 ou 2 octets, suivant le nombre d'éléments de l'énumération (65535 au maximum). Donc 1 octet dans mon cas.

Partitionner : j' y ai pensé, mais avec un index sur chr, ca reviendrait au meme que partitionner par chr (valeurs de 1 a 26), non?

Effectivement, je n' ai que ces colonnes dans ce cas. Je craignais que les index me serviraient peu, a l'exception de chr. Tu me le confirmes.

J'utilise un autre moteur : tokudb. Il fait me fait deja des beaux miracles (index clusterés, insertions rapides, IO reduits) et je pense avoir boosté ses paramètres au max. Par contre, je connais moins ceux de mysqld. Je vais m'entretenir avec leur support technique pour optimiser mon serveur.

Hélas pour les tables en mémoire... Elles sont déjà enterrées depuis longtemps :P

Un ordi costaud : je pense être déjà pas mal au max. Je dispose d'une station dédiée sous centos avec xeon et 48GO, hdd infiniband sur un jbod ZFS (600MO/s). Les données sont compressées par tokudb (moins de données via le reseau et moins de IO) ainsi que on the fly par l'array de disque. Par contre, je ne pourrais pas avoir des slaves, ma licence tokudb n'autorise que 1 poste.

J'avais le rêve d'annoter mes jeux de positions via des tables d'annotations telles que ancestral, donc chromosome / position + 1 ou 2 infos par tables. Mais le génome humain est 3 milliards de nucléotides...

Tu peux me dire que ce que je veux faire est utopique, ca me va :p. Je cherche a savoir si j' ai fait le max.

Merci encore de ton support.
Z.
23/02/2013, 16h24
ericd69
si tu veux avoir un numérotage cohérent pos de 0 à 4 milliards tu dois utiliser int unsigned car int va de -2 milliard à +2 milliards

les tables entièrement en mémoire c'est justement ce qui est fait avec un serveur dédié à oracle (hyper cher) avec 1To de mémoire vive et les dd qui ne servent qu'à de la réplication... le rêve à un cout prohibitif bien sur...

le partitionnement est utile si tu cherches une ou des séquences particulières sous réserve qu'elle ne soient pas réparties sur toutes les partitions par la méthode de partition choisie... ça peut donc accélérer ou ralentir certains traitements...

c'est quoi les primary key, elles apparaissent pas? faut les dimensionner en conséquence et pas laisser mysql en faire une sinon il prend du big int par défaut il me semble...

d'ordre général, quand tu as un compteur (0 à n) faut choisir le type qui permet de stocker n comme valeur dans sa version non signée (unsigned) sinon:
- soit il faut prendre le type supérieur (peu efficace en terme de place)
- soit, en mode non strict, il interprétera certaines valeurs avec un - (celle avec un bit de poids fort à 1)
- soit, en mode strict, il déclenchera une erreur
ce que j'aime pas dans le "peut"... c'est le doute... de plus, enum est codé en dur une table c'est plus souple, un alter table et un re-remplissage de la colonne complet pas vraiment...

après pour comprendre mieux à quoi correspondent chr et pos exactement?... pos (comme position?) est relatif au génome complet ou à chr
23/02/2013, 21h05
Zwiter

unisgned int : je suis tout a fait d'accord. Toutefois, pos est la position sur le chromosome, et le plus grand chromosome : 250 000 000. Donc j' ai pas le choix que int.

1T de RAM... ouf ! mais pas pour nous.

Partitionnement : les recherches pourraient se faire par chromosomes. J'imagine bien de paralléliser les 26 chromosomes. Mais est ce que c' est un avantage par rapport a un index sur chr ?

Les primary key sont pas définitivement définie : j' ai testé celles qui iraient le plus vite (aucune, chr, chr + pos). Mais après 24h, aucune des différentes combinaisons de clé a permis de terminer la requête.

Je ne savais pas que mysql redimensionne les index en big int. Je me rensigne la dessus.

Enum est en dure. Mais mon moteur tokudb permet de suprimer et creer des colonnes sans lock de la table. Ducoup les données sont disponibles. De plus, l'ADN est composé que de 4 nucléotides : ACGT. Sauf découverte scientifique majeur, ca ne changera pas.

Merci enormement pour tes commentaires !

Voici les scripts de création des 2 tables :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 CREATE TABLE `get_ancestral` ( `chr` TINYINT(3) UNSIGNED NOT NULL, `pos` INT(11) UNSIGNED NOT NULL, `ancestral` ENUM('.','A','C','T','G','a','c','t','g','N','-') NOT NULL, INDEX `chr` (`chr`) ) COLLATE='latin1_swedish_ci' ENGINE=TokuDB; CREATE TABLE `ancestral` ( `chr` TINYINT(4) UNSIGNED NOT NULL, `pos` INT(11) UNSIGNED NOT NULL, `allele` ENUM('A','C','T','G','a','c','t','g','N','-') NOT NULL, INDEX `chr` (`chr`) ) COLLATE='latin1_swedish_ci' ENGINE=TokuDB;
Pour le nombre de positions numérotées a partir de 1 pour chaque chromosome, je te réfère a l'article wikipedia sur les chromosomes humain :
http://fr.wikipedia.org/wiki/Chromosomes_humains

Encore une fois : merci !

Et la requête pour compter les enregistrement pour chaque chromosome dans la très grande table ancestral :
Code:

1 2 3 4 5 # Time: 130223 15:24:25 # User@Host: root[root] @ [172.16.1.1] # Query_time: 756.795936 Lock_time: 0.000074 Rows_sent: 25 Rows_examined: 3095693981 SET timestamp=1361651065; select chr, count(*) from ancestral group by chr;
Je trouve que ainsi, ca tourne plutot vite. Pourquoi la jointure met-elle un temps infiniment plus grand?

23/02/2013, 21h58
ericd69

ah voilà c'est mieux quand tu donnes des billes!! oublie pas que tes données (leur nom) sont évidentes pour toi pas pour les autres...

diviser pour mieux régner!!!

bien sur que ça ramène à un jeu de données acceptable pour chaque traitement...
alors oui ça vaut le coup de partitionner sur le chromosome (type "list")...tu peux même dispacher les partitions sur des disques différents, c'est supporté...

à tester si ça joue vraiment... je sais pas s'il parallélisera mais ça ramènera à des fichiers moins lourds...vu que la moyennes des autosomes est de 120M bases

parce que tu joins 2 énormes tables qu'il faut bufferiser, traiter puis recracher les résultats... c'est pas un simple tri comme l'autre...

c'est jamais une bonne idée de ne pas avoir une clé primaire!!!!

quand tu fais ta recherche ancestral contient quoi en fait pour être aussi compact par rapport à l'autre qui sert de référence...

rapide tout est relatif biensur :aie: faut que tu boostes les buffers liés à tokdb...

une meilleure approche peut-être, te faire un petit cluster (physique voir logique au moins)... là tu es plus garanti de paralléliser mais là je sais pas si c'est possible pour toi... car je ne suis pas sur de combien de thread mysql génère ou utilise sur ce genre de traitement...

si tu peux aussi tester, si tu peux pas te faire un petit cluster de plusieurs ordi, si tu découpes en une table physique par chromosome... et de faire des requêtes inner join sur chacune éventuellement rassemblée avec des unions...
24/02/2013, 00h17
Zwiter

Merci pour ton temps et ton expertise. J'apprécie énormément.

J'ai lancé le partitioning de ma table ancestral. Je testerai cela sur 1 chromosome des que l'importation des données ancestral sera terminée.

Le but de tout ca est de tester si je peux annoter mes données via MySQL en un temps raisonnable, ou si je devrais passer par un script (perl ou programme en C).

je me doute...

mais bon je pense que là le plus efficace c'est vraiment la partition manuelle comme je te l'ai décri en mp...

car tu retombes alors dans des volumes de données acceptables...

y a pas de secret les échanges dd c'est le goulot d'étranglement ici pour toi...

une table par chromosome ça te donne donc une structure simple et compacte, par exemple:
Code:

1 2 3 4 5 create table chr1( pos int unsigned, allele enum('A','C','T','G','a','c','t','g','N','-') NOT NULL, primary key(pos) )ENGINE=TokuDB;
au passage, évite d'avoir la version majuscule et minuscule car lui ne te les trouveras pas comme égaux vu qu'ils n'ont pas le même identifiant dans la liste de l'enum...
pos peut servir de clé primaire car elle est unique pour une base sur un chromosome pas besoin de collation (plus de collision possible puisqu'on a un seul chromosome dans la table). ici y a pas de texte et tu crées une bd pour le truc (humain, animal, moisissure, etc...) de référence et une pour celui à comparer... comme ça une bd=un élément à utiliser pour les tests

une astuce est de te faire un api de procédures stockées qui exécutent des recherches paramétriques ensuite en encapsulant les appels à des requêtes préparée construite dynamiquement avec le nom des bd à utiliser...

teste en faisant un truc genre
Code:

1 2 select count(*) from bd1.chr1 a inner join bd2.chr1 b on a.pos=b.pos
ça te compte toutes les bases en commun dans les 2 bd
tu te crée une bd "api" qui te sert à mettre tes procédures stockée indépendamment des bd stockant les données.la version procédurale de ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 delimiter $$ drop procedure if exists api.compare_chr$$ create procedure api.compare_chr(in c tinyint unsigned,in sujet varchar(64),in ref varchar(64)) begin set @a=concat('select count(*) from `',sujet,'`.`chr',c,'` a inner join `',ref,'`.`chr',c,'` b on a.pos=b.pos'); prepare comparechr from @a; execute comparechr; deallocate prepare comparechr; end$$ #autre déclarations de procédures... delimiter ;
l'appel est alors:

Code:

call api.compare_chr(1,'humain1','humain2');

24/02/2013, 02h45
Zwiter

J'avais entendu parlé de cette solution lors d'une des réunions mensuelles des bioinformaticiens de Montréal. J'avoue avoir pensé naïvement que avec les ressources que j'avais a ma disposition (Xeon 48Go RAM + infiniband), ce genre de requêtes passeraient.

Mon dernier benchmark portera sur le temps d'exécution de la jointure d'une table ancestral_chr1 jointe avec une table get_ancestral_chr1.

Merci ericd69 !

Voici le résultat de la requête avec la table d'annotation ancestral qui ne contient que le chromosome 1 : 13 secondes!
Code:

1 2 3 4 5 # Time: 130223 22:57:21 # User@Host: root[root] @ [172.16.1.1] # Query_time: 12.977553 Lock_time: 0.000085 Rows_sent: 1 Rows_examined: 248356 SET timestamp=1361678241; select count(*) from databases.ancestral_chr1 natural join data.get_ancestral where chr=1;
Je vais donc spliter mes tables d'annotation par chromosome, et peut etre aussi ma table de données.
Milles merci pour ton aide
Z.

24/02/2013, 15h45
ericd69

fais les 2 et tu verras que les temps d'analyse tomberont encore... bien que 13s sur le plus gros chromosome c'est déjà très bien :ccool:

le temps du split est largement compensé....

c'est le principe sur tout traitement massif que tu peux splitter, c'est pour ça que beaucoup de trucs en bio info comme séquençage adn, le test de molécules, etc... le projet de calcul distribué boinc est basé sur ce principe en distribuant des unité de travail qui sont traités en parallèle par des volontaires...