Star-Tree Indexes and Aggregation Acceleration

Most aggregations in OpenSearch are computed at query time by scanning doc values, bucketing, and reducing (see Aggregations). That is flexible — any field, any filter, any nesting — but the cost scales with the number of matching documents. A terms over a billion-doc index that touches every document does a billion doc-value reads, every time, even if the answer is the same hourly dashboard tile you have rendered a thousand times.

The star-tree index attacks this from the other direction: it pre-aggregates during indexing. You declare a set of dimensions (the fields you group/filter on) and metrics (the fields you sum/count/min/max/avg), and OpenSearch builds a compact tree, inside each Lucene segment, whose nodes already hold the rolled-up metric values for every dimension combination. At search time, an eligible aggregation is answered by walking the tree instead of scanning documents — turning an O(matching-docs) operation into something close to O(tree-depth). The result is bounded, predictable latency for the aggregation shapes you planned for.

This is a composite index — it does not change your stored documents or your normal query path. It is an opt-in acceleration structure that the search layer auto-detects and uses when the request matches. It builds on DocValues and Fielddata (the tree's metric values are columnar, doc-value-backed) and accelerates the framework in Aggregations.

The design is tracked across three real RFCs/metas — read them before you touch the code, because they carry the rationale and the scope boundaries:

• [RFC] Pre Compute Aggregations with Star Tree index — #12498
• [META] Star Tree Index issue list — #13875
• [Star Tree][Search][RFC] resolve aggregation via star tree — #14871

After this chapter you can: explain the star-tree data structure and the role of the star node; write a composite/star_tree mapping; describe how the tree is built as part of a segment; trace how the search path detects and resolves an eligible aggregation against the tree; and reason about the storage-vs-latency trade-off and the (deliberately bounded) set of supported aggregations.

Note: The star-tree comes from the Apache Pinot lineage of the same name. The OpenSearch implementation is its own thing, but if you have read the Pinot star-tree paper the vocabulary (dimensions, the special "star" record) will be familiar.

The data structure

A star-tree is a prefix tree over an ordered list of dimensions. Pick an order for your dimensions — say [status, region]. Every path from the root down to a leaf fixes a prefix of dimension values; the node at the end of that path stores the aggregated metrics for all documents matching that prefix.

Concretely, for dimensions status then region and a metric sum(bytes):

                       root
            ┌───────────┼───────────────┐
       status=200    status=404      status=*      (the STAR node)
        ┌────┴────┐      │            ┌────┴────┐
     region=us  region=eu  region=*  region=us  region=*
        │          │        │          │          │
   sum=1.2e9   sum=8.0e8  sum=2.0e9  sum=3.0e9  sum=5.0e9

Two ideas do the heavy lifting:

1. Sorted, ordered dimensions. Documents are sorted by the dimension order, so building the tree is a grouped roll-up, and querying is a descent that narrows the candidate set one dimension at a time.

2. The star node (*). At each level, in addition to the children for each concrete value, the tree holds a special star child that aggregates across all values of that dimension. This is what makes a query that does not filter on a dimension cheap: instead of summing over every region=… child, you jump to region=*, which already holds the cross-region roll-up. The star node is the whole trick — it turns "no filter on this dimension" into a single edge.

flowchart TD
    Root["root"] -->|status=200| S200["node: status=200"]
    Root -->|status=404| S404["node: status=404"]
    Root -->|status=*| SSTAR["STAR node: status=* (all statuses)"]
    S200 -->|region=us| L1["leaf: sum,count for 200/us"]
    S200 -->|region=eu| L2["leaf: 200/eu"]
    S200 -->|region=*| L3["STAR leaf: 200/all-regions"]
    SSTAR -->|region=us| L4["leaf: all-status/us"]
    SSTAR -->|region=*| L5["STAR leaf: GRAND TOTAL"]

The bottom-right region=* under status=* is the grand total — the answer to "sum(bytes) over the whole segment with no filters" in one lookup.

max-leaf-docs and the size bound

A naive tree would create a star-node path for every dimension combination, which explodes. The build is bounded by max_leaf_docs (the spec calls it the max-leaf-docs threshold): a node is only split further while the number of documents under it exceeds the threshold. Below it, the node keeps the documents as a small ordered run and aggregates them on the fly during the (tiny) descent. This caps the number of nodes, trading a bounded amount of per-query work for a bounded index size. Tuning it is the central storage-vs-latency knob (see the trade-off table).

The mapping: a composite index field of type star_tree

You declare the star-tree in the index mapping as a composite field. It is not a field you index values into — it is a derived structure over other fields. Exact key names evolve across versions, so create one and read it back, but the shape is:

PUT /logs-startree
{
  "settings": {
    "index.number_of_shards": 1,
    "index.composite_index": true,
    "index.append_only.enabled": true
  },
  "mappings": {
    "composite": {
      "request_stats": {
        "type": "star_tree",
        "config": {
          "max_leaf_docs": 10000,
          "ordered_dimensions": [
            { "name": "status" },
            { "name": "region" }
          ],
          "metrics": [
            { "name": "bytes", "stats": ["sum", "max", "min", "value_count"] },
            { "name": "latency_ms", "stats": ["avg"] }
          ]
        }
      }
    },
    "properties": {
      "status":     { "type": "integer" },
      "region":     { "type": "keyword" },
      "bytes":      { "type": "long" },
      "latency_ms": { "type": "float" }
    }
  }
}

A few things that bite people and are worth internalizing:

• Append-only. Star-tree indices are designed for immutable, append-only data (logs, metrics). Updates/deletes do not fit the precomputed-roll-up model cleanly, which is why the feature is gated behind append-only settings. Check the current gating in your branch — grep below.
• Ordered dimensions. The order matters for which queries are cheap; a filter on the first dimension is the cheapest descent. Order dimensions by how often you filter on them.
• Bounded stats. avg is stored as sum + value_count and divided at read time (the same associative-decomposition trick the normal avg reduce uses). You cannot ask the tree for a stat you did not declare.

cd ~/src/OpenSearch
# The mapper + config parsing for the composite/star_tree field.
grep -rln "star_tree\|StarTree\|composite" \
  server/src/main/java/org/opensearch/index/mapper/ | head
grep -rn "max_leaf_docs\|ordered_dimensions\|StarTreeMapper\|CompositeMappedFieldType" \
  server/src/main/java/org/opensearch/index/mapper/ | head -20
# The feature flag / settings that gate it.
grep -rn "composite_index\|STAR_TREE\|isCompositeIndexEnabled\|append_only" \
  server/src/main/java/org/opensearch/index/ | head -20

Built during indexing, as part of the segment

The star-tree is not a separate file you build with an admin API. It is written inside the Lucene segment, by a composite-index DocValuesConsumer that runs at flush and at merge, exactly when the rest of the segment's doc values are written (see Refresh, Flush, Merge). That is why it is "free" at query time and why it is immutable: it shares the segment's lifecycle.

The build, per segment:

1. Read the declared dimension and metric doc values for every document in the segment.
2. Sort the documents by the ordered-dimension tuple.
3. Aggregate to produce the leaf records, then build star-node records bottom-up, splitting only while a node exceeds max_leaf_docs.
4. Serialize the tree (node array + the aggregated metric doc values) into the segment as additional files written through the composite codec/format.

flowchart LR
    Flush["segment flush / merge"] --> Read["read dimension+metric docvalues"]
    Read --> Sort["sort docs by ordered dims"]
    Sort --> Rollup["aggregate -> leaf records"]
    Rollup --> Star["build star nodes bottom-up (bounded by max_leaf_docs)"]
    Star --> Write["write tree + metric docvalues into the SEGMENT"]

Because it is built at flush and merge, the tree is always consistent with the segment it lives in; merging two segments rebuilds the tree over the merged docs. That also means the cost shows up as indexing/merge CPU and disk, not query CPU — you pay once at write time for every read after.

cd ~/src/OpenSearch
ls server/src/main/java/org/opensearch/index/compositeindex/
# The builder + the per-segment writer.
grep -rln "StarTreeBuilder\|StarTreeDocValuesConsumer\|OnHeapStarTreeBuilder\|OffHeapStarTreeBuilder" \
  server/src/main/java/org/opensearch/index/compositeindex/ | head
grep -rn "build(\|appendStarTreeDocument\|max_leaf_docs\|StarTreeField" \
  server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/ | head -20
# The codec/format that actually writes it into the segment files.
grep -rln "Composite99\|StarTree.*Format\|Composite.*Codec\|DocValuesFormat" \
  server/src/main/java/org/opensearch/index/codec/composite/ | head

Note: Names like Composite99Codec / OnHeapStarTreeBuilder are version-stamped and will drift — the grep -rln above finds the real site in your checkout. Do not hard-code a class name from this page into a PR description.

The search path: detection and resolution

This is the part that makes the feature transparent. You do not add a "use the star-tree" flag to your query. The search layer inspects the aggregation request and decides whether the star-tree can answer it; if so, it resolves the answer from the tree; if not, it falls back to the normal doc-value scan. RFC #14871 is the canonical description of this resolution logic.

An aggregation is star-tree-eligible only if all of these hold:

The resolution, conceptually:

flowchart TD
    Req["aggregation request"] --> Check{"all dims/metrics declared?<br/>supported agg shape?"}
    Check -- no --> Scan["normal docvalue scan (default path)"]
    Check -- yes --> Pick["pick star-tree values source"]
    Pick --> Desc["descend tree: concrete child for filtered dim,<br/>STAR child for unfiltered dim"]
    Desc --> Emit["read precomputed metric(s) at the resolved node(s)"]
    Emit --> Reduce["feed into the normal InternalAggregation reduce"]

The elegant part: the resolved metric values are fed into the same InternalAggregation reduce you already know from Aggregations. Per-segment, the star-tree produces a partial; the shard- and coordinator-level reduce are unchanged. The star-tree only replaces the collection step, and only when eligible. That is also why it composes with concurrent segment search — each segment slice either uses its star-tree or scans, then the normal slice/coordinator reduce runs.

cd ~/src/OpenSearch
# The values source / resolution that decides to use the tree.
grep -rln "StarTree\|CompositeIndex\|getStarTreeValues\|supportsStarTree" \
  server/src/main/java/org/opensearch/search/aggregations/ \
  server/src/main/java/org/opensearch/search/startree/ 2>/dev/null | head
grep -rn "StarTreeQueryHelper\|StarTreeFilter\|canUseStarTree\|StarTreeValuesSource" \
  server/src/main/java/org/opensearch/search/ | head -20

Worked example: which queries hit the tree

Given the mapping above (ordered_dimensions = [status, region], metric sum(bytes)):

Trade-offs

Supported aggregations are deliberately bounded to those that decompose into associative roll-ups: sum, min, max, value_count, avg (as sum/count), and the bucketing (terms, range, date_histogram on a declared dimension) that maps to tree descents. Sketch-based aggs (cardinality via HyperLogLog++, percentiles via t-digest) and anything reading an undeclared field are not supported and silently fall back — which is the correct behavior, but means a mis-declared mapping yields no speedup with no error. Check the current supported set in your branch rather than trusting this list:

cd ~/src/OpenSearch
grep -rn "SUPPORTED\|MetricStat\|StarTreeQueryHelper\|isSupported" \
  server/src/main/java/org/opensearch/search/startree/ \
  server/src/main/java/org/opensearch/index/compositeindex/datacube/ 2>/dev/null | head -20

Warning: Because falling back is silent, "the star-tree isn't speeding anything up" is a real and common report. Always confirm the tree was actually used (profile / a star-tree stat) before concluding it doesn't help — see Validation.

Trace it yourself

# 0. Build/run a node with the composite-index feature enabled (check your version's flag).
cd ~/src/OpenSearch
grep -rn "composite_index\|STAR_TREE_INDEX\|FeatureFlags" \
  server/src/main/java/org/opensearch/common/util/FeatureFlags.java | head

# 1. Create the index (mapping above), bulk-load enough docs to force several segments.
curl -s -XPUT 'localhost:9200/logs-startree' -H 'Content-Type: application/json' \
  --data-binary @startree-mapping.json
for b in 1 2 3 4 5; do
  for i in $(seq 1 5000); do
    printf '{"index":{}}\n{"status":%s,"region":"r%s","bytes":%s,"latency_ms":%s}\n' \
      "$((200 + (RANDOM%3)*100))" "$((RANDOM%5))" "$((RANDOM%100000))" "$((RANDOM%500))"
  done | curl -s -H 'Content-Type: application/x-ndjson' \
      -XPOST 'localhost:9200/logs-startree/_bulk?refresh=true' --data-binary @- >/dev/null
done
curl -s 'localhost:9200/_cat/segments/logs-startree?v'   # confirm multiple segments

# 2. Run an ELIGIBLE agg and an INELIGIBLE agg; compare took.
curl -s 'localhost:9200/logs-startree/_search?pretty' -H 'Content-Type: application/json' -d '
{ "size":0, "aggs": { "by_status": { "terms": { "field":"status" },
    "aggs": { "b": { "sum": { "field":"bytes" } } } } } }' | grep '"took"'

curl -s 'localhost:9200/logs-startree/_search?pretty' -H 'Content-Type: application/json' -d '
{ "size":0, "aggs": { "uniq": { "cardinality": { "field":"region" } } } }' | grep '"took"'  # falls back

# 3. profile=true — look for a star-tree collector/values source in the breakdown.
curl -s 'localhost:9200/logs-startree/_search?pretty' -H 'Content-Type: application/json' -d '
{ "profile":true, "size":0, "aggs": { "b": { "sum": { "field":"bytes" } } } }' \
  | grep -i "star\|StarTree\|collector" | head

# 4. Read the owning code.
grep -rln "StarTreeBuilder" server/src/main/java/org/opensearch/index/compositeindex/ | head
grep -rln "StarTreeQueryHelper\|canUseStarTree" server/src/main/java/org/opensearch/search/ | head
./gradlew :server:test --tests "*StarTree*" 2>&1 | tail -15

Common bugs and symptoms

Validation: prove you understand this

1. Draw a star-tree for dimensions [a, b] and metric sum(m), and point to the single node that answers "sum(m) over everything with no filter." What is that node called and why does it make a no-filter query O(1)?
2. Explain what max_leaf_docs bounds, and the storage-vs-latency consequence of making it very small vs very large.
3. List the exact eligibility conditions for an aggregation to be resolved by the star-tree, and give one agg that is not supported and why it falls back.
4. Where in the segment lifecycle is the tree built, and why does that make it immutable and "free" at query time? Tie it to flush and merge.
5. A teammate says "I added a star-tree but my dashboard is the same speed." List the three things you would check (in order) and the one command that proves whether the tree was used.
6. Explain why a star-tree-resolved aggregation can still feed the unchanged InternalAggregation.reduce, and how it composes with concurrent segment search.

Next: Tiered Caching, or the star-tree aggregation capstone.