Use Sparse Index

Introduction

Apache Pinot supports different types of indexes such as forward indexes, Bloom filters, hash and sorted inverse dense indexes, or range inverted indexes. Sparse indexes are a hybrid between inverted indexes and Bloom filters designed to speed up queries that filter results using equality (or IN) over a column with very high cardinality, such as columns storing hundreds of thousands of random values, UUIDs, or public IPs. They are a StarTree extension that shines particularly when tiered storage is used.

Description

Sparse indexes group rows into contiguous chunks of a predefined size and classify column values into a fixed number of partitions using one or many hash functions (also called mappers). Finally, it creates a pseudo-inverted index between each partition and each chunk.

When a filter such as column = constant is used, the sparse index looks for the partition where the constant belongs. Then it uses the pseudo-inverted index to obtain the chunks where this partition is found. These are the only row groups where the predicate may evaluate to true, so this information is used to optimize I/O access.

This method is useful when the segment is stored locally, but it is particularly notable when using tiered storage. In this case, instead of downloading the whole forward index, Pinot only downloads the interesting chunks. This significantly reduces the number of bytes downloaded from the cloud object storage.

Sparse indexes are probabilistic at chunk level. They can include extra candidate chunks, which are removed by final predicate evaluation.

Sparse index cannot be created on a column that also has an inverted index enabled, and it is not supported on MAP columns.

Enable sparse indexes

To enable the sparse index StarTree extension, set pinot.server.instance.index.sparse.enabled to true in the server configuration. One way to do so is to use the POST /cluster/configs API from Swagger.

After adding new configurations, restart existing servers.

If the pinot.server.instance.index.sparse.enabled property is not set to true, you can create sparse indexes, but they won’t be used during query execution.

Create sparse indexes

Sparse indexes have to be declared in the table configuration, specifically in the fieldConfigList section. For example, the following JSON defines a sparse index in the deviceId column:

{
  "tableName": "example",
  //...
  "fieldConfigList": [
    //...
    {
      "name": "deviceId",
      "indexes": {
        "sparse": {
          "chunkSize": 1024,
          "partitions": 10000,
          "hashFunctionCount": 3
        }
      }
    }
    //...
  ]
}

Sparse indexes support several configuration options:

Property	Type	Default	Recommended	Affects size	Description
chunkSize	int	1024	128 to 8192	inverse trend, not strictly linear	Chunk size. Must be a power of 2.
partitions	int	10000	depends on cardinality and target FP	generally increases, often sub-linear	Number of partitions used.
hashFunctionCount	int	3	1 to 8	often close to linear	Number of partition mappers (hashes).

chunkSize

Specifies the number of documents that form a chunk.
This option must be a power of 2.
Smaller chunks typically reduce false positives and numEntriesScannedInFilter, but may increase index size.

partitions

Specifies how many partitions values are classified into.
The recommended value depends on expected cardinality and false-positive targets.
Increasing partitions generally increases index size and can improve selectivity.

hashFunctionCount

Specifies the number of function mappers used.
Larger values improve selectivity but increase index lookups and index size.
In practice, index size often grows close to linearly with this parameter.

Extra options

The following configurations should only be used in extremely unique use cases. Typically, we do not recommend configuring these options:

seedGenerator

An integer used as a seed to later generate seeds used to generate each hash function. Any integer value is valid, and they produce similar values and do not affect the index size. This option should only be defined in the strange case that collisions are very frequent in one or many hash functions.

mapperId

A string that identifies the type of hash function used. At this moment, the only valid value is murmur.

Quick tuning workflow

1. Pick high-cardinality columns queried with = or IN.
2. Benchmark representative queries and track:
   • timeUsedMs
   • numEntriesScannedInFilter
   • numDocsScanned
3. Tune in this order:
   • chunkSize first
   • partitions second
   • hashFunctionCount third
4. Compare p50/p95 latency, scan metrics, and index size.
5. Reload/rebuild segments after configuration changes.

Quick formula intuition

Let $R$ be rows, $c$ chunk size, $m$ partitions, $k$ hash count, and $v$ average values per row.
Define $N_c = \lceil R / c \rceil$ and $n = c \cdot v$.

$$p_{\mathrm{fp},\mathrm{chunk}} \approx \left(1 - e^{-n/m}\right)^k$$

Here, $p_{\mathrm{fp},\mathrm{chunk}}$ is the approximate probability that a chunk is selected by sparse index even when it does not contain the target value (chunk-level false positive).

$$E_{\mathrm{entries}} \approx N_c \cdot k \cdot m \cdot \left(1 - e^{-n/m}\right)$$

Here, $E_{\mathrm{entries}}$ is an index-size proxy: the expected number of sparse index entries in the segment. Larger $E_{\mathrm{entries}}$ usually means a larger on-disk sparse index.

For formulas and deeper sizing guidance, see Sparse Index.