query planner guide
1.0.0
[Placeholder]
Un planificateur de requête est un composant d'un système de gestion de base de données (SGBD) qui est responsable de la génération d'un plan d'exécution d'une requête de base de données. Le plan de requête spécifie les étapes que les SGBD prendront pour récupérer les données demandées par la requête. L'objectif du planificateur de requête est de générer un plan aussi efficace que possible, ce qui signifie qu'il renvoie les données à l'utilisateur le plus rapidement possible.
Les planificateurs de requête sont des logiciels complexes et ils peuvent être difficiles à comprendre. Ce guide de mise en œuvre d'un planificateur de requêtes basé sur les coûts vous fournira un aperçu étape par étape du processus, comment mettre en œuvre votre propre planificateur de requête basé sur les coûts, tout en couvrant les concepts de base du planificateur de requête.
Écrit par AI, édité par Human
Ce guide est écrit pour:
Objectifs:
graphique TD
utilisateur ((utilisateur))
analyseur [analyser de requête]
planificateur [planificateur de requête]
Exécuteur [Processeur de requête]
Utilisateur - Requête texte -> Parser
analyseur - AST -> planificateur
Planificateur - Plan physique -> Exécuteur
L'architecture de base d'un moteur de requête est composée de ces composants:
Normalement, les planificateurs de requête sont divisés en 2 types:
Heuristic Planner est le planificateur de requête qui a utilisé des règles prédéfinies pour générer un plan de requête.
Le planificateur basé sur les coûts est le planificateur de requête qui en fonction du coût de génération de requête, il essaie de trouver le plan optimal en fonction du coût de la requête d'entrée.
Bien que Heuristic Planner trouve généralement le meilleur plan en appliquant des règles de transformation s'il sait que le plan transformé est meilleur, le planificateur basé sur les coûts trouvera le meilleur plan en énumérant des plans équivalents et essayez de trouver le meilleur plan parmi eux.
Dans le planificateur de requête basé sur les coûts, il est généralement composé de phases:
Dans la phase d'énumérations du plan, le planificateur énumérera les plans équivalents possibles.
Après cela, dans la phase d'optimisation des requêtes, le planificateur recherchera le meilleur plan à partir de la liste des plans énumérés. Le meilleur plan est le plan ayant le coût le plus bas, que le modèle de coût (ou la fonction de coût) est défini.
Parce que le naturel du plan logique est d'avoir une structure en forme d'arbre, vous pouvez donc penser que l'optimisation / la recherche est en fait un problème de recherche d'arbres. Et il y a beaucoup d'algorithmes de recherche d'arbres ici:
Remarques: En théorie, il est possible d'utiliser tout type d'algorithme de recherche d'arbres. Cependant, de manière pratique, ce n'est pas possible car le temps de recherche est augmenté lorsque notre algorithme de recherche est complexe
Remarques: Les conditions de terminaison de recherche sont généralement:
Planificateur de requête volcano (ou générateur d'optimiseur volcano) est un planificateur de requête basé sur les coûts
Volcano Planner utilise une approche de programmation dynamique pour trouver le meilleur plan de requête à partir de la liste des plans énumérés.
Détails: https://ieeexplore.ieee.org/document/344061 (je suis trop paresseux pour expliquer le document ici)
Voici une excellente explication: https://15721.Courses.cs.cmu.edu/Spring2017/slides/15-optimizer2.pdf#page=9
Notre planificateur de requêtes, est un planificateur de requête basé sur les coûts, suivant l'idée de base du planificateur de requête volcano, notre planificateur sera composé de 2 phases principales:
graphique LR
ast ((ast))
logical_plan [plan]
explore_plans ["`
Plan n ° 1
...
Plan #N
`"]
implémentation_plan ["plan #x (meilleur plan)"]
AST - Convertir en plan logique -> logical_plan
Logical_Plan - Phase d'exploration -> explore_plans
explore_plans - phase d'optimisation -> implémentation_plan
linkstyle 1,2 Couleur: orange, trait: orange, largeur de course: 5px
Le plan logique est la datastructure tenant l'abstraction de l'étape de transformation requise pour exécuter la requête.
Voici un exemple de plan logique:
graphique TD
1.
2 ["JOIN"];
3 ["Scan TBL1"];
4 ["JOIN"];
5 ["Scan Tbl2"];
6 ["Scan TBL3"];
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
4 -> 6;
Bien que le plan logique ne contient que l'abstraction, le plan physique est la datastructure détenant les détails de l'implémentation. Chaque plan logique aura plusieurs plans physiques. Par exemple, une jointure logique pourrait comporter de nombreux plans physiques tels que la jointure de hachage, la jointure de fusion, la jointure de diffusion, etc.
Le groupe équivalent est un groupe d'expressions équivalentes (qui pour chaque expression, leur plan logique est logiquement équivalent)
par exemple
graphique TD
Groupe des subgraphs # 8
Expr # 8 ["Scan TBL2 (Field1, Field2, ID)"]
fin
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 11
Expr # 11 ["join"]
fin
Expr # 11 -> Groupe # 7
Expr # 11 -> Groupe # 10
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7 ["scan tbl1 (id, champ1)"]
fin
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraphs # 10
Expr # 10 ["join"]
fin
Expr # 10 -> Groupe # 8
Expr # 10 -> Groupe # 9
Groupe de substanières # 9
Expr # 9 ["Scan Tbl3 (id, field2)"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
EXPR # 12 ["Projet TBL1.ID, TBL1.Field1, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
EXPR # 6 ["Projet TBL1.ID, TBL1.Field1, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 12 -> Groupe # 11
Expr # 6 -> Groupe # 5
Ici, nous pouvons voir que Group#6 a 2 expressions équivalentes, qui représentent toutes deux la même requête (on fait du scan à partir du tableau puis du projet, on pousse la projection vers le bas pour scanner le nœud).
La règle de transformation est la règle pour passer d'un plan logique à un autre plan logique équivalent logique
Par exemple, le plan:
graphique TD
1.
2 ["JOIN"];
3 ["Scan TBL1"];
4 ["JOIN"];
5 ["Scan Tbl2"];
6 ["Scan TBL3"];
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
4 -> 6;
Lors de l'application de la transformation de poussée de projection, est transformé en:
graphique TD
1 ["Projet *. *"];
2 ["JOIN"];
3 ["Scan TBL1 (ID, Field1)"];
4 ["JOIN"];
5 ["Scan Tbl2 (Field1, Field2)"];
6 ["Scan TBL3 (ID, Field2, Field2)"];
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
4 -> 6;
La règle de transformation peut être affectée par des traits / propriétés logiques tels que le schéma de table, les statistiques de données, etc.
La règle de mise en œuvre est la règle pour retourner les plans physiques donnés par un plan logique.
La règle de mise en œuvre peut être affectée par des traits / propriétés physiques tels que la disposition des données (triée ou non), etc.
Dans la phase d'exploration, le planificateur appliquera des règles de transformation, générant des plans logiques équivalents
Par exemple, le plan:
graphique TD
1326583549 ["Project Tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"];
-425111028 ["JOIN"];
-349388609 ["Scan TBL1"];
1343755644 ["JOIN"];
-1043437086 ["Scan TBL2"];
-1402686787 ["Scan TBL3"];
1326583549 -> -425111028;
-425111028 -> -349388609;
-425111028 -> 1343755644;
1343755644 -> -1043437086;
1343755644 -> -1402686787;
Après avoir appliqué des règles de transformation, résultant en le graphique suivant:
graphique TD
Groupe des subgraphs # 8
Expr # 8 ["Scan TBL2 (ID, Field1, Field2)"]
fin
Groupe des sub-graphiques # 11
Expr # 11 ["join"]
Expr # 14 ["join"]
fin
Expr # 11 -> Groupe # 7
Expr # 11 -> Groupe # 10
Expr # 14 -> Groupe # 8
Expr # 14 -> Groupe # 12
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
Expr # 16 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Expr # 16 -> Groupe # 2
Expr # 16 -> Groupe # 13
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des subgraphs # 13
Expr # 15 ["join"]
fin
Expr # 15 -> Groupe # 1
Expr # 15 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7 ["scan tbl1 (id, champ1)"]
fin
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraphs # 10
Expr # 10 ["join"]
fin
Expr # 10 -> Groupe # 8
Expr # 10 -> Groupe # 9
Groupe de substanières # 9
Expr # 9 ["Scan Tbl3 (id, field2)"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 12
Expr # 13 ["join"]
fin
Expr # 13 -> Groupe # 7
Expr # 13 -> Groupe # 9
Groupe des subgraphs # 6
EXPR # 12 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.id, Tbl3.Field2, Tbl3.Field2"]
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 12 -> Groupe # 11
Expr # 6 -> Groupe # 5
Ici, nous pouvons voir que la règle Pushdown de projection et la règle de réorganisation sont appliquées.
La phase d'optimisation est de traverser l'arbre élargi en phase d'exploration, pour trouver le meilleur plan pour notre requête.
Ce "réellement" est une optimisation de recherche d'arbre, vous pouvez donc utiliser n'importe quel algorithme de recherche d'arbre que vous pouvez imaginer (mais vous devez vous assurer qu'il est correct).
Voici l'exemple du plan physique généré après la phase d'optimisation:
graphique TD
Groupe # 6 ["
Groupe n ° 6
Sélectionné: Project Tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Opérateur: ProjectOperator
Coût: coût (CPU = 641400,00, MEM = 1020400012.00, temps = 1000000,00)
"]
Groupe # 6 -> Groupe # 11
Groupe # 11 ["
Groupe n ° 11
Sélectionné: rejoindre
Opérateur: hashjoinopérateur
Coût: coût (CPU = 641400,00, MEM = 1020400012.00, temps = 1000000,00)
"]
Groupe # 11 -> Groupe # 7
Groupe # 11 -> Groupe # 10
Groupe # 7 ["
Groupe n ° 7
Sélectionné: scan TBL1 (ID, Field1)
Opérateur: NormalscanOperator
Coût: coût (CPU = 400,00, MEM = 400000,00, heure = 1000,00)
"]
Groupe # 10 ["
Groupe n ° 10
Sélectionné: rejoindre
Opérateur: MergejoinOperator
Traits: trié
Coût: coût (CPU = 640000,00, MEM = 20000012.00, heure = 1100000,00)
"]
Groupe # 10 -> Groupe # 8
Groupe # 10 -> Groupe # 9
Groupe # 8 ["
Groupe n ° 8
Sélectionné: scan Tbl2 (ID, Field1, Field2)
Opérateur: NormalscanOperator
Traits: trié
Coût: coût (CPU = 600000,00, MEM = 12,00, temps = 1000000,00)
"]
Groupe # 9 ["
Groupe n ° 9
Sélectionné: scan tbl3 (id, field2)
Opérateur: NormalscanOperator
Traits: trié
Coût: coût (CPU = 40000,00, MEM = 20000000,00, temps = 100000,00)
"]
Le plan généré a montré le plan logique sélectionné, le coût estimé et l'opérateur physique
Notre planificateur effectuera une recherche d'épuisement pour trouver le meilleur plan
Puisque le code du planificateur est grand, je n'écrirai donc pas le guide étape par étape, mais je vais expliquer chaque élément du code à la place
Ici, nous définirons une langue de requête qui a utilisé à fond ce tutoriel
SELECT emp . id ,
emp . code ,
dept . dept_name ,
emp_info . name ,
emp_info . origin
FROM emp
JOIN dept ON emp . id = dept . emp_id
JOIN emp_info ON dept . emp_id = emp_info . idLe langage de requête que nous implémenterons est une langue de type SQL. Cependant, par souci de simplicité, nous limiterons sa fonctionnalité et sa syntaxe.
La langue est apparue sous forme de
SELECT tbl . field , [...]
FROM tbl JOIN [...] Il ne prendra en charge que pour SELECT et JOIN , également le champ dans la déclaration de sélection doit être entièrement qualifié (sous forme de table.field ), toutes les autres fonctionnalités ne seront pas prises en charge
Tout d'abord, nous devons définir l'AST pour notre langue. AST (ou syntaxe abstrait) est un arbre utilisé pour représenter la structure syntaxique d'un texte.
Étant donné que notre langue est si simple, nous pouvons simplement définir la structure AST dans plusieurs codes:
sealed trait Identifier
case class TableID ( id : String ) extends Identifier
case class FieldID ( table : TableID , id : String ) extends Identifier
sealed trait Statement
case class Table ( table : TableID ) extends Statement
case class Join ( left : Statement , right : Statement , on : Seq [( FieldID , FieldID )]) extends Statement
case class Select ( fields : Seq [ FieldID ], from : Statement ) extends Statement
Par exemple, une requête
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . idpeut être représenté comme
Select (
Seq (
FieldID ( TableID ( " tbl1 " ), " id " ),
FieldID ( TableID ( " tbl1 " ), " field1 " ),
FieldID ( TableID ( " tbl2 " ), " id " ),
FieldID ( TableID ( " tbl2 " ), " field1 " ),
FieldID ( TableID ( " tbl2 " ), " field2 " ),
FieldID ( TableID ( " tbl3 " ), " id " ),
FieldID ( TableID ( " tbl3 " ), " field2 " ),
FieldID ( TableID ( " tbl3 " ), " field2 " )
),
Join (
Table ( TableID ( " tbl1 " )),
Join (
Table ( TableID ( " tbl2 " )),
Table ( TableID ( " tbl3 " )),
Seq (
FieldID ( TableID ( " tbl2 " ), " id " ) -> FieldID ( TableID ( " tbl3 " ), " id " )
)
),
Seq (
FieldID ( TableID ( " tbl1 " ), " id " ) -> FieldID ( TableID ( " tbl2 " ), " id " )
)
)
)Après avoir défini la structure AST, nous devrons écrire l'analyseur de requête, qui est utilisé pour convertir la requête du texte en forme AST.
Étant donné que ce guide utilise Scala pour l'implémentation, nous choisirons des combinants Scala-Parser pour créer notre analyseur de requête.
Classe d'analyser de requête:
object QueryParser extends ParserWithCtx [ QueryExecutionContext , Statement ] with RegexParsers {
override def parse ( in : String )( implicit ctx : QueryExecutionContext ) : Either [ Throwable , Statement ] = {
Try (parseAll(statement, in) match {
case Success (result, _) => Right (result)
case NoSuccess (msg, _) => Left ( new Exception (msg))
}) match {
case util. Failure (ex) => Left (ex)
case util. Success (value) => value
}
}
private def select : Parser [ Select ] = ??? // we will implement it in later section
private def statement : Parser [ Statement ] = select
}
Définissez ensuite quelques règles d'analyse:
// common
private def str : Parser [ String ] = """ [a-zA-Z0-9_]+ """ .r
private def fqdnStr : Parser [ String ] = """ [a-zA-Z0-9_]+.[a-zA-Z0-9_]+ """ .r
// identifier
private def tableId : Parser [ TableID ] = str ^^ (s => TableID (s))
private def fieldId : Parser [ FieldID ] = fqdnStr ^^ { s =>
val identifiers = s.split( '.' )
if (identifiers.length != 2 ) {
throw new Exception ( " should never happen " )
} else {
val table = identifiers.head
val field = identifiers( 1 )
FieldID ( TableID (table), field)
}
} Voici deux règles, qui sont utilisées pour analyser les identifiants: TableID et FieldID .
L'ID de table (ou le nom du tableau) ne contient généralement que des caractères, des nombres et des soulignements ( _ ), nous utiliserons donc un simple regex [a-zA-Z0-9_]+ pour identifier le nom du tableau.
D'un autre côté, ID de champ (pour le qualificatif de champ) dans notre langue est un nom de champ entièrement qualifié. Normalement, il est [a-zA-Z0-9_]+.[a-zA-Z0-9_]+ forme de table.field .
Après avoir défini les règles pour analyser les identifiants, nous pouvons désormais définir des règles pour analyser la déclaration de requête:
// statement
private def table : Parser [ Table ] = tableId ^^ (t => Table (t))
private def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) " La règle table est une règle simple, elle crée simplement le nœud Table en utilisant la TableID analysée à partir de la règle tableId .
La subQuery est la règle pour analyser la sous-requête. Dans SQL, nous pouvons écrire une requête qui ressemble à ceci:
SELECT a
FROM ( SELECT b FROM c) d Le SELECT b FROM c est la sous-requête dans la déclaration ci-dessus. Ici, dans notre langage de requête simple, nous indiquerons qu'une instruction est une sous-questionuse si elle est enfermée par une paire de parenthèses ( () ). Étant donné que notre langue n'a qu'une déclaration sélectionnée, nous pouvons écrire la règle d'analyse comme suit:
def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "Nous allons maintenant définir les règles d'analyse pour la déclaration de sélection:
private def fromSource : Parser [ Statement ] = table ||| subQuery
private def select : Parser [ Select ] =
" SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep(
" JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)
) ^^ {
case _ ~ fields ~ _ ~ src ~ joins =>
val p = if (joins.nonEmpty) {
def chain ( left : Statement , right : Seq [( Statement , Seq [( FieldID , FieldID )])]) : Join = {
if (right.isEmpty) {
throw new Exception ( " should never happen " )
} else if (right.length == 1 ) {
val next = right.head
Join (left, next._1, next._2)
} else {
val next = right.head
Join (left, chain(next._1, right.tail), next._2)
}
}
val temp = joins.map { join =>
val statement = join._1._1._2
val joinOn = join._2.map(on => on._1._1 -> on._2)
statement -> joinOn
}
chain(src, temp)
} else {
src
}
Select (fields, p)
}Dans SQL, nous pouvons utiliser une sous-questionnaire comme source de jointure. Par exemple:
SELECT * . *
FROM tbl1
JOIN ( SELECT * . * FROM tbl2)
JOIN tbl3Ainsi, notre analyseur mettra également en œuvre des règles pour analyser la sous-requête dans la partie de jointure de la déclaration, c'est pourquoi nous avons la règle d'analyse:
" SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep( " JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)Voir queryparser.scala pour la mise en œuvre complète
Voir queryparserspec.scala
Après avoir généré l'AST à partir de la requête texte, nous pouvons le convertir directement au plan logique
Tout d'abord, définissons l'interface de notre plan logique:
sealed trait LogicalPlan {
def children () : Seq [ LogicalPlan ]
}
children sont la liste du plan logique des enfants. Par exemple:
graphique TD
1326583549 ["Project Tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"];
-425111028 ["JOIN"];
-349388609 ["Scan TBL1"];
1343755644 ["JOIN"];
-1043437086 ["Scan TBL2"];
-1402686787 ["Scan TBL3"];
1326583549 -> -425111028;
-425111028 -> -349388609;
-425111028 -> 1343755644;
1343755644 -> -1043437086;
1343755644 -> -1402686787;
Les nœuds enfants du nœud PROJECT sont le premier nœud JOIN . Le nœud de premier JOIN a 2 enfants, qui sont le deuxième nœud JOIN et le nœud SCAN tbl1 . Bientôt, ...
Étant donné que notre langage de requête est simple, nous n'avons besoin que de 3 types de nœud logique:
case class Scan ( table : ql. TableID , projection : Seq [ String ]) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq .empty
}
case class Project ( fields : Seq [ql. FieldID ], child : LogicalPlan ) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq (child)
}
case class Join ( left : LogicalPlan , right : LogicalPlan , on : Seq [(ql. FieldID , ql. FieldID )]) extends LogicalPlan {
override def children () : Seq [ LogicalPlan ] = Seq (left, right)
}
Ensuite, nous pouvons écrire la fonction pour convertir l'AST en plan logique:
def toPlan ( node : ql. Statement ) : LogicalPlan = {
node match {
case ql. Table (table) => Scan (table, Seq .empty)
case ql. Join (left, right, on) => Join (toPlan(left), toPlan(right), on)
case ql. Select (fields, from) => Project (fields, toPlan(from))
}
}Voir logicalplan.scala pour une implémentation complète
Nous pouvons définir des cours pour le groupe comme suit:
case class Group (
id : Long ,
equivalents : mutable. HashSet [ GroupExpression ]
) {
val explorationMark : ExplorationMark = new ExplorationMark
var implementation : Option [ GroupImplementation ] = None
}
case class GroupExpression (
id : Long ,
plan : LogicalPlan ,
children : mutable. MutableList [ Group ]
) {
val explorationMark : ExplorationMark = new ExplorationMark
val appliedTransformations : mutable. HashSet [ TransformationRule ] = mutable. HashSet ()
}
Group est l'ensemble des plans qui sont logiquement équivalents.
Chaque GroupExpression représente un nœud de plan logique. Puisque nous avons défini un nœud de plan logique aura une liste de nœuds enfants (dans la section précédente), et que le GroupExpression représente un nœud de plan logique, et le Group représente un ensemble de plans équivalents, de sorte que les enfants de GroupExpression sont une liste de Group
par exemple
graphique TD
Groupe des subgraphs # 8
Expr # 8
fin
Groupe de substanières n ° 2
Expr # 2
fin
Groupe des sub-graphiques # 11
Expr # 11
fin
Expr # 11 -> Groupe # 7
Expr # 11 -> Groupe # 10
Groupe de substanières # 5
Expr # 5
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7
fin
Groupe de sous-graphe n ° 1
Expr # 1
fin
Groupe des subgraphs # 10
Expr # 10
fin
Expr # 10 -> Groupe # 8
Expr # 10 -> Groupe # 9
Groupe de substanières # 9
Expr # 9
fin
Groupe des subgraps # 3
Expr # 3
fin
Groupe des subgraphs # 6
Expr # 12
Expr # 6
fin
Expr # 12 -> Groupe # 11
Expr # 6 -> Groupe # 5
Comme nous pouvons le voir ici, le Group#6 a 2 expressions équivalentes: Expr#12 et Expr#6 , et les enfants de Expr#12 sont Group#11
Remarques: Nous allons implémenter plusieurs transformations rondes dans la phase d'exploration, donc pour chaque Group et GroupExpression , nous avons une indication ExplorationMark indiquant l'état d'exploration.
class ExplorationMark {
private var bits : Long = 0
def get : Long = bits
def isExplored ( round : Int ) : Boolean = BitUtils .getBit(bits, round)
def markExplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = true )
def markUnexplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = false )
}
ExplorationMark n'est qu'une classe de wrapper Bitset, il marquera le bit i -th comme 1 si le i -th round est exploré, marquez 0 autrement.
ExplorationMark peut également être utilisé pour visualiser la transformation exacte, voir la visualisation pour plus de détails
Le mémo est un tas d'aides pour aider à construire les groupes équivalents. Memo est composé de plusieurs hashmap pour cacher l'expression du groupe et du groupe, fournissent également des méthodes pour enregistrer une nouvelle expression de groupe ou de groupe.
class Memo (
groupIdGenerator : Generator [ Long ] = new LongGenerator ,
groupExpressionIdGenerator : Generator [ Long ] = new LongGenerator
) {
val groups : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]()
val parents : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]() // lookup group from group expression ID
val groupExpressions : mutable. HashMap [ LogicalPlan , GroupExpression ] = mutable. HashMap [ LogicalPlan , GroupExpression ]()
def getOrCreateGroupExpression ( plan : LogicalPlan ) : GroupExpression = {
val children = plan.children()
val childGroups = children.map(child => getOrCreateGroup(child))
groupExpressions.get(plan) match {
case Some (found) => found
case None =>
val id = groupExpressionIdGenerator.generate()
val children = mutable. MutableList () ++ childGroups
val expression = GroupExpression (
id = id,
plan = plan,
children = children
)
groupExpressions += plan -> expression
expression
}
}
def getOrCreateGroup ( plan : LogicalPlan ) : Group = {
val exprGroup = getOrCreateGroupExpression(plan)
val group = parents.get(exprGroup.id) match {
case Some (group) =>
group.equivalents += exprGroup
group
case None =>
val id = groupIdGenerator.generate()
val equivalents = mutable. HashSet () + exprGroup
val group = Group (
id = id,
equivalents = equivalents
)
groups.put(id, group)
group
}
parents += exprGroup.id -> group
group
}
}
Voir memo.scala pour la mise en œuvre complète
La première étape à l'intérieur du planificateur est l'initialisation
graphique LR
requête ((requête))
ast ((ast))
root_plan ((rootplan))
root_group ((RootGroup))
Query - "QueryParser.Parse (Query)" -> AST
ast - "logicalplan.toplan (ast)" -> root_plan
root_plan - "memo.getorcreategroup (rootplan)" -> root_group
Premièrement, la requête sera analysée en AST. Puis converti en plan logique, appelé root plan , puis initialisez le groupe à partir root plan , appelé root group .
def initialize ( query : Statement )( implicit ctx : VolcanoPlannerContext ) : Unit = {
ctx.query = query
ctx.rootPlan = LogicalPlan .toPlan(ctx.query)
ctx.rootGroup = ctx.memo.getOrCreateGroup(ctx.rootPlan)
// assuming this is first the exploration round,
// by marking the initialRound(0) as explored,
// it will be easier to visualize the different between rounds (added nodes, add connections)
ctx.memo.groups.values.foreach(_.explorationMark.markExplored(initialRound))
ctx.memo.groupExpressions.values.foreach(_.explorationMark.markExplored(initialRound))
}Voir volcanoplanner.scala pour plus de détails
Par exemple, la requête:
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . idAprès l'initialisation, les groupes ressembleront à ceci:
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 6 -> Groupe # 5
Ici, vous pouvez voir cela, chaque groupe a exactement une expression équivalente
Après initialisation, est maintenant la phase d'exploration, qui explorera tous les plans équivalents possibles.
La méthode d'exploration est assez simple:
Avant de plonger dans le code d'exploration, parlons d'abord de la règle de transformation.
La règle de transformation est une règle utilisée pour transformer un plan logique en un autre plan logique équivalent s'il correspond à la condition de règle.
Voici l'interface de la règle de transformation:
trait TransformationRule {
def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean
def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression
}
Étant donné que le plan logique est une datastructure en forme d'arbre, la mise en œuvre match des règles de transformation correspond donc à l'arborescence.
Par exemple, voici la match utilisée pour correspondre au nœud du projet tout en vérifiant si ce sont des descendants contenant la jointure et la numérisation:
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case Project (_, child) => check(child)
case _ => false
}
}
// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
node match {
case Scan (_, _) => true
case Join (left, right, _) => check(left) && check(right)
case _ => false
}
}Ce plan est "apparié":
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan"]
fin
Groupe des subgraphs # 6
EXPR # 6 ["Projet"]
fin
Expr # 6 -> Groupe # 5
Bien que ce plan ne soit pas:
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 3
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["scan"]
fin
Groupe des sub-graphiques # 7
EXPR # 7 ["Projet"]
fin
Expr # 7 -> Groupe # 6
Groupe de sous-graphe n ° 1
Expr # 1 ["scan"]
fin
Groupe des subgraps # 3
Expr # 3 ["projet"]
fin
Expr # 3 -> Groupe # 2
Groupe des subgraphs # 6
Expr # 6 ["join"]
fin
Expr # 6 -> Groupe # 1
Expr # 6 -> Groupe # 5
Comme nous l'avons déjà dit, la méthode d'exploration est:
Et voici le code d'exploration (assez simple, hein):
private def exploreGroup (
group : Group ,
rules : Seq [ TransformationRule ],
round : Int
)( implicit ctx : VolcanoPlannerContext ) : Unit = {
while ( ! group.explorationMark.isExplored(round)) {
group.explorationMark.markExplored(round)
// explore all child groups
group.equivalents.foreach { equivalent =>
if ( ! equivalent.explorationMark.isExplored(round)) {
equivalent.explorationMark.markExplored(round)
equivalent.children.foreach { child =>
exploreGroup(child, rules, round)
if (equivalent.explorationMark.isExplored(round) && child.explorationMark.isExplored(round)) {
equivalent.explorationMark.markExplored(round)
} else {
equivalent.explorationMark.markUnexplored(round)
}
}
}
// fire transformation rules to explore all the possible transformations
rules.foreach { rule =>
if ( ! equivalent.appliedTransformations.contains(rule) && rule.`match`(equivalent)) {
val transformed = rule.transform(equivalent)
if ( ! group.equivalents.contains(transformed)) {
group.equivalents += transformed
transformed.explorationMark.markUnexplored(round)
group.explorationMark.markUnexplored(round)
}
}
}
if (group.explorationMark.isExplored(round) && equivalent.explorationMark.isExplored(round)) {
group.explorationMark.markExplored(round)
} else {
group.explorationMark.markUnexplored(round)
}
}
}
}Voir volcanoplanner.scala pour plus de détails
Il est maintenant temps de mettre en œuvre certaines règles de transformation
La poussée de projection est une règle de transformation simple, utilisée pour pousser la projection vers le bas vers la couche de stockage.
Par exemple, la requête
SELECT field1, field2
from tbla le plan
graphique LR
Projet [Project Field1, Field2]
scan [scan tbl]
Projet -> scanner
Avec ce plan, lors de l'exécution, les lignes de la couche de stockage (sous scan) seront entièrement récupérées, puis les champs inutiles seront supprimés (projet). Les données inutiles doivent encore passer du nœud de numérisation au nœud de projet, il y a donc des efforts gaspillés ici.
Nous pouvons l'améliorer en indiquant simplement que la couche de stockage ne récupéra que les champs nécessaires. Maintenant, le plan sera transformé en:
graphique LR
Projet [Project Field1, Field2]
Scan ["Scan TBL (Field1, Field2)"]
Projet -> scanner
Entrons dans le code:
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case Project (_, child) => check(child)
case _ => false
}
}
// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
node match {
case Scan (_, _) => true
case Join (left, right, _) => check(left) && check(right)
case _ => false
}
}Notre règle Pushdown de projection ici, correspondra au plan quand il sera le nœud du projet, et tous ses descendants sont scan et joignent uniquement le nœud.
Remarques: En fait, la véritable correspondance de poussée de projection est plus complexe, mais pour la simplicité, la règle de correspondance ici est juste le nœud de projet avec scan et rejoindre les descendants
Et voici le code de transformation:
override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
val plan = expression.plan. asInstanceOf [ Project ]
val pushDownProjection = mutable. ListBuffer [ FieldID ]()
extractProjections(plan, pushDownProjection)
val newPlan = Project (plan.fields, pushDown(pushDownProjection.distinct, plan.child))
ctx.memo.getOrCreateGroupExpression(newPlan)
}
private def extractProjections ( node : LogicalPlan , buffer : mutable. ListBuffer [ FieldID ]) : Unit = {
node match {
case Scan (_, _) => () : Unit
case Project (fields, parent) =>
buffer ++= fields
extractProjections(parent, buffer)
case Join (left, right, on) =>
buffer ++= on.map(_._1) ++ on.map(_._2)
extractProjections(left, buffer)
extractProjections(right, buffer)
}
}
private def pushDown ( pushDownProjection : Seq [ FieldID ], node : LogicalPlan ) : LogicalPlan = {
node match {
case Scan (table, tableProjection) =>
val filteredPushDownProjection = pushDownProjection.filter(_.table == table).map(_.id)
val updatedProjection =
if (filteredPushDownProjection.contains( " * " ) || filteredPushDownProjection.contains( " *.* " )) {
Seq .empty
} else {
(tableProjection ++ filteredPushDownProjection).distinct
}
Scan (table, updatedProjection)
case Join (left, right, on) => Join (pushDown(pushDownProjection, left), pushDown(pushDownProjection, right), on)
case _ => throw new Exception ( " should never happen " )
}
}Le code de transformation trouvera d'abord toutes les projections du nœud du projet racine, puis les pousse à tous les nœuds de balayage en dessous.
Visualiser notre règle, par exemple, le plan
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 6 -> Groupe # 5
Après avoir appliqué une transformation de poussée de projection, entraînera un nouveau plan équivalent avec les projections qui sont poussées vers les opérations de balayage (le nouveau plan est l'arbre avec des nœuds de bordure orange).
graphique TD
Groupe des subgraphs # 8
Expr # 8 ["Scan TBL2 (ID, Field1, Field2)"]
fin
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 11
Expr # 11 ["join"]
fin
Expr # 11 -> Groupe # 7
Expr # 11 -> Groupe # 10
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7 ["scan tbl1 (id, champ1)"]
fin
Groupe des subgraphs # 10
Expr # 10 ["join"]
fin
Expr # 10 -> Groupe # 8
Expr # 10 -> Groupe # 9
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe de substanières # 9
Expr # 9 ["Scan Tbl3 (id, field2)"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
EXPR # 12 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.id, Tbl3.Field2, Tbl3.Field2"]
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 12 -> Groupe # 11
Expr # 6 -> Groupe # 5
Style Expr # 12-AVILLET-largeur: 4px, trait: orange
Style Expr # 8-AVET-largeur: 4px, trait: orange
Style Expr # 10-AVET-largeur: 4px, trait: orange
Style Expr # 9 AVILLEME-VIE: 4px, trait: orange
Style Expr # 11 AVC-UDETH: 4px, trait: orange
Style Expr # 7-AVILLET-largeur: 4px, trait: orange
LinkStyle 0-AVC-largeur: 4px, trait: orange
Linkstyle 1-AVC-largeur: 4px, trait: orange
Linkstyle 6 AVC-large: 4px, trait: orange
Linkstyle 7 AVC-large: 4px, trait: orange
Linkstyle 8 AVC-large: 4px, trait: orange
Voir projectionpushdown.scala pour la mise en œuvre complète
Rejoindre la réorganisation est également l'une des transformations les plus reconnues du monde du planificateur de requête. Notre planificateur mettra également en œuvre une règle de transformation de réorganisation.
Étant donné que rejoindre la réorganisation dans le monde réel n'est pas une pièce facile à mettre en œuvre. Nous allons donc implémenter une version simple et arnaque de la règle de réorganisation de jointure ici.
Tout d'abord, la match des règles:
// check if the tree only contains SCAN and JOIN nodes, and also extract all SCAN nodes and JOIN conditions
private def checkAndExtract (
node : LogicalPlan ,
buffer : mutable. ListBuffer [ Scan ],
joinCondBuffer : mutable. ListBuffer [(ql. FieldID , ql. FieldID )]
) : Boolean = {
node match {
case node @ Scan (_, _) =>
buffer += node
true
case Join (left, right, on) =>
joinCondBuffer ++= on
checkAndExtract(left, buffer, joinCondBuffer) && checkAndExtract(right, buffer, joinCondBuffer)
case _ => false
}
}
private def buildInterchangeableJoinCond ( conditions : Seq [(ql. FieldID , ql. FieldID )]) : Seq [ Seq [ql. FieldID ]] = {
val buffer = mutable. ListBuffer [mutable. Set [ql. FieldID ]]()
conditions.foreach { cond =>
val set = buffer.find { set =>
set.contains(cond._1) || set.contains(cond._2)
} match {
case Some (set) => set
case None =>
val set = mutable. Set [ql. FieldID ]()
buffer += set
set
}
set += cond._1
set += cond._2
}
buffer.map(_.toSeq)
}
override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
val plan = expression.plan
plan match {
case node @ Join (_, _, _) =>
val buffer = mutable. ListBuffer [ Scan ]()
val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
if (checkAndExtract(node, buffer, joinCondBuffer)) {
// only match if the join is 3 tables join
if (buffer.size == 3 ) {
var check = true
val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
interChangeableCond.foreach { c =>
check &= c.size == 3
}
check
} else {
false
}
} else {
false
}
case _ => false
}
} Notre règle ne sera appariée que si nous correspondons à la jointure à 3 voies (le nombre de tableaux impliqués doit être 3, et la condition de jointure doit être à 3 voies, comme tbl1.field1 = tbl2.field2 = tbl3.field3 )
Par exemple,
tbl1
JOIN tbl2 ON tbl1 . field1 = tbl2 . field2
JOIN tbl3 ON tbl1 . field1 = tbl3 . field3 L'instruction de jointure ici sera "appariée" car il s'agit de jointure à 3 voies (c'est la jointure entre tbl1 , tbl2 , tbl3 , et la condition est tbl1.field1 = tbl2.field2 = tbl3.field3 )
Ensuite, est le code de transformation:
override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
val plan = expression.plan. asInstanceOf [ Join ]
val buffer = mutable. ListBuffer [ Scan ]()
val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
checkAndExtract(plan, buffer, joinCondBuffer)
val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
//
val scans = buffer.toList
implicit val ord : Ordering [ Scan ] = new Ordering [ Scan ] {
override def compare ( x : Scan , y : Scan ) : Int = {
val xStats = ctx.statsProvider.tableStats(x.table.id)
val yStats = ctx.statsProvider.tableStats(y.table.id)
xStats.estimatedTableSize.compareTo(yStats.estimatedTableSize)
}
}
def getJoinCond ( left : Scan , right : Scan ) : Seq [(ql. FieldID , ql. FieldID )] = {
val leftFields = interChangeableCond.flatMap { c =>
c.filter(p => p.table == left.table)
}
val rightFields = interChangeableCond.flatMap { c =>
c.filter(p => p.table == right.table)
}
if (leftFields.length != rightFields.length) {
throw new Exception ( s " leftFields.length( ${leftFields.length} ) != rightFields.length( ${rightFields.length} ) " )
} else {
leftFields zip rightFields
}
}
val sorted = scans.sorted
val newPlan = Join (
sorted( 0 ),
Join (
sorted( 1 ),
sorted( 2 ),
getJoinCond(sorted( 1 ), sorted( 2 ))
),
getJoinCond(sorted( 0 ), sorted( 1 ))
)
ctx.memo.getOrCreateGroupExpression(newPlan)
}Le code de transformation ici, réorganisera les tables par sa taille estimée.
Par exemple, si nous avons 3 tableaux A, B, C avec une taille estimée de 300B, 100B, 200B et une déclaration A JOIN B JOIN C B JOIN C JOIN A
Remarques: Vous remarquerez peut-être dans ce code, nous avons utilisé les statistiques de la table pour fournir un indice pour transformer le plan. En pratique, le planificateur peut utiliser toutes sortes de statistiques pour faciliter sa transformation telle que la taille du tableau, la taille des lignes, le nombre nul, l'histogramme, etc.
Visualiser notre règle, par exemple, le plan
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 6 -> Groupe # 5
Après avoir rejoint la transformation de réorganisation,
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
Expr # 8 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Expr # 8 -> Groupe # 2
Expr # 8 -> Groupe # 7
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7 ["join"]
fin
Expr # 7 -> Groupe # 1
Expr # 7 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 6 -> Groupe # 5
Style Expr # 8-AVET-largeur: 4px, trait: orange
Style Expr # 7-AVILLET-largeur: 4px, trait: orange
Linkstyle 2-AVC-largeur: 4px, trait: orange
Linkstyle 6 AVC-large: 4px, trait: orange
Linkstyle 3-AVC-Width: 4px, trait: orange
Linkstyle 7 AVC-large: 4px, trait: orange
Nous pouvons voir que tbl2 JOIN tbl1 JOIN tbl3 est créé à partir de tbl1 JOIN tbl2 JOIN tbl3 est généré par la transformation (les nœuds et les bords nouvellement ajoutés sont indiqués par les lignes orange)
Voir x3TableJoinreOrderBysize.Scala pour la mise en œuvre complète
Maintenant, nous pouvons mettre nos règles de transformation en un seul endroit
private val transformationRules : Seq [ Seq [ TransformationRule ]] = Seq (
Seq ( new ProjectionPushDown ),
Seq ( new X3TableJoinReorderBySize )
)Et les exécuter pour explorer les groupes équivalents
for (r <- transformationRules.indices) {
exploreGroup(ctx.rootGroup, transformationRules(r), r + 1 )
}Par exemple, le plan
graphique TD
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 6
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 6 -> Groupe # 5
Après avoir été exploré, aboutira à ce graphique
graphique TD
Groupe des subgraphs # 8
Expr # 8 ["Scan TBL2 (ID, Field1, Field2)"]
fin
Groupe de substanières # 11
Expr # 11 ["join"]
Expr # 14 ["join"]
fin
Expr # 11 -> Groupe # 7
Expr # 11 -> Groupe # 10
Expr # 14 -> Groupe # 8
Expr # 14 -> Groupe # 12
Groupe de substanières n ° 2
Expr # 2 ["scan tbl2"]
fin
Groupe de substanières # 5
Expr # 5 ["join"]
Expr # 16 ["join"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
Expr # 16 -> Groupe # 2
Expr # 16 -> Groupe # 13
Groupe des subgraphs # 4
Expr # 4 ["join"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe des subgraphs # 13
Expr # 15 ["join"]
fin
Expr # 15 -> Groupe # 1
Expr # 15 -> Groupe # 3
Groupe des sub-graphiques # 7
Expr # 7 ["scan tbl1 (id, champ1)"]
fin
Groupe de sous-graphe n ° 1
Expr # 1 ["scan tbl1"]
fin
Groupe des subgraphs # 10
Expr # 10 ["join"]
fin
Expr # 10 -> Groupe # 8
Expr # 10 -> Groupe # 9
Groupe de substanières # 9
Expr # 9 ["Scan Tbl3 (id, field2)"]
fin
Groupe des subgraps # 3
Expr # 3 ["scan tbl3"]
fin
Groupe des subgraphs # 12
Expr # 13 ["join"]
fin
Expr # 13 -> Groupe # 7
Expr # 13 -> Groupe # 9
Groupe des subgraphs # 6
EXPR # 12 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.id, Tbl3.Field2, Tbl3.Field2"]
Expr # 6 ["Projet Tbl1.id, Tbl1.field1, Tbl2.id, Tbl2.Field1, Tbl2.Field2, Tbl3.Id, Tbl3.Field2, Tbl3.Field2"]
fin
Expr # 12 -> Groupe # 11
Expr # 6 -> Groupe # 5
Style Expr # 12-AVILLET-largeur: 4px, trait: orange
Style Expr # 8-AVET-largeur: 4px, trait: orange
Style Expr # 10-AVET-largeur: 4px, trait: orange
Style Expr # 13-AVET-largeur: 4px, trait: orange
Style Expr # 14-AVILLET-VIE: 4px, trait: orange
Style Expr # 11 AVC-UDETH: 4px, trait: orange
Style Expr # 9 AVILLEME-VIE: 4px, trait: orange
Style Expr # 15 AVC-largeur: 4px, trait: orange
Style Expr # 7-AVILLET-largeur: 4px, trait: orange
Style Expr # 16-AVILLE-URGE: 4px, trait: orange
LinkStyle 0-AVC-largeur: 4px, trait: orange
Linkstyle 15 AVC-large: 4px, trait: orange
LinkStyle 12-AVET-largeur: 4px, trait: orange
Linkstyle 1-AVC-largeur: 4px, trait: orange
LinkStyle 16-AVILLE-AVEC: 4px, trait: orange
Linkstyle 13-AVILLE-AVEC: 4px, trait: orange
Linkstyle 2-AVC-largeur: 4px, trait: orange
Linkstyle 6 AVC-large: 4px, trait: orange
Linkstyle 3-AVC-Width: 4px, trait: orange
Linkstyle 10-AVILLE-UNE: 4px, trait: orange
Linkstyle 7 AVC-large: 4px, trait: orange
Linkstyle 14-AVET-largeur: 4px, trait: orange
Linkstyle 11-AVETH-Width: 4px, trait: orange
Voir volcanoplanner.scala pour plus de détails
Après la phase d'exploration, nous avons maintenant un arbre entièrement élargi contenant tous les plans possibles, est maintenant la phase d'optimisation.
Dans cette phase, nous trouverons le meilleur plan pour notre groupe racine. Le processus d'optimisation est décrit comme suivant:
Voici un exemple
graphique TD
Groupe de sous-graphe # 2 ["Groupe # 2 (Cost = 1)"]
Expr # 2 ["Expr # 2 (Cost = 1)"]
fin
Groupe de sous-graphe # 5 ["Groupe # 5 (Cost = 3)"]
Expr # 5 ["Expr # 5 (Cost = max (3,2) = 3"]
fin
Expr # 5 -> Groupe # 1
Expr # 5 -> Groupe # 4
SUBGRAPH GROUP # 4 ["Groupe # 4 (Cost = 2)"]
Expr # 4 ["Expr # 4 (Cost = max (1,2) = 2)"]
Expr # 7 ["Expr # 7 (Cost = 1 + 2 = 3)"]
fin
Expr # 4 -> Groupe # 2
Expr # 4 -> Groupe # 3
Groupe de sous-graphe # 1 ["Groupe # 1 (Cost = 3)"]
Expr # 1 ["Expr # 1 (Cost = 3)"]
fin
Groupe de sous-graphe # 3 ["Groupe # 3 (Cost = 2)"]
Expr # 3 ["Expr # 3 (Cost = 2)"]
fin
Groupe de sous-graphe # 6 ["Groupe # 6 (Cost = 4.5)"]
Expr # 6 ["Expr # 6 (coût = 3 * 1,5 = 4,5)"]
fin
Expr # 6 -> Groupe # 5
Groupe de sous-graphe # 8 ["Groupe # 8 (Cost = 1)"]
Expr # 8 ["Expr # 8 (Cost = 1)"]
fin
Groupe de sous-graphe # 9 ["Groupe # 9 (Cost = 2)"]
Expr # 9 ["Expr # 9 (Cost = 2)"]
fin
Expr # 7 -> Groupe # 8
Expr # 7 -> Groupe # 9
Par exemple, le coût Expr#4 est calculé par ses coûts de groupe d'enfants ( Group#2 et Group#3 ) en utilisant la fonction max . Un autre exemple est le Group#4 , son coût est calculé en calculant la valeur min entre les coûts de ses expressions équivalentes.
Étant donné que l'objectif de la phase d'optimisation est de produire le meilleur plan physique compte tenu des expressions de groupe explorées. Nous pouvons définir le plan physique comme suit:
sealed trait PhysicalPlan {
def operator () : Operator
def children () : Seq [ PhysicalPlan ]
def cost () : Cost
def estimations () : Estimations
def traits () : Set [ String ]
}
L' operator est l'opérateur physique, qui a utilisé le plan, nous le couvrirons dans la section ultérieure. Ensuite, children sont la liste des nœuds de plan pour enfants, ils sont habitués à participer au processus de calcul des coûts. Le troisième attribut est cost , cost est un objet détenant des informations sur les coûts (tels que le coût du processeur, le coût de la mémoire, le coût IO, etc.). estimations sont la propriété détenant des statistiques estimées sur le plan (telles que le nombre de lignes, la taille des lignes, etc.), il participe également au calcul des coûts. Enfin, traits sont un ensemble de traits physiques, qui affectent la règle de mise en œuvre pour affecter le processus de génération de plan physique.
Ensuite, nous pouvons implémenter les classes de nœuds physiques:
case class Scan (
operator : Operator ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq .empty // scan do not receive any child
}
case class Project (
operator : Operator ,
child : PhysicalPlan ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq (child)
}
case class Join (
operator : Operator ,
leftChild : PhysicalPlan ,
rightChild : PhysicalPlan ,
cost : Cost ,
estimations : Estimations ,
traits : Set [ String ] = Set .empty
) extends PhysicalPlan {
override def children () : Seq [ PhysicalPlan ] = Seq (leftChild, rightChild)
}
Voir PhysicalPlan.Scala pour la mise en œuvre complète
La première chose en phase d'optimisation, c'est-à-dire que nous devons mettre en œuvre les règles de mise en œuvre. La règle de mise en œuvre est la règle pour passer du plan logique en plans physiques sans les exécuter.
Étant donné que nous n'exécutons pas directement le plan physique dans le planificateur, nous retournerons donc le générateur de plan physique à la place, il est également plus facile de personnaliser la fonction de coût pour chaque nœud.
Voici l'interface de la règle d'implémentation:
trait PhysicalPlanBuilder {
def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ]
}
trait ImplementationRule {
def physicalPlanBuilders ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ]
}
Ici, le PhysicalPlanBuilder est l'interface utilisée pour construire le plan physique, compte tenu des plans physiques de l'enfant.
Par exemple, la jointure logique a 2 implémentations physiques sont de jointure de hachage et de jointure de fusion
graphique TD
Enfant # 1 ["Enfant # 1"]
Enfant # 2 ["Enfant # 2"]
Enfant # 3 ["Enfant # 3"]
Enfant # 4 ["Enfant # 4"]
hash_join ["` hachage join
Coût = F (coût (enfant # 1), coût (enfant # 2))
`"]
Merge_join ["" Merge Rejoin
Coût = g (coût (enfant # 3), coût (enfant # 4))
`"]
hash_join --> child#1
hash_join --> child#2
merge_join --> child#3
merge_join --> child#4
the HASH JOIN cost is using function f() to calculate cost, and MERGE JOIN is using function g() to calculate cost, both are using its children as function parameters. So it's easier to code if we're returning just the phyiscal plan builder from the implementation rule instead of the physical plan.
As we've said before, the optimization process is described as following:
And here is the code:
private def implementGroup ( group : Group , combinedRule : ImplementationRule )(
implicit ctx : VolcanoPlannerContext
) : GroupImplementation = {
group.implementation match {
case Some (implementation) => implementation
case None =>
var bestImplementation = Option .empty[ GroupImplementation ]
group.equivalents.foreach { equivalent =>
val physicalPlanBuilders = combinedRule.physicalPlanBuilders(equivalent)
val childPhysicalPlans = equivalent.children.map { child =>
val childImplementation = implementGroup(child, combinedRule)
child.implementation = Option (childImplementation)
childImplementation.physicalPlan
}
// calculate the implementation, and update the best cost for group
physicalPlanBuilders.flatMap(_.build(childPhysicalPlans)).foreach { physicalPlan =>
val cost = physicalPlan.cost()
bestImplementation match {
case Some (currentBest) =>
if (ctx.costModel.isBetter(currentBest.cost, cost)) {
bestImplementation = Option (
GroupImplementation (
physicalPlan = physicalPlan,
cost = cost,
selectedEquivalentExpression = equivalent
)
)
}
case None =>
bestImplementation = Option (
GroupImplementation (
physicalPlan = physicalPlan,
cost = cost,
selectedEquivalentExpression = equivalent
)
)
}
}
}
bestImplementation.get
}
}This code is an exhaustive search code, which is using recursive function to traverse all nodes. At each node (group), the function is called once to get its best plan while also calculate the optimal cost of that group.
Finally, the best plan for our query is the best plan of the root group
val implementationRules = new ImplementationRule {
override def physicalPlanBuilders (
expression : GroupExpression
)( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
expression.plan match {
case node @ Scan (_, _) => implement. Scan (node)
case node @ Project (_, _) => implement. Project (node)
case node @ Join (_, _, _) => implement. Join (node)
}
}
}
ctx.rootGroup.implementation = Option (implementGroup(ctx.rootGroup, implementationRules))See VolcanoPlanner.scala for full implementation
Here is an example of the plan after optimization, it's shown the selected logical node, the selected physical operator, and the estimated cost
graph TD
Group#6["
Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
"]
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
"]
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
"]
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
"]
Next, we will implement some implementation rules.
The first, easiest one is the implementation rule of logical PROJECT
object Project {
def apply ( node : logicalplan. Project )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
Seq (
new ProjectionImpl (node.fields)
)
}
}
class ProjectionImpl ( projection : Seq [ql. FieldID ]) extends PhysicalPlanBuilder {
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
val child = children.head
val selfCost = Cost (
estimatedCpuCost = 0 ,
estimatedMemoryCost = 0 ,
estimatedTimeCost = 0
) // assuming the cost of projection is 0
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + child.cost().estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + child.cost().estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + child.cost().estimatedTimeCost
)
val estimations = Estimations (
estimatedLoopIterations = child.estimations().estimatedLoopIterations,
estimatedRowSize = child.estimations().estimatedRowSize // just guessing the value
)
Some (
Project (
operator = ProjectOperator (projection, child.operator()),
child = child,
cost = cost,
estimations = estimations,
traits = child.traits()
)
)
}
}
The implementation rule for logical PROJECT, is returning one physical plan builder ProjectionImpl . ProjectionImpl cost calculation is simple, it just inherits the cost from the child node (because the projection is actually not doing any intensive operation). Beside that, it also updates the estimation (in this code, estimation is also inherit from the child node)
See Project.scala for full implementation
Writing implementation rule for logical JOIN is way harder than PROJECTION.
One first reason is, a logical JOIN has many physical implementation, such as HASH JOIN, MERGE JOIN, BROADCAST JOIN, etc.
The second reason is, estimating cost for physical JOIN is also hard, because it depends on lots of factors such as row count, row size, data histogram, indexes, data layout, etc.
So, to keep everything simple in this guide, I will only implement 2 physical JOIN: HASH JOIN and MERGE JOIN. The cost estimation functions are fictional (just to show how it works, I'm not trying to correct it). And in the MERGE JOIN, all data is assuming to be sorted by join key.
Here is the code:
object Join {
def apply ( node : logicalplan. Join )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
val leftFields = node.on.map(_._1).map(f => s " ${f.table.id} . ${f.id} " )
val rightFields = node.on.map(_._2).map(f => s " ${f.table.id} . ${f.id} " )
Seq (
new HashJoinImpl (leftFields, rightFields),
new MergeJoinImpl (leftFields, rightFields)
)
}
}
The HASH JOIN:
class HashJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {
private def viewSize ( plan : PhysicalPlan ) : Long = {
plan.estimations().estimatedLoopIterations * plan.estimations().estimatedRowSize
}
// noinspection ZeroIndexToHead,DuplicatedCode
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
// reorder the child nodes, the left child is the child with smaller view size (smaller than the right child if we're store all of them in memory)
val (leftChild, rightChild) = if (viewSize(children( 0 )) < viewSize(children( 1 ))) {
(children( 0 ), children( 1 ))
} else {
(children( 1 ), children( 0 ))
}
val estimatedLoopIterations = Math .max(
leftChild.estimations().estimatedLoopIterations,
rightChild.estimations().estimatedLoopIterations
) // just guessing the value
val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
val selfCost = Cost (
estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)
Some (
Join (
operator = HashJoinOperator (
leftChild.operator(),
rightChild.operator(),
leftFields,
rightFields
),
leftChild = leftChild,
rightChild = rightChild,
cost = cost,
estimations = estimations,
traits = Set .empty // don't inherit trait from children since we're hash join
)
)
}
}
We can see that the cost function of HASH JOIN is composed of its children costs and estimations
val selfCost = Cost (
estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)Next, the MERGE JOIN:
class MergeJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {
// noinspection ZeroIndexToHead,DuplicatedCode
override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
val (leftChild, rightChild) = (children( 0 ), children( 1 ))
if (leftChild.traits().contains( " SORTED " ) && rightChild.traits().contains( " SORTED " )) {
val estimatedTotalRowCount =
leftChild.estimations().estimatedLoopIterations +
rightChild.estimations().estimatedLoopIterations
val estimatedLoopIterations = Math .max(
leftChild.estimations().estimatedLoopIterations,
rightChild.estimations().estimatedLoopIterations
) // just guessing the value
val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
val selfCost = Cost (
estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
estimatedMemoryCost = 0 , // no additional memory cost
estimatedTimeCost = estimatedTotalRowCount
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)
Some (
Join (
operator = MergeJoinOperator (
leftChild.operator(),
rightChild.operator(),
leftFields,
rightFields
),
leftChild = leftChild,
rightChild = rightChild,
cost = cost,
estimations = estimations,
traits = leftChild.traits() ++ rightChild.traits()
)
)
} else {
None
}
}
}
Same with HASH JOIN, MERGE JOIN also uses its children costs and estimations to calculate its cost, but with different formulla:
val selfCost = Cost (
estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
estimatedMemoryCost = 0 , // no additional memory cost
estimatedTimeCost = estimatedTotalRowCount
)
val childCosts = Cost (
estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
estimatedTimeCost = 0
)
val estimations = Estimations (
estimatedLoopIterations = estimatedLoopIterations,
estimatedRowSize = estimatedOutRowSize
)
val cost = Cost (
estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)See HashJoinImpl.scala and MergeJoinImpl.scala for full implementation
You can see other rules and physical plan builders here:
Now, after done implementing the implementation rules, now we can find our best plan. Let's start over from the user query
SELECT tbl1 . id ,
tbl1 . field1 ,
tbl2 . id ,
tbl2 . field1 ,
tbl2 . field2 ,
tbl3 . id ,
tbl3 . field2 ,
tbl3 . field2
FROM tbl1
JOIN tbl2 ON tbl1 . id = tbl2 . id
JOIN tbl3 ON tbl2 . id = tbl3 . idwill be converted to the logical plan
graph TD
1326583549["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"];
-425111028["JOIN"];
-349388609["SCAN tbl1"];
1343755644["JOIN"];
-1043437086["SCAN tbl2"];
-1402686787["SCAN tbl3"];
1326583549 --> -425111028;
-425111028 --> -349388609;
-425111028 --> 1343755644;
1343755644 --> -1043437086;
1343755644 --> -1402686787;
After exploration phase, it will generate lots of equivalent plans
graph TD
subgraph Group#8
Expr#8["SCAN tbl2 (id, field1, field2)"]
fin
subgraph Group#11
Expr#11["JOIN"]
Expr#14["JOIN"]
fin
Expr#11 --> Group#7
Expr#11 --> Group#10
Expr#14 --> Group#8
Expr#14 --> Group#12
subgraph Group#2
Expr#2["SCAN tbl2"]
fin
subgraph Group#5
Expr#5["JOIN"]
Expr#16["JOIN"]
fin
Expr#5 --> Group#1
Expr#5 --> Group#4
Expr#16 --> Group#2
Expr#16 --> Group#13
subgraph Group#4
Expr#4["JOIN"]
fin
Expr#4 --> Group#2
Expr#4 --> Group#3
subgraph Group#13
Expr#15["JOIN"]
fin
Expr#15 --> Group#1
Expr#15 --> Group#3
subgraph Group#7
Expr#7["SCAN tbl1 (id, field1)"]
fin
subgraph Group#1
Expr#1["SCAN tbl1"]
fin
subgraph Group#10
Expr#10["JOIN"]
fin
Expr#10 --> Group#8
Expr#10 --> Group#9
subgraph Group#9
Expr#9["SCAN tbl3 (id, field2)"]
fin
subgraph Group#3
Expr#3["SCAN tbl3"]
fin
subgraph Group#12
Expr#13["JOIN"]
fin
Expr#13 --> Group#7
Expr#13 --> Group#9
subgraph Group#6
Expr#12["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
Expr#6["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
fin
Expr#12 --> Group#11
Expr#6 --> Group#5
style Expr#12 stroke-width: 4px, stroke: orange
style Expr#8 stroke-width: 4px, stroke: orange
style Expr#10 stroke-width: 4px, stroke: orange
style Expr#13 stroke-width: 4px, stroke: orange
style Expr#14 stroke-width: 4px, stroke: orange
style Expr#11 stroke-width: 4px, stroke: orange
style Expr#9 stroke-width: 4px, stroke: orange
style Expr#15 stroke-width: 4px, stroke: orange
style Expr#7 stroke-width: 4px, stroke: orange
style Expr#16 stroke-width: 4px, stroke: orange
linkStyle 0 stroke-width: 4px, stroke: orange
linkStyle 15 stroke-width: 4px, stroke: orange
linkStyle 12 stroke-width: 4px, stroke: orange
linkStyle 1 stroke-width: 4px, stroke: orange
linkStyle 16 stroke-width: 4px, stroke: orange
linkStyle 13 stroke-width: 4px, stroke: orange
linkStyle 2 stroke-width: 4px, stroke: orange
linkStyle 6 stroke-width: 4px, stroke: orange
linkStyle 3 stroke-width: 4px, stroke: orange
linkStyle 10 stroke-width: 4px, stroke: orange
linkStyle 7 stroke-width: 4px, stroke: orange
linkStyle 14 stroke-width: 4px, stroke: orange
linkStyle 11 stroke-width: 4px, stroke: orange
And the at optimization phase, a final best plan is chose
graph TD
Group#6["
Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
"]
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
"]
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
"]
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
"]
Now we've done building a functional query planner which can optimize the query from user, but our query plan could not run by itself. So it's the reason why now we will implement the query processor to test out our query plan.
Basically the query process receive input from the query planner, and execute them
graphique LR
plan(("Physical Plan"))
storage[("Storage Layer")]
processor["Query Processor"]
plan -- execute --> processor
storage -- fetch --> processor
Volcano/iterator model is the query processing model that is widely used in many DBMS. It is a pipeline architecture, which means that the data is processed in stages, with each stage passing the output of the previous stage to the next stage.
Each stage in the pipeline is represented by an operator. Operators are functions that perform a specific operation on the data, such as selecting rows, filtering rows, or aggregating rows.
Usually, operator can be formed directly from the query plan. For example, the query
SELECT field_1
FROM tbl
WHERE field = 1will have the plan
graph TD
project["PROJECT: field_1"]
scan["SCAN: tbl"]
filter["FILTER: field = 1"]
project --> scan
filter --> project
will create a chain of operators like this:
scan = {
next() // fetch next row from table "tbl"
}
project = {
next() = {
next_row = scan.next() // fetch next row from scan operator
projected = next_row["field_1"]
return projected
}
}
filter = {
next() = {
next_row = {}
do {
next_row = project.next() // fetch next row from project operator
} while (next_row["field"] != 1)
return next_row
}
}
results = []
while (row = filter.next()) {
results.append(row)
}
notes : this pseudo code did not handle for end of result stream
The basic interface of an operator is described as following:
trait Operator {
def next () : Option [ Seq [ Any ]]
}
See Operator.scala for full implementation of all operators
Let's define a query
SELECT emp . id ,
emp . code ,
dept . dept_name ,
emp_info . name ,
emp_info . origin
FROM emp
JOIN dept ON emp . id = dept . emp_id
JOIN emp_info ON dept . emp_id = emp_info . idwith some data and stats
val table1 : Datasource = Datasource (
table = " emp " ,
catalog = TableCatalog (
Seq (
" id " -> classOf [ String ],
" code " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id
),
rows = Seq (
Seq ( " 1 " , " Emp A " ),
Seq ( " 2 " , " Emp B " ),
Seq ( " 3 " , " Emp C " )
),
stats = TableStats (
estimatedRowCount = 3 ,
avgColumnSize = Map ( " id " -> 10 , " code " -> 32 )
)
)
val table2 : Datasource = Datasource (
table = " dept " ,
catalog = TableCatalog (
Seq (
" emp_id " -> classOf [ String ],
" dept_name " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by emp_id (this is just a fake trait to demonstrate how trait works)
),
rows = Seq (
Seq ( " 1 " , " Dept 1 " ),
Seq ( " 1 " , " Dept 2 " ),
Seq ( " 2 " , " Dept 3 " ),
Seq ( " 3 " , " Dept 3 " )
),
stats = TableStats (
estimatedRowCount = 4 ,
avgColumnSize = Map ( " emp_id " -> 10 , " dept_name " -> 255 )
)
)
val table3 : Datasource = Datasource (
table = " emp_info " ,
catalog = TableCatalog (
Seq (
" id " -> classOf [ String ],
" name " -> classOf [ String ],
" origin " -> classOf [ String ]
),
metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id (this is just a fake trait to demonstrate how trait works)
),
rows = Seq (
Seq ( " 1 " , " AAAAA " , " Country A " ),
Seq ( " 2 " , " BBBBB " , " Country A " ),
Seq ( " 3 " , " CCCCC " , " Country B " )
),
stats = TableStats (
estimatedRowCount = 3 ,
avgColumnSize = Map ( " id " -> 10 , " name " -> 255 , " origin " -> 255 )
)
)The cost model is optimized for CPU
val costModel : CostModel = ( currentCost : Cost , newCost : Cost ) => {
currentCost.estimatedCpuCost > newCost.estimatedCpuCost
}Now, executing the query by running this code:
val planner = new VolcanoPlanner
QueryParser .parse(query) match {
case Left (err) => throw err
case Right (parsed) =>
val operator = planner.getPlan(parsed)
val result = Utils .execute(operator)
// print result
println(result._1.mkString( " , " ))
result._2.foreach(row => println(row.mkString( " , " )))
}it will print:
emp.id,emp.code,dept.dept_name,emp_info.name,emp_info.origin
1,Emp A,Dept 1,AAAAA,Country A
1,Emp A,Dept 2,AAAAA,Country A
2,Emp B,Dept 3,BBBBB,Country A
3,Emp C,Dept 3,CCCCC,Country B
Voila, We've done building a fully functional query planner and query engine :). You can start writing one for your own, good luck
See Demo.scala for full demo code
Thanks for reading this, this guide is quite long, and not fully correct, but I've tried my best to write it as understandably as possible ?
