FTS5 Phrase Matching and Query Degradation in SQLite

FTS5 Phrase Matching Behavior and Misinterpretation of Token Sub-Sequences

The core issue revolves around the behavior of SQLite’s FTS5 (Full-Text Search) when handling multi-token phrases and the misunderstanding of how phrase matching operates. The documentation states that a phrase matches a document if the document contains at least one sub-sequence of tokens that matches the sequence of tokens that make up the phrase. This has led to confusion about whether FTS5 progressively degrades a multi-token phrase into smaller subqueries when an exact match is not found.

The expectation was that if a query like MATCH "one two three" does not yield results, FTS5 would automatically try subqueries like MATCH "one two", MATCH "one three", and MATCH "two three", and if those fail, further degrade to MATCH "one", MATCH "two", and MATCH "three". However, this is not how FTS5 operates. Instead, FTS5 strictly looks for the exact sequence of tokens as specified in the phrase. If the exact sequence is not found, no further degradation or alternative matching is attempted.

This behavior is consistent with the documentation but has led to confusion due to the interpretation of the term "sub-sequence." The documentation implies that the entire sequence of tokens must be present in the document for a match to occur, not that the query will be broken down into smaller sub-sequences for progressive matching.

Misinterpretation of "Sub-Sequence" and Implicit AND vs. OR Logic

The confusion arises from the interpretation of the term "sub-sequence" in the context of FTS5 phrase matching. The term "sub-sequence" in the documentation refers to the sequence of tokens within the document, not the query. It means that the document must contain a sequence of tokens that matches the sequence specified in the query. For example, if the query is "one two three", the document must contain the tokens "one", "two", and "three" in that exact order for a match to occur.

This is different from the implicit AND logic that is applied when multiple tokens are specified without quotation marks. For example, the query one two three (without quotes) is interpreted as one AND two AND three, meaning that the document must contain all three tokens, but not necessarily in sequence. This is a crucial distinction that affects how queries are processed and what results are returned.

The expectation that FTS5 would degrade a multi-token phrase into smaller subqueries with OR logic (e.g., one OR two OR three) is not supported by the current implementation. FTS5 does not automatically generate OR conditions for individual tokens when a phrase match fails. This behavior is by design, as FTS5 is optimized for exact phrase matching rather than progressive degradation.

Implementing Controlled Query Degradation and Relevance Scoring

Given that FTS5 does not support automatic query degradation, users who require this functionality must implement it manually. This involves breaking down the original query into smaller subqueries and combining the results with appropriate relevance scoring. For example, if the original query is "one two three", the user could manually generate subqueries like "one two", "one three", "two three", and "one" OR "two" OR "three", and then combine the results with a relevance score that reflects the degree of match.

One approach to implementing controlled query degradation is to use the ORDER BY rank clause in combination with auxiliary functions provided by FTS5. The rank column can be used to sort the results based on their relevance to the query. For example, the query SELECT * FROM fts5tbl('one OR two OR three') ORDER BY rank will return documents that contain any of the tokens "one", "two", or "three", sorted by their relevance score.

To achieve more granular control over the relevance scoring, users can define custom auxiliary functions that assign scores based on the number of tokens matched and their positions within the document. For example, a document that matches all three tokens in sequence ("one two three") could be assigned a higher score than a document that matches only two tokens ("one two"), and so on.

Another approach is to use a combination of FTS5 and traditional SQL queries to implement progressive degradation. For example, the user could first attempt to match the full phrase ("one two three"), and if no results are found, proceed to match sub-phrases ("one two", "one three", "two three"), and finally individual tokens ("one", "two", "three"). The results from each step could be combined into a single result set, with appropriate relevance scoring applied.

In summary, while FTS5 does not support automatic query degradation, users can achieve similar functionality by manually breaking down queries and combining results with custom relevance scoring. This approach requires a deeper understanding of FTS5’s behavior and the use of auxiliary functions and traditional SQL queries to implement the desired logic.

Detailed Explanation of FTS5 Phrase Matching and Query Degradation

FTS5 Phrase Matching Behavior

FTS5 is designed to match exact sequences of tokens within documents. When a phrase query is executed, FTS5 searches for documents that contain the exact sequence of tokens specified in the query. For example, the query "one two three" will only match documents that contain the tokens "one", "two", and "three" in that exact order. This behavior is consistent with the documentation, which states that a phrase matches a document if the document contains at least one sub-sequence of tokens that matches the sequence of tokens that make up the phrase.

The term "sub-sequence" in this context refers to the sequence of tokens within the document, not the query. It means that the document must contain a sequence of tokens that matches the sequence specified in the query. This is different from the behavior of some other full-text search engines, which may automatically degrade a multi-token phrase into smaller subqueries when an exact match is not found.

Misinterpretation of "Sub-Sequence"

The confusion arises from the interpretation of the term "sub-sequence" in the context of FTS5 phrase matching. Some users have interpreted this term to mean that FTS5 will automatically break down a multi-token phrase into smaller subqueries when an exact match is not found. For example, if the query "one two three" does not yield results, FTS5 would automatically try subqueries like "one two", "one three", and "two three", and if those fail, further degrade to "one", "two", and "three".

However, this is not how FTS5 operates. FTS5 strictly looks for the exact sequence of tokens as specified in the phrase. If the exact sequence is not found, no further degradation or alternative matching is attempted. This behavior is by design, as FTS5 is optimized for exact phrase matching rather than progressive degradation.

Implicit AND vs. OR Logic

Another source of confusion is the difference between phrase queries and queries with implicit AND logic. When multiple tokens are specified without quotation marks, FTS5 applies implicit AND logic. For example, the query one two three (without quotes) is interpreted as one AND two AND three, meaning that the document must contain all three tokens, but not necessarily in sequence.

In contrast, a phrase query like "one two three" requires the tokens to appear in the exact sequence specified. This is a crucial distinction that affects how queries are processed and what results are returned. The expectation that FTS5 would degrade a multi-token phrase into smaller subqueries with OR logic (e.g., one OR two OR three) is not supported by the current implementation.

Implementing Controlled Query Degradation

Combining FTS5 with Traditional SQL Queries

This approach requires a deeper understanding of FTS5’s behavior and the use of auxiliary functions and traditional SQL queries to implement the desired logic. However, it provides greater flexibility and control over the search results, allowing users to tailor the search experience to their specific needs.

Relevance Scoring and Auxiliary Functions

Relevance scoring is a critical aspect of implementing controlled query degradation. FTS5 provides several auxiliary functions that can be used to calculate relevance scores based on the number of tokens matched and their positions within the document. For example, the bm25() function can be used to calculate a relevance score based on the BM25 ranking algorithm, which takes into account the frequency of the tokens within the document and the inverse document frequency (IDF) of the tokens.

Users can also define custom auxiliary functions to implement more sophisticated relevance scoring algorithms. For example, a custom function could assign higher scores to documents that match more tokens or to documents where the tokens appear closer together. This allows users to fine-tune the search results to better match their specific requirements.

Example of Controlled Query Degradation

To illustrate the process of implementing controlled query degradation, consider the following example. Suppose we have a document collection and we want to search for the phrase "one two three". If no exact match is found, we want to degrade the query to "one two", "one three", "two three", and finally to "one" OR "two" OR "three".

The following SQL queries demonstrate how this could be implemented:

-- Attempt to match the full phrase
SELECT * FROM fts5tbl WHERE fts5tbl MATCH '"one two three"' ORDER BY rank;

-- If no results, degrade to sub-phrases
SELECT * FROM fts5tbl WHERE fts5tbl MATCH '"one two"' ORDER BY rank;
SELECT * FROM fts5tbl WHERE fts5tbl MATCH '"one three"' ORDER BY rank;
SELECT * FROM fts5tbl WHERE fts5tbl MATCH '"two three"' ORDER BY rank;

-- If still no results, degrade to individual tokens
SELECT * FROM fts5tbl WHERE fts5tbl MATCH 'one OR two OR three' ORDER BY rank;

The results from each query can be combined into a single result set, with appropriate relevance scoring applied. For example, documents that match the full phrase could be assigned a higher score than documents that match only a sub-phrase or individual tokens.

Conclusion

In conclusion, FTS5’s phrase matching behavior is designed to match exact sequences of tokens within documents. While this behavior is consistent with the documentation, it has led to confusion among users who expect FTS5 to automatically degrade multi-token phrases into smaller subqueries when an exact match is not found. To achieve this functionality, users must implement controlled query degradation manually, using a combination of FTS5 and traditional SQL queries, along with custom relevance scoring algorithms.

By understanding the nuances of FTS5’s behavior and leveraging its auxiliary functions, users can tailor the search experience to their specific needs, ensuring that relevant documents are returned even when an exact match is not found. This approach requires a deeper understanding of FTS5’s capabilities and a willingness to experiment with different query strategies, but it ultimately provides greater flexibility and control over the search results.

FTS5 Phrase Matching and Query Degradation in SQLite

FTS5 Phrase Matching Behavior and Misinterpretation of Token Sub-Sequences

Misinterpretation of "Sub-Sequence" and Implicit AND vs. OR Logic

Implementing Controlled Query Degradation and Relevance Scoring