rkrishn7 opened a new issue, #27498:
URL: https://github.com/apache/datafusion/issues/27498

   ### 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 `Row`s, 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.
   
   ```rust
   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 (#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


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to