Skip to main content

Overview and Purpose

A forward index is the fundamental data structure that maps document IDs (row indices) to their actual column values in StarTree Cloud. It serves as the primary mechanism for retrieving column values when processing queries that select, aggregate, or sort data. Unlike specialized indexes that accelerate specific query patterns, the forward index is the default storage mechanism that enables basic data access. It maintains a direct mapping from each row to its corresponding values, allowing the system to efficiently retrieve data for any query operation. Forward indexes are particularly important for:
  • SELECT clause operations that retrieve actual values
  • Aggregation functions that compute over column values
  • GROUP BY and ORDER BY operations that organize results
  • Any query pattern that requires access to the raw data values
Forward indexes are enabled by default for all columns. They can be selectively disabled in specific scenarios to save storage space when other indexes sufficiently support your query patterns.

How the Index Works

Core Concepts

At its core, a forward index implements a straightforward mapping:
StarTree Cloud offers multiple implementations of forward indexes, optimized for different data characteristics:
  1. Dictionary-Encoded Forward Index: Maps row IDs to dictionary IDs rather than actual values, providing space efficiency for columns with low to medium cardinality.
  2. Sorted Forward Index: Uses run-length encoding for sorted columns, storing only the start and end document IDs for each unique value, offering significant compression benefits.
  3. Raw Value Forward Index: Stores actual values directly, eliminating dictionary lookup overhead and improving performance for high-cardinality columns.
The implementation choice affects both storage requirements and query performance, with each approach offering different trade-offs.

Example Illustration

Consider a column storing product categories: Dictionary-Encoded Approach:
  1. Create a dictionary mapping unique values to IDs:
  2. Store these IDs in the forward index instead of the actual values:
Sorted Forward Index Approach (if the column is sorted): Instead of storing an ID for each row, store ranges:
Raw Value Approach: Store the actual values directly:

Types of Forward Indexes

Dictionary-Encoded Forward Index (Default)

The dictionary-encoded forward index uses bit compression to efficiently store dictionary IDs instead of actual values. When to Use:
  • For columns with low to medium cardinality (few unique values)
  • When compression is important to reduce storage requirements
  • For columns that may benefit from inverted indexes
Benefits:
  • Significant space savings for columns with duplicate values
  • Enables efficient inverted index creation
  • Dictionary IDs are bit-packed to the fewest bits that can count the distinct values. General compression codecs don’t apply to dictionary-encoded columns; see Compression.
Trade-offs:
  • Adds one level of indirection (dictionary lookup) when retrieving values
  • Less efficient for columns with high cardinality
  • For string columns, may add padding overhead in the dictionary

Sorted Forward Index

When a column is physically sorted, StarTree Cloud can use a specialized sorted forward index that combines run-length encoding with dictionary encoding. When to Use:
  • For columns that are used as a sort key for the segment
  • When the column has an enabled dictionary
  • For columns frequently used in range filters and sorting operations
Benefits:
  • Maximum compression efficiency
  • Improved data locality (related values are stored together)
  • Automatically serves as both a forward and inverted index
  • Enables efficient binary search for range queries
Requirements:
  • The segment must be sorted by the column
  • Dictionary encoding must be enabled for the column

Raw Value Forward Index

The raw value forward index stores actual values directly instead of dictionary IDs, eliminating dictionary lookup overhead. When to Use:
  • For columns with high cardinality (many unique values)
  • When query performance is more important than storage efficiency
  • For columns rarely used in equality filters
Benefits:
  • Eliminates dictionary lookup overhead
  • Better performance for sequential value scanning
  • No padding overhead for variable-length data
Trade-offs:
  • Typically requires more storage space
  • Does not support inverted indexes
  • Less efficient for random access patterns

Configuration

Dictionary-Encoded Forward Index Configuration

Dictionary-encoded forward indexes are the default. To explicitly configure one:
For multi-value columns with repeated entries, you can enable MV_ENTRY_DICT compression:

Sorted Forward Index Configuration

To enable a sorted forward index for real-time tables, specify the sorted column in the table configuration:
Note:
  • For offline tables, data must be pre-sorted before ingestion. The sortedColumn property is ignored for offline tables.
  • For online tables, only one column should be included. Using an array with more than one column will not result in segments being sorted by all the columns listed in the array.

Raw Value Forward Index Configuration

To enable a raw value forward index, set the encoding type to RAW:

Compression Options

The following compression options are available:
  • PASS_THROUGH: No compression
  • SNAPPY: Balanced compression ratio and speed
  • ZSTANDARD: High compression ratio but slower
  • LZ4: Fast compression with moderate ratio
  • GZIP: High compression ratio but slower

Raw Index Configuration Parameters

  1. compressionCodec: Defines the compression algorithm to use.
  2. deriveNumDocsPerChunk: For variable-length data, determines whether to derive chunk size dynamically (true) or use a fixed value (false).
  3. rawIndexWriterVersion: The on-disk format version used to write the raw index. The default is 6 on clusters created on StarTree Cloud 0.17.0 or later, and 4 on older clusters. See Raw forward index format V6.
  4. targetDocsPerChunk: Sets the target number of documents per chunk.
  5. targetMaxChunkSize: Sets the maximum size of a chunk in bytes.

Raw forward index format V6

V6 is a raw forward index format that makes variable-length columns smaller on disk. Starting with StarTree Cloud 0.17.0, raw forward indexes default to V6 with ZSTANDARD compression on new clusters. Clusters created before 0.17.0 keep writing V4 until StarTree switches their default; contact StarTree support to move a cluster to V6. Each chunk of a raw index starts with a header that locates every value in the chunk. V4 writes cumulative byte offsets in that header, which change on almost every row and compress poorly. V6 writes the size of each value instead. Sizes repeat a lot, so the header compresses well, and the server rebuilds the offsets when it reads the chunk. The values themselves are stored the same way in both versions. Columns it applies to:
  • Single-value raw STRING, BYTES, BIG_DECIMAL, JSON, and MAP columns
  • All multi-value raw columns
Fixed-width single-value columns (INT, LONG, FLOAT, DOUBLE, BOOLEAN, TIMESTAMP) and dictionary-encoded columns don’t change. Columns using the PASS_THROUGH codec don’t benefit, because nothing is compressed. What to expect: In internal tests on realistic string data, both using ZSTANDARD, V6 forward indexes were about 28% smaller than V4, and server CPU dropped by roughly 4–8% on most queries. Combined with the move from LZ4 to ZSTANDARD, raw forward indexes were about 56% smaller. Data with little repetition, such as random strings, shrinks much less. Query results are the same in both formats.

Default compression codec

From 0.17.0, raw forward indexes that don’t set compressionCodec use ZSTANDARD instead of LZ4, on new and existing clusters. ZSTANDARD compresses better but costs more CPU to decompress, which shows most on tiered storage, where every chunk read is a fetch plus a decompress. Raw metric columns stay uncompressed, and MAP columns stay on LZ4.

Which segments change

The defaults apply only to segments built after the change, by ingestion, a segment push, or a minion task. Existing segments keep their format and codec, and restarting or reloading a server doesn’t rewrite them. A table can hold V4 and V6 segments, and LZ4 and ZSTANDARD segments, at the same time. A column that sets rawIndexWriterVersion or compressionCodec in the table config keeps that value. Remove the setting from the column’s forward index config to pick up the cluster default.

Set the version for a column

To use V6 on a cluster that still defaults to V4, set rawIndexWriterVersion to 6 on the column:
To keep a column on V4, set rawIndexWriterVersion to 4 the same way. Only new segments go back to V4; existing V6 segments stay in V6 and keep loading normally.

Disabling Forward Index

To disable a forward index for storage optimization:

Important Considerations When Disabling Forward Index

Disabling a forward index has the following limitations:
  1. Supported only for offline segments: Not applicable to real-time segments.
  2. Range index requirements: If the column has a range index, it must be single-valued and use range index version 2.
  3. Dictionary and inverted index: To support regeneration on reload, both dictionary and inverted index must be enabled.
  4. Multi-value columns: Ordering and duplicate entries in multi-value columns will not be preserved if forward index is regenerated after being disabled.
  5. Query limitations: Columns with disabled forward indexes cannot be used in:
    • SELECT clause
    • GROUP BY or ORDER BY clauses
    • Some aggregation functions (SUM, AVG, etc.)
    • DISTINCT queries
    • Range queries without a version 2 range index