Skip to main content

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.
The FST index is case-sensitive, so it only serves case-sensitive REGEXP_LIKE. LIKE is always evaluated case-insensitively and never uses the FST index. To accelerate LIKE, or REGEXP_LIKE with the 'i' flag, add an IFST index instead.

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:
  1. Compact Representation: Represents all possible text patterns in the column as a directed graph structure that recognizes valid strings.
  2. Prefix Optimization: Particularly efficient for prefix searches, as the FST can quickly traverse the initial states of the automaton.
  3. Storage Efficiency: Achieves 4-6x reduction in on-disk index size compared to other text indexing approaches.
  4. Dictionary Integration: Leverages dictionary encoding to further optimize performance and storage.
The FST index works on the column’s dictionary, not on rows. It finds the dictionary values that match the pattern. Turning those values into matching rows takes an inverted index on the same column, or the column being the table’s sorted column. Without one of them, the query still scans every row in the filter. See Add an inverted index.

Example Illustration

For a column storing product names:
  1. Traditional Text Index: Stores tokenized terms and their positions, consuming significant storage space.
  2. 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
When processing a query like 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:
The rewrite also makes the match case-sensitive, which 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 one LIKE 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.
The legacy format is "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:
This applies to each column in the filter separately. If a query filters on two columns with REGEXP_LIKE, both need FST and an inverted index. Otherwise the second column is still scanned.

Important Configuration Requirements

  1. Column type: The column must be a single-value STRING column. Multi-value columns and other data types aren’t supported.
  2. Dictionary Encoding: The column must be dictionary-encoded (not RAW encoded).
    • Set encodingType to DICTIONARY (this is the default if left unspecified)
  3. 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)
  4. 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 in EXPLAIN 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

  1. Prefix Query Efficiency: FST indexes perform best with anchored prefix patterns ('^prefix'). Unanchored patterns and leading wildcards force a walk of the whole index.
  2. Storage Benefits: The primary advantage is the 4-6x reduction in on-disk index size compared to other text index types.
  3. Case Sensitivity: FST is case-sensitive. LIKE and REGEXP_LIKE with 'i' use IFST, not FST.
  4. Dictionary Requirement: The requirement for dictionary encoding means FST indexes are best suited for columns with manageable cardinality.
  5. Complementary Use: Consider using FST indexes alongside other index types:
    • FST for case-sensitive regex and prefix queries, IFST for LIKE and 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