Cloud Connected

I’m working since a few months on how storing trees in MySQL. It started like “hey, let’s make a database of every genre of heavy metal music!”. So I began with the easy way : a tree structure in a table genre with id and parent_id columns. And then I came to the point where I wanted to display the entire tree. This is just impossible with a reasonable number of queries, as there is no recursive syntax in standard SQL nor in MySQL (Oracle has the CONNECT BY extension). So I started researching the web.

There are basically three ways to store a tree in a relationnal databases : adjacency list, nested set and materialized path, plus a few more like nested intervals. Let’s put it clear : they all suck.

• Adjacency list model is the one I used the first time (with parent_id column). It’s easy to create but impossible to query deeply without recursivity.
• Nested set model is quite easy to query, but is indeed pretty fucked up (tree is limited in size, very hard to read without maths, almost all the lines of the table need to be updated each time a node is added, moved or deleted!). Nested intervals model tries to remove the size limitation of nested sets model, but involves way to much maths.
• Materialized path is great and easy to understand, but very slow because it involves heavy use of the “LIKE” operator.

More on that here, here and here.

Then I found two very interesting articles. One is a reply on MySQL Forums about materialized path performance problem, recommending an approach based on normalized schema to store paths. The other is an implementation using PostgreSQL by depesz that also use a normalized schema. The point is to create a table dedicated to store all the paths from every nodes to every nodes. This looks to me like a very good approach, as it’s easy to understand, easy to maintain, easy to query and performance-ok (with appropriate indexes). Unfortunalty, the implementation I found relies to much on PostgreSQL and doesn’t work out-of-the-box with MySQL (because of the use of triggers and of some queries that needs to be rewriten). So I reworked it to work with MySQL 5, and changed a few things. I strongly recommend that you read depesz’s post for a complete understanding of the approach before you continue.

More… »

D’abord, il va de soi (mais ça va mieux en le disant) que les mots de passe d’une application web ne doivent pas être stockés en clair, mais sous forme d’un hash. Lors de la procédure d’authentification, il suffit de calculer le hash du mot de passe saisi par l’utilisateur, et de le comparer avec celui stocké en base.

L’algorithme le plus répandu pour calculer un hash est MD5. Néanmoins, depuis 2004 plusieurs vulnérabilités ont été découvertes, aussi il est préférable d’utiliser SHA1. Quel est meilleur type pour stocker ces hashs dans une table MySQL ?

Un hash SHA1 mesure 160 bits ou 40 caractères hexadécimaux. Un hash MD5 mesure 128 bits soit 32 caractères hexadécimaux.

Stocker sous forme de chaine

La longueur du hash est fixe : il est donc préférable d’utiliser le type CHAR (CHAR(40) pour du SHA1, CHAR(32) pour du MD5). En effet, le type VARCHAR prendrait plus d’espace car il utilise un octet supplémentaire pour stocker la longueur de la chaine.

Ensuite, il faut faire attention à l’encodage. En effet, si la table est en UTF-8, les caractères seront probablement stockés sur 3 octets (ça peut varier selon le moteur de stockage). Il vaut mieux spécifier l’encodage de cette colonne à ASCII, grâce à CHARACTER SET ascii.

Enfin, la colonne est évidemment NOT NULL, pour économiser un bit (la valeur NULL est stockée dans un bit supplémentaire), à moins que l’application en ait besoin (ça existe des utilisateurs sans mot de passe ?).

Exemple :

mysql> create table t (
    -> password char(40) character set ascii not null
    -> ) engine=MyISAM character set utf8;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values(SHA1('monSuperMotDePasse'));
Query OK, 1 row affected (0.00 sec)

mysql> select * from t;
+------------------------------------------+
| password                                 |
+------------------------------------------+
| 35ea5a462298bd78c1648fbea2195988c46d103f |
+------------------------------------------+
1 row in set (0.00 sec)

L’espace utilisé est donc 40 octets pour un hash SHA1, car le type CHAR avec le jeu de caractère ASCII stocke chaque caractère sur un octet (8 bits).

Stocker sous forme binaire

Vous l’aurez surement remarqué, 40 octets ça fait 320 bits, c’est à dire le double de la taille du hash SHA1 brut (idem pour MD5 : 32×8 = 256). Pour faire simple, c’est le prix à payer pour avoir un mot de passe lisible et “imprimable” (c’est à dire que vous pouvez copier/coller sans problème) en base. L’autre solution consiste à stocker le hash brut directement sous forme binaire.

Le type a utilisé n’est donc plus CHAR, mais BINARY qui stocke des chaines binaires. Il faut lui préciser la longueur en octets, donc BINARY(20) pour du SHA1 (160/8 = 20), et BINARY(16) pour du MD5 (128/8 = 16). Il n’y a plus à se soucier du jeu de caractères.

Pour convertir une chaine de caractère en chaine binaire, il faut utiliser UNHEX. Pour l’opération inverse, il faut utiliser HEX. Note pour les utilisateurs de PHP : la fonction hash accepte un troisième paramètre optionnel $raw_output qui, s’il vaut true, permet de récupérer le résultat binaire directement (voir http://fr.php.net/manual/fr/function.hash.php).

Exemple :

mysql> create table t2 (
    -> password binary(20) not null
    -> ) engine=MyIsam character set utf8;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t2 values(UNHEX(SHA1('monSuperMotDePasse')));
Query OK, 1 row affected (0.00 sec)

mysql> select HEX(password) from t2;
+------------------------------------------+
| HEX(password)                            |
+------------------------------------------+
| 35EA5A462298BD78C1648FBEA2195988C46D103F |
+------------------------------------------+
1 row in set (0.00 sec)

L’espace utilisé est donc 20 octets pour hash SHA1, soit 2 fois moins que la version en chaine de caractères. L’inconvénient est qu’il faut penser à utiliser UNHEX ou HEX dès qu’on veut le hash sous une forme imprimable. C’est rarement le cas, et comme les opérations de comparaisons (utilisées pour l’authentification de l’utilisateur) peuvent s’effectuer avec les version binaires, ça ne me dérange pas.

En savoir plus

• The CHAR and VARCHAR Types
• Column Character Set and Collation
• The BINARY and VARBINARY Types
• Make Your Data as Small as Possible

Vous ne le saviez peut-être pas, mais contrairement aux types de chaine de caractères (varchar, char, …), le chiffre entre parenthèses pour un type numérique n’a aucune influence sur la taille maximale du type. Autrement dit, on peut stocker le même nombre dans un int(11) que dans un int(3), un int ou même un int(42). Ce qui influe la taille maximale, c’est le type en lui même : tinyint, smallint, mediumint, int et bigint.

Tableau de correspondance des tailles (source : http://dev.mysql.com/doc/refman/5.1/en/numeric-types.html)

Alors quel est l’intérêt de la préciser une taille ? Il n’y en a qu’un seul, c’est lorsque le type est utilisé avec l’option zerofill, option assez peu connue qui permet de compléter avec le champ avec des zéros pour atteindre la taille spécifiée.

Exemple :

mysql> create table test_int (
    -> normal_int int unsigned not null,
    -> zerofilled_int int(6) unsigned zerofill not null
    -> );
Query OK, 0 rows affected (0.00 sec)

mysql> insert into test_int values (123456789, 123456789), (42,42);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> select * from test_int;
+------------+----------------+
| normal_int | zerofilled_int |
+------------+----------------+
|  123456789 |      123456789 |
|         42 |         000042 |
+------------+----------------+
2 rows in set (0.00 sec)

Comme vous pouvez le constater dans l’exemple précédent, il n’y aucune différence sur la première ligne (un nombre composé de 9 chiffres tient sans problème dans un int(6)), par contre dans la seconde, le champ avec l’option zerofill est complété par des zéros pour atteindre 6 chiffres. Un exemple concret d’utilisation : stocker des numéros de série normalisé (genre des numéros de bon de commande du type “BDC-000042″), car ça évite de faire un padding.

Bref, tout ça pour dire : ça ne sert à rien d’essayer d’optimiser ses tables MySQL avec ça, ce n’est pas en mettant int(4) qu’on va gagner de la place, mais plutôt en utilisant le type adapté (en l’occurence smallint).

Disons que vous soyez en charge d’une application web écrite en PHP/MySQL, par exemple l’intranet de votre entreprise, et que vous ayez soudainement besoin de l’internationaliser parce que votre entreprise installe des bureaux à l’étranger et que, malheureusement, notre merveilleuse langue française n’est pas parlée dans tous les pays du monde.

Pour les templates, pas de problème, gettext est là pour ça (je reviendrais peut-être dessus dans un futur article, si je suis motivé). Si vous n’avez pas envie de mettre les mains dans le système, votre framework propose sûrement une émulation plus ou moins performante en pur PHP, ou, au pire, une solution “maison”. Bref, ça c’est facile.

Ce qui pose plus de problèmes, ce sont les données présentes en base. Par exemple : la liste de catégories pour les tickets d’incidents des clients. Elle est stockée en base dans une table qui contient notamment l’intitulé de cette catégorie. Oui, mais cet intitulé doit être traduit. Et comme les catégories sont gérées dynamiquement, ce n’est pas envisage d’utiliser la méthode gettext qui repose sur des fichiers statiques.

Transformer le modèle

Nous allons commencer par ajouter une table pour stocker les traductions. Si on envisage la catégorie comme un élément identifié par un id uniquement, les traductions sont liées à une catégorie par une relation “1-N” : 1 catégorie possède N traductions. Chaque traduction est identifiée par un code de langue. L’idée est de retirer les champs contenant du texte à traduire de la catégorie, et de les stocker dans la table contenant les traductions

Schéma de la base

On crée donc les tables suivantes :

CREATE TABLE `category` (
	`id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
	`created_at` DATETIME NOT NULL,
	`deleted_at` DATETIME NULL,
	PRIMARY KEY (`id`)
) ENGINE = InnoDB;

CREATE TABLE `category_i18n` (
	`category_id` INT UNSIGNED NOT NULL,
	`lang` VARCHAR(6) NOT NULL,
	`name` VARCHAR(45) NOT NULL,
	PRIMARY KEY (`lang`, `category_id`),
	INDEX `category_i18n_category_fk` (`category_id` ASC),
	CONSTRAINT `category_i18n_category_fk`
		FOREIGN KEY (`category_id` )
		REFERENCES `category` (`id` )
		ON DELETE CASCADE
) ENGINE = InnoDB;

More… »

On me demande souvent comment j’organise le développement web dans mon entreprise : comment on arrive à coder à plusieurs sur le même fichier sans se marcher sur les pieds, comment on archive les versions, comment on effectue les livraisons en production, etc. Il est vrai que le développement web collaboratif est souvent mal organisé, et il est courant d’avoir comme seul outil un simple dossier partagé…

Contraintes liées au développement web collaboratif

Contrairement à un projet classique qui ne nécessite “que” un compilateur et des bibliothèques, une application web est une association complexe de plusieurs composants logiciels dont les versions et les configurations très variables peuvent influer sur le bon fonctionnement de l’application :

• un serveur web (vhost, htaccess, mod_rewrite, etc.),
• l’interpréteur php (options de php.ini, modules supplémentaires comme pdo, gettext, etc.),
• le sgbd (configuration des users, etc.).

Donc la solution “classique” d’avoir un poste de développement par développeur est ici difficile à maintenir : il faudrait installer tous ces logiciels sur chaque poste et surtout veiller à avoir une configuration identique partout. Et ça se complique dès qu’il faut faire une mise à jour de la config…

Une autre solution serait d’avoir un serveur de dev unique (pour éviter les problèmes de maintenance évoqués ci-avant), et de travailler directement dessus via des partages de fichiers (Samba, NFS, etc.). Or cette solution pose plusieurs problèmes :

• en cas d’accès concurrents à un fichier : le risque est grand de voir ses modifications écrasées par un autre développeur ;
• en cas de modifications lourdes (exemple : un refactoring de la base) : les autres développeurs sont bloqués ;
• impossible d’utiliser correctement le svn : il n’y a qu’une seule version des fichiers et on ne sait pas qui l’a modifiée.

Nous avons donc créée une solution intermédiaire : un serveur de dev unique (pour une maintenance facile), qui fournit des serveurs virtuels pour chaque développeur (pour une bonne séparation des données et une utilisation optimale de svn).

Le serveur de dev fonctionne avec Debian GNU/Linux, les postes clients avec Windows XP.

More… »

La question à 2 centimes d’euros du jour : qu’est-ce qu’on obtient comme résultat avec une requête SQL de ce genre de celle ci-dessous (avec un MySQL) ?

select * from ma_table where id = 42 = 0;

La réponse est : toute la table sauf la ligne dont l’id vaut 42 ! En fait, en raison de la précédence des opérateurs, cette requête est équivalente à :

select * from ma_table where (id = 42) = 0

Comme l’opérateur de comparaison = retourne 0 (FALSE) ou 1 (TRUE) (ou NULL si un des 2 arguments vaut NULL), l’expression id = 42 = 0 est parfaitement valide et est équivalente à id != 42.

Mais à quoi ça sert me direz-vous ? A faire des injections SQL dans un site PHP qui ne filtre pas correctement ses variables… A bon entendeur !

Avec MySQL, stocker un booléen (0 ou 1) dans un type enum (plutôt que dans un type numérique comme le ferait toute personne saine d’esprit), est une *très* mauvaise idée, qui fera à coup sûr perdre quelques heures au développeur qui devra maintenir le code. Et voici pourquoi.

Disons que la table qui a été créée ressemble à ça :

create table enum_is_evil (
  id integer not null auto_increment,
  value enum('0','1') not null default '0',
  primary key (id)
);

insert into enum_is_evil (value) values ('0'), ('0'), ('1');

Si on ne fait pas gaffe qu’il s’agit d’un enum et pas d’un type numérique (comme on pourrait logiquement le supposer), voila ce que ça donne…

mysql> select * from enum_is_evil where value = 0;
Empty set (0.00 sec)

Bon, aucun résultat alors qu’on devrait en avoir 2… Essayons autre chose.

mysql> select * from enum_is_evil where value = 1;
+----+-------+
| id | value |
+----+-------+
|  1 | 0     |
|  2 | 0     |
+----+-------+
2 rows in set (0.00 sec)

Youpi ! C’est n’importe quoi !

Et voyons ce qui se passe quand on ne fait pas attention à l’insertion, c’est encore plus drole.

insert into enum_is_evil (value) values (0), (0), (1);

Note : cette requête produit des warnings (logique), mais lorsqu’elle est executée dans un script, il n’y aucune chance de s’en apercevoir.

mysql> select * from enum_is_evil where value = 0;
+----+-------+
| id | value |
+----+-------+
|  4 |       |
|  5 |       |
+----+-------+
2 rows in set (0.00 sec)

Yeah, des valeurs vides dans la table alors qu’on devrait avoir uniquement des 0 ou des 1 !

mysql> select * from enum_is_evil where value = 1;
+----+-------+
| id | value |
+----+-------+
|  1 | 0     |
|  2 | 0     |
|  6 | 0     |
+----+-------+
3 rows in set (0.00 sec)

Encore mieux, la valeur “1″ qu’on a ajoutée est devenue un “0″ !

Conclusion : bien que tout ça soit logique quand on lit la doc du type ENUM (il suffit d’ajouter des quotes autour des valeurs pour obtenir les bons résultats), c’est une source d’erreur potentielle assez vicieuse quand on s’attend à travailler avec un type numérique. Utilisez plutôt un TINYINT !

Voici une petite requête pour MySQL ≥ 5 qui peut être utile si vous cherchez à obtenir la liste des champs d’une table, pour l’exporter en tant qu’entête d’un fichier CSV par exemple.

select group_concat(column_name SEPARATOR ";")
from information_schema.columns
where table_schema = 'DB_NAME' and table_name = 'TABLE_NAME'
group by table_name;

La requête suivant permet d’exporter une table complète en CSV, sans passer par un langage de script (à condition d’avoir la permission FILE).

select *
into outfile '/tmp/foo.csv'
fields terminated by ';' optionally enclosed by '"'
lines terminated by '\n'
from DB_NAME.TABLE_NAME;

Plus d’infos dans la doc de MySQL.