Tag Archives: mysql

Trees in SQL : an approach based on materialized paths and normalization for MySQL

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.

Continue reading

Quel est le meilleur type pour stocker un mot de passe dans une table MySQL ?

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

MySQL INT(11) a la même taille que INT(3)

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)

Type Bytes Minimum Value (Signed/Unsigned) Maximum Value (Signed/Unsigned)
TINYINT 1 -128 127
0 255
SMALLINT 2 -32768 32767
0 65535
MEDIUMINT 3 -8388608 8388607
0 16777215
INT 4 -2147483648 2147483647
0 4294967295
BIGINT 8 -9223372036854775808 9223372036854775807
0 18446744073709551615

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).

Une syntaxe SQL originale

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 !

Stocker un bool avec un enum, c’est mal.

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 !

Requêtes pour faire du CSV avec MySQL

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 = '<em>DB_NAME</em>' and table_name = '<em>TABLE_NAME</em>'
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 '<em>/tmp/foo.csv</em>'
fields terminated by ';' optionally enclosed by '"'
lines terminated by '\n'
from <em>DB_NAME</em>.<em>TABLE_NAME</em>;

Plus d’infos dans la doc de MySQL.