infer parquet file order from metadata, write order in ParquetSink #19433

adriangb · 2025-12-21T05:00:00Z

The idea here is to use the metadata in parquet files to infer sort orders, thus it is not required for users to specify it manually.

This should probably be split into multiple PRs:

Record sort order when writing into a table created as WITH ORDER
Refactor PartitionedFile construction
Collect ordering during statistics collection

adriangb · 2025-12-21T05:00:16Z

@zhuqi-lucas you may be intersted in this

zhuqi-lucas · 2025-12-21T08:35:36Z

Great work @adriangb, i will review it next week !

zhuqi-lucas · 2025-12-23T08:54:15Z

datafusion/catalog-listing/src/table.rs

+    // Check that all orderings are identical
+    let first = all_orderings[0];
+    for ordering in &all_orderings[1..] {
+        if *ordering != first {


Do we want to support more relax cases, for example to use similar to:

datafusion/datafusion/physical-expr/src/equivalence/properties/mod.rs

Line 533 in e6faacb

pub fn ordering_satisfy(

zhuqi-lucas · 2025-12-23T08:55:40Z

datafusion/core/tests/physical_optimizer/filter_pushdown/mod.rs

  SELECT 1372708800 + value AS t
  FROM generate_series(0, 99999)
-  ORDER BY t
+  ORDER BY t + 1


Why this changes to t+1?

Because it was picking up the ordering and causing even less data to be read 😆

zhuqi-lucas · 2025-12-23T09:00:13Z

datafusion/sqllogictest/test_files/parquet.slt


 statement ok
 DROP TABLE t;
+


It seems only test ASC NULLS FIRST. Better to add test cases for:
- DESC ordering
- Multi-column ordering
- Files with no ordering metadata

zhuqi-lucas · 2025-12-23T09:05:00Z

datafusion/physical-expr-common/src/sort_expr.rs

    }

+    /// Checks if `other` is a prefix of this `LexOrdering`.
+    pub fn is_prefix(&self, other: &LexOrdering) -> bool {


I meet some similar topic for the sort pushdown, and submitted a PR, i prefer to use eq_properties to do similar things, it will handle more cases after my try in my internal project.

The ordering_satisfy will handle more cases than prefix.

I gave it a review - looks nice! I can sequence this behind your PR if needed.

zhuqi-lucas · 2025-12-23T09:06:01Z

Great work @adriangb i left some initial review comments, i will review again for more details.

adriangb · 2025-12-31T01:07:31Z

@zhuqi-lucas ping to take a look at this when you get a chance. Thanks!

zhuqi-lucas

LGTM, thank you @adriangb for the great work, left some comments and question.

zhuqi-lucas · 2025-12-31T06:03:57Z

datafusion/catalog-listing/src/table.rs

+            if let Some(ordering) = &file.ordering {
+                all_orderings.push(ordering);
+            } else {
+                // If any file has no ordering, we can't derive a common ordering


We may add some debug or tracing log here:

Suggested change

// If any file has no ordering, we can't derive a common ordering

// If any file has no ordering, we can't derive a common ordering

tracing!(

"Cannot derive common ordering: file {} has different ordering ({:?}) than first file ({:?})",

file.object_meta.location, ordering, first

);

zhuqi-lucas · 2025-12-31T06:08:35Z

datafusion/execution/src/cache/cache_manager.rs

    CacheAccessor<Path, Arc<Statistics>, Extra = ObjectMeta>
 {
    /// Retrieves the information about the entries currently cached.
    fn list_entries(&self) -> HashMap<Path, FileStatisticsCacheEntry>;


Is it useful that we can add the has_ordering info to the FileStatisticsCacheEntry?

FileStatisticsCacheEntry { object_meta: object_meta.clone(), num_rows: stats.num_rows, num_columns: stats.column_statistics.len(), table_size_bytes: stats.total_byte_size, statistics_size_bytes: 0, has_ordering, // NEW: indicates if ordering is cached },

zhuqi-lucas · 2025-12-31T06:11:14Z

datafusion/catalog-listing/src/table.rs

+    // Check that all orderings are identical
+    let first = all_orderings[0];
+    for ordering in &all_orderings[1..] {
+        if *ordering != first {


Is it possible to use ordering_satisfy?

zhuqi-lucas · 2025-12-31T06:13:41Z

datafusion/datasource/src/file_format.rs

+/// Metadata fetched from a file, including statistics and ordering.
+///
+/// This struct is returned by [`FileFormat::infer_stats_and_ordering`] to
+/// provide all metadata in a single read, avoiding duplicate I/O operations.


Suggested change

/// Metadata fetched from a file, including statistics and ordering.

///

/// This struct is returned by [`FileFormat::infer_stats_and_ordering`] to

/// provide all metadata in a single read, avoiding duplicate I/O operations.

/// Metadata fetched from a file, including statistics and ordering.

///

/// This struct is returned by [`FileFormat::infer_stats_and_ordering`] to

/// provide all metadata in a single read, avoiding duplicate I/O operations.

///

/// Note: Individual components (statistics and ordering) are typically cached

/// separately by [`FileStatisticsCache`] implementations to enable partial cache hits.

zhuqi-lucas · 2025-12-31T06:15:26Z

datafusion/datasource-parquet/src/file_format.rs

+            // may not be compatible with Parquet sorting columns (e.g. ordering on `random()`).
+            // So if we cannot create a Parquet sorting column from the ordering requirement,
+            // we skip setting sorting columns on the Parquet sink.
+            lex_ordering_to_sorting_columns(&ordering).ok()


Great point!

zhuqi-lucas · 2025-12-31T06:23:00Z

datafusion/execution/src/cache/cache_unit.rs

+    /// Cached file orderings, keyed by file path.
+    /// Stored separately from statistics to maintain backwards compatibility
+    /// with the FileStatisticsCache trait interface.
+    orderings: DashMap<Path, (ObjectMeta, Option<LexOrdering>)>,


Is it possible we just use one map:

pub struct DefaultFileStatisticsCache { // Store both stats and ordering together cache: DashMap<Path, CacheEntry>, } struct CacheEntry { meta: ObjectMeta, statistics: Arc<Statistics>, ordering: Option<LexOrdering>, // Initially None until fetched }

zhuqi-lucas · 2025-12-31T06:26:23Z

datafusion/physical-expr-common/src/sort_expr.rs

+        // [a ASC, b DESC] is NOT a prefix of [a ASC, b ASC, c ASC] (mismatch in middle)
+        assert!(!ordering_abc.is_prefix(&ordering_ab));
+    }



Maybe add some tests for file modification:

#[tokio::test] async fn test_ordering_cache_invalidation_on_file_modification() { let cache = DefaultFileStatisticsCache::default(); let path = Path::from("test.parquet"); // Cache with original metadata let meta_v1 = ObjectMeta { location: path.clone(), last_modified: Utc.timestamp_nanos(1000), size: 100, e_tag: None, version: None, }; let ordering_v1 = Some(LexOrdering::new(vec![...]).unwrap()); cache.put_ordering(&path, ordering_v1.clone(), &meta_v1); // Verify cached assert_eq!(cache.get_ordering(&path, &meta_v1), Some(ordering_v1.clone())); // File modified (size changed) let meta_v2 = ObjectMeta { last_modified: Utc.timestamp_nanos(2000), size: 200, // ← changed ..meta_v1.clone() }; // Should return None (cache miss due to size mismatch) assert_eq!(cache.get_ordering(&path, &meta_v2), None); // Cache new version let ordering_v2 = Some(LexOrdering::new(vec![...]).unwrap()); cache.put_ordering(&path, ordering_v2.clone(), &meta_v2); // Old metadata should still be invalid assert_eq!(cache.get_ordering(&path, &meta_v1), None); // New metadata should work assert_eq!(cache.get_ordering(&path, &meta_v2), Some(ordering_v2)); }

zhuqi-lucas · 2025-12-31T06:30:12Z

datafusion/datasource-parquet/src/metadata.rs

+    let column_idx = sorting_col.column_idx as usize;
+
+    // Get the column path from the Parquet schema
+    // The column_idx in SortingColumn refers to leaf columns


Should we add test to nest type, it also can be sorted?

I am not sure if it's possible?

zhuqi-lucas · 2025-12-31T06:32:56Z

datafusion/catalog-listing/src/table.rs

+            let ordering = self
+                .options
+                .format
+                .infer_ordering(ctx, store, Arc::clone(&self.file_schema), meta)


Here we get the cached statistic, but we still need to compute the ordering info.

If it's possible we only have one entry for it, and cached it or not. And the cache including the computed ordering info.

zhuqi-lucas · 2025-12-31T11:24:20Z

FYI @adriangb, i will be out for next 3 days, feel free to merge.

zhuqi-lucas self-requested a review December 21, 2025 08:35

zhuqi-lucas reviewed Dec 23, 2025

View reviewed changes

adriangb marked this pull request as ready for review December 29, 2025 06:44

adriangb added 6 commits December 29, 2025 00:45

infer parquet file order from metadata, write order in ParquetSink

97bf1ff

cache ordering info

1a640d4

add missing module

de3140c

fix test

1450282

typo

a796bf4

lint

1a52a45

adriangb force-pushed the infer-ordering branch from 8fb624f to 1a52a45 Compare December 29, 2025 06:45

fix, add tests

53aab8b

zhuqi-lucas approved these changes Dec 31, 2025

View reviewed changes

-                // If any file has no ordering, we can't derive a common ordering
+                // If any file has no ordering, we can't derive a common ordering
+                tracing!(
+        "Cannot derive common ordering: file {} has different ordering ({:?}) than first file ({:?})",
+        file.object_meta.location, ordering, first
+    );

infer parquet file order from metadata, write order in ParquetSink #19433

Are you sure you want to change the base?

infer parquet file order from metadata, write order in ParquetSink #19433

Conversation

adriangb commented Dec 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

adriangb commented Dec 21, 2025

Uh oh!

zhuqi-lucas commented Dec 21, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuqi-lucas commented Dec 23, 2025

Uh oh!

adriangb commented Dec 31, 2025

Uh oh!

zhuqi-lucas left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zhuqi-lucas commented Dec 31, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

adriangb commented Dec 21, 2025 •

edited

Loading

zhuqi-lucas commented Dec 31, 2025 •

edited

Loading