Implement Z-order sorting option in Optimize operation

[wjones127]

Description

Would like to be able to z-order tables. We probably need to implement a z-order sorting function in apache/arrow-rs first.

Use Case

Related Issue(s)

Probably should prioritize #1125 first.

[MrPowers]

It'd be great if someone could grab this. Z ORDERing provides a "killer feature" functionality to end users. I think this functionality will get us a lot of users.

[wjones127]

Design doc for Z-order is here: https://docs.google.com/document/d/1TYFxAUvhtYqQ6IHAZXjliVuitA5D1u793PMnzsH_3vs/edit#heading=h.q7ah6pca24ul

Note that DataFusion has a spilling sort node, which can sort arbitrarily large inputs: apache/datafusion#1568. We should try to reuse that if possible.

However, we should still get optimize working in basic cases first.

[MrPowers]

Here's the suggested interface for Z ORDER: delta_table.optimize.z_order(["col1", "col2"]).

Z Ordering allows users to fully enjoy the power of data skipping.

Even a naive implementation that simply sorts the data would be really useful for the data community. We could release a naive algorithm to start and then swap in a more fancy implementation later.

Even an implementation that simply sorts on one column would be a huge win right now.

[wjones127]

TODO:

• Implement z-order sort key function
• Register function as a scalar UDF
• Implement sorting query that sorts the data by the z-order sort key, then drops the key

z-order sort key function

1. Map each column to a one or more 4-byte (32-bit) value. Variable width columns can map to a configurable number of int32s; for example strings we'll use the first 4 x N bytes of the string.
2. Interleave the bits of the mapped values into a single binary array. That array is the z-order sort key.

[roeap]

I may be completely off here, as I have not yet gone too deep into how the transformation in z-order curves actually work. at least on a high level though I do believe that the arrow-row package - at least conceptually - does something very similar, in that it reduces the multi-columnar representation to one that can be operated on (and sorted) as a single scalar-like value.

Main difference would be that it aims to sort lexicographically, rather then by some other means. Thus (and agian, haven't gone deep on that one) I wonder if we can take inspiration from the arrow row crate and "just" change the kernel that handles the reduction do one dimensional space?

https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-2/