В этом посте мы представим обзор того, как выполняются запросы Cypher, чтобы показать, как помогает Ronja.

Выполнение запроса Cypher происходит в следующих шагах, где Ronja обрабатывает шаги 2 — 5:

1. Преобразовать строку входного запроса в абстрактное синтаксическое дерево (AST)
2. Оптимизировать и нормализовать АСТ
3. Создать график запроса из нормализованного AST
4. Создайте логический план из X
5. Перепишите логический план
6. Создать план выполнения из логического плана
7. Выполнить запрос, используя план выполнения

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

Преобразовать строку входного запроса в абстрактное синтаксическое дерево (AST)

Входная строка запроса сначала маркируется, а затем анализируется в AST .

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

На этом этапе AST размечен семантической информацией, и мы сохраняем ссылку на исходную строку входного запроса.

Оптимизировать и нормализовать АСТ

Ronja начинает с выполнения простых оптимизаций и нормализаций на AST; некоторые из них включают в себя:

• Перемещение всех меток и типов из предложения MATCH в WHERE
• Подавление избыточных СО
• Расширение псевдонимов; например, RETURN * => RETURN x как x, y как y
• Складывание констант; например, 1 + 2 * 4 => 9
• Присвоение имен узлам анонимных шаблонов; например, MATCH () => MATCH (n)
• Преобразование оператора равенства в ‘IN’: MATCH (n) WHERE id (n) = 12 => MATCH n WHERE id (n) IN [12]
• Другие нормализации

Создать график запроса из нормализованного AST

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

Создать логический план из графа запросов

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

Логический план создается для каждого графа запросов (в зависимости от запроса граф запросов может состоять из графиков подзапросов). Это делается поэтапно, следуя подходу снизу вверх.

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

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

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

Перепишите логический план

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

Создать план выполнения из логического плана

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

MATCH (a1:Artist {name: ‘Artist-1′}), (a2:Artist),

p = shortestPath((a1)-[*..3]-(a2))

RETURN p LIMIT 5

MATCH (a1:Artist {name: ‘Artist-1′})-[:PERFORMED_AT]->

     (:Concert)<-[:PERFORMED_AT]-(a2:Artist)

MATCH (a1)-[:SIGNED_WITH]->(corp:Company)<-[:SIGNED_WITH]-(a2)

RETURN a2, COUNT(*)

ORDER BY COUNT(*) DESC

MATCH (a:Author),

(a)-[:WROTE]->(b:Book),

(s:Store)

WHERE (b)-[:SOLD_AT]->(s:Store) AND s.SalesRank > 3 RETURN a.FullName, b.Title, s.StoreName