A query engine is a crucial component of any modern search infrastructure. It serves a dual purpose: enabling users to effectively search through vast datasets while providing a structured input for the system to process.

At its core, a query engine takes natural language inputs or structured queries, breaks them down into a machine-readable format, and constructs a query tree. This tree structure allows for the logical grouping and hierarchical processing of the query components, enabling precise filtering, weighting, and scoring of search results. By providing this structured input, the query engine not only enhances the user experience but also ensures that the search system operates efficiently and effectively, returning the most relevant data in response to complex queries

Query Tree Representation

A query tree breaks down the query into nodes, each representing a specific operation or condition. For example, a node can represent logical operators like AND, OR, or comparison operators like LESS_THAN.

Defining Operations via Nodes

Each node in the query tree defines a set of operations. These can include logical operators (AND, OR), comparison operators (LESS_THAN, GREATER_THAN), and specific functions like colbert(‘some text’). This structured approach allows for detailed parsing of text into a structured query language.

Scoring Parameters

The query tree also allows for the definition of scoring parameters. By specifying how different elements of the query should be weighted, we can customize the ranking of search results.

Example:

fusion([colbert('some text'), greaterThan(date, 01-01-1970)])

Inspiration from Existing Systems

Systems like Vespa offer query languages where ranking functions can be defined, providing a robust framework for building and optimizing query engines.

Query Execution: The Sum of Its Parts

Query execution is a critical phase in the search process where the structured query is processed to retrieve the most relevant results. This phase is much more than a simple keyword match; it’s a complex operation involving several interconnected components that work together to deliver precise and efficient search outcomes.

Let’s break down these components to understand how they contribute to the overall process.

1. Parsing and Tree Construction

The first step in query execution is parsing the user’s input. The query engine interprets the natural language or structured query and converts it into a query tree. This tree is a hierarchical structure where each node represents an operation or condition—such as logical operators (AND, OR), comparisons (LESS_THAN, GREATER_THAN), or specific search functions. The tree format allows the query engine to systematically analyze and process each component of the query, ensuring that different parts of the query can be executed independently or in combination.

2. Logical Grouping and Optimization

Once the query tree is constructed, the query engine applies logical grouping to organize related elements together. This step is crucial for optimizing query execution, as it allows the engine to prioritize more relevant parts of the query. For instance, operations that can drastically reduce the dataset, such as filtering by date or location, are typically executed first. This optimization ensures that subsequent steps operate on a smaller, more manageable subset of data, improving overall efficiency and reducing computational load.

3. Node Execution and Data Retrieval

With the query tree optimized, the query engine begins executing each node. Execution involves applying the operations defined in the tree nodes to the dataset. For example, if a node specifies an AND operation between two conditions, the engine will retrieve only those records that meet both conditions. This step is iterative, with each level of the query tree being processed in sequence.

As the engine navigates through the tree, it progressively narrows down the dataset until it isolates the most relevant results.

4. Scoring and Ranking

After executing the query tree, the engine proceeds to score and rank the retrieved results. Scoring involves evaluating the relevance of each result based on predefined criteria, such as the presence of certain keywords, the credibility of the source, or the recency of the data. The query engine may use a combination of these factors, applying weights to each to calculate a final relevance score. The results are then ranked according to these scores, with the most relevant data appearing at the top.

5. Post-Processing and Output Formatting

The final stage of query execution involves post-processing the results. This step can include additional filtering, formatting the output to match user preferences, or applying further optimizations such as deduplication. The goal of post-processing is to ensure that the output is not only accurate and relevant but also presented in a user-friendly manner. The structured format of the query engine’s output enables integration with other systems, such as data visualization tools or automated report generators.

6. Continuous Optimization

Query execution doesn’t end with delivering the results. We can use the query engine to adjust our search, increasing recall by augmenting and expanding the query. We can also reduce latency with query likelihood models that automatically attempt to filter the data based on how likely the query is to want those documents.

There’s no guaranteed solution that will perfectly fit your needs, so it’s worth evaluating different approaches.

What’s Next?

As we continue to innovate and refine our query engine, we’re focusing on a few key areas:

Query Optimizations for Approximate Nearest Neighbor (ANN)

We’re implementing query adapters that improve retrieval functionality. Existing embeddings can be transformed to improve retrieval during query time, enhancing personalized relevancy.

Enabling Seamless Embedding Updates

To ensure our search engine remains up-to-date with the latest information, we will develop mechanisms to automatically build queries that consider embedding updates. This is crucial as new data continually comes in, requiring constant adjustments to cluster assignments and search parameters.

Arbitrary Scoring

In search and ranking, scoring functions play a pivotal role in determining the relevance of retrieved documents or data points. These functions evaluate each result based on how well it matches the query, producing a score that guides the ranking of results.

It’s not always clear how to rerank these documents, as more complicated ranking methods usually are applied in phases to prevent high latency.

We want to express phased ranking as part of the query, enabling rapid experimentation of different ranking methods. This should increase developer productivity and improve search results.

Conclusion

Query engines are a critical part of any search engine. They give us an abstraction to expand or refine the query and decide the most efficient execution strategy.

Users depend on an expressive query engine to interface with their data. Queries can also be a way that users quickly evaluate different retrieval and ranking strategies.