Skip to content

Add lookup-only GroupValues::find #27498

Open

Description

@rkrishn7

Is your feature request related to a problem or challenge?

GroupValues::intern returns the group id of each input row, assigning the next id to every key not yet stored. That is all in-tree aggregation needs: each batch is interned and then accumulated, so every key belongs in the table. A caller that is about to insert can also tell new groups from existing ones, because group ids are dense and increasing: with let before = group_values.len() before intern, a row's group is new iff groups[row] >= before.

A caller that only needs to probe a GroupValues has no cheap option. Probing with intern stores every miss, and GroupValues can't remove a single group afterwards.

This came up while maintaining long-lived, TTL-bounded state with GroupValues. Such state needs to drop expired groups, and today there's no cheap way to compact a GroupValues. I first proposed selective retention in #24603, but after the discussion there I don't think it's the right path.

One way compaction can be avoided is by spreading the state over several GroupValues instances and dropping each one whole once it expires. That only works if the caller can check, cheaply and without inserting, which keys of a batch an instance already holds. Checking with intern instead:

  • stores every miss in the instance, where it stays until the whole instance is dropped;
  • makes an instance that should only be read keep growing (rehashing and reallocating);
  • leaves the caller tracking which group ids are real and which were only probed.

The other workaround is a separate key index (a HashSet of Rows, say) next to each GroupValues. That stores every key twice and repeats the hashing and comparison work GroupValues already does.

Describe the solution you'd like

A lookup that never inserts. It seems like a generally useful extension as find is the read-only counterpart of intern, for any caller that wants to probe a GroupValues without changing it.

pub trait GroupValues: Send {
    /// Looks up the group id for each input row of `cols` without assigning
    /// new group ids.
    ///
    /// When the function returns, `groups` has been cleared and contains one
    /// entry per input row: `Some(group_id)` if the value is already stored
    /// and `None` otherwise. Stored values and group ids are unchanged.
    fn find(&mut self, cols: &[ArrayRef], groups: &mut Vec<Option<usize>>) -> Result<()>;
}

&mut self lets implementations reuse their hashing scratch buffers, as intern does. Each built-in implementation can share its probe path with intern and skip the insert.

We can make it a required method (a breaking change for custom GroupValues), or give it a default that returns not_impl_err!. A supports_find() flag seems unnecessary since every built-in implementation can support it, and a flag would be a second method to keep in sync with find that tells the caller nothing the error doesn't.

Describe alternatives you've considered

  • Compare len() before and after intern. This identifies groups that existed before the batch, but it inserts, so it only fits an instance the caller is writing to anyway.
  • Arbitrary removal (Add arbitrary group retention for grouped aggregation state #24603). With retain_groups, a caller could intern and then remove the misses. That's two operations and a rebuild where one read suffices, and it depends on an API that is hard to make cheap for every accumulator.
  • A separate key index per instance. This duplicates every key and its hashing, as described above.

Additional context

No response

Willingness to contribute

I plan to contribute to this feature independently

Activity

  1. added theissue type on Nov 17, 2026
  2. rkrishn7 commented on Nov 17, 2026

    @rkrishn7
    ContributorAuthor

    take

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

enhancementNew feature or request

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

    Sponsor
    SponsoredKunjungi sekarang
    Promo