Введение 3
Постановка задачи 4
1. Обзор альтернативных вариантов решения поставленной задачи 5
1.1. gRPC 5
1.2. GraphQL 5
1.3. Графовые базы данных 5
1.4. TeamCity searchQL 5
2. Описание структур 7
2.1. Схема генератора 7
2.2. Язык запросов 9
3. Исполнение запроса 11
3.1. Парсинг запроса 11
3.2. Построение графа исполнения 12
3.3. Вычисление и оптимизации 14
3.4. Вычисление резултата в зависимости от типа вершины 16
3.5. Порядок вычисления 32
4. Генерация кода 34
4.1. Парсеры 34
4.2. Объекты 34
4.3. Граф исполнения 35
4.4. Исполнение запроса 35
Заключение 36
Список литературы 37
Часто появляется необходимость добавить в уже существующий проект возможность поиска, который при этом не должен использовать много ресурсов системы. И существующих способов доступа к данным не всегда достаточно, особенно если нужно объединить в сервисе поиска несколько существующих вариантов доступа к данным. Поэтому приходится добавлять новую функциональность поиска с новым языком, вычислителем запросов и т.д. Если реализовывать такой язык для конкретной системы, то добавление новых параметров поиска становится и слишком сложным(приходится вносить изменения в разные части кода) и рутинным(новый код почти полностью совпадает со старым). Поэтому имеет смысл разработать генератор такого языка, который по схеме иерархической структуры будет генерировать код парсера и вычислителя языка.
В силу ограниченности ресурсов, одним из немногих способов оптимизации остается уменьшение количества объектов, с которыми вычислитель взаимодействует при вычислении запроса. Также нужно учитывать индивидуальные особенности проекта, для которого создается язык запросов, и хотелось бы иметь возможность регулировать какие оптимизации(к каким объектам, переходам) и в какой степени применять.
В ходе работы удалось:
• разработать синтаксис языка, который позволяет делать запросы произвольной сложности к иерархической структуре
• реализовать генератор кода для парсера и вычислителя этого языка
• разработать и реализовать эффективный алгоритм вычисления запросов, с возможностью регулировать оптимизации на уровне схемы генератора
• с помощью генератора кода был создан пример языка поиска для структуры сервера TeamCity. [7]
Таким образом задав схему генератора для произвольной иерархической структуры и реализовав переходы по ней, можно искать произвольный объект с условием на этом объект и с условием на то, в каких объектах его нужно искать. Также при предоставлении некоторой дополнительной информации о структуре и новых способов доступа к ее объектам, возможна оптимизация вычисления запроса, при помощи которой во время вычисления будет затронуто существенно меньшее количество объектов. Весь код доступен по следующей ссылке: https://github.com/ilyavoronin/search-ql- generator
