Analyseur SQL C++ pour une table

Question

Je suis en train de programmer une base de données très simple à partir de rien en C++ avec un analyseur SQL. J'ai tout fait. Donc, si j'ai une entrée SQL comme ça:

SELECT * FROM table WHERE `First Name`="John" AND `Last Name`="Doe" 

L'analyseur l'analyse. Le problème maintenant est de faire quelque chose avec cette information. J'ai besoin de regarder dans ma table et de trouver en fait tous les enregistrements dont le prénom est John et le nom de famille est Doe.

Je pensais pouvoir implémenter un arbre qui aurait ET comme nœud principal, avec == comme fils. L'enfant de gauche étant le prénom et l'enfant de droite étant le nom de famille. Et chaque fois que c'est vrai, poussez cet enregistrement dans un vecteur et imprimez le vecteur à la fin.

Tout cela semble fantastique en théorie, mais je n'ai aucune idée de la façon dont l'implémenter. Si j'ai une instruction if comme

if(record.firstname == "John") 

Comment puis-je modifier dynamiquement ==, il pourrait peut-être !=.

Answer 1

Ce dont vous avez besoin est de traduire le SQL dans une langue qui peut être directement exécutée. Le terme technique pour cela est le "plan de requête". Le plan de requête est les opérations de bas niveau (par exemple recherche d'index, jointure, tri) que fera le moteur de base de données, ainsi que la manière dont les opérations s'emboîtent. N'importe quel moteur de base de données décent vous donnera un moyen de voir le plan de la requête.

Dans le cas des systèmes SQL, il est généralement appelé EXPLAIN. Je vous recommande d'obtenir votre SGBD favori (si vous n'avez pas de favori, tous les SGBD Open Source décents le font, y compris MySQL et PostgreSQL) et d'examiner les plans de diverses requêtes juste pour voir quel genre d'opérations le "réel" "Les systèmes mettent en œuvre.

Je recommande également de regarder dans l'algèbre relationnelle. Si vous avez accès à une bibliothèque bien fournie, tout manuel décent sur les bases de données comportera une section ou un chapitre, mais demander à Google de renvoyer un bon nombre de bonnes références. L'algèbre relationnelle a l'avantage d'être à la fois sympa sur le plan théorique et de la mettre en œuvre de façon «évidente» à l'aide d'opérations de base de données de bas niveau. Vous pouvez finir par le modifier au-delà de la reconnaissance, mais cela devrait vous donner un bon départ.

Voyons maintenant un aperçu de base. Lisez d'abord quelque chose sur l'algèbre relationnelle, puis lisez la suite.

La structure de données principale que vous devez implémenter est le flux de tuples. Chaque tuple dans le flux est différent, mais ils ont tous la même forme: chaque champ du tuple a un nom et un type. Les opérations de requête prennent un ou plusieurs flux de tuples (une table, à propos, peut être considérée comme un flux de tuples) et renvoie un seul flux de tuples.

Tenir compte d'une instruction SQL SELECT base de la forme:

SELECT fields 
FROM table1,table2 
WHERE select_conditions, join_conditions 

Ici, select_conditions sont des conditions telles que gender='F' ou age > 18, où un champ est comparé à une constante. Les join_conditions sont des conditions qui correspondent à un champ d'une table par rapport à un champ d'une autre table. (Nous ignorerons le cas de comparer deux champs de la même table pour le moment.)

Ensuite, un plan simple requête pourrait être:

s1 := Select(table1, select_conditions_1) 
s2 := Select(table2, select_conditions_2) 
j := Join(join_conditions, s1, s2) 
res := Project(fields, j) 

L'opération Select prend un flux de tuples, et retourne un flux de tuples avec la même forme, avec les tuples qui ne correspondent pas aux conditions enlevé. L'opération Project prend un flux de tuples et retourne un flux de tuples de type différent; tout ce qu'il fait est de supprimer, réorganiser ou dupliquer les champs. Enfin, l'opération Join joint deux flux de tuples ensemble, rejoignant deux tuples qui correspondent aux conditions de jointure. (Si vous ne savez pas ce qu'est une opération de jointure de base de données, vous devez vraiment le savoir.) Demander à Google et également consulter la commande "join" d'Unix.)

Donc dans ce cas, s1 est un flux de Tuples qui représente les tuples de la table 1 qui correspondent aux conditions de sélection qui s'appliquent à la table 1. C'est une histoire similaire pour s2. Le flux j correspond aux flux s1 et s2 joints en fonction des conditions de jointure. Enfin, vous projetez uniquement les champs mentionnés dans la requête.

La traduction de SQL en une forme intermédiaire de type algèbre relationnelle est en réalité assez facile. Cependant, les traductions simples ont tendance à être extrêmement inefficaces. Ici, nous implémentons l'opération select en examinant chaque enregistrement de la table et en retournant ceux qui correspondent. La requête doit donc être optimisée, en fonction à la fois de la structure de la requête et des informations disponibles dans la table.

Par exemple, supposons que table1 a des champs age et gender, et nous avons les conditions de sélection et age > 18gender = 'F'. Supposons en outre que table1 a un index (appelé table1_age_idx) sur le champ age, mais aucun index sur le champ gender. Il est clair que nous devrions utiliser l'index. Nous pouvons le faire en divisant l'opération en deux opérations les plus élémentaires:

s1a := IndexSelect(table1_age_idx, age > 18) 
s2b := FilterSelect(s1a, gender = 'F') 

Ici, nous avons divisé l'opération de sélection en deux. Le premier select est implémenté en utilisant une requête d'index (notez que le select est maintenant sur l'index, pas la table!), Et le second peut être implémenté en filtrant le flux, en supprimant tout tuple pour lequel gender n'est pas 'F'.

La mise en œuvre de la jointure peut être effectuée de plusieurs façons (la jointure de tri-fusion et la jointure par hachage sont populaires). Lequel est le meilleur dépend de la requête et de la base de données. Certains index (par exemple B-tree et friends) renvoient des enregistrements triés par clé, donc si vous avez déjà fait un IndexSelect sur un champ auquel vous vous joignez par la suite, alors une jointure de tri-fusion est probablement meilleure, car le tri est inutile. La même chose s'applique s'il existe une clause ORDER BY dans un champ de jointure.

Comme vous pouvez le voir, c'est là que les choses vraiment intelligentes se produisent. Les optimiseurs de requêtes réelles utilisent des statistiques sur la taille d'une table et la taille probable des flux de tuple intermédiaires dans le cadre de leur calcul. C'est payant de savoir une chose ou deux sur les compilateurs ici.