Project 5: Extending Star-Tree Aggregations

Most aggregations in OpenSearch are computed at query time by walking DocValues across every matching document — general, correct, and, for a high-cardinality dashboard query over a billion documents, slow. The star-tree index is the precomputation answer: during indexing, OpenSearch builds a composite index — a tree keyed on a set of dimension fields, with precomputed metric aggregations at each node — so that a matching (filter dims, metric) query is answered by a bounded tree traversal instead of a full DocValues scan. It is one of the highest-leverage pieces of search-performance engineering in the codebase, and it is still young: the set of supported dimension types, metric aggregations, and query shapes that can be resolved against the tree is deliberately incomplete.

This project asks you to extend the star-tree — add support for one aggregation, dimension type, or query shape it does not yet handle — starting from a slice you can scope in a weekend (a resolution gap with a clear "falls back to the default path" symptom) and ending at a real, tested, upstreamable feature.

Note: Read Star-Tree Aggregations and the Aggregations deep dive before you start. This brief assumes you know what a composite index is, what the difference between an ordinal dimension and a numeric dimension is, what star_tree mapping config looks like, and how AggregatorFactories build the query-time aggregation tree. It will not re-derive them.

This is the hardest brief in the portfolio. The star-tree spans the mapping layer, a custom composite-index builder that runs at flush/merge time, a custom Lucene DocValuesFormat, and the aggregation resolution path that decides — per query — whether the tree can answer it. A full new aggregation is a multi-week change. The discipline here, even more than elsewhere, is to scope to a resolution slice: a case the tree could answer but currently does not, where your change is "teach the resolver to recognize it" rather than "build new tree structure."

Problem & motivation

The star-tree was introduced to bound aggregation latency for the dashboard-style workload: many terms + date_histogram filters, a handful of sum/avg/min/max/value_count metrics, run repeatedly over an append-mostly index. When the query's filter dimensions and requested metrics are a subset of the dimensions and metrics the tree was built on, OpenSearch can resolve the aggregation against the tree — reading a precomputed metric at a node — instead of running the normal collector over every matching document.

The gaps that make this a project:

• Not every metric aggregation is supported. The initial set is the "additive" metrics that compose cleanly up a tree (sum, min, max, value_count, and avg as sum/count). Aggregations whose partial results do not trivially merge — or that need a different stored representation — are not yet resolvable. (avg already shows the pattern: you store sum and count and divide at read time. The same "store a decomposable intermediate" trick extends to more aggregations than are currently wired.)
• Not every dimension type is supported. Keyword/ordinal and numeric dimensions work; other field types, ranges as dimensions, or specific date-rounding granularities may not resolve.
• The resolver is conservative. Even for a supported metric, a query can fail to resolve — and silently fall back to the slow default path — because the resolver does not recognize the query shape (an extra clause, a sub-aggregation arrangement, a date_histogram interval the tree was not built for). The symptom is not an error; it is the star-tree silently not being used, which is invisible unless you are looking for it.

That last point is the key to scoping. The cheapest real contribution is to find a query that should resolve against an existing tree but does not, and either make it resolve or make the not-resolving observable so an operator can see the fallback. Both are mergeable; the first is a feature, the second is the diagnostic that the feature work depends on.

Real-world grounding

The star-tree is RFC-driven and tracked by a meta-issue with a live sub-issue list. These are real:

• [RFC] Pre-compute aggregations with a star-tree index — OpenSearch #12498: https://github.com/opensearch-project/OpenSearch/issues/12498
• [META] Star-tree index — issue list — OpenSearch #13875: https://github.com/opensearch-project/OpenSearch/issues/13875
• [Star Tree][Search][RFC] Resolve aggregation via star-tree — OpenSearch #14871: https://github.com/opensearch-project/OpenSearch/issues/14871

Issue #14871 is the one you live in: it is specifically about the resolution path — which aggregations/queries get matched to the tree — and it is exactly the surface where a scoped slice is realistic. The meta-issue #13875 is the durable anchor for "what is built, what is in flight, what is open."

Citation discipline: the star-tree's supported-aggregation list moves fast. Do not cite a sub-issue number you have not opened and read. Run a live search before you scope: is:issue is:open label:"Search:Aggregations" star tree and is:issue is:open "star tree" resolve OR support OR aggregation in opensearch-project/OpenSearch, and read the current checklist in #13875. Link the current sub-issue in your design note; the three issues above are the anchors.

Subsystems you'll touch

Deep dives that cover the surrounding ground: Star-tree engineering chapter · Aggregations deep dive · DocValues and fielddata (the columnar layer the tree precomputes over) · Search execution (where the resolution decision lives) · Refresh/flush/merge (when the builder runs).

Phased plan

The discipline of this project is that Phase 1 produces a diagnostic that is mergeable on its own and that you then need in order to do Phases 3–4 honestly. You cannot tune resolution you cannot observe.

Phase 0 — Build it, build a tree, and watch it resolve (1 day)

Build OpenSearch from source and stand up an index with a star_tree composite mapping.

# In your OpenSearch clone:
./gradlew assemble
./gradlew run        # single node, REST on :9200

# Create an index with a star-tree composite index.
curl -s -X PUT localhost:9200/logs -H 'Content-Type: application/json' -d '{
  "settings": {
    "index.number_of_shards": 1,
    "index.composite_index": true,
    "index.append_only.enabled": true
  },
  "mappings": {
    "composite": {
      "startree": {
        "type": "star_tree",
        "config": {
          "ordered_dimensions": [ { "name": "status" }, { "name": "region" } ],
          "metrics": [ { "name": "bytes", "stats": [ "sum", "max", "value_count" ] } ]
        }
      }
    },
    "properties": {
      "status": { "type": "keyword" },
      "region": { "type": "keyword" },
      "bytes":  { "type": "integer" }
    }
  }
}' | python3 -m json.tool

Note: the exact settings names (index.composite_index, the composite/startree mapping shape, whether append_only is required) change across versions. Grep the mapper test for the current canonical mapping before you trust the snippet above: grep -rn "star_tree\|ordered_dimensions\|StarTreeMapper" server/src/*/java/org/opensearch/index/mapper.

Index some documents, then run an aggregation that should resolve and one that should not, and find out how the codebase tells you which path ran. This is the crux of Phase 0.

# A query that should resolve against the tree (filter on a dimension, sum a metric):
curl -s localhost:9200/logs/_search -H 'Content-Type: application/json' -d '{
  "size": 0,
  "query": { "term": { "status": "200" } },
  "aggs": { "total": { "sum": { "field": "bytes" } } }
}'

Now find the resolution decision in code:

grep -rn "StarTree" server/src/main/java/org/opensearch/search/aggregations | head -40
grep -rn "canUseStarTree\|getStarTreeQueryContext\|StarTreeQueryContext\|supportedStarTree" \
  server/src/main/java/org/opensearch/search | head -40
grep -rn "class StarTreeQueryContext\|StarTreeFilter\|StarTreeValuesIterator" \
  server/src/main/java/org/opensearch/search/startree

Write a one-page capstone-work/resolution-path.md: query → AggregatorFactory → the resolution check → StarTreeQueryContext (resolved) or the normal collector (fallback). With file:line citations. This is your execution-path-mastery artifact and you cannot skip it. You must be able to point at the exact branch where a query is decided to be tree-resolvable or not.

Phase 1 — Make the fallback observable (the scoped, mergeable slice)

Right now the painful truth is that "the star-tree silently did not get used" is nearly invisible. Make it observable. Add a profile/stats signal that says, per aggregation, whether it resolved against the star-tree or fell back — and why it fell back.

The cleanest hook is the profiler. The aggregation profiler (GET /_search?profile=true) already reports per-aggregator timing; add a debug field that records the star-tree decision.

grep -rn "class.*ProfilingAggregator\|AggregationProfiler\|collectDebugInfo\|debug" \
  server/src/main/java/org/opensearch/search/profile/aggregation
grep -rn "collectDebugInfo" server/src/main/java/org/opensearch/search/aggregations/metrics

// In the metric aggregator that can be star-tree-backed (e.g. the sum aggregator), when it has a
// StarTreeQueryContext it records that; when it does not, it records the reason.
@Override
public void collectDebugInfo(BiConsumer<String, Object> add) {
    super.collectDebugInfo(add);
    add.accept("star_tree_used", starTreeQueryContext != null);
    if (starTreeQueryContext == null && starTreeFallbackReason != null) {
        add.accept("star_tree_fallback_reason", starTreeFallbackReason); // e.g. "metric not supported by tree"
    }
}

Set starTreeFallbackReason at the exact resolution branches you mapped in Phase 0 (unsupported metric, dimension not in tree, query shape not recognized, no composite index on the field).

Then a unit/integration test that asserts the profiler reports star_tree_used: true for a resolvable query and a specific star_tree_fallback_reason for one that is not:

// StarTreeAggregationProfileIT (OpenSearchIntegTestCase-based)
public void testProfileReportsStarTreeUsage() throws Exception {
    // ... create the star_tree index above, index docs, refresh ...
    SearchResponse r = client().prepareSearch("logs")
        .setSize(0)
        .setQuery(QueryBuilders.termQuery("status", "200"))
        .addAggregation(AggregationBuilders.sum("total").field("bytes"))
        .setProfile(true)
        .get();
    Map<String, Object> debug = firstAggProfileDebug(r);     // helper that drills into the profile tree
    assertEquals(Boolean.TRUE, debug.get("star_tree_used"));
}

Run the gates:

./gradlew spotlessApply
./gradlew :server:test --tests "*StarTree*"
./gradlew precommit

Why this is the right Phase 1: it is a minimum diff, it is exactly the kind of observability maintainers merge without an RFC, and it forces you to enumerate every resolution branch — which is precisely the map you need to make a branch resolve in Phase 3. A clean "star-tree usage in the profiler" PR is a credible first star-tree contribution and the meta-issue #13875 almost certainly has observability on its checklist.

Phase 2 — Reproduce a silent fallback and characterize it

Using your Phase-1 profiler signal, find a query that you believe the tree should answer but that falls back. Write it down as a failing-expectation test (the profiler reports a fallback today; after Phase 3 it should report star_tree_used: true).

# Compare results AND path for the same logical aggregation, with and without a forced fallback.
# Forcing fallback (so you have a correctness oracle): point the same query at a non-composite index.

Characterize the gap precisely in capstone-work/design.md: is it an unsupported metric, an unsupported dimension type, or a query shape the resolver does not recognize? Each has a different implementation surface and a different difficulty. Pick the one with the smallest surface.

Phase 3 — Make it resolve (the feature)

Now the real work. Choose one, scoped tightly:

Whatever you pick, the non-negotiable is correctness: the star-tree result must equal the default path's result for the same query, byte for byte (these are exact aggregations, not approximations — unlike ANN there is no recall tolerance). Your test asserts equality against the non-composite path.

// The correctness oracle: same data, same query, two indices — one with the star-tree, one without.
assertEquals(
    aggResult("logs-no-startree", query, agg),   // default DocValues path
    aggResult("logs-startree",    query, agg));   // resolved against the tree

Phase 4 — Prove the latency win

A star-tree change that does not move latency is not worth the maintenance surface. Use an OpenSearch Benchmark macro run (or the JMH approach from the perf-regression lab): a fixed aggregation query set, run against the star-tree index vs the same data without a star-tree, on a realistic document count.

query                         path        p50 (ms)   p99 (ms)   docs scanned
sum(bytes) filter status      default        420       1180      120,000,000
sum(bytes) filter status      star-tree        3          9          (tree)
<your newly-resolved query>   default         ...        ...        ...
<your newly-resolved query>   star-tree        ...        ...       (tree)

The headline number is "the newly-resolved query now takes the tree path," shown by the star_tree_used: true from Phase 1 and the latency drop. Both together are the proof.

Deliverables

• capstone-work/resolution-path.md — query → factory → resolution branch → context/fallback, with citations
• capstone-work/design.md — the gap (metric / dimension / query shape), the slice chosen, what you rejected
• Phase 1: a profiler/stats signal for star-tree usage + fallback reason, with a test
• Phase 2: a characterized silent-fallback case, captured as a failing-expectation test
• (Phase 3) the resolver/metric change that makes that case resolve, behind a correctness oracle test
• (Phase 4) an OSB/JMH latency before/after table proving the tree path is taken and faster
• capstone-work/validation.md — ./gradlew spotlessApply precommit output, test commands, seeds, dataset
• A CHANGELOG.md entry under ## [Unreleased]
• An upstreaming decision: a DCO-signed OpenSearch PR for the Phase-1 observability slice, or a written scoped proposal under #14871
• A 500–1000 word write-up: the resolution gap, the path you traced, the correctness argument

Difficulty & time

The star-tree is the deepest subsystem in this portfolio because the data structure, its on-disk format, and the per-query resolution decision are all in scope. Scope ruthlessly to the resolution layer for your first contribution; leave the builder and format for a stretch.

Stretch goals

• Wire the star-tree usage stat into the index/shard stats API (not just the per-query profiler) so an operator can see, fleet-wide, what fraction of aggregations are resolving against trees.
• Add a _validate/query-style explain for star-tree resolution: "this aggregation would/would not resolve against star-tree X, because Y."
• For a decomposable metric you added in Phase 3, add the off-heap builder path so it works under the OffHeapStarTreeBuilder, not just on-heap.
• Reproduce the spirit of #14871 end to end: take one concrete query from that thread that does not resolve today and make it resolve, with the profiler proof and the latency table in the PR.

Evaluation

Self-grade against the 100-point rubric. For this project:

A finished Phase 1 at 90+ is a real, merged observability contribution in OpenSearch's highest-leverage aggregation subsystem — and the foundation for the resolution feature in Phase 3.

How to turn this into a real contribution

1. Start from observability, not the feature. The Phase-1 profiler signal is the upstream target. "The star-tree silently does not get used" is a known operator pain, the change is low-blast-radius, and it needs no new RFC — only a comment under #13875 / #14871.
2. Comment before you code. The star-tree is RFC-governed. Read #12498 and the #13875 checklist, then comment on #14871 with the specific resolution gap you intend to close. Confirm a maintainer agrees it should resolve before you change the resolver — the conservatism may be deliberate.
3. One slice per PR. Observability, then (separately) the resolution/metric change. Never bundle a new resolvable metric with the profiler signal — reviewers will split it.
4. Bring a correctness oracle, not a recall number. Star-tree aggregations are exact. The reviewer's first question is "does it match the default path on every query?" Arrive with that test already in the PR, plus the latency table.
5. DCO applies. This is core OpenSearch: git commit -s, CHANGELOG.md, the backport bot. Get the sign-off email right locally before you push.

If only Phase 1 lands, you have shipped a genuinely useful diagnostic in the most sophisticated aggregation engine OpenSearch has — and you have the map that makes the resolution feature tractable. That is the point of scoping from the observability slice up.