Cours
Manipulation de données en SQL
4 h
335.5K
En tant que data scientist, vous serez souvent confronté à des volumes de données considérables. Manipuler des données (présentes en quantités massives) n’a rien d’évident. Pour gagner en efficacité, vous devez comprendre clairement comment les données sont organisées physiquement, afin de pouvoir les traiter avec des techniques adaptées.
SQL est une compétence indispensable pour tout ingénieur logiciel moderne, car la plupart des logiciels reposent sur des données et s’intègrent à un SGBDR (système de gestion de base de données relationnelle). Qu’il s’agisse d’une application web, d’une API ou d’un outil interne, le SGBDR est omniprésent. Et SQL est le langage de requête d’un SGBDR.
Pour un data scientist, il est essentiel de connaître SQL et ses techniques associées. Pour interroger un SGBDR et obtenir des réponses précises aux questions que vous vous posez sur vos données, SQL est le strict minimum.
Dans sa dernière vidéo avec DataCamp, David Robinson (Chief Data Scientist @ DataCamp) montre comment il utilise SQL dans un problème de data science. Jetez-y un œil. Son approche est très instructive.
Aujourd’hui, vous allez découvrir une technique appelée indexation qui concerne principalement l’organisation des données au sein d’une base, et vous allez en implémenter quelques-unes en SQL. Vous verrez comment l’indexation permet de stocker l’information dans une base de données et comment elle peut accélérer l’exécution des requêtes.
N.B. : Avant de lire ce tutoriel, il est vivement recommandé de maîtriser les bases de SQL si ce n’est pas déjà le cas. Le cours de DataCamp Intro to SQL for Data Science est une excellente ressource pour réviser les fondamentaux.
Bref aperçu de l’organisation des enregistrements dans un fichier
Avant d’aborder l’indexation, il est indispensable de comprendre comment les données sont organisées physiquement dans des fichiers. Sans entrer dans tous les détails, avoir cette vue d’ensemble vous aidera à saisir très clairement l’indexation. Allons-y.
L’organisation des enregistrements/données concerne la manière dont les enregistrements sont stockés et, de façon générale, on distingue deux grands types d’organisation :
-
Organisation ordonnée : tous les enregistrements d’un fichier sont triés selon une clé de recherche. La recherche binaire est généralement utilisée pour chercher une valeur dans le fichier ordonné. La recherche est alors très efficace car sa complexité reste en temps logarithmique. En revanche, l’insertion devient coûteuse, car vous devrez potentiellement réorganiser tout le fichier pour accueillir le nouvel élément.
-
Organisation non ordonnée : les enregistrements sont insérés là où il y a de la place, souvent à la fin du fichier. Comme on utilise une recherche linéaire, la recherche est moins efficace que dans la variante précédente, mais l’insertion coûte moins cher.
Même si vous disposez d’une organisation ordonnée, que se passe-t-il si la taille des blocs et celle de chaque enregistrement sont très grandes ? Explorons cela dans la section suivante.
Pourquoi indexer
Commençons par la motivation derrière l’indexation pour stocker des fichiers/informations de manière efficace et améliorer les autres opérations associées.
Supposons que vous ayez une table (relation) contenant plusieurs enregistrements dans une base de données. Ces enregistrements sont répartis en 1000 blocs. Visuellement, l’organisation ressemble à ceci :
À partir de cette organisation, on constate que :
- L’ordre est appliqué à la première colonne des enregistrements (considérez qu’il s’agit d’une base relationnelle où les données sont organisées en tables)
- Le nombre de blocs dans lequel l’ensemble des données est réparti est de 1000 blocs.
Gardez en tête que chaque enregistrement contient d’autres colonnes, mais pour cette organisation, l’ordre est appliqué à la première colonne et les blocs sont répartis en conséquence. Si vous effectuez une recherche binaire pour trouver une valeur dans cette organisation, le temps total sera de $\log_{2}1000$, soit 10 unités de temps. Peut-on améliorer ce temps de recherche ?
Bien sûr.
Imaginez que vous lisiez un livre sans page d’index. Vous ouvrez une page au hasard (ou, en recherche binaire, la page du milieu) et vous feuilletez à gauche et à droite jusqu’à trouver la page voulue. Cela prend du temps, n’est-ce pas ?
Avec une page d’index, la recherche serait plus efficace : vous iriez directement à la bonne page en consultant l’index. Vous pouvez appliquer le même principe d’indexation à la situation ci-dessus.
Voici comment appliquer l’indexation ici, en résumé :
- Conservez un pointeur de bloc pour chaque bloc, associé aux valeurs ordonnées utilisées dans l’organisation précédente.
On obtient ainsi un nombre de blocs bien plus réduit pour stocker les fichiers de données. Pour rechercher un enregistrement, il suffit alors d’interroger cette nouvelle organisation composée d’un plus petit nombre de blocs et vous atteindrez votre enregistrement (s’il existe) beaucoup plus vite. Visualisons cela. En supposant que l’indexation réduise à 8 blocs, vous obtiendrez l’organisation suivante :
Le temps de recherche baisse drastiquement avec moins de blocs. Supposons que vous recherchiez l’enregistrement 90. Avec ce nouvel index, vous commencez par localiser son pointeur de bloc, qui est ici 3, puis, grâce à cette information, vous retrouvez les données d’origine en un seul accès.
Le temps de recherche sera donc $\log_{2}8 + 1$ = 4 unités de temps, ce qui est nettement inférieur au cas précédent.
Cet exemple illustre la nécessité de recourir à l’indexation. Voici quelques points importants à retenir :
- Le tri des données d’origine ne peut se faire que sur un seul champ. Les entrées d’index sont alors créées en fonction de ce champ. Vous n’obtiendrez un gain de performance que si la recherche utilise ce champ (point extrêmement important).
- Les index sont eux-mêmes ordonnés.
- Un enregistrement d’index contient deux champs (structure du fichier d’index) :
- La clé du fichier d’origine
- Un pointeur vers le bloc où se trouve cette clé dans les données d’origine
- On utilise la recherche binaire pour parcourir les index.
- Pour accéder à un enregistrement via les entrées indexées, le nombre moyen d’accès aux blocs requis est :
$\log_{2}B_i + 1$ , où $B_i$ est le nombre de blocs dans les enregistrements indexés - Un index peut être créé sur n’importe quel champ de la relation (clé primaire, clés candidates, attributs non clés).
Selon l’ordre des données d’origine et le nombre d’enregistrements conservés dans le fichier d’index, il existe plusieurs schémas d’indexation. Dans la section suivante, vous verrez les plus répandus.
Différentes stratégies d’indexation :
- Indexation dense : si une entrée d’index est créée pour chaque valeur de clé de recherche, on parle d’indexation dense. Reportez-vous au schéma ci-dessous pour une visualisation.
- Indexation clairsemée : si une entrée d’index n’est créée que pour certains enregistrements, on parle d’indexation clairsemée. Voici un schéma pour l’illustrer.
Ces diagrammes rendent les deux schémas d’indexation assez intuitifs. Un point crucial ici : l’exemple d’indexation clairsemée ci-dessus combine en réalité indexation dense et clairsemée. En effet, il existe une entrée d’index pour chaque valeur de clé de recherche unique (1, 2 et 3), mais pas pour chaque enregistrement.
Voyons maintenant d’autres types de schémas d’indexation selon le niveau d’index. En indexation à un seul niveau, il n’y a qu’un seul fichier d’index. Mais lorsque ce fichier devient trop volumineux, il peut à son tour être indexé : on parle alors d’indexation multiniveau. Approfondissons.
Voici un aperçu des stratégies d’indexation selon le niveau.
Indexation à un seul niveau :
- Index primaire
- Index de regroupement (clustered)
- Index secondaire
Indexation multiniveau :
- Arbre B
- Arbre B+
Nous étudierons toutes les stratégies d’indexation à un seul niveau. En fin de tutoriel, vous trouverez un lien pour explorer les schémas multiniveaux si vous le souhaitez. Examinons maintenant l’index primaire.
Index primaire :
Un index primaire est un fichier ordonné dont les enregistrements ont une longueur fixe avec deux champs :
- Le premier champ correspond à la clé primaire du fichier de données.
- Le second champ est un pointeur vers le bloc de données où se trouve la clé primaire. - Source
L’index créé sur le premier enregistrement de chaque bloc est appelé ancre de bloc (block anchor). En indexation primaire, le nombre d’entrées d’index = le nombre de blocs de données d’origine. Le nombre moyen d’accès aux blocs avec un index primaire est :
Reportez-vous au schéma suivant pour mieux comprendre : 
La figure de droite représente les données d’origine réparties en plusieurs blocs. Notez que la colonne contenant les nombres 1, 2, 3, …, 9 correspond aux clés primaires. La figure de gauche représente les entrées d’index, où chaque entrée comprend :
- Le premier enregistrement de chaque bloc de données (ancre de bloc)
- Un pointeur vers le bloc.
Prenez un instant pour déterminer de quel type d’indexation il s’agit (clairsemée ou dense). Utilisez la section comments pour partager votre réponse.
Passons maintenant à l’index de regroupement.
Index de regroupement (clustering) :
Un index de regroupement est créé sur un fichier de données dont les enregistrements sont physiquement ordonnés selon un attribut non clé, qui ne possède pas de valeur distincte pour chaque enregistrement. Cet attribut, appelé champ de regroupement (clustering field), sert de base à l’indexation. D’où le nom d’index de regroupement.
Les schémas facilitent la compréhension. Ici, les données d’origine sont ordonnées selon un attribut non clé et, pour chaque valeur distincte de cet attribut, une entrée d’index est créée. Le nombre moyen d’accès aux blocs pour localiser un enregistrement avec ce schéma est $\geq$ $\log_{2}B_i + 1$ , où $B_i$ est le nombre de blocs dans les enregistrements indexés. Notez le signe $\geq$.
Avec un index de regroupement, après avoir localisé le bloc contenant une clé particulière, vous pouvez être amené à parcourir d’autres blocs (comme le suggère le schéma ci-dessus).
Réfléchissez au type d’indexation dont il s’agit (clairsemée ou dense). Partagez votre réponse dans les commentaires. Voyons maintenant l’index secondaire.
Index secondaire :
Supposons que vous ayez une table appelée Employee dans votre base. Elle comporte les attributs suivants :
- employee_id
- employee_name
- employee_department
- employee_salary
employee_id est la clé primaire. Vous avez déjà créé un index primaire basé sur employee_id. Mais lors du développement d’une application, vous constatez que la plupart des requêtes utilisent l’attribut employee_name. Dans ce cas, l’index primaire ne vous aidera pas beaucoup, et il est pertinent de maintenir un index séparé pour toutes les valeurs de employee_name. De toute façon, les noms des employés ne seront pas stockés de manière ordonnée dans la base. Les indexer accélérera donc nettement les requêtes portant sur les noms.
Voici un exemple classique d’indexation secondaire. Essayons d’en donner une représentation :
N’hésitez pas à proposer une meilleure représentation dans la section comments si vous en avez une.
Voyons maintenant comment créer des index dans PostgreSQL. Suivez le cours de DataCamp Joining Data in PostgreSQL si vous souhaitez en revoir les bases.
Créer des index dans PostgreSQL
Avant de créer des index dans une base PostgreSQL, vous avez besoin de données dans une table. Créons une table simple nommée Student avec les enregistrements suivants :
- student_id
- student_name
- student_year
Vous ferez de student_id la clé primaire, et vous n’autoriserez pas les valeurs nulles pour les noms et les années.
La requête correspondante est la suivante :
CREATE TABLE STUDENT(
student_id TEXT PRIMARY KEY,
student_name TEXT NOT NULL,
student_year TEXT NOT NULL
);
Une fois la table créée, il faut y insérer des données. Pour aller vite, utilisez un fichier .csv et importez-le dans Student. Vous pouvez importer un fichier .csv compatible dans une table PostgreSQL avec la requête suivante :
COPY STUDENT FROM '/path/to/csv/Student.csv' WITH (FORMAT csv);
La requête ci-dessus suppose que le fichier .csv à importer s’appelle Student.
Regardons maintenant les données. L’exécution de select * from STUDENT; renvoie les enregistrements suivants : 
La requête select doit renvoyer un total de 86 enregistrements. Vous pouvez désormais créer des index. Pour un index sur une seule colonne, utilisez la syntaxe suivante :
CREATE INDEX index_name
ON table_name (column_name);
Créons un index sur le champ student_id (index primaire).
CREATE INDEX id_index
ON STUDENT (student_id);
Vous pouvez aussi créer des index multi-colonnes :
CREATE INDEX id_index
ON STUDENT (student_id,student_name);
Vous pouvez supprimer un index avec la syntaxe suivante :
DROP INDEX index_name;
Il est difficile de percevoir l’impact de l’indexation sur une petite table comme STUDENT. Mais si la table était volumineuse (imaginez les données d’une grande université), l’indexation jouerait un rôle clé.
C’est fait !
Félicitations d’être allé jusqu’au bout. Dans ce tutoriel, vous avez découvert l’indexation, ses usages et différents schémas. Vous avez aussi vu comment réaliser une indexation simple dans PostgreSQL.
En revanche, nous n’avons pas étudié l’indexation multiniveau. Voici d’excellentes ressources si vous souhaitez l’explorer :
Mais l’indexation est-elle toujours utile ? Dans certains cas, il n’est pas recommandé d’en créer.
J’espère que ce tutoriel vous a permis d’éclaircir les bases de l’indexation. Partagez vos découvertes dans la section comments.
Découvrez le Learn SQL Hub de DataCamp.
Sujets