Pourquoi SQLite utilise du bytecode

Fonctionnement général d’un moteur de base de données SQL

• Tous les moteurs de base de données SQL fonctionnent de manière similaire
  • Ils transforment la requête SQL saisie en « requête préparée » (Prepared Statement)
  • Ils « exécutent » ensuite cette requête préparée pour produire un résultat
• Dans SQLite, une requête préparée est représentée par une instance de l’objet sqlite3_stmt
• Il existe essentiellement deux façons de représenter une requête préparée
  • Approche bytecode : utilisée par SQLite
  • Approche par arbre d’objets : utilisée par MySQL et PostgreSQL

Avantages de l’approche bytecode

• Facile à comprendre
  • Composée d’une simple suite d’instructions, donc facile à afficher
  • Le mot-clé EXPLAIN permet d’examiner le bytecode d’une requête SQL
• Débogage facile
  • Séparation claire entre les étapes de parsing/analyse et l’exécution
  • Dans un build de débogage, la commande PRAGMA vdbe_trace=ON permet de suivre l’exécution du bytecode
• Exécution incrémentale possible
  • Une requête SQL écrite en bytecode peut s’exécuter ligne par ligne, s’arrêter, puis reprendre
  • Avec l’approche par arbre d’objets, tout l’arbre est exécuté d’un coup, ce qui rend l’exécution incrémentale difficile
• Faible consommation mémoire
  • Le bytecode est plus compact qu’un AST
  • Les Prepared Statement étant souvent conservés longtemps en cache mémoire, l’usage mémoire est important
• Exécution rapide
  • Il y a moins de décisions à prendre à chaque étape, ce qui accélère l’exécution

Avantages de l’approche par arbre d’objets

• Possibilité de modifier le plan d’exécution à l’exécution
  • Un arbre d’objets se modifie facilement même pendant l’exécution
  • Il est possible d’optimiser dynamiquement selon l’avancement de la requête
• Plus facile à paralléliser
  • Chaque nœud de traitement peut être affecté à un thread distinct
  • Il suffit de synchroniser le transfert des données entre les nœuds
  • Cette approche est avantageuse pour exécuter des requêtes analytiques volumineuses (OLAP) sur plusieurs cœurs

Avis de GN⁺

• L’objectif principal de SQLite étant le traitement transactionnel (OLTP) dans des environnements IoT, l’approche bytecode semble bien adaptée. Elle permet d’offrir de bonnes performances tout en restant simple et légère.
• À l’inverse, MySQL et PostgreSQL sont aussi largement utilisés pour l’analyse de grands volumes de données. Les avantages d’une approche par arbre d’objets, capable d’optimiser dynamiquement le plan d’exécution et de se paralléliser, peuvent donc y être davantage mis en avant.
• Cela dit, l’approche par arbre d’objets présente aussi des inconvénients, notamment un débogage et une analyse des performances plus difficiles. De plus, le coût du parcours de l’arbre peut faire qu’une requête simple soit parfois plus lente qu’avec du bytecode.
• L’essentiel est de choisir l’approche la plus adaptée à l’usage et à l’objectif. Pour un SGBDR généraliste, on peut aussi envisager une approche hybride qui combine les avantages et les inconvénients des deux modèles.

[GN⁺]

Commentaire Hacker News

• Le fait que SQLite utilise une machine virtuelle (VM) à bytecode plutôt qu’un arbre syntaxique abstrait (AST) pour exécuter les requêtes SQL constitue un choix de conception intéressant pour une base de données. Les avantages du bytecode par rapport à un AST sont les suivants :

  • Compacité : le bytecode est plus compact qu’un AST, car il n’a pas besoin de malloc cachés, d’en-têtes d’objet ni de pointeurs pour les sous-expressions.
  • Performance : l’exécution du bytecode est plus rapide grâce à une meilleure utilisation du cache et à moins de cache misses dues au suivi de pointeurs.
  • Exécution incrémentale : avec une pile explicite, il est plus facile en bytecode de suspendre et reprendre l’exécution sans dérouler la pile principale.

• Les VM à bytecode et les interpréteurs sont souvent associés aux langages de programmation généralistes, mais ils peuvent aussi être étonnamment utiles dans d’autres contextes, par exemple :

  • eBPF : mécanisme d’extension du noyau Linux.
  • Langage d’expression DWARF : utilisé par des débogueurs comme GDB et LLDB.
  • Format de fichier RAR : inclut un encodage en bytecode pour des transformations de données personnalisées.

• Microsoft SQL Server utilise en interne un arbre d’objets, mais la sortie du plan de requête reste présentée sous forme de table, ce qui montre la difficulté de rendre un arbre d’objets sous forme tabulaire.

• Les programmeurs savent souvent précisément quelles recherches d’index doivent avoir lieu dans une boucle ; dans certains cas, il peut donc être avantageux d’écrire directement du bytecode ou d’utiliser un langage impératif de haut niveau au lieu de SQL. L’exprimer en SQL peut être contraignant.

• Si le goulot d’étranglement ne se situe pas dans l’exécution du bytecode (par exemple au niveau de la mémoire ou de la vitesse du disque), il n’est pas forcément nécessaire de le convertir en code natif via une compilation JIT.

• De nombreux langages de programmation, comme Python, Ruby et Lua, utilisent en interne du bytecode ou des AST. En raison des choix de conception des bases de données, des instructions faciles à analyser peuvent être utiles pour les bibliothèques tierces ou les implémentations d’ORM sujettes aux erreurs.