You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "Rich-T-kid (via GitHub)" <gi...@apache.org> on 2026/08/04 16:21:53 UTC

[I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Rich-T-kid opened a new issue, #24089:
URL: https://github.com/apache/datafusion/issues/24089

   ### Is your feature request related to a problem or challenge?
   
   see context here 
   - https://github.com/apache/datafusion/pull/23187#discussion_r3688359028
   
   `DictionaryGroupValuesColumn::take_n` emits the first n groups and rebuilds the remainder in-place. Every call hashes all surviving distinct values from scratch to reconstruct value_dedup, making repeated partial emissions O(G² / batch_size) over the lifetime of a query, where G is the total number of distinct values seen. Additionally, `arrow::compute::take` does not compact the backing storage for Utf8View, BinaryView, or nested dictionary value arrays; the rebuilt column retains a reference to the full original allocation rather than releasing memory proportional to the dropped groups. Under a high-cardinality dictionary key with frequent spill-driven partial emissions (e.g. streaming aggregation with a large fan-out), this combination causes both CPU and peak RSS to grow super-linearly with group count.
   
   ### Describe the solution you'd like
   
   see context here 
   - https://github.com/apache/datafusion/pull/23187#discussion_r3708572028
   
   
   Two targeted improvements:
   
   1. Incremental dedup table on rebuild. Instead of re-hashing all surviving inner slots after a take_n, retain a dirty-flag or generation counter on value_dedup and only remove the entries that were fully emitted (i.e. whose inner_slot is not referenced by any remaining group). This keeps the rebuild cost proportional to the number of emitted distinct values rather than the number of surviving ones, reducing amortized complexity from O(G²/B) to O(G).
   2. Storage compaction for view and nested types. After calling `compute::take` to subset the inner values array, explicitly compact Utf8View / BinaryView columns by calling `StringViewArray::gc` (or equivalent) to release unreferenced buffers. For nested dictionary values, apply the same compaction recursively. This bounds peak memory to the live distinct-value set rather than the union of all values ever seen in a partition.
   
   ### Describe alternatives you've considered
   
   Keeping the current implementation. This is not ideal due to performance issues mentioned above.
   
   ### Additional context
   
   - https://github.com/apache/datafusion/issues/23993
   - https://github.com/apache/datafusion/pull/23187
   - https://github.com/apache/datafusion/pull/23523


-- 
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: github-unsubscribe@datafusion.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5307951577

   > @saadtajwar #23187 is not merged  šŸš€ 
   
   Sweet thanks for the update! Starting on this now!


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5181805688

   cc @saadtajwar since you expressed in https://github.com/apache/datafusion/issues/23921#issuecomment-5097889953


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5232676580

   Note just for visibility: will start on this when #23187 is merged in :) 


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5358225307

   @Rich-T-kid & @kumarUjjawal - ready for review #24476 ! Thanks in advance for your feedback!
   
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5182093690

   Thanks @Rich-T-kid ! Happy to look into this 😁 


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5182100236

   take


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [I] Optimize take_n on DictionaryGroupValuesColumn [datafusion]

Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on issue #24089:
URL: https://github.com/apache/datafusion/issues/24089#issuecomment-5307947191

   @saadtajwar #23187 is not merged  šŸš€ 


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org