query planner guide скачать - query planner guide Скачать исходный код

[Заполнитель]

Введение

Планировщик запросов является компонентом системы управления базами данных (СУБД), которая отвечает за создание плана для выполнения запроса базы данных. В плане запроса указывается шаги, которые предпримет СУБД для извлечения данных, запрошенных запросом. Цель планировщика запросов - создать план, который является максимально эффективным, а это означает, что он будет возвращать данные пользователю как можно быстрее.

Планировщики запросов являются сложными частями программного обеспечения, и их может быть трудно понять. Это руководство по реализации планировщика запросов на основе затрат предоставит вам пошаговый обзор процесса, как реализовать свой собственный планировщик запросов на основе затрат, но при этом по-прежнему охватывает основные концепции планировщика запросов.

Написано ИИ, под редакцией человека

Целевая аудитория

Это руководство написано для:

кто работал с двигателями запросов
кому любопытно, хотят сделать свои собственные вещи
Кто хочет изучать биологические вещи, но ненавидит математику

Цели:

Способен понять основное планирование запросов
Способен написать свой собственный планировщик запросов

Основная архитектура двигателя запроса

 График тд
    Пользователь ((пользователь))
    Паризер [Parser Parser]
    Планировщик [планировщик запросов]
    Исполнитель [процессор запроса]
    Пользователь -текстовый запрос -> анализатор
    Паризер -AST -> Планировщик
    Планировщик -физический план -> Исполнитель

Основная архитектура двигателя запроса состоит из этих компонентов:

Проанализ запроса: используется для анализа ввода пользователя, обычно в формате текста, читаемого на человеку (например, SQL)
Планировщик запросов: используется для создания плана/стратегии для выполнения запроса. Обычно планировщик запросов выберет лучший план среди нескольких планов, созданных из одного запроса
Процессор запросов: используется для выполнения плана запроса, который выводит планировщик запросов

Типы планировщиков запросов

Обычно планировщики запросов делятся на 2 типа:

эвристический планировщик
Планировщик на основе стоимости

Эвристический планировщик-это планировщик запросов, который использовал заранее определенные правила для создания плана запросов.

Планировщик, основанный на затратах,-это планировщик запросов, который на основе стоимости генерации запроса он пытается найти оптимальный план на основе стоимости запроса ввода.

В то время как эвристический планировщик обычно находит лучший план по применению правил преобразования, если он знает, что преобразованный план лучше, планировщик, основанный на затратах, находит лучший план путем перечисленного эквивалентных планов и попытаться найти лучший план среди них.

Планировщик запросов на основе затрат

В планировщике запросов на основе затрат он обычно состоит из этапов:

План перечисления
Оптимизация запроса

На этапе перечисления плана планировщик будет перечислять возможные эквивалентные планы.

После этого, на этапе оптимизации запросов, планировщик будет искать лучший план из списка перечисленных планов. Лучший план - это план, имеющий самую низкую стоимость, которую определяется модель затрат (или функция затрат).

Потому что естественным логическим планом является наличие деревьев, так что вы можете подумать, что оптимизация/поиск на самом деле является проблемой поиска деревьев. И здесь есть много алгоритмов поиска деревьев:

Исчерпывающий поиск, такой как детерминированное динамическое программирование. Алгоритм будет выполнять поиск лучшего плана до условий завершения поиска
Рандомизированный поиск, такой как рандомизированный поиск дерева. Алгоритм будет выполнять поиск лучшего плана до условий завершения поиска

Примечания: Теоретически можно использовать любой вид алгоритма поиска деревьев. Однако на практике это невозможно, поскольку время поиска увеличивается, когда наш алгоритм поиска является сложным

Примечания: Условия завершения поиска обычно:

Ищите истощение (когда больше не планирует посещать)
Порог затрат (при обнаружении плана, что стоимость ниже, чем определенный порог затрат)
время (когда этап поиска работает слишком долго)

Планировщик запросов вулкана

Планировщик запросов вулканов (или генератор оптимизатора вулкана)-это планировщик запросов на основе затрат

Планировщик Volcano использует динамический подход программирования, чтобы найти лучший план запросов из списка перечисленных планов.

Подробная информация: https://ieeexplore.ieee.org/document/344061 (мне лень объяснять бумагу здесь)

Вот отличное объяснение: https://15721.courses.cs.cmu.edu/spring2017/slides/15-optimizer2.pdf#page=9

Создание нашего планировщика запросов на основе затрат

Наш планировщик запросов - это планировщик запросов, основанный на затратах, следуя основной идее планировщика запроса вулкана, наш планировщик будет состоять из 2 основных этапов:

Фаза исследования/поиска
Фаза реализации/оптимизации

 График LR
    ast ((ast))
    logical_plan [план]
    exproded_plans ["`
        План № 1
        ...
        План #N
    `"]
    реализация_план ["План #x (лучший план)"]
    AST -преобразовать в логический план -> logical_plan
    logical_plan -фаза исследования -> exproded_plans
    exproded_plans -фаза оптимизации -> реализация_план
    Linkstyle 1,2 Цвет: оранжевый, ход: оранжевый, ширина хода: 5px

Глоссарий

Логический план

Логический план - это DataStructure, удерживая абстракцию шага преобразования, необходимая для выполнения запроса.

Вот пример логического плана:

 График тд
    1 ["Project TBL1.id, TBL1.Field1, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"];
    2 ["Join"];
    3 ["сканировать TBL1"];
    4 ["Join"];
    5 ["сканировать TBL2"];
    6 ["Сканировать TBL3"];
    1 -> 2;
    2 -> 3;
    2 -> 4;
    4 -> 5;
    4 -> 6;

Физический план

Хотя логический план содержит только абстракцию, физический план - это Datastructure, содержащая детали реализации. Каждый логический план будет иметь несколько физических планов. Например, логическое соединение может иметь много физических планов, таких как хэш -присоединение, объединение, трансляция и т. Д.

Эквивалентная группа

Эквивалентная группа - это группа эквивалентных выражений (которые для каждого выражения их логический план логически эквивалентен)

например

 График тд
    Группа подграфа № 8
        Expr#8 ["Scan TBL2 (Field1, Field2, Id)"]
    конец
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 11
        Expr#11 ["Join"]
    конец
    Экспр#11 -> Группа № 7
    Экспр#11 -> Группа № 10
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфа группа № 7
        Expr#7 ["Сканировать TBL1 (ID, Field1)"]
    конец
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 10
        Expr#10 ["Join"]
    конец
    Экспр#10 -> Группа № 8
    Экспр#10 -> Группа № 9
    Подграфа группа № 9
        Expr#9 ["Сканировать tbl3 (id, field2)"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#12 ["Проект TBL1.id, TBL1.Field1, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"]
        Expr#6 ["Проект TBL1.id, TBL1.Field1, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"]
    конец
    Expr#12 -> Группа № 11
    Expr#6 -> Группа № 5

Здесь мы видим, что Group#6 имеет 2 эквивалентных выражения, которые представляют один и тот же запрос (один делает сканирование из таблицы, затем проект, один спускает проекцию вниз к узлу сканирования).

Правило трансформации

Правило преобразования - это правило преобразования из одного логического плана в другой логический эквивалентный логический план

Например, план:

 График тд
    1 ["Project TBL1.id, TBL1.Field1, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"];
    2 ["Join"];
    3 ["сканировать TBL1"];
    4 ["Join"];
    5 ["сканировать TBL2"];
    6 ["Сканировать TBL3"];
    1 -> 2;
    2 -> 3;
    2 -> 4;
    4 -> 5;
    4 -> 6;

При применении проекционного преобразования отжимания преобразуется в:

 График тд
    1 ["Проект *. *"];
    2 ["Join"];
    3 ["сканировать tbl1 (id, field1)"];
    4 ["Join"];
    5 ["Сканировать TBL2 (Field1, Field2)"];
    6 ["Сканировать tbl3 (id, field2, field2)"];
    1 -> 2;
    2 -> 3;
    2 -> 4;
    4 -> 5;
    4 -> 6;

Правило преобразования может влиять логическими признаками/свойствами, такими как схема таблицы, статистика данных и т. Д.

Правило реализации

Правило реализации - это правило, чтобы вернуть физические планы с учетом логического плана.

Правило реализации может влиять на физические признаки/свойства, такие как макет данных (отсортированный или нет) и т. Д.

Фаза исследования

На этапе разведки планировщик будет применять правила преобразования, генерируя эквивалентные логические планы

Например, план:

 График тд
    1326583549 ["Project TBL1.id, TBL1.Field1, TBL2.id, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"];
    -425111028 ["join"];
    -349388609 ["сканировать TBL1"];
    1343755644 ["join"];
    -1043437086 ["сканировать TBL2"];
    -1402686787 ["сканировать TBL3"];
    1326583549 -> -425111028;
    -425111028 -> -349388609;
    -425111028 -> 1343755644;
    1343755644 -> -1043437086;
    1343755644 -> -1402686787;

После применения правил преобразования, что приведет к следующему графику:

 График тд
    Группа подграфа № 8
        Expr#8 ["Scan TBL2 (ID, Field1, Field2)"]
    конец
    Группа подграфа № 11
        Expr#11 ["Join"]
        Expr#14 ["Join"]
    конец
    Экспр#11 -> Группа № 7
    Экспр#11 -> Группа № 10
    Expr#14 -> Группа № 8
    Expr#14 -> Группа № 12
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
        Expr#16 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Expr#16 -> Группа № 2
    Expr#16 -> Группа № 13
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Группа подграфа № 13
        Expr#15 ["Join"]
    конец
    Expr#15 -> Группа № 1
    Expr#15 -> Группа № 3
    Подграфа группа № 7
        Expr#7 ["Сканировать TBL1 (ID, Field1)"]
    конец
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 10
        Expr#10 ["Join"]
    конец
    Экспр#10 -> Группа № 8
    Экспр#10 -> Группа № 9
    Подграфа группа № 9
        Expr#9 ["Сканировать tbl3 (id, field2)"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 12
        Expr#13 ["Join"]
    конец
    Expr#13 -> Группа № 7
    Expr#13 -> Группа № 9
    Группа подграфа № 6
        Expr#12 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#12 -> Группа № 11
    Expr#6 -> Группа № 5

Здесь мы видим, что применяется правило отжимания проекции и правило переупорядочения присоединения.

Фаза оптимизации

Фаза оптимизации состоит в том, чтобы пересечь расширенное дерево на этапе разведки, чтобы найти лучший план для нашего запроса.

Это «на самом деле» - это оптимизация поиска деревьев, поэтому вы можете использовать любой алгоритм поиска дерева, который вы можете себе представить (но вы должны убедиться, что это правильно).

Вот пример сгенерированного физического плана после фазы оптимизации:

 График тд
    Группа № 6 ["
    Группа № 6
Выбранный: Project TBL1.id, TBL1.Field1, TBL2.id, TBL2.Field1, TBL2.Field2, TBL3
Оператор: Projectoperator
Стоимость: стоимость (процессор = 641400,00, MEM = 1020400012,00, время = 1000000,00)
"]
Группа № 6 -> Группа № 11
Группа № 11 ["
Группа № 11
Выбран: присоединиться
Оператор: Hashjoinoperator
Стоимость: стоимость (процессор = 641400,00, MEM = 1020400012,00, время = 1000000,00)
"]
Группа № 11 -> Группа № 7
Группа № 11 -> Группа № 10
Группа № 7 ["
Группа № 7
Выбрано: сканировать TBL1 (ID, Field1)
Оператор: Normalscanoperator
Стоимость: стоимость (процессор = 400,00, mem = 400000,00, время = 1000,00)
"]
Группа № 10 ["
Группа № 10
Выбран: присоединиться
Оператор: Mergejoinoperator
Черты: отсортировано
Стоимость: стоимость (процессор = 640000,00, MEM = 20000012,00, время = 1100000,00)
"]
Группа № 10 -> Группа № 8
Группа № 10 -> Группа № 9
Группа № 8 ["
Группа № 8
Выбрано: сканирование TBL2 (ID, Field1, Field2)
Оператор: Normalscanoperator
Черты: отсортировано
Стоимость: стоимость (процессор = 600000,00, mem = 12,00, время = 1000000,00)
"]
Группа № 9 ["
Группа № 9
Выбрано: сканировать TBL3 (ID, Field2)
Оператор: Normalscanoperator
Черты: отсортировано
Стоимость: стоимость (процессор = 40000,00, MEM = 20000000,00, время = 100000,00)
"]

Сгенерированный план показал выбранный логический план, расчетную стоимость и физический оператор

Оптимизировать/Поиск завершения

Наш планировщик выполнит поиск истощения, чтобы найти лучший план

Погружение в коды

Поскольку код планировщика большой, поэтому я не буду писать пошаговое руководство, но вместо этого я объясню каждый кусок кода

Язык запросов

Здесь мы определим язык запросов, который тщательно использовал этот учебник

 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 . id

Язык запросов, который мы будем реализовать, является SQL-подобным языком. Однако для простоты мы ограничим его функциональность и синтаксис.

Язык появляется в форме

 SELECT tbl . field , [...]
FROM tbl JOIN [...]

Он будет поддерживать только для SELECT and JOIN , а также поле в SELECT, должно быть полностью квалифицировано (в форме table.field ), все другие функции не будут поддерживаться

Аст

Во -первых, мы должны определить AST для нашего языка. AST (или Abstract Syntax Tree) - это дерево, используемое для представления синтаксической структуры текста.

Поскольку наш язык настолько прост, мы просто можем определить структуру AST в нескольких строках кодов:

 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

Например, запрос

 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 . id

может быть представлен как

 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 " )
    )
  )
)

Простой анализатор запроса

После определения структуры AST нам придется написать анализатор запроса, который используется для преобразования текстового запроса в форму AST.

Поскольку это руководство использует SCALA для реализации, мы выберем CALA-Parser-комбинтеры для создания нашего анализатора запроса.

Запрос класса анализатора:

 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
}

Затем определите некоторые правила анализа:

 // 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)
  }
}

Вот два правила, которые используются для анализа идентификаторов: TableID и FieldID .

Идентификатор таблицы (или имя таблицы) обычно содержит только символы, числа и подчеркивание ( _ ), поэтому мы будем использовать простой режиссер [a-zA-Z0-9_]+ для идентификации имени таблицы.

С другой стороны, идентификатор поля (для квалификатора на поле) на нашем языке полностью квалифицированное поле. Обычно это в форме table.field , и имя поля также обычно содержит только символы, числа и подчеркивание, поэтому мы будем использовать Regex [a-zA-Z0-9_]+.[a-zA-Z0-9_]+ для анализации имени поля.

После определения правил анализа идентификаторов теперь мы можем определить правила для анализа заявления запроса:

 // statement
private def table : Parser [ Table ] = tableId ^^ (t => Table (t))
private def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "

Правило table - это простое правило, оно просто создает узел Table , используя проанализированную TableID из правила tableId .

subQuery -это правило, чтобы проанализировать подрезы. В SQL мы можем написать запрос, который выглядел так:

 SELECT a
FROM ( SELECT b FROM c) d

SELECT b FROM c -это подпрограмма в вышеуказанном операторе. Здесь, на нашем простом языке запросов, мы укажем, что утверждение является подзайдарием, если оно прилагается парой скобок ( () ). Поскольку у нашего языка есть только выбранное утверждение, мы можем написать правило Parse как следующее:

 def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "

Теперь мы определим правила Parse для выбора оператора:

 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)
  }

В SQL мы можем использовать подзаголовок в качестве источника соединения. Например:

 SELECT * . *
FROM tbl1
    JOIN ( SELECT * . * FROM tbl2)
    JOIN tbl3

Таким образом, наш анализатор также будет реализовать правила, чтобы анализировать подрезы в части Заявления, поэтому у нас есть правило Parse:

 " SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep( " JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)

См. Queryparser.scala для полной реализации

Тестирование нашего анализатора запроса

См. Queryparserspec.scala

Логический план

После генерации AST из текстового запроса мы можем напрямую преобразовать его в логический план

Во -первых, давайте определим интерфейс для нашего логического плана:

 sealed trait LogicalPlan {
  def children () : Seq [ LogicalPlan ]
}

children - это список детского логического плана. Например:

 График тд
    1326583549 ["Project TBL1.id, TBL1.Field1, TBL2.id, TBL2.Field1, TBL2.Field2, TBL3.ID, TBL3.Field2, TBL3.Field2"];
    -425111028 ["join"];
    -349388609 ["сканировать TBL1"];
    1343755644 ["join"];
    -1043437086 ["сканировать TBL2"];
    -1402686787 ["сканировать TBL3"];
    1326583549 -> -425111028;
    -425111028 -> -349388609;
    -425111028 -> 1343755644;
    1343755644 -> -1043437086;
    1343755644 -> -1402686787;

Дочерние узлы узла PROJECT являются первым узлом JOIN . Первый узел JOIN имеет 2 ребенка, которые являются вторым узлом JOIN и узлом SCAN tbl1 . Скоро, ...

Поскольку наш язык запроса прост, нам нужно только 3 типа логического узла:

Проект: представляют проекционный оператор в отношении алгебры
Присоединение: представляйте логическое соединение
Сканирование: представляют сканирование таблицы

 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)
}

Затем мы можем написать функцию, чтобы преобразовать AST в логический план:

 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))
  }
}

См. LogicalPlan.Scala для полной реализации

Эквивалентные группы

Группа

Мы можем определить классы для группы как следующие:

 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 - это набор планов, которые логически эквивалентны.

Каждое GroupExpression представляет собой логический узел плана. Поскольку мы определили, что узел логического плана будет иметь список детских узлов (в предыдущем разделе), а GroupExpression представляет собой логический узел плана, а Group представляет собой набор эквивалентных планов, поэтому дети GroupExpression - это список Group

например

 График тд
    Группа подграфа № 8
        Экспр#8
    конец
    Группа подграфа № 2
        Экспр#2
    конец
    Группа подграфа № 11
        Экспр#11
    конец
    Экспр#11 -> Группа № 7
    Экспр#11 -> Группа № 10
    Группа подграфа № 5
        Экспр#5
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Экспр#4
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфа группа № 7
        Экспр#7
    конец
    Подграфой Группа № 1
        Экспр#1
    конец
    Группа подграфа № 10
        Экспр#10
    конец
    Экспр#10 -> Группа № 8
    Экспр#10 -> Группа № 9
    Подграфа группа № 9
        Экспр#9
    конец
    Группа подграфа № 3
        Экспр#3
    конец
    Группа подграфа № 6
        Экспр#12
        Экспр#6
    конец
    Expr#12 -> Группа № 11
    Expr#6 -> Группа № 5

Как мы видим здесь, Group#6 имеет 2 эквивалентных выражения: Expr#12 и Expr#6 , а дети Expr#12 - Group#11

Примечания: Мы будем реализовать многочисленное круглое преобразование на этапе разведки, поэтому для каждой Group и GroupExpression у нас есть индикация ExplorationMark статуса исследования.

 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 -это просто класс Bitset Wrapper, он будет отмечать i-th как 1, если I-Th Round исследуются, отметьте как 0 в противном случае.

ExplorationMark также можно использовать для визуализации точного преобразования, см. Визуализацию для более подробной информации

Меморандум

Памятка - это группа помощников, которые помогают построить эквивалентные группы. Памятка состоит из нескольких HashMap для кэширования выражения группы и группы, также предоставляя методы для регистрации новой группы или группы.

 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
  }
}

Смотрите Memo.Scala для полной реализации

Инициализация

Первым шагом внутри планировщика является инициализация

 График LR
    запрос ((запрос))
    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

Во -первых, запрос будет проанализирован в AST. Затем преобразован в логический план, называемый root plan , затем инициализируйте группу из root plan , называемого 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))
}

См. Volcanoplanner.scala для более подробной информации

Например, запрос:

 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 . id

После инициализации группы будут выглядеть так:

 График тд
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#6 -> Группа № 5

Здесь вы можете видеть это, у каждой группы есть ровно одно эквивалентное выражение

Фаза исследования

После инициализации в настоящее время фаза разведки, которая изучит все возможные эквивалентные планы.

Метод исследования довольно прост:

Для каждой группы примените правила преобразования, чтобы найти все эквивалентные выражения группы и добавить в эквивалентный набор, пока мы не сможем найти какой -либо новый эквивалентный план
Для выражения каждой группы исследуйте все детские группы

Правило трансформации

Прежде чем погрузиться в код разведки, давайте сначала поговорим о правиле преобразования.

Правило преобразования - это правило, используемое для преобразования логического плана в другой эквивалентный логический план, если оно соответствует условию правила.

Вот интерфейс правила преобразования:

 trait TransformationRule {
  def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean

  def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression
}

Поскольку логический план-это деревоподобная Datastructure, поэтому реализация match правил преобразования сопоставлена на дереве.

Например, вот match , которое используется для соответствия узлу проекта, а также проверяйте, есть ли потомки, содержащие соединение и только сканирование:

 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
  }
}

Этот план «сопоставлен»:

 График тд
    Группа подграфа № 2
        Expr#2 ["сканирование"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["сканирование"]
    конец
    Группа подграфа № 3
        Expr#3 ["сканирование"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект"]
    конец
    Expr#6 -> Группа № 5

Пока этот план не:

 График тд
    Группа подграфа № 2
        Expr#2 ["сканирование"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 3
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Scan"]
    конец
    Подграфа группа № 7
        Expr#7 ["Проект"]
    конец
    Expr#7 -> Группа № 6
    Подграфой Группа № 1
        Expr#1 ["сканирование"]
    конец
    Группа подграфа № 3
        Expr#3 ["Проект"]
    конец
    Expr#3 -> Группа № 2
    Группа подграфа № 6
        Expr#6 ["Join"]
    конец
    Экспр#6 -> Группа № 1
    Expr#6 -> Группа № 5

План перечисления

Как мы уже говорили, метод исследования:

Для каждой группы примените правила преобразования, чтобы найти все эквивалентные выражения группы и добавить в эквивалентный набор, пока мы не сможем найти какой -либо новый эквивалентный план
Для выражения каждой группы исследуйте все детские группы

И вот код разведки (довольно простой, да):

 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)
      }
    }
  }
}

См. Volcanoplanner.scala для более подробной информации

Реализуйте некоторые правила преобразования

Теперь пришло время внедрить некоторые правила преобразования

Проекционное отжимание

Проекционное отключение - это простое правило преобразования, используемое для продвижения проекции вниз до уровня хранения.

Например, запрос

 SELECT field1, field2
from tbl

имеет план

 График LR
    Проект [Project Field1, Field2]
    Сканировать [сканировать TBL]
    Проект -> сканирование

С помощью этого плана при выполнении ряды от уровня хранения (под сканированием) будут полностью извлечены, а затем ненужные поля будут отброшены (проект). Ненужные данные все еще должны перейти от узла сканирования к узлу проекта, поэтому здесь есть некоторые потраченные впустую усилия.

Мы можем сделать это лучше, просто просто сообщите слою хранения только необходимые поля. Теперь план будет преобразован в:

 График LR
    Проект [Project Field1, Field2]
    Сканирование ["Сканирование TBL (Field1, Field2)"]
    Проект -> сканирование

Давайте перейдем к коду:

 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
  }
}

Наше правило отжимания проекции здесь будет соответствовать плану, когда это узел проекта, и все его потомки сканируют и присоединяются только к узлу.

Примечания: На самом деле совпадение с отжиманием в реальном проекции более сложное, но ради простоты правило совпадения здесь - это просто узел проекта с сканированием и присоединением к потомкам

А вот код преобразования:

 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 " )
  }
}

Код преобразования сначала найдет все прогнозы из узла корневого проекта, а затем подтолкнут их ко всем узлам сканирования под ним.

Визуализация нашего правила, например, план

 График тд
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#6 -> Группа № 5

После применения проекции преобразования отжимания приведет к тому, что новый эквивалентный план с прогнозами выдвигается до операций сканирования (новый план - дерево с оранжевыми пограничными узлами).

 График тд
    Группа подграфа № 8
        Expr#8 ["Scan TBL2 (ID, Field1, Field2)"]
    конец
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 11
        Expr#11 ["Join"]
    конец
    Экспр#11 -> Группа № 7
    Экспр#11 -> Группа № 10
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфа группа № 7
        Expr#7 ["Сканировать TBL1 (ID, Field1)"]
    конец
    Группа подграфа № 10
        Expr#10 ["Join"]
    конец
    Экспр#10 -> Группа № 8
    Экспр#10 -> Группа № 9
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Подграфа группа № 9
        Expr#9 ["Сканировать tbl3 (id, field2)"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#12 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#12 -> Группа № 11
    Expr#6 -> Группа № 5
    стиль expr#12-й удар: 4px, ход: оранжевый
    стиль expr#8 ширина хода: 4px, ход: оранжевый
    стиль expr#10 ширина хода: 4px, ход: оранжевый
    стиль expr#9 ширина хода: 4px, ход: оранжевый
    стиль expr#11-й удар: 4px, ход: оранжевый
    стиль expr#7 ширина хода: 4px, ход: оранжевый
    LinkStyle 0 школьная ширина: 4px, ход: оранжевый
    Linkstyle 1-й удар: 4px, ход: оранжевый
    Linkstyle 6 штриховой ширины: 4px, ход: оранжевый
    Linkstyle 7-й удар: 4px, ход: оранжевый
    LinkStyle 8-й удар: 4PX, ход: оранжевый

См. ProtectionPushdown.scala для полной реализации

Присоединяйтесь к повторному заказу

Join Reorder также является одной из самых признанных трансформаций в мире планировщика запросов. Наш планировщик также будет реализовать правило трансформации повторного порядка.

Поскольку присоединение к повторному порядок в реальном мире не является легкой статьей для реализации. Таким образом, мы будем реализовать простую, разгроможденную версию правила join reorder здесь.

Во -первых, match правила:

 // 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
  }
}

Наше правило будет сопоставлено только в том случае, если мы сопоставляем трехстороннее соединение (количество задействованной таблицы должно быть 3, а условие соединения должно быть трехсторонним, например tbl1.field1 = tbl2.field2 = tbl3.field3 )

Например,

tbl1
    JOIN tbl2 ON tbl1 . field1 = tbl2 . field2
    JOIN tbl3 ON tbl1 . field1 = tbl3 . field3

Заявление об соединении здесь будет «сопоставлено» с момента его трехстороннего соединения (это соединение между tbl1 , tbl2 , tbl3 , а условием является tbl1.field1 = tbl2.field2 = tbl3.field3 )

Далее, это код преобразования:

 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)
}

Код преобразования здесь переупорядочивает таблицы по его предполагаемому размеру.

Например, если у нас есть 3 таблицы a, b, c с расчетным размером 300b, 100b, 200b и оператором соединения A JOIN B JOIN C , тогда он будет преобразован в B JOIN C JOIN A

Примечания: Вы можете заметить в этом коде, мы использовали статистику таблицы, чтобы дать намек на преобразование плана. На практике планировщик может использовать всевозможные статистики, чтобы помочь ее преобразованиям, таким как размер таблицы, размер строки, количество нулевых, гистограмма и т. Д.

Визуализация нашего правила, например, план

 График тд
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#6 -> Группа № 5

После того, как присоединяется трансформация повторного порядка, что привело к

 График тд
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
        Expr#8 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Expr#8 -> Группа № 2
    Expr#8 -> Группа № 7
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфа группа № 7
        Expr#7 ["Join"]
    конец
    Expr#7 -> Группа № 1
    Expr#7 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#6 -> Группа № 5
    стиль expr#8 ширина хода: 4px, ход: оранжевый
    стиль expr#7 ширина хода: 4px, ход: оранжевый
    Linkstyle 2-й удар: 4px, ход: оранжевый
    Linkstyle 6 штриховой ширины: 4px, ход: оранжевый
    Linkstyle 3-й удар: 4px, ход: оранжевый
    Linkstyle 7-й удар: 4px, ход: оранжевый

Мы видим, что tbl2 JOIN tbl1 JOIN tbl3 создано из tbl1 JOIN tbl2 JOIN tbl3 генерируется преобразованием (вновь добавленные узлы и края обозначены оранжевыми линиями)

См. X3tablejoinreorderbysize.scala для полной реализации

Собрать все преобразования вместе

Теперь мы можем поставить наши правила трансформации в одном месте

 private val transformationRules : Seq [ Seq [ TransformationRule ]] = Seq (
  Seq ( new ProjectionPushDown ),
  Seq ( new X3TableJoinReorderBySize )
)

И запустите их, чтобы исследовать эквивалентные группы

 for (r <- transformationRules.indices) {
  exploreGroup(ctx.rootGroup, transformationRules(r), r + 1 )
}

Например, план

 График тд
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 6
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#6 -> Группа № 5

После изучения, приведет к этому графику

 График тд
    Группа подграфа № 8
        Expr#8 ["Scan TBL2 (ID, Field1, Field2)"]
    конец
    Группа подграфа № 11
        Expr#11 ["Join"]
        Expr#14 ["Join"]
    конец
    Экспр#11 -> Группа № 7
    Экспр#11 -> Группа № 10
    Expr#14 -> Группа № 8
    Expr#14 -> Группа № 12
    Группа подграфа № 2
        Expr#2 ["Сканировать TBL2"]
    конец
    Группа подграфа № 5
        Expr#5 ["Join"]
        Expr#16 ["Join"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Expr#16 -> Группа № 2
    Expr#16 -> Группа № 13
    Группа подграфа № 4
        Expr#4 ["Join"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Группа подграфа № 13
        Expr#15 ["Join"]
    конец
    Expr#15 -> Группа № 1
    Expr#15 -> Группа № 3
    Подграфа группа № 7
        Expr#7 ["Сканировать TBL1 (ID, Field1)"]
    конец
    Подграфой Группа № 1
        Expr#1 ["Сканировать TBL1"]
    конец
    Группа подграфа № 10
        Expr#10 ["Join"]
    конец
    Экспр#10 -> Группа № 8
    Экспр#10 -> Группа № 9
    Подграфа группа № 9
        Expr#9 ["Сканировать tbl3 (id, field2)"]
    конец
    Группа подграфа № 3
        Expr#3 ["Scan TBL3"]
    конец
    Группа подграфа № 12
        Expr#13 ["Join"]
    конец
    Expr#13 -> Группа № 7
    Expr#13 -> Группа № 9
    Группа подграфа № 6
        Expr#12 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
        Expr#6 ["Проект tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    конец
    Expr#12 -> Группа № 11
    Expr#6 -> Группа № 5
    стиль expr#12-й удар: 4px, ход: оранжевый
    стиль expr#8 ширина хода: 4px, ход: оранжевый
    стиль expr#10 ширина хода: 4px, ход: оранжевый
    стиль expr#13-weadth: 4px, ход: оранжевый
    стиль expr#14-й удар: 4px, ход: оранжевый
    стиль expr#11-й удар: 4px, ход: оранжевый
    стиль expr#9 ширина хода: 4px, ход: оранжевый
    стиль expr#15 ширина хода: 4px, ход: оранжевый
    стиль expr#7 ширина хода: 4px, ход: оранжевый
    стиль expr#16-й удар: 4px, ход: оранжевый
    LinkStyle 0 школьная ширина: 4px, ход: оранжевый
    LinkStyle 15-й удар: 4PX, ход: оранжевый
    Linkstyle 12 штриховой ширины: 4px, ход: оранжевый
    Linkstyle 1-й удар: 4px, ход: оранжевый
    Linkstyle 16 штриховой ширины: 4px, ход: оранжевый
    LinkStyle 13 штриховой ширины: 4PX, ход: оранжевый
    Linkstyle 2-й удар: 4px, ход: оранжевый
    Linkstyle 6 штриховой ширины: 4px, ход: оранжевый
    Linkstyle 3-й удар: 4px, ход: оранжевый
    Linkstyle 10 штриховой ширину: 4px, ход: оранжевый
    Linkstyle 7-й удар: 4px, ход: оранжевый
    LinkStyle 14-й удар: 4PX, ход: оранжевый
    LinkStyle 11-й удар: 4PX, ход: оранжевый

См. Volcanoplanner.scala для более подробной информации

Фаза оптимизации

После фазы разведки у нас теперь есть полностью расширенное дерево, содержащее все возможные планы, теперь это этап оптимизации.

На этом этапе мы найдем лучший план для нашей корневой группы. Процесс оптимизации описывается следующим образом:

Для каждой группы мы найдем наилучшую реализацию, выбрав группу, выражающую с самой низкой стоимостью
Для каждой группы выражение, сначала мы перечисляем физические реализации из логического плана. Затем для каждой физической реализации мы рассчитаем ее стоимость, используя его затраты на детскую группу.

Вот пример

 График тд
    Группа подграфов № 2 ["Группа № 2 (стоимость = 1)"]
        Expr#2 ["expr#2 (stop = 1)"]
    конец
    Группа подграфов № 5 ["Группа № 5 (стоимость = 3)"]
        Expr#5 ["expr#5 (stop = max (3,2) = 3"]
    конец
    Expr#5 -> Группа № 1
    Expr#5 -> Группа № 4
    Группа подграфов № 4 ["Группа № 4 (стоимость = 2)"]
        Expr#4 ["expr#4 (stop = max (1,2) = 2)"]
        Expr#7 ["expr#7 (stop = 1+2 = 3)"]
    конец
    Expr#4 -> Группа № 2
    Expr#4 -> Группа № 3
    Группа подграфов № 1 ["Группа № 1 (стоимость = 3)"]
        Expr#1 ["expr#1 (stost = 3)"]
    конец
    Группа подграфов № 3 ["Группа № 3 (стоимость = 2)"]
        Expr#3 ["expr#3 (stop = 2)"]
    конец
    Группа подграфов № 6 ["Группа № 6 (стоимость = 4,5)"]
        Expr#6 ["expr#6 (стоимость = 3*1,5 = 4,5)"]
    конец
    Expr#6 -> Группа № 5
    Группа подграфов № 8 ["Группа № 8 (стоимость = 1)"]
        Expr#8 ["expr#8 (stop = 1)"]
    конец
    Группа подграфов № 9 ["Группа № 9 (Стеной = 2)"]
        Expr#9 ["expr#9 (stop = 2)"]
    конец
    Expr#7 -> Группа № 8
    Expr#7 -> Группа № 9

Например, стоимость Expr#4 рассчитывается по затратам на детскую группу ( Group#2 и Group#3 ) с использованием функции max . Другим примером является Group#4 , ее стоимость рассчитывается путем расчета значения MIN между затратами на ее эквивалентные выражения.

Физический план

Поскольку цель фазы оптимизации состоит в том, чтобы создать лучший физический план, учитывая исследуемые выражения группы. Мы можем определить физический план как следующее:

 sealed trait PhysicalPlan {
  def operator () : Operator

  def children () : Seq [ PhysicalPlan ]

  def cost () : Cost

  def estimations () : Estimations

  def traits () : Set [ String ]
}

operator - это физический оператор, который использовал для выполнения плана, мы рассмотрим его в последующем разделе. Тогда children - это список узлов детского плана, они привыкли участвовать в процессе расчета затрат. Третий атрибут - это cost , cost - это информация о хранении объекта (например, стоимость процессора, стоимость памяти, стоимость ввода и т. Д.). estimations - это оценочная статистика о плане (например, количество строк, размер строки и т. Д.), Он также участвует в расчете затрат. Наконец, traits - это набор физических признаков, которые влияют на правило реализации, чтобы повлиять на процесс генерации физического плана.

Далее мы можем реализовать классы физических узлов:

 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)
}

См. PhysysPlan.Scala для полной реализации

Правило реализации

Первое, что на этапе оптимизации, то есть мы должны внедрить правила реализации. Правило реализации - это правило для преобразования из логического плана в физические планы без их выполнения.

Поскольку мы не выполняем физический план в планировщике, поэтому мы вернем строитель физического плана, также легче настроить функцию стоимости для каждого узла.

Вот интерфейс правила реализации:

 trait PhysicalPlanBuilder {
  def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ]
}

trait ImplementationRule {
  def physicalPlanBuilders ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ]
}

Здесь PhysicalPlanBuilder - это интерфейс, используемый для строительства физического плана, учитывая физические планы ребенка.

Например, логическое соединение имеет 2 физических реализации - это хэш -соединение и объединение

 График тд
    Ребенок №1 ["Ребенок № 1"]
    Ребенок №2 ["Ребенок № 2"]
    Ребенок № 3 ["Ребенок № 3"]
    Ребенок № 4 ["Ребенок № 4"]
    hash_join ["` jash gin 
    стоимость = f (стоимость (ребенок № 1), стоимость (ребенок № 2))
    `"]
    merge_join ["` merge join
    cost=g(cost(child#3),cost(child#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.

Finding the best plan

As we've said before, the optimization process is described as following:

For each group, we will find the best implementation by choosing the group expressing with the lowest cost
For each group expression, first we will enumerate the physical implementations from the logical plan. Then for each physical implementation, we will calculate its cost using its child group costs.

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)
"]

Implement the implementation rules

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:

осуществлять
строитель

Putting all pieces together

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 . id

will 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)"]
    конец
    subgraph Group#11
        Expr#11["JOIN"]
        Expr#14["JOIN"]
    конец
    Expr#11 --> Group#7
    Expr#11 --> Group#10
    Expr#14 --> Group#8
    Expr#14 --> Group#12
    subgraph Group#2
        Expr#2["SCAN tbl2"]
    конец
    subgraph Group#5
        Expr#5["JOIN"]
        Expr#16["JOIN"]
    конец
    Expr#5 --> Group#1
    Expr#5 --> Group#4
    Expr#16 --> Group#2
    Expr#16 --> Group#13
    subgraph Group#4
        Expr#4["JOIN"]
    конец
    Expr#4 --> Group#2
    Expr#4 --> Group#3
    subgraph Group#13
        Expr#15["JOIN"]
    конец
    Expr#15 --> Group#1
    Expr#15 --> Group#3
    subgraph Group#7
        Expr#7["SCAN tbl1 (id, field1)"]
    конец
    subgraph Group#1
        Expr#1["SCAN tbl1"]
    конец
    subgraph Group#10
        Expr#10["JOIN"]
    конец
    Expr#10 --> Group#8
    Expr#10 --> Group#9
    subgraph Group#9
        Expr#9["SCAN tbl3 (id, field2)"]
    конец
    subgraph Group#3
        Expr#3["SCAN tbl3"]
    конец
    subgraph Group#12
        Expr#13["JOIN"]
    конец
    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"]
    конец
    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)
"]

Bonus: query execution

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

 graph LR
    plan(("Physical Plan"))
    storage[("Storage Layer")]
    processor["Query Processor"]
    plan -- execute --> processor
    storage -- fetch --> processor

Volcano/Iterator model

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 = 1

will 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 operators

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

Testing a simple query

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 . id

with 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 ?

Расширять