Как база данных понимает и выполняет ваш запрос?
Изображение на обложке
Эта статья переведена Анжелой Ни.
Векторный запрос в Milvus - это процесс получения векторов с помощью скалярной фильтрации на основе булевых выражений. С помощью скалярной фильтрации пользователи могут ограничить результаты запроса определенными условиями, наложенными на атрибуты данных. Например, если пользователь запрашивает фильмы, выпущенные в 1990-2010 годах и имеющие оценку выше 8,5 балла, ему будут представлены только те фильмы, атрибуты которых (год выпуска и оценка) удовлетворяют условию.
В этой статье мы рассмотрим, как выполняется запрос в Milvus, начиная с ввода выражения запроса и заканчивая генерацией плана запроса и его выполнением.
Перейти к:
Выражение запроса
Выражение запроса с фильтрацией атрибутов в Milvus использует синтаксис EBNF (Extended Backus-Naur form). Ниже показаны правила выражения в Milvus.
Синтаксис выражений
Логические выражения могут быть созданы с помощью комбинации бинарных логических операторов, унарных логических операторов, логических выражений и одиночных выражений. Поскольку синтаксис EBNF сам по себе рекурсивен, логическое выражение может быть результатом комбинации или частью большего логического выражения. Логическое выражение может содержать множество подлогических выражений. То же правило действует и в Milvus. Если пользователю необходимо отфильтровать атрибуты результатов с помощью множества условий, он может создать свой собственный набор условий фильтрации, комбинируя различные логические операторы и выражения.
Булево выражение
На изображении выше показана часть правил булевых выражений в Milvus. В выражение можно добавлять унарные логические операторы. В настоящее время Milvus поддерживает только унарный логический оператор "not", который указывает на то, что система должна отбирать векторы, значения скалярного поля которых не удовлетворяют результатам вычислений. Бинарные логические операторы включают "и" и "или". К одиночным выражениям относятся выражения термов и сравнения.
Базовые арифметические вычисления, такие как сложение, вычитание, умножение и деление, также поддерживаются при выполнении запроса в Milvus. Следующее изображение демонстрирует приоритет операций. Операторы перечислены сверху вниз в порядке убывания старшинства.
Приоритет
Как в Milvus обрабатывается выражение запроса на определенные фильмы?
Предположим, что в Milvus хранится большое количество данных о фильмах, и пользователь хочет запросить определенные фильмы. Например, каждый фильм, хранящийся в Milvus, имеет следующие пять полей: идентификатор фильма, год выпуска, тип фильма, оценка и постер. В этом примере тип данных идентификатора фильма и года выпуска - int64, а оценки фильма - данные с плавающей точкой. Также постеры фильмов хранятся в формате векторов с плавающей точкой, а тип фильма - в формате строковых данных. Примечательно, что поддержка строкового типа данных - это новая возможность в Milvus 2.1.
Например, если пользователь хочет запросить фильмы с оценками выше 8,5. При этом фильмы должны быть выпущены в период с десятилетия до 2000 года по десятилетие после 2000 года или их тип должен быть либо комедией, либо боевиком, пользователю необходимо ввести следующее предикатное выражение: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action])
.
Получив выражение запроса, система выполнит его в следующем порядке:
- Запрос на фильмы с оценкой выше 8,5. Результаты запроса называются "result1".
- Вычислите 2000 - 10, чтобы получить "результат2" (1990).
- Вычислите 2000 + 10, чтобы получить "результат3" (2010).
- Запросите фильмы со значением
release_year
больше, чем "результат2", и меньше, чем "результат3". Иными словами, системе нужно запросить фильмы, выпущенные в период с 1990 по 2010 год. Результаты запроса называются "result4". - Запрос на фильмы, которые являются либо комедиями, либо боевиками. Результаты запроса называются "result5".
- Объедините "result4" и "result5", чтобы получить фильмы, которые либо выпущены в период с 1990 по 2010 год, либо относятся к категории комедий или боевиков. Полученные результаты называются "result6".
- Возьмите общую часть в "result1" и "result6", чтобы получить конечный результат, удовлетворяющий всем условиям.
Пример фильма
Генерация плана AST
Milvus использует инструмент с открытым исходным кодом ANTLR (ANother Tool for Language Recognition) для генерации AST (абстрактного синтаксического дерева) плана. ANTLR - это мощный генератор парсеров для чтения, обработки, выполнения или перевода структурных текстовых или бинарных файлов. Более конкретно, ANTLR может генерировать синтаксический анализатор для построения и обхода деревьев разбора на основе предварительно заданного синтаксиса или правил. Ниже показан пример, в котором входным выражением является "SP=100;". LEXER, встроенная в ANTLR функция распознавания языка, генерирует четыре лексемы для входного выражения - "SP", "=", "100" и ";". Затем инструмент выполнит дальнейший разбор этих четырех лексем, чтобы сгенерировать соответствующее дерево разбора.
дерево разбора
Механизм walker является важной частью инструмента ANTLR. Он предназначен для просмотра всех деревьев разбора, чтобы проверить, подчиняется ли каждый узел правилам синтаксиса, или для обнаружения определенных чувствительных слов. Некоторые из соответствующих API перечислены на рисунке ниже. Поскольку ANTLR начинает с корневого узла и спускается вниз через все подузлы до самого низа, нет необходимости различать порядок прохождения по дереву разбора.
программа для просмотра дерева разбора
Milvus генерирует PlanAST для запроса аналогично ANTLR. Однако использование ANTLR требует переопределения довольно сложных правил синтаксиса. Поэтому Milvus использует одно из наиболее распространенных правил - правила булевых выражений, и зависит от пакета Expr, открытого на GitHub для запроса и разбора синтаксиса выражений запроса.
Во время запроса с фильтрацией атрибутов Milvus, получив выражение запроса, сгенерирует примитивное дерево нерешенных планов с помощью ant-parser, метода разбора, предоставляемого Expr. Примитивное дерево плана, которое мы получим, представляет собой простое двоичное дерево. Затем дерево плана подвергается тонкой настройке с помощью Expr и встроенного оптимизатора в Milvus. Оптимизатор в Milvus очень похож на вышеупомянутый механизм walker. Поскольку функциональность оптимизации дерева планов, предоставляемая Expr, довольно сложна, нагрузка на встроенный оптимизатор Milvus в значительной степени облегчается. В конечном итоге анализатор рекурсивно анализирует оптимизированное дерево планов, чтобы сгенерировать план AST в структуре буферов протоколов (protobuf).
Рабочий процесс создания АСТ плана
Выполнение запроса
Выполнение запроса - это в корне выполнение плана AST, сгенерированного на предыдущих шагах.
В Milvus план AST определяется в структуре proto. На рисунке ниже представлено сообщение со структурой protobuf. Существует шесть типов выражений, среди которых двоичное выражение и унарное выражение, далее могут быть двоичное логическое выражение и унарное логическое выражение.
protobuf1
protobuf2
На рисунке ниже представлено UML-изображение выражения запроса. Оно демонстрирует базовый класс и производный класс каждого выражения. Каждый класс имеет метод, принимающий параметры посетителя. Это типичный паттерн проектирования посетителей. Milvus использует этот паттерн для выполнения плана AST, поскольку его главным преимуществом является то, что пользователям не нужно ничего делать с примитивными выражениями, а можно напрямую обратиться к одному из методов в паттерне, чтобы изменить определенный класс выражения запроса и соответствующие элементы.
UML
При выполнении плана AST Milvus сначала получает узел плана типа proto-. Затем с помощью внутреннего синтаксического анализатора C++ proto получают узел плана типа segcore. После получения двух типов узлов плана Milvus принимает серию обращений к классам, а затем модифицирует и выполняет во внутренней структуре узлов плана. Наконец, Milvus перебирает все узлы плана выполнения, чтобы получить отфильтрованные результаты. Окончательные результаты выводятся в формате битовой маски. Битовая маска - это массив битовых чисел ("0" и "1"). Данные, удовлетворяющие условиям фильтрации, помечаются в битовой маске как "1", а данные, не удовлетворяющие требованиям, помечаются в битовой маске как "0".
выполнить рабочий процесс
О серии "Глубокое погружение
После официального объявления об общей доступности Milvus 2.0 мы организовали эту серию блогов Milvus Deep Dive, чтобы дать глубокую интерпретацию архитектуры и исходного кода Milvus. В этой серии блогов рассматриваются следующие темы:
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word