Implementing Efficient Suffix Matching in SQLite FTS5: Strategies and Trade-offs

Understanding FTS5 Tokenization Limitations and Suffix Matching Requirements

Issue Overview
SQLite’s Full-Text Search (FTS5) module is optimized for prefix-based queries (e.g., natural*), but lacks native support for suffix matching (e.g., *natural). This limitation stems from FTS5’s tokenization architecture, which indexes terms in a forward-oriented B-tree structure. Prefix searches are accelerated through sequential disk reads of indexed terms, while suffix searches require reverse traversal of term characters—a pattern incompatible with FTS5’s design.

The absence of suffix matching forces developers to seek workarounds when implementing use cases like:

• Finding words ending with specific character sequences (e.g., .com in email domains).
• Supporting linguistic analyses requiring suffix detection (e.g., pluralization rules).
• Enabling partial matches in log analysis or DNA sequence searches.

Storage constraints further complicate the problem, as common solutions like duplicating reversed text in shadow columns may double storage requirements. Alternatives must balance query performance, storage overhead, and computational complexity.

Architectural Constraints and Storage-Driven Trade-offs

Possible Causes

1. FTS5 Tokenizer Design:
   FTS5 tokenizes text into terms using rules defined by its tokenizer (e.g., unicode61). These terms are stored in a B-tree optimized for prefix scans. Suffix matching would require reverse-term indexing or exhaustive term scans, neither of which are supported natively.

2. Indexing Efficiency:
   B-tree structures excel at range queries for prefixes but cannot efficiently locate suffixes without a reverse index. Implementing such an index would increase storage and memory usage, conflicting with SQLite’s lightweight ethos.

3. Tokenization Granularity:
   The trigram tokenizer (used in specialized FTS5 tables) splits text into three-character sequences, enabling arbitrary substring matching. However, this increases index size by up to 10x compared to standard tokenizers, making it impractical for storage-limited environments.

4. Vocabulary Table Limitations:
   The fts5vocab virtual table provides access to indexed terms, enabling manual suffix searches via LIKE '%suffix'. However, querying this table requires loading all terms into memory, which is computationally expensive for large datasets.

Workarounds, Optimization Techniques, and Implementation Guidelines

Troubleshooting Steps, Solutions & Fixes

1. Reverse Text Shadow Column

Concept: Store a reversed copy of the target text in a separate FTS5 table or column. Suffix searches become prefix searches on the reversed text.

Implementation:

-- Original table with reversed text  
CREATE TABLE documents (  
    id INTEGER PRIMARY KEY,  
    content TEXT,  
    content_reversed TEXT  
);  

-- FTS5 table for reversed content  
CREATE VIRTUAL TABLE fts_documents_reversed USING fts5(content_reversed);  

Query Translation:

• Original suffix search: *natural → Reversed prefix search: laturan*

SELECT id, content  
FROM documents  
WHERE id IN (  
    SELECT rowid  
    FROM fts_documents_reversed  
    WHERE content_reversed MATCH 'laturan*'  
);  

Trade-offs:

• Storage Overhead: Doubles storage requirements due to duplicated reversed text.
• Indexing Complexity: Requires triggers or application logic to maintain the reversed column.
• Query Translation: Adds latency to query processing.

2. Trigram Tokenizer for Substring Matching

Concept: Use FTS5’s trigram tokenizer to index all three-character subsequences, enabling arbitrary substring matching.

Implementation:

-- Create FTS5 table with trigram tokenizer  
CREATE VIRTUAL TABLE fts_trigram USING fts5(  
    content,  
    tokenize = 'trigram'  
);  

Query Execution:

-- Suffix search for 'natural'  
SELECT *  
FROM fts_trigram  
WHERE content MATCH '*natural';  

Trade-offs:

• Storage Impact: Trigram tables consume 5–10x more space than standard FTS5 tables.
• Query Performance: Slower than prefix searches due to higher term density.
• Compatibility: Requires SQLite 3.43.0+ and explicit tokenizer configuration.

3. Hybrid fts5vocab Query Expansion

Concept: Use the fts5vocab virtual table to dynamically expand suffix queries into OR combinations of matching terms.

Implementation:

-- Create FTS5 table and vocabulary  
CREATE VIRTUAL TABLE fts_content USING fts5(content);  
CREATE VIRTUAL TABLE fts_vocab USING fts5vocab(fts_content, 'row');  

-- Query expansion for suffix 'natural'  
WITH matched_terms AS (  
    SELECT term  
    FROM fts_vocab  
    WHERE term LIKE '%natural'  
)  
SELECT *  
FROM fts_content  
WHERE content MATCH (  
    SELECT GROUP_CONCAT(term, ' OR ')  
    FROM matched_terms  
);  

Trade-offs:

• Memory Usage: Loading all vocabulary terms can be prohibitive for large datasets.
• Latency: Two-step query process increases response time.
• False Positives: Overly broad matches if terms contain the suffix as a substring (e.g., supernatural).

4. Application-Side Suffix Filtering

Concept: Perform a broad prefix search with FTS5, then filter results using application logic.

Implementation:

-- Broad prefix search for 'nat'  
SELECT *  
FROM fts_content  
WHERE content MATCH 'nat*';  

-- Application-side filtering  
results = [row for row in cursor if row['content'].endswith('natural')]  

Trade-offs:

• Network/CPU Overhead: Transfers more data than necessary.
• Predictability: Performance degrades with dataset size.

5. Leveraging External Tools

Concept: Offload suffix indexing to external full-text engines (e.g., Apache Lucene) while using SQLite for primary storage.

Implementation:

• Store raw text in SQLite.
• Index suffixes in a dedicated search engine.
• Query the external engine for matching document IDs, then retrieve content from SQLite.

Trade-offs:

• Complexity: Introduces dependency on external systems.
• Consistency: Requires synchronization between SQLite and the external index.

Final Recommendations

1. For Storage-Constrained Systems: Use reverse shadow columns with FTS5. Optimize storage via compression (e.g., zlib) or partial indexing of critical fields.
2. For High-Performance Requirements: Deploy trigram tokenizer tables, accepting higher storage costs.
3. For Dynamic Query Workloads: Combine fts5vocab with caching mechanisms to reduce vocabulary scan overhead.
4. For Hybrid Architectures: Pair SQLite with embedded search engines like SQLite’s own spellfix1 for phonetic matching or sqlean extensions for regex support.

By aligning the solution with specific performance, storage, and latency requirements, developers can mitigate FTS5’s suffix matching limitations effectively.