🚀 Prova Zilliz Cloud, la versione completamente gestita di Milvus, gratuitamente—sperimenta prestazioni 10 volte più veloci! Prova Ora>>

milvus-logo
LFAI
  • Home
  • Blog
  • In che modo il database comprende ed esegue la query?

In che modo il database comprende ed esegue la query?

  • Engineering
May 05, 2022
Milvus

Cover image Immagine di copertina

Questo articolo è stato trascritto da Angela Ni.

Una query vettoriale in Milvus è il processo di recupero di vettori tramite un filtro scalare basato su un'espressione booleana. Con il filtraggio scalare, gli utenti possono limitare i risultati delle loro interrogazioni con determinate condizioni applicate agli attributi dei dati. Ad esempio, se un utente interroga i film usciti nel periodo 1990-2010 e con un punteggio superiore a 8,5, solo i film i cui attributi (anno di uscita e punteggio) soddisfano la condizione.

Questo post si propone di esaminare come viene completata una query in Milvus, dall'inserimento di un'espressione di query alla generazione del piano di query e all'esecuzione della stessa.

Vai a:

Espressione della query

L'espressione di una query con filtraggio degli attributi in Milvus adotta la sintassi EBNF (Extended Backus-Naur form). L'immagine seguente mostra le regole di espressione in Milvus.

Expression Syntax Sintassi dell'espressione

Le espressioni logiche possono essere create utilizzando la combinazione di operatori logici binari, operatori logici unari, espressioni logiche e singole espressioni. Poiché la sintassi EBNF è di per sé ricorsiva, un'espressione logica può essere il risultato della combinazione o parte di un'espressione logica più grande. Un'espressione logica può contenere molte sottoespressioni logiche. La stessa regola si applica a Milvus. Se un utente ha bisogno di filtrare gli attributi dei risultati con molte condizioni, può creare il proprio insieme di condizioni di filtraggio combinando diversi operatori logici ed espressioni.

Boolean expression Espressione booleana

L'immagine qui sopra mostra una parte delle regole delle espressioni booleane in Milvus. Gli operatori logici unari possono essere aggiunti a un'espressione. Attualmente Milvus supporta solo l'operatore logico unario "not", che indica che il sistema deve prendere i vettori i cui valori del campo scalare non soddisfano i risultati del calcolo. Gli operatori logici binari includono "and" e "or". Le espressioni singole includono le espressioni di termine e le espressioni di confronto.

In Milvus sono supportati anche i calcoli aritmetici di base, come addizione, sottrazione, moltiplicazione e divisione, durante un'interrogazione. L'immagine seguente mostra la precedenza delle operazioni. Gli operatori sono elencati dall'alto verso il basso in ordine decrescente.

Precedence Precedenza

Come viene elaborata in Milvus un'espressione di interrogazione su determinati film?

Supponiamo che in Milvus ci sia un'abbondanza di dati di film e che l'utente voglia interrogare alcuni film. Ad esempio, ogni film memorizzato in Milvus ha i seguenti cinque campi: ID film, anno di uscita, tipo di film, colonna sonora e poster. In questo esempio, il tipo di dati dell'ID del film e dell'anno di uscita è int64, mentre i punteggi dei film sono dati in virgola mobile. Inoltre, le locandine dei film sono memorizzate nel formato di vettori a virgola mobile e il tipo di film nel formato di dati stringa. In particolare, il supporto per i dati di tipo stringa è una novità di Milvus 2.1.

Per esempio, se un utente vuole interrogare i film con un punteggio superiore a 8,5. I film devono essere usciti da un decennio prima del 2000 a un decennio dopo il 2000 o devono essere di tipo commedia o film d'azione, l'utente deve inserire la seguente espressione di predicato: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action]).

Una volta ricevuta l'espressione della query, il sistema la eseguirà con la seguente precedenza:

  1. Ricerca di film con punteggio superiore a 8,5. I risultati della query sono chiamati "risultato1".
  2. Calcolare 2000 - 10 per ottenere "risultato2" (1990).
  3. Calcolare 2000 + 10 per ottenere "risultato3" (2010).
  4. Cercare i film con il valore di release_year maggiore di "risultato2" e minore di "risultato3". In altre parole, il sistema deve cercare i film usciti tra il 1990 e il 2010. I risultati dell'interrogazione sono chiamati "risultato4".
  5. Interrogare i film che sono commedie o film d'azione. I risultati della query sono chiamati "risultato5".
  6. Combinare "risultato4" e "risultato5" per ottenere film che sono usciti tra il 1990 e il 2010 o che appartengono alla categoria delle commedie o dei film d'azione. I risultati sono chiamati "risultato6".
  7. Prendete la parte comune di "risultato1" e "risultato6" per ottenere i risultati finali che soddisfano tutte le condizioni.

Film example Esempio di film

Generazione di piani AST

Milvus utilizza lo strumento open-source ANTLR (ANother Tool for Language Recognition) per la generazione di piani AST (abstract syntax tree). ANTLR è un potente generatore di parser per la lettura, l'elaborazione, l'esecuzione o la traduzione di file di testo o binari. Più specificamente, ANTLR può generare un parser per costruire e percorrere alberi di parsing basati su regole o sintassi predefinite. L'immagine seguente è un esempio in cui l'espressione di input è "SP=100;". LEXER, la funzionalità di riconoscimento linguistico integrata in ANTLR, genera quattro token per l'espressione di input: "SP", "=", "100" e ";". Quindi lo strumento analizza ulteriormente i quattro token per generare l'albero di parsè corrispondente.

parse tree albero di parsè

Il meccanismo del walker è una parte fondamentale dello strumento ANTLR. È progettato per percorrere tutti gli alberi di parsing per esaminare se ogni nodo rispetta le regole sintattiche o per rilevare alcune parole sensibili. Alcune delle API rilevanti sono elencate nell'immagine seguente. Poiché ANTLR parte dal nodo radice e scende attraverso ogni sotto-nodo fino in fondo, non è necessario differenziare l'ordine di percorrenza dell'albero di parses.

parse tree walker camminatore dell'albero di parsè

Milvus genera il PlanAST per le query in modo simile ad ANTLR. Tuttavia, l'uso di ANTLR richiede la ridefinizione di regole sintattiche piuttosto complicate. Pertanto, Milvus adotta una delle regole più diffuse, quella delle espressioni booleane, e dipende dal pacchetto Expr, disponibile su GitHub, per interrogare e analizzare la sintassi delle espressioni di query.

Durante una query con filtraggio degli attributi, Milvus genera un albero del piano primitivo irrisolto usando ant-parser, il metodo di parsing fornito da Expr, quando riceve l'espressione della query. Il piano primitivo ottenuto è un semplice albero binario. L'albero del piano viene poi perfezionato da Expr e dall'ottimizzatore integrato in Milvus. L'ottimizzatore di Milvus è molto simile al meccanismo del walker già citato. Poiché la funzionalità di ottimizzazione dell'albero del piano fornita da Expr è piuttosto sofisticata, l'onere dell'ottimizzatore integrato in Milvus viene alleggerito in larga misura. Infine, l'analizzatore analizza l'albero del piano ottimizzato in modo ricorsivo per generare un AST del piano nella struttura dei buffer di protocollo (protobuf).

plan AST workflow Flusso di lavoro del piano AST

Esecuzione della query

L'esecuzione di una query è in fondo l'esecuzione del piano AST generato nelle fasi precedenti.

In Milvus, un piano AST è definito in una struttura proto. L'immagine sottostante rappresenta un messaggio con la struttura protobuf. Esistono sei tipi di espressioni, tra cui l'espressione binaria e l'espressione unaria, che possono avere anche l'espressione logica binaria e l'espressione logica unaria.

protobuf1 protobuf1

protobuf2 protobuf2

L'immagine seguente è un'immagine UML dell'espressione di query. Mostra la classe base e la classe derivata di ogni espressione. Ogni classe è dotata di un metodo per accettare i parametri del visitatore. Questo è un tipico modello di progettazione del visitatore. Milvus utilizza questo pattern per eseguire il piano AST, in quanto il suo principale vantaggio è che gli utenti non devono fare nulla alle espressioni primitive, ma possono accedere direttamente a uno dei metodi del pattern per modificare la classe dell'espressione di query e i relativi elementi.

UML UML

Quando si esegue un piano AST, Milvus riceve prima un nodo di piano di tipo proto. Poi ottiene un nodo di piano di tipo segcore tramite il parser interno C++ proto. Una volta ottenuti i due tipi di nodi di piano, Milvus accetta una serie di accessi alle classi e poi modifica ed esegue la struttura interna dei nodi di piano. Infine, Milvus cerca tra tutti i nodi del piano di esecuzione per ottenere i risultati filtrati. I risultati finali sono presentati nel formato di una bitmask. Una bitmask è un array di numeri di bit ("0" e "1"). I dati che soddisfano le condizioni del filtro sono contrassegnati da "1" nella bitmask, mentre quelli che non soddisfano i requisiti sono contrassegnati da "0" nella bitmask.

execute workflow eseguire il flusso di lavoro

Informazioni sulla serie Deep Dive

Con l'annuncio ufficiale della disponibilità generale di Milvus 2.0, abbiamo organizzato questa serie di blog Milvus Deep Dive per fornire un'interpretazione approfondita dell'architettura e del codice sorgente di Milvus. Gli argomenti trattati in questa serie di blog includono:

Try Managed Milvus for Free

Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.

Get Started

Like the article? Spread the word

Continua a Leggere