Skip to content

feat(array): add IsCompoundSorted agg fn - #10661

Open
joacoc wants to merge 12 commits into
vortex-data:developfrom
joacoc:footer-sort-key
Open

feat(array): add IsCompoundSorted agg fn#10661
joacoc wants to merge 12 commits into
vortex-data:developfrom
joacoc:footer-sort-key

Conversation

@joacoc

@joacoc joacoc commented Oct 21, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

Adds a new agg fn to check a compound sort key and store the result in the file stats.

Summary

The current implementation adds a new aggregate function called IsCompoundSorted that lets the user check whether rows are sorted by a declared compound key. It uses the same sort order as IsSorted, so it has the same limitations (only ASC with nulls first.)

Changes

  • Adds a new IsCompoundSorted agg fn and its options
  • Benchmarks

API Changes

@joseph-isaacs

joseph-isaacs commented Oct 29, 2026

Copy link
Copy Markdown
Contributor

We need not change the footer, but use the new nested footer stats + AggFns

@joacoc

joacoc commented Oct 29, 2026

Copy link
Copy Markdown
Contributor Author

@joseph-isaacs yeap, I just cleaned it up. I already have the new AggFn, but I'm still refining it a bit

@joacoc

joacoc commented Oct 30, 2026

Copy link
Copy Markdown
Contributor Author

Ok, so a bit of an overview, the options for the aggfn are like this:

pub struct SortOrderOptions {
    pub fields: Vec<(FieldName, SortDirection)>
}

The sort uses aggregate_fn::fns::is_sorted::is_sorted, so it is limited to ASC. But I kept SortDirection for both directions just in case that in the future DESC is supported. One thing I could add is strictness, right now it defaults to strict = false, but we could add an option to SortOrderOptions and let the user declare strictness.

I still have to do some checks around the writer and bench.

@joacoc
joacoc marked this pull request as ready for review October 30, 2026 16:26
@joacoc joacoc mentioned this pull request Oct 30, 2026
Closed
@joacoc joacoc changed the title feat(file): add sort keys to footer feat(array): add IsCompoundSorted agg fn Oct 31, 2026
connortsui20 added a commit that referenced this pull request Nov 2, 2026
@connortsui20
Update the PR state in the research notes for 2026-11-02
29a1fff 
U2, U3, U4, U6, U7 and U8 merged on 2026-11-02 in #11012, #11014 and
#11016, and the DataFusion literal fix #11067 merged right after U2. So
order constraint 1 holds, and phase 1 starts from develop. The graph
shows these nodes as merged, and parts 2 and 4 name the PR that fixed
each finding.

#10953 now keeps i32 days and widens only the days part to i64 when a
value does not fit. It has no review, and it conflicts with the
DateTimeParts compare kernel that U2 changed. #11056 still waits on its
request for changes. #10661 replaces the closed #10482 for file sort
statistics.

In the type roadmap, only the N1 sentence changes.

Signed-off-by: Connor Tsui <[email protected]>
@connortsui20 connortsui20 mentioned this pull request Nov 2, 2026
Open
12 of 49 tasks
joseph-isaacs
joseph-isaacs reviewed Nov 3, 2026
View reviewed changes
Comment thread docs/specs/file-format.md Resolved
connortsui20 added a commit that referenced this pull request Nov 3, 2026
@connortsui20
Name the nodes of the extension dependency graph after the PR plan of #…
ea1ac85 
…11114

Each node of the graph is now one PR, with the ID that the PR plan in #11114 uses. The claims node points to #11115, the old phase 1 node splits into NU and CL, and the shared pushdown and the lift rule become separate low-priority nodes. The graph also links #10661, #10686 and #10793 as open PRs to coordinate with.

Signed-off-by: Connor Tsui <[email protected]>
joacoc added 11 commits November 10, 2026 11:07
@joacoc
(feat) add sort keys to footer
9b439a5 
Sort keys indicate that a file is lexicographically
sorted. The current implementation writes and reads
sort keys present in a footer.

One currently missing piece is that it doesn't
assert that the rows are truly sorted, so a user
could write an unsorted file and declare in the footer
that the rows are sorted.

To add this assertion, we could use
an agg_fn that checks multiple columns at the same time
and validates that the rows are sorted across all chunks.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) docs changes
fb1f1b7 
Unintended changes.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) docs removed line
b0d6bb8 
Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) rename footer SortKey type to SortKeySpec for consistency
a404dde 
Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(feat) accept multiple sort keys
d6adee3 
When reviewing the code, I noticed that footer
properties are always vectors, so I stopped
to think about whether a vec of sort keys would
make sense, and it turns out that yes, even
DataFusion can support multiple sort keys.
So what I did was just update it from a single
sort key to multiple valid sort keys.

Also added SortKey and SortKeyRef as type aliases.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) cleanup vortex-file footer
db18788 
The previous work was incorrectly writing
the sort keys in the footer as a spec rather
than writing them as an aggregate function.
This commit cleans up the previous incorrect work.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(feat) add sort order aggregate fn
d0e8df3 
This commit adds the SortOrder aggregate fn
into the `vortex-array` crate.

The new `SortOrder` basically reuses the sort
already implemented for fastpaths, so it has
the same limitations (only ASC and nulls first).

The `SortOptions` are ser/de using protobuf,
and there is no support for strictness, but I
could simple be added.

I tried to add enough documentation to understand
how the pair check works.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(bench) add bench to measure sortedness/pairness checks
f0e0262 
I think the most important to measure is for utf-8 and
the single column bench to assert that not much on top
of the fastest case (single column/field sort),
similar to `IsSorted`.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) test file write, and add the aggfn to the unstable edition
73a1ad9 
Similar to other new agg fns, they need to be
added to the unstable edition.

Also, this commit adds a test to check that the aggregate
fn is correctly written into the file stats, but it is
not present in the layout zones.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(rename) SortOrder to IsCompoundSorted
b0e1e3e 
Given that already exists `IsSorted` and
`IsStrictSorted` I found appropiate to call it
`IsCompoundSorted`.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) zed md autoformat
51f6866 
Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc
(fix) pending TODO, about moving the root entry check
b3df4b7 
There was one pending TODO about where to check whether the root entry
was compatible with the `IsCompoundSorted` agg fn. This is just a fix
for that, the check now lives in `FileStatsAccumulator::try_new`.

If the root has no entry for the stats, the write should err. Otherwise
the stat won't be written and the user won't notice. So, if the user
requests `IsCompoundSorted` with legacy stats, or with a non-nullable
root (which has no root entry), the write now errs.

Signed-off-by: Joaquin Colacci <[email protected]>
@joacoc

joacoc commented Nov 10, 2026

Copy link
Copy Markdown
Contributor Author

@joseph-isaacs, rebased and also fixed a TODO I had pending.

@joacoc joacoc mentioned this pull request Nov 10, 2026
Open
@joseph-isaacs joseph-isaacs mentioned this pull request Nov 13, 2026
Merged

This branch has not been deployed

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

Reviewers

@joseph-isaacs joseph-isaacs joseph-isaacs approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@joacoc @joseph-isaacs