Visualisation des index SQLite

 (mrsuh.com)
3 points par GN⁺ 2024-11-16 | 1 commentaires | Partager sur WhatsApp
  • Analyse de la structure B-Tree pour comprendre comment les index SQLite sont réellement disposés sur disque et en mémoire, avec dump et visualisation des données d’index
  • Les index sont organisés en pages et cellules : une page contient le lien vers l’enfant droit et les données des cellules, tandis qu’une cellule contient les données d’index, le rowId et le lien vers l’enfant gauche
  • Les seules informations fournies par sqlite3_analyzer — taille de page, nombre d’entrées, profondeur du B-tree, nombre de pages utilisées — étant insuffisantes, des fonctions de débogage ont été ajoutées au code source de SQLite
  • Les expériences comparent le nombre d’enregistrements, ASC/DESC, les index basés sur des expressions, UNIQUE avec NULL, les Partial Index, les index multicolonnes, ainsi que les combinaisons texte, REAL et entier+texte
  • Avec 1 000 000 d’enregistrements, créer l’index avant l’insertion donne 3 342 pages, tandis que le créer après l’insertion donne 2 930 pages ; après VACUUM ou REINDEX, le nombre descend également à 2 930 pages

Pourquoi regarder directement à l’intérieur des index SQLite

  • Il s’agit d’une expérience visant à aller au-delà de la structure de base des index pour vérifier la structure de données, les algorithmes et le mode de stockage sur disque réels
  • L’objectif est d’observer comment un SGBD stocke les index sur disque et en mémoire, et comment il y accède lors des recherches
  • SQLite a été choisi comme sujet d’expérimentation pour les raisons suivantes
    • C’est un SGBD largement utilisé dans les navigateurs, les applications mobiles et les systèmes d’exploitation
    • Il est facile à déboguer avec une simple application cliente, sans serveur séparé
    • Son code source est plus petit que celui de MySQL ou PostgreSQL, tout en utilisant des structures de données similaires pour les index
    • Il est open source

Un B-Tree composé de pages et de cellules

  • Selon la documentation de SQLite, les index sont stockés sous forme de structure B-Tree
  • Dans SQLite, l’unité correspondant à un nœud est la page
    • Une page stocke les données des cellules
    • Une page possède un lien vers la page enfant droite
  • Une cellule contient les données d’index, le rowId et le lien vers la page enfant gauche
  • Chaque ligne d’une table SQLite possède par défaut un rowId unique, qui se comporte comme une clé primaire lorsqu’aucune clé primaire explicite n’est définie
  • Chaque page a une taille fixe, comprise entre 512 et 65 536 octets
  • Les en-têtes de page et de cellule utilisent 4 octets pour stocker les liens enfants
    • Pour connaître le numéro de la page enfant, il faut lire séparément l’en-tête avec la fonction get4byte(...)
  • Exemples de structures internes de SQLite
    • MemPage : contient notamment le numéro de page pgno, le nombre de cellules nCell, la zone d’index des cellules aCellIdx et le pointeur vers l’image disque des données de page aData
    • CellInfo : contient notamment pPayload, qui pointe vers le début du payload

Les limites de sqlite3_analyzer et les fonctions de débogage

  • sqlite3_analyzer permet de consulter des informations générales sur un index
    • Un exemple de sortie inclut notamment la taille de page 4096, le nombre d’entrées 1000, la profondeur du B-tree 2 et le nombre de pages utilisées 4
  • Mais cet outil se limite à des informations de synthèse et ne permet pas d’inspecter directement les cellules internes de l’index ni le payload
  • Après plusieurs semaines d’expérimentation, des fonctions d’analyse d’index ont été écrites
    • Code : sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Ces fonctions lisent le contenu de l’index sélectionné et l’affichent sur STDOUT
    • Le flux est SQL query -> selected index -> stdout
    • La sortie inclut le numéro de page, le numéro de la page enfant droite, le numéro de cellule, le numéro de la page enfant gauche, le payload et le rowId
  • L’environnement d’expérimentation peut être lancé avec Docker
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

Évolution de la méthode de visualisation

  • Au début, d3-org-tree était utilisé pour visualiser la structure des index
  • À mesure que l’arbre devenait plus profond et que le nombre de pages augmentait à chaque niveau, l’espacement entre les pages est devenu difficile à ajuster, produisant des images trop grandes et difficiles à lire
  • Des ajustements en JavaScript et CSS ont été tentés sans résultat satisfaisant, puis une représentation textuelle de la structure a été adoptée pendant un temps
  • La sortie texte affiche le nombre total de pages, le nombre total de cellules, le nombre de pages et de cellules par niveau, les informations des pages, les informations des cellules et le payload
  • Par la suite, l’extension ImageMagick de PHP a été utilisée pour produire des images avec un contrôle plus fin du design et des espacements
  • L’image finale contient les informations suivantes
    • Affichage des informations générales de l’index en haut à gauche
    • Affichage du nombre total de pages et de cellules pour chaque niveau
    • Pour chaque page, affichage du numéro de page, du lien vers l’enfant droit, ainsi que des informations de la première et de la dernière cellule
    • À chaque niveau, seule une partie des pages est affichée, en incluant la première et la dernière page
    • La page racine se trouve au premier niveau
  • La commande pour générer une image à partir du dump est la suivante
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Comment le nombre d’enregistrements change la forme de l’index

  • Une table column1 INT NOT NULL est créée avec un index column1 ASC, puis la structure est observée en faisant varier le nombre d’enregistrements
  • Un index avec 1 enregistrement se compose de 1 niveau, 1 page et 1 cellule
  • Un index avec 1 000 enregistrements est généré et visualisé de la même manière
  • Un index avec 1 000 000 d’enregistrements a la structure suivante
    • 3 niveaux
    • 2 930 pages
    • 1 000 000 cellules
  • Comme les données ont été ajoutées dans l’ordre, lorsque rowId = 1, column1 = 1

Sens de tri et index d’expression

  • idx_asc et idx_desc sont créés sur les mêmes données afin de comparer les index ASC/DESC
  • L’index ASC est identique à l’index précédent, puisque le tri par défaut est ASC
    • L’élément avec rowId=1,000,000, column1=1,000,000, payload=1,000,000 se trouve dans la dernière cellule de la page la plus à droite
    • L’élément avec rowId=1, column1=1, payload=1 se trouve dans la première cellule de la page la plus à gauche
  • L’index DESC est disposé à l’inverse
    • L’élément avec rowId=1, column1=1, payload=1 se trouve dans la dernière cellule de la page la plus à droite
    • L’élément avec rowId=1,000,000, column1=1,000,000, payload=1,000,000 se trouve dans la première cellule de la page la plus à gauche
  • Un index basé sur une expression stocke la chaîne produite par l’expression
    • L’exemple extrait $.timestamp d’un texte JSON, puis le convertit avec strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') pour créer un index ASC
    • Des expressions plus complexes peuvent aussi être utilisées, et seul leur résultat est stocké dans l’index

NULL, Partial Index et multicolonnes

  • SQLite prend en charge les index UNIQUE contenant des valeurs NULL
    • L’exemple insère les valeurs 1, de nombreux NULL et 1000000, puis exécute CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • L’index visualisé semble ne stocker que les valeurs non NULL
  • Un Partial Index avec la condition WHERE column1 IS NOT NULL filtre les valeurs NULL
    • Cet index ne contient qu’une seule page
    • Il permet des recherches plus rapides que l’exemple UNIQUE précédent
  • Un index multicolonne stocke toutes les données des champs dans l’ordre au sein de la cellule
    • L’exemple est un index (column1 ASC, column2 ASC)
    • Dans la visualisation, les champs sont séparés par deux-points :

Moment de création de l’index et effet de reconstruction

  • Le cas où l’index est créé avant l’insertion des données est comparé à celui où l’index est créé après l’insertion de toutes les données
  • Lorsque de nouvelles données sont ajoutées, l’arbre doit se rééquilibrer lui-même
  • Créer l’index en une seule fois sur des données existantes peut être beaucoup plus efficace
  • Les deux index se ressemblent, mais le second, qui comporte moins de pages, peut être plus rapide
  • Pour 1 000 000 de cellules, le résultat de la comparaison est le suivant
Catégorie Total Pages Total Cells
Créé avant insertion 3342 1000000
Créé après insertion 2930 1000000
  • Une optimisation similaire peut être effectuée avec VACUUM ou REINDEX
    • VACUUM recrée les index et les tables avec les données
    • REINDEX idx recrée uniquement l’index
  • Dans l’exemple, les deux commandes réduisent le nombre de pages de 3342 à 2930

Stockage des index selon le type de données

  • Pour les données texte, les chaînes courtes sont stockées directement dans les cellules de l’index, tandis que les textes longs doivent être stockés séparément
    • L’exemple insère les valeurs de text-1 à text-1000000 et crée un index column1 ASC
    • On peut constater que les chaînes réelles sont directement stockées dans l’index
  • Les données REAL sont également stockées dans l’index et visualisées
    • L’exemple utilise les valeurs 1.14, 2.14, ..., 1000000.14
  • Un index composite combinant entier et texte est également observé
    • L’exemple crée un index (column1 ASC, column2 ASC) sur une table (column1 INT, column2 TEXT)
    • L’entier et la chaîne sont stockés ensemble dans la même cellule, conformément à la définition de l’index

Reproduction et prochaines étapes

  • L’expérience montre comment les index SQLite sont structurés, comment les données des enregistrements sont stockées en mémoire et comment le B-Tree organise les données et y accède
  • La visualisation sert à analyser et comparer différents index
  • Tous les exemples peuvent être reproduits avec les commandes suivantes
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • Le code et les exemples se trouvent dans mrsuh/sqlite-index
  • La prochaine étape consiste à visualiser les recherches basées sur les index et à explorer quelques requêtes SQL

À lire aussi

1 commentaires

 
GN⁺ 2024-11-16
Avis sur Hacker News

  • Il est dit que chaque ligne d’une table SQLite possède par défaut un rowId unique, qui se comporte comme une clé primaire s’il n’y a pas de clé primaire explicite, mais en réalité SQLite utilise le rowid même lorsqu’il existe une clé primaire.
    Ce serait intéressant de visualiser l’index de clé primaire d’une table WITHOUT ROWID. Ce type d’index est particulièrement intéressant.
    Même si deux index se ressemblent, le fait que le second ait moins de pages ne signifie pas forcément qu’il est plus rapide. Ce qui compte, c’est la hauteur de l’arbre, puis le fait de devoir, après avoir trouvé une valeur dans l’index, lire le reste des données dans une table séparée (rowid), ou bien d’avoir les données directement disponibles comme avec WITHOUT ROWID. La différence est particulièrement marquée pour les requêtes par plage comme where 50 <= col <= 100.

    • Pour un seul accès, c’est bien la hauteur de l’arbre qui compte, mais si l’on accède souvent à l’index, la taille totale peut aussi être très importante pour le taux de succès du cache.
    • Il y a une exception au fait que SQLite utilise rowid même en présence d’une clé primaire. Si l’on crée un INTEGER PRIMARY KEY, SQLite l’utilise à la place [1].
      [1]: https://sqlite.org/rowidtable.html

  • SQLite est assez atypique dans presque toutes ses manières de faire, et je pense que c’est encore plus vrai pour le traitement des requêtes.
    SQLite a tendance à privilégier la simplicité plutôt que les performances, et implémente donc souvent les choses différemment des autres bases de données que j’ai utilisées. SQLite ne concurrence pas vraiment les autres bases de données, mais plutôt les fichiers JSON/XML de stockage persistant. Donc regarder son implémentation n’apprend pas forcément grand-chose sur la manière dont une vraie base de données ferait la même chose.

    • Il concurrence les deux. SQLite sert clairement de stockage persistant local, mais il concurrence aussi d’autres systèmes de gestion de bases de données relationnelles dans les situations où l’on n’a pas besoin d’un processus serveur séparé.
      Cela signifie certes que les exigences sont très différentes, mais ses usages ne se limitent pas à remplacer des fichiers JSON/XML.
    • SQLite est un vrai moteur de base de données. Je suppose que tu veux plutôt dire qu’il ne concurrence pas les serveurs de bases de données.
    • Il n’est pas si éloigné de la façon dont d’autres serveurs de systèmes de gestion de bases de données traitent le stockage et les index. Les principes sont quasiment les mêmes, surtout lorsque SQLite fonctionne en mode WAL.

  • Le site est tellement agréable à lire que cela donne vraiment envie de le lire.

    • Sur iPhone, la taille du texte du corps est trop grande. Le texte important dans les schémas est beaucoup plus petit, ce qui oblige à éloigner le téléphone du visage pour lire le corps du texte, puis à le rapprocher pour lire les schémas ; c’est assez gênant.
    • C’est vraiment confortable de pouvoir lire le contenu sans publicités envahissantes. L’article est aussi excellent.

  • “indexes” est à la fois la forme de la troisième personne du singulier du présent du verbe “to index” et le pluriel nominal de “index”. En revanche, “indices” est le pluriel traditionnel, surtout utilisé dans les contextes mathématiques et scientifiques.
    En anglais courant, “indexes” est fréquent, mais dans les domaines techniques, on préfère parfois indices pour des raisons de précision linguistique. Dans ce contexte, utiliser “indices” améliore la clarté en distinguant l’action d’indexer du pluriel d’index.

    • Les deux conviennent (https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). Les documentations de SQLite et PostgreSQL, par exemple, utilisent indexes.
    • Si l’on essaie de mettre “time series” au pluriel, ce n’est pas simple.
      En Finlande, j’ai vu des gens utiliser “time series” au pluriel et “time serie” au singulier.
    • Je ne sais pas au nom de quelle autorité tu affirmes cela.
      Tous les principaux systèmes de gestion de bases de données relationnelles utilisent le terme indexes.
    • Cela dépend du public visé. Si l’on s’adresse au monde académique, on écrit indices ; si l’on s’adresse au grand public, “indices” peut passer pour prétentieux.

  • Ce serait intéressant de voir comment PostgreSQL fait la même chose. Il y aurait sûrement beaucoup à apprendre par comparaison.

  • Pour voir différentes dispositions avec moins de travail, on pourrait aussi produire du TGF pour yEd.