Overview and Purpose
A Finite State Transducer (FST) index is a specialized data structure that accelerates regular expression queries on text columns while dramatically reducing the on-disk index size. It provides efficient pattern matching capabilities while consuming 4-6 times less storage space compared to traditional indexing approaches. In StarTree Cloud (powered by Apache Pinot), FST indexes are particularly valuable for:- Supporting regular expression (regex) queries on text columns
- Optimizing prefix matches written as
REGEXP_LIKE(col, '^prefix') - Reducing index storage requirements for text search functionality
- Pattern matching across large text datasets with storage efficiency
- Applications requiring wildcard searches with storage constraints
FST indexes are optimized for regex operations and prefix queries. They complement text indexes by providing a more storage-efficient option for specific text search patterns.
How the Index Works
Core Concepts
Traditional text indexing approaches can require significant storage space to enable pattern matching across text data. The FST index takes a different approach, using finite state transducers - a specialized data structure from computational linguistics - to represent patterns efficiently. The FST index in StarTree Cloud:- Compact Representation: Represents all possible text patterns in the column as a directed graph structure that recognizes valid strings.
- Prefix Optimization: Particularly efficient for prefix searches, as the FST can quickly traverse the initial states of the automaton.
- Storage Efficiency: Achieves 4-6x reduction in on-disk index size compared to other text indexing approaches.
- Dictionary Integration: Leverages dictionary encoding to further optimize performance and storage.
Example Illustration
For a column storing product names:- Traditional Text Index: Stores tokenized terms and their positions, consuming significant storage space.
- FST Index Approach:
- Builds a finite state automaton representing all product names
- Enables regex queries like
REGEXP_LIKE(product, '^Smart')to quickly find all products starting with “Smart” - Consumes 4-6x less storage space compared to text index
WHERE REGEXP_LIKE(product, '^Phone'), FST can efficiently traverse the initial states of the automaton that correspond to the prefix “Phone”, then identify all possible completions that exist in the data.
Which queries use the index
If the column doesn’t have the index the predicate needs, the query still returns correct results. It just evaluates the pattern against every dictionary value instead.
For example, to rewrite a
LIKE prefix filter so it uses the FST index:
LIKE isn’t. If you need case-insensitive matching, keep LIKE and add an IFST index.
Anchor prefix patterns with ^
REGEXP_LIKE matches anywhere in the value unless the pattern is anchored. An unanchored pattern such as 'Smart' is treated as .*Smart.*, so the FST index has to walk every path in the index. That can be slower than not having the index at all.
Start prefix patterns with ^ (for example '^Smart') so the index can go straight to the matching prefix. A trailing .* isn’t needed. Add $ only when the value must end where the pattern ends.
Configuration
Enabling FST Index
To enable an FST index on a column in your StarTree Cloud table, add the following configuration to your table definition:Alternative Configuration (Legacy Method)
You can also use the older configuration format:Case-insensitive matching (IFST index)
The IFST index is the case-insensitive version of the FST index. It’s the oneLIKE and REGEXP_LIKE(col, 'pattern', 'i') use. It has the same column requirements as FST and also needs an inverted index to avoid a scan.
"indexTypes": ["IFST"]. A column can have both FST and IFST if it gets both kinds of queries.
Add an inverted index
Add an inverted index on every column you filter with FST or IFST, unless the column is the table’s sorted column:REGEXP_LIKE, both need FST and an inverted index. Otherwise the second column is still scanned.
Important Configuration Requirements
- Column type: The column must be a single-value
STRINGcolumn. Multi-value columns and other data types aren’t supported. - Dictionary Encoding: The column must be dictionary-encoded (not RAW encoded).
- Set
encodingTypetoDICTIONARY(this is the default if left unspecified)
- Set
- Segment Types: FST indexes are only supported on:
- Completed segments (offline mode)
- Committed segments (real-time mode)
- Not supported on consuming segments (real-time in-progress segments)
- Inverted or sorted index: The column needs an inverted index, or must be the sorted column, for the filter to avoid a full scan. See Add an inverted index.
Adding the index to an existing table
You can add FST or IFST to a table that already has data. Update the table config, then reload the table’s segments to build the index. The reload fails for a column that doesn’t meet the requirements above.Check that the index is used
FST and IFST don’t appear by name inEXPLAIN PLAN output. Look at the filter operator for the column instead:
In query stats, a working setup shows
numEntriesScannedInFilter close to zero for that column.
Performance Considerations
- Prefix Query Efficiency: FST indexes perform best with anchored prefix patterns (
'^prefix'). Unanchored patterns and leading wildcards force a walk of the whole index. - Storage Benefits: The primary advantage is the 4-6x reduction in on-disk index size compared to other text index types.
- Case Sensitivity: FST is case-sensitive.
LIKEandREGEXP_LIKEwith'i'use IFST, not FST. - Dictionary Requirement: The requirement for dictionary encoding means FST indexes are best suited for columns with manageable cardinality.
- Complementary Use: Consider using FST indexes alongside other index types:
- FST for case-sensitive regex and prefix queries, IFST for
LIKEand case-insensitive regex - Inverted index on the same column, which FST and IFST need to avoid scans
- Text index for more complex text search needs
- FST for case-sensitive regex and prefix queries, IFST for

