Tracking Issue: Garbage Collection

[connortsui20]

This is a tracking issue for adding the ability to express precise garbage collection in Vortex.

Whether this is a new Array node or a free-standing function, we will want this to live in vortex-array as all of the relevant types to this live there as well.

Motivation

We have several physical encodings (canonical and non-canonical) that can store "garbage" or unreferenced values. These are:

• ListView: Views can have gaps of unreferenced elements.
• VarBinView: Similar to ListView, buffers might not be fully utilized.
• Dict: There can be unreferenced dictionary values
• DenseUnion (new): stores index offsets into child array which need to be sorted, but not necessarily monotonically increasing (there can be gaps after a filter).

For ListView, we have a bunch of rebuild* methods that are free-standing functions on the ListView type. We generally just call this right before compression, but it is hard to express "garbage collect the list view at this arbitrary point in time" during execution of the array tree. I believe that VarBinView has a similar compaction method.

Dict and DenseUnion have it even worse because they are not canonical types, which means that we basically have zero control over when they can get compacted.

To me, it seems like the only solution here is to have some sort of GarbageCollectArray node in the array tree.

Design

I think that a GarbageCollect array is warranted here, as that allows us to reorder the operation in the array tree. Likely, we always want to "lift" it up to the top of the execution so that we can perform the garbage collection after all lazy operations have had a chance to reduce the work.

We should be able to push down every single operation that has the same input dtype through this array. For example, if I have a list_contains function, we can push that through the garbage collect so that we do not need to do the expensive operation for nothing. And then since the output dytpe of list_contains is a boolean array, the GarbageCollect node becomes a no-op.

Steps

• Initial implementation
• Documentation
• Public API stabilization

Unresolved questions

• Is it possible to have the same optimization / reordering behavior without expressing this operation as an Array node?

Implementation history

• Feature: add listview rebuild + cleanup #4819
• Feature: ListView rebuilding strategies #4830
• Performance: ListViewArray zero-copyable to ListArray optimizations #5129

[joseph-isaacs]

What is the decision procedure to add this node to the tree? What owns that.

[connortsui20]

It would have to be an optimization step probably? As soon as we detect one of these encodings in the array tree, just insert this node directly above it

[robert3005]

The thing that has to be worked out here is when you materialise this node and when do you get rid of it. I think the consumer of the List/Union/Utf8 array will have to figure out whether to gc or not gc. How does this node optimizes the decision making process?

[connortsui20]

I think the List/Union/Utf8 array would probably default to always inserting a GC node on top of itself, and then after all pushdown has happened, this is just a normal execution tree. And I don't think it has to be a "smart" decision making process, I think we basically always want to pull up this node to the top of the array tree.

If it is at the top of the array tree, either the input underneath it is a List/Union/UTF8 array and we just do the compaction (for example, right before export to arrow or duckdb), or it is of a different type and then it become a no-op (it would just remove itself during execution)