zhuqi-lucas commented on code in PR #186:
URL: https://github.com/apache/datafusion-site/pull/186#discussion_r3544644957
##########
content/blog/2026-07-05-sort-pushdown.md:
##########
@@ -0,0 +1,625 @@
+---
+layout: post
+title: Sort Pushdown in DataFusion: Skip Sorts, Skip Decode, Skip I/O
+date: 2026-07-05
+author: Qi Zhu
+categories: [performance]
+---
+
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+[TOC]
+
+*Qi Zhu, [Massive](https://www.massive.com/)*
+
+**[Apache DataFusion] now automatically takes advantage of sortedness in the
+data — even when the data is only *partially* sorted, and even when
+DataFusion has not been told about the ordering ahead of time.** This post
+explains why that matters and walks through how DataFusion achieves it,
+through a combination of plan-time sort pushdown, runtime scan reordering,
+and mid-scan row-group pruning driven by [dynamic filters][dyn-filters-blog].
+
+[Apache DataFusion]: https://datafusion.apache.org/
+[dyn-filters-blog]:
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
+
+## Why sort pushdown matters
+
+Many real datasets are at least partly sorted on disk:
+
+- Time-series files are written in ingestion-time order.
+- Event logs are sharded and sorted by event id.
+- Partitioned tables have a natural ordering by partition key.
+- Modern data lakes based on [Apache Iceberg] and similar formats
+ often have to work with data **as it was written** — resorting the
+ whole table isn't an option.
+
+But that "pre-existing sortedness" is only useful if the query engine can
+**notice** it and **use** it. Two common failure modes:
+
+1. The engine doesn't know about the ordering — the writer didn't set
+ Parquet `sorting_columns`, and the table definition doesn't include a
+ [`WITH
ORDER`](https://datafusion.apache.org/user-guide/sql/ddl.html#create-external-table)
clause.
+2. The engine knows the *per-file* ordering, but the file *listing* on
+ disk is in a different order, so global sortedness can't be proven at
+ plan time.
+
+In both cases, an `ORDER BY` or `ORDER BY ... LIMIT N` query pays the
+cost of a full external `SortExec` — a pipeline-blocking operator that
+must see every input row before emitting anything, dominating both
+latency and peak memory on large scans.
+
+Min/max statistics used for *predicate* pushdown are well-known and
+widely implemented across databases. Using them to *reason about sort
+order* — deleting redundant sorts, biasing scan order toward the
+most-promising data — is less common. This post is about how DataFusion
+does the latter.
+
+[Apache Iceberg]: https://iceberg.apache.org/
+
+## What DataFusion could already do — and what was missing
+
+DataFusion has always been able to skip the sort in the **exact** case,
+using the machinery covered in [@akurmustafa's earlier post on
+ordering analysis][ordering-analysis]: when the table definition
+declares an ordering (via `WITH ORDER` or Parquet `sorting_columns`)
+**and** the on-disk file listing already matches that order, the
+existing `EnsureRequirements` rule sees that the scan's
+`output_ordering` satisfies the request and **removes the redundant
+`SortExec`** entirely.
+
+This post is about **everything else** — the messier real-world cases
+where sortedness exists but isn't provable up front:
+
+- Files listed in the "wrong" order on disk (each file internally
+ sorted, but the listing doesn't match).
+- Declared ordering with **overlapping** ranges across files.
+- **No** declared ordering at all.
+- `ORDER BY ... DESC` on ASC-sorted data.
+
+Three complementary techniques close each gap:
+
+1. **Statistics-based sort elimination** (`Exact` path). Extend the
+ optimizer to prove ordering from min/max statistics after
+ reordering the file list, then delete the `SortExec` entirely.
+2. **Runtime scan reorder** (`Inexact` path). Keep the `SortExec`, but
+ bias scan order so the *most-promising* data is read first —
+ `TopK`'s [dynamic filter][dyn-filters-blog] tightens quickly and
+ downstream data is pruned by statistics before it's read.
+3. **Runtime row-group dynamic pruning** ([#22450]). Inside the
+ parquet decoder loop, re-check the live `TopK` threshold at every
+ row-group boundary and physically remove pruned row groups before
+ any bytes are fetched.
+
+Together these compose into a **three-layer pruning stack**
+(file-level, row-group-level, row-level), all driven by the same
+`TopK` dynamic filter. Headline results:
+
+- **Sort elimination**: 2×–49× faster on ASC-LIMIT queries where the
+ file list was in the wrong disk order.
+- **Runtime row-group pruning ([#22450])**: 5 of 11 `topk_tpch`
+ queries run 3–4× faster with zero regressions; total runtime drops
+ −44%.
+
+The rest of this post walks through each technique in turn.
+
+[#22450]: https://github.com/apache/datafusion/pull/22450
+[#20839]: https://github.com/apache/datafusion/pull/20839
+[Apache Parquet]: https://parquet.apache.org/
+[ordering-analysis]:
https://datafusion.apache.org/blog/2025/03/11/ordering-analysis/
+
+## How DataFusion Tracks Ordering
+
+<img src="/blog/images/sort-pushdown/plan-diff.svg" alt="EXPLAIN before /
after: SortExec eliminated once ordering is Exact" width="100%"
class="img-fluid"/>
+
+DataFusion's
[`FileScanConfig`](https://docs.rs/datafusion-datasource/latest/datafusion_datasource/file_scan_config/struct.FileScanConfig.html)
carries an ordering claim for
+each scan's output, which is one of:
+
+- **`Exact`** — the optimizer is *certain* the output is in this order,
Review Comment:
Ack — kept `SortExec` here as this section is DataFusion internals.
##########
content/blog/2026-07-05-sort-pushdown.md:
##########
@@ -0,0 +1,625 @@
+---
+layout: post
+title: Sort Pushdown in DataFusion: Skip Sorts, Skip Decode, Skip I/O
+date: 2026-07-05
+author: Qi Zhu
+categories: [performance]
+---
+
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+[TOC]
+
+*Qi Zhu, [Massive](https://www.massive.com/)*
+
+**[Apache DataFusion] now automatically takes advantage of sortedness in the
+data — even when the data is only *partially* sorted, and even when
+DataFusion has not been told about the ordering ahead of time.** This post
+explains why that matters and walks through how DataFusion achieves it,
+through a combination of plan-time sort pushdown, runtime scan reordering,
+and mid-scan row-group pruning driven by [dynamic filters][dyn-filters-blog].
+
+[Apache DataFusion]: https://datafusion.apache.org/
+[dyn-filters-blog]:
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
+
+## Why sort pushdown matters
+
+Many real datasets are at least partly sorted on disk:
+
+- Time-series files are written in ingestion-time order.
+- Event logs are sharded and sorted by event id.
+- Partitioned tables have a natural ordering by partition key.
+- Modern data lakes based on [Apache Iceberg] and similar formats
+ often have to work with data **as it was written** — resorting the
+ whole table isn't an option.
+
+But that "pre-existing sortedness" is only useful if the query engine can
+**notice** it and **use** it. Two common failure modes:
+
+1. The engine doesn't know about the ordering — the writer didn't set
+ Parquet `sorting_columns`, and the table definition doesn't include a
+ [`WITH
ORDER`](https://datafusion.apache.org/user-guide/sql/ddl.html#create-external-table)
clause.
+2. The engine knows the *per-file* ordering, but the file *listing* on
+ disk is in a different order, so global sortedness can't be proven at
+ plan time.
+
+In both cases, an `ORDER BY` or `ORDER BY ... LIMIT N` query pays the
+cost of a full external `SortExec` — a pipeline-blocking operator that
+must see every input row before emitting anything, dominating both
+latency and peak memory on large scans.
+
+Min/max statistics used for *predicate* pushdown are well-known and
+widely implemented across databases. Using them to *reason about sort
+order* — deleting redundant sorts, biasing scan order toward the
+most-promising data — is less common. This post is about how DataFusion
+does the latter.
+
+[Apache Iceberg]: https://iceberg.apache.org/
+
+## What DataFusion could already do — and what was missing
+
+DataFusion has always been able to skip the sort in the **exact** case,
+using the machinery covered in [@akurmustafa's earlier post on
+ordering analysis][ordering-analysis]: when the table definition
+declares an ordering (via `WITH ORDER` or Parquet `sorting_columns`)
+**and** the on-disk file listing already matches that order, the
+existing `EnsureRequirements` rule sees that the scan's
+`output_ordering` satisfies the request and **removes the redundant
+`SortExec`** entirely.
+
+This post is about **everything else** — the messier real-world cases
+where sortedness exists but isn't provable up front:
+
+- Files listed in the "wrong" order on disk (each file internally
+ sorted, but the listing doesn't match).
+- Declared ordering with **overlapping** ranges across files.
+- **No** declared ordering at all.
+- `ORDER BY ... DESC` on ASC-sorted data.
+
+Three complementary techniques close each gap:
+
+1. **Statistics-based sort elimination** (`Exact` path). Extend the
+ optimizer to prove ordering from min/max statistics after
+ reordering the file list, then delete the `SortExec` entirely.
+2. **Runtime scan reorder** (`Inexact` path). Keep the `SortExec`, but
+ bias scan order so the *most-promising* data is read first —
+ `TopK`'s [dynamic filter][dyn-filters-blog] tightens quickly and
+ downstream data is pruned by statistics before it's read.
+3. **Runtime row-group dynamic pruning** ([#22450]). Inside the
+ parquet decoder loop, re-check the live `TopK` threshold at every
+ row-group boundary and physically remove pruned row groups before
+ any bytes are fetched.
+
+Together these compose into a **three-layer pruning stack**
+(file-level, row-group-level, row-level), all driven by the same
+`TopK` dynamic filter. Headline results:
+
+- **Sort elimination**: 2×–49× faster on ASC-LIMIT queries where the
+ file list was in the wrong disk order.
+- **Runtime row-group pruning ([#22450])**: 5 of 11 `topk_tpch`
+ queries run 3–4× faster with zero regressions; total runtime drops
+ −44%.
+
+The rest of this post walks through each technique in turn.
+
+[#22450]: https://github.com/apache/datafusion/pull/22450
+[#20839]: https://github.com/apache/datafusion/pull/20839
+[Apache Parquet]: https://parquet.apache.org/
+[ordering-analysis]:
https://datafusion.apache.org/blog/2025/03/11/ordering-analysis/
+
+## How DataFusion Tracks Ordering
+
+<img src="/blog/images/sort-pushdown/plan-diff.svg" alt="EXPLAIN before /
after: SortExec eliminated once ordering is Exact" width="100%"
class="img-fluid"/>
+
+DataFusion's
[`FileScanConfig`](https://docs.rs/datafusion-datasource/latest/datafusion_datasource/file_scan_config/struct.FileScanConfig.html)
carries an ordering claim for
+each scan's output, which is one of:
+
+- **`Exact`** — the optimizer is *certain* the output is in this order,
+ and removes redundant
[`SortExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort/struct.SortExec.html)
operators entirely.
+ `LIMIT N` becomes a static fetch on the source (the reader stops the
+ moment N rows are emitted).
+- **`Inexact`** — the optimizer believes the output is probably ordered
+ but cannot prove it. Downstream operators like
+
[`SortPreservingMergeExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort_preserving_merge/struct.SortPreservingMergeExec.html)
can still benefit, but the
+ explicit `SortExec` stays for correctness. In this case `TopK`'s
+ [dynamic filter][dyn-filters-blog] tightens as the heap fills, and
+ data whose min/max cannot beat the threshold is pruned before it is
+ fully read.
+
+For example, given a query that returns the 10 most recent trades:
+
+```sql
+SELECT ts, symbol, amount FROM trades ORDER BY ts DESC LIMIT 10;
+```
+
+- With no ordering knowledge, DataFusion scans everything and uses a
+ `TopK` heap to keep the running best 10.
+- With **`Exact`** ordering, DataFusion drops the sort entirely and
+ stops reading after emitting 10 rows.
+- With **`Inexact`** ordering, the `SortExec` stays but scans start
+ from the most-promising data, so the `TopK` threshold tightens fast
Review Comment:
Done — applied suggested phrasing.
##########
content/blog/2026-07-05-sort-pushdown.md:
##########
@@ -0,0 +1,625 @@
+---
+layout: post
+title: Sort Pushdown in DataFusion: Skip Sorts, Skip Decode, Skip I/O
+date: 2026-07-05
+author: Qi Zhu
+categories: [performance]
+---
+
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+[TOC]
+
+*Qi Zhu, [Massive](https://www.massive.com/)*
+
+**[Apache DataFusion] now automatically takes advantage of sortedness in the
+data — even when the data is only *partially* sorted, and even when
+DataFusion has not been told about the ordering ahead of time.** This post
+explains why that matters and walks through how DataFusion achieves it,
+through a combination of plan-time sort pushdown, runtime scan reordering,
+and mid-scan row-group pruning driven by [dynamic filters][dyn-filters-blog].
+
+[Apache DataFusion]: https://datafusion.apache.org/
+[dyn-filters-blog]:
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
+
+## Why sort pushdown matters
+
+Many real datasets are at least partly sorted on disk:
+
+- Time-series files are written in ingestion-time order.
+- Event logs are sharded and sorted by event id.
+- Partitioned tables have a natural ordering by partition key.
+- Modern data lakes based on [Apache Iceberg] and similar formats
+ often have to work with data **as it was written** — resorting the
+ whole table isn't an option.
+
+But that "pre-existing sortedness" is only useful if the query engine can
+**notice** it and **use** it. Two common failure modes:
+
+1. The engine doesn't know about the ordering — the writer didn't set
+ Parquet `sorting_columns`, and the table definition doesn't include a
+ [`WITH
ORDER`](https://datafusion.apache.org/user-guide/sql/ddl.html#create-external-table)
clause.
+2. The engine knows the *per-file* ordering, but the file *listing* on
+ disk is in a different order, so global sortedness can't be proven at
+ plan time.
+
+In both cases, an `ORDER BY` or `ORDER BY ... LIMIT N` query pays the
+cost of a full external `SortExec` — a pipeline-blocking operator that
+must see every input row before emitting anything, dominating both
+latency and peak memory on large scans.
+
+Min/max statistics used for *predicate* pushdown are well-known and
+widely implemented across databases. Using them to *reason about sort
+order* — deleting redundant sorts, biasing scan order toward the
+most-promising data — is less common. This post is about how DataFusion
+does the latter.
+
+[Apache Iceberg]: https://iceberg.apache.org/
+
+## What DataFusion could already do — and what was missing
+
+DataFusion has always been able to skip the sort in the **exact** case,
+using the machinery covered in [@akurmustafa's earlier post on
+ordering analysis][ordering-analysis]: when the table definition
+declares an ordering (via `WITH ORDER` or Parquet `sorting_columns`)
+**and** the on-disk file listing already matches that order, the
+existing `EnsureRequirements` rule sees that the scan's
+`output_ordering` satisfies the request and **removes the redundant
+`SortExec`** entirely.
+
+This post is about **everything else** — the messier real-world cases
+where sortedness exists but isn't provable up front:
+
+- Files listed in the "wrong" order on disk (each file internally
+ sorted, but the listing doesn't match).
+- Declared ordering with **overlapping** ranges across files.
+- **No** declared ordering at all.
+- `ORDER BY ... DESC` on ASC-sorted data.
+
+Three complementary techniques close each gap:
+
+1. **Statistics-based sort elimination** (`Exact` path). Extend the
+ optimizer to prove ordering from min/max statistics after
+ reordering the file list, then delete the `SortExec` entirely.
+2. **Runtime scan reorder** (`Inexact` path). Keep the `SortExec`, but
+ bias scan order so the *most-promising* data is read first —
+ `TopK`'s [dynamic filter][dyn-filters-blog] tightens quickly and
+ downstream data is pruned by statistics before it's read.
+3. **Runtime row-group dynamic pruning** ([#22450]). Inside the
+ parquet decoder loop, re-check the live `TopK` threshold at every
+ row-group boundary and physically remove pruned row groups before
+ any bytes are fetched.
+
+Together these compose into a **three-layer pruning stack**
+(file-level, row-group-level, row-level), all driven by the same
+`TopK` dynamic filter. Headline results:
+
+- **Sort elimination**: 2×–49× faster on ASC-LIMIT queries where the
+ file list was in the wrong disk order.
+- **Runtime row-group pruning ([#22450])**: 5 of 11 `topk_tpch`
+ queries run 3–4× faster with zero regressions; total runtime drops
+ −44%.
+
+The rest of this post walks through each technique in turn.
+
+[#22450]: https://github.com/apache/datafusion/pull/22450
+[#20839]: https://github.com/apache/datafusion/pull/20839
+[Apache Parquet]: https://parquet.apache.org/
+[ordering-analysis]:
https://datafusion.apache.org/blog/2025/03/11/ordering-analysis/
+
+## How DataFusion Tracks Ordering
+
+<img src="/blog/images/sort-pushdown/plan-diff.svg" alt="EXPLAIN before /
after: SortExec eliminated once ordering is Exact" width="100%"
class="img-fluid"/>
+
+DataFusion's
[`FileScanConfig`](https://docs.rs/datafusion-datasource/latest/datafusion_datasource/file_scan_config/struct.FileScanConfig.html)
carries an ordering claim for
+each scan's output, which is one of:
+
+- **`Exact`** — the optimizer is *certain* the output is in this order,
+ and removes redundant
[`SortExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort/struct.SortExec.html)
operators entirely.
+ `LIMIT N` becomes a static fetch on the source (the reader stops the
+ moment N rows are emitted).
+- **`Inexact`** — the optimizer believes the output is probably ordered
+ but cannot prove it. Downstream operators like
+
[`SortPreservingMergeExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort_preserving_merge/struct.SortPreservingMergeExec.html)
can still benefit, but the
+ explicit `SortExec` stays for correctness. In this case `TopK`'s
+ [dynamic filter][dyn-filters-blog] tightens as the heap fills, and
+ data whose min/max cannot beat the threshold is pruned before it is
+ fully read.
+
+For example, given a query that returns the 10 most recent trades:
+
+```sql
+SELECT ts, symbol, amount FROM trades ORDER BY ts DESC LIMIT 10;
+```
+
+- With no ordering knowledge, DataFusion scans everything and uses a
+ `TopK` heap to keep the running best 10.
+- With **`Exact`** ordering, DataFusion drops the sort entirely and
+ stops reading after emitting 10 rows.
+- With **`Inexact`** ordering, the `SortExec` stays but scans start
+ from the most-promising data, so the `TopK` threshold tightens fast
+ and the rest is pruned by statistics.
+
+The optimizer rule that upgrades a scan from `Unsupported` to
+`Exact`/`Inexact` — and that removes the resulting redundant
+`SortExec` — is
[`PushdownSort`](https://github.com/apache/datafusion/blob/main/datafusion/physical-optimizer/src/pushdown_sort.rs).
`PushdownSort`
+runs late, after `EnsureRequirements` has finalised the plan shape.
Review Comment:
Done — dropped the `runs late after EnsureRequirements` and plan-walk detail.
##########
content/blog/2026-07-05-sort-pushdown.md:
##########
@@ -0,0 +1,625 @@
+---
+layout: post
+title: Sort Pushdown in DataFusion: Skip Sorts, Skip Decode, Skip I/O
+date: 2026-07-05
+author: Qi Zhu
+categories: [performance]
+---
+
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+[TOC]
+
+*Qi Zhu, [Massive](https://www.massive.com/)*
+
+**[Apache DataFusion] now automatically takes advantage of sortedness in the
+data — even when the data is only *partially* sorted, and even when
+DataFusion has not been told about the ordering ahead of time.** This post
+explains why that matters and walks through how DataFusion achieves it,
+through a combination of plan-time sort pushdown, runtime scan reordering,
+and mid-scan row-group pruning driven by [dynamic filters][dyn-filters-blog].
+
+[Apache DataFusion]: https://datafusion.apache.org/
+[dyn-filters-blog]:
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
+
+## Why sort pushdown matters
+
+Many real datasets are at least partly sorted on disk:
+
+- Time-series files are written in ingestion-time order.
+- Event logs are sharded and sorted by event id.
+- Partitioned tables have a natural ordering by partition key.
+- Modern data lakes based on [Apache Iceberg] and similar formats
+ often have to work with data **as it was written** — resorting the
+ whole table isn't an option.
+
+But that "pre-existing sortedness" is only useful if the query engine can
+**notice** it and **use** it. Two common failure modes:
+
+1. The engine doesn't know about the ordering — the writer didn't set
+ Parquet `sorting_columns`, and the table definition doesn't include a
+ [`WITH
ORDER`](https://datafusion.apache.org/user-guide/sql/ddl.html#create-external-table)
clause.
+2. The engine knows the *per-file* ordering, but the file *listing* on
+ disk is in a different order, so global sortedness can't be proven at
+ plan time.
+
+In both cases, an `ORDER BY` or `ORDER BY ... LIMIT N` query pays the
+cost of a full external `SortExec` — a pipeline-blocking operator that
+must see every input row before emitting anything, dominating both
+latency and peak memory on large scans.
+
+Min/max statistics used for *predicate* pushdown are well-known and
+widely implemented across databases. Using them to *reason about sort
+order* — deleting redundant sorts, biasing scan order toward the
+most-promising data — is less common. This post is about how DataFusion
+does the latter.
+
+[Apache Iceberg]: https://iceberg.apache.org/
+
+## What DataFusion could already do — and what was missing
+
+DataFusion has always been able to skip the sort in the **exact** case,
+using the machinery covered in [@akurmustafa's earlier post on
+ordering analysis][ordering-analysis]: when the table definition
+declares an ordering (via `WITH ORDER` or Parquet `sorting_columns`)
+**and** the on-disk file listing already matches that order, the
+existing `EnsureRequirements` rule sees that the scan's
+`output_ordering` satisfies the request and **removes the redundant
+`SortExec`** entirely.
+
+This post is about **everything else** — the messier real-world cases
+where sortedness exists but isn't provable up front:
+
+- Files listed in the "wrong" order on disk (each file internally
+ sorted, but the listing doesn't match).
+- Declared ordering with **overlapping** ranges across files.
+- **No** declared ordering at all.
+- `ORDER BY ... DESC` on ASC-sorted data.
+
+Three complementary techniques close each gap:
+
+1. **Statistics-based sort elimination** (`Exact` path). Extend the
+ optimizer to prove ordering from min/max statistics after
+ reordering the file list, then delete the `SortExec` entirely.
+2. **Runtime scan reorder** (`Inexact` path). Keep the `SortExec`, but
+ bias scan order so the *most-promising* data is read first —
+ `TopK`'s [dynamic filter][dyn-filters-blog] tightens quickly and
+ downstream data is pruned by statistics before it's read.
+3. **Runtime row-group dynamic pruning** ([#22450]). Inside the
+ parquet decoder loop, re-check the live `TopK` threshold at every
+ row-group boundary and physically remove pruned row groups before
+ any bytes are fetched.
+
+Together these compose into a **three-layer pruning stack**
+(file-level, row-group-level, row-level), all driven by the same
+`TopK` dynamic filter. Headline results:
+
+- **Sort elimination**: 2×–49× faster on ASC-LIMIT queries where the
+ file list was in the wrong disk order.
+- **Runtime row-group pruning ([#22450])**: 5 of 11 `topk_tpch`
+ queries run 3–4× faster with zero regressions; total runtime drops
+ −44%.
+
+The rest of this post walks through each technique in turn.
+
+[#22450]: https://github.com/apache/datafusion/pull/22450
+[#20839]: https://github.com/apache/datafusion/pull/20839
+[Apache Parquet]: https://parquet.apache.org/
+[ordering-analysis]:
https://datafusion.apache.org/blog/2025/03/11/ordering-analysis/
+
+## How DataFusion Tracks Ordering
+
+<img src="/blog/images/sort-pushdown/plan-diff.svg" alt="EXPLAIN before /
after: SortExec eliminated once ordering is Exact" width="100%"
class="img-fluid"/>
+
+DataFusion's
[`FileScanConfig`](https://docs.rs/datafusion-datasource/latest/datafusion_datasource/file_scan_config/struct.FileScanConfig.html)
carries an ordering claim for
+each scan's output, which is one of:
+
+- **`Exact`** — the optimizer is *certain* the output is in this order,
+ and removes redundant
[`SortExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort/struct.SortExec.html)
operators entirely.
+ `LIMIT N` becomes a static fetch on the source (the reader stops the
+ moment N rows are emitted).
+- **`Inexact`** — the optimizer believes the output is probably ordered
+ but cannot prove it. Downstream operators like
+
[`SortPreservingMergeExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort_preserving_merge/struct.SortPreservingMergeExec.html)
can still benefit, but the
+ explicit `SortExec` stays for correctness. In this case `TopK`'s
+ [dynamic filter][dyn-filters-blog] tightens as the heap fills, and
+ data whose min/max cannot beat the threshold is pruned before it is
+ fully read.
+
+For example, given a query that returns the 10 most recent trades:
+
+```sql
+SELECT ts, symbol, amount FROM trades ORDER BY ts DESC LIMIT 10;
+```
+
+- With no ordering knowledge, DataFusion scans everything and uses a
+ `TopK` heap to keep the running best 10.
+- With **`Exact`** ordering, DataFusion drops the sort entirely and
+ stops reading after emitting 10 rows.
+- With **`Inexact`** ordering, the `SortExec` stays but scans start
+ from the most-promising data, so the `TopK` threshold tightens fast
+ and the rest is pruned by statistics.
+
+The optimizer rule that upgrades a scan from `Unsupported` to
+`Exact`/`Inexact` — and that removes the resulting redundant
+`SortExec` — is
[`PushdownSort`](https://github.com/apache/datafusion/blob/main/datafusion/physical-optimizer/src/pushdown_sort.rs).
`PushdownSort`
+runs late, after `EnsureRequirements` has finalised the plan shape.
+It walks each `SortExec`, asks the child leaf via `try_pushdown_sort`
+which flavour the source can produce, and rewrites accordingly.
+
+## The `Exact` Path · Sort Elimination via Statistics
+
+<img src="/blog/images/sort-pushdown/phase1-file-reorder.svg" alt="File
reorder: rearranging files within a partition by min/max statistics so the file
list is in range order" width="100%" class="img-fluid" /><br/>
+*Figure: file reorder by per-file `min/max` puts the file list in range
+order without touching file contents.*
+
+DataFusion could already recognize the *exact* sortedness case (declared
+ordering + matching on-disk file list). The new capability is recognizing
+sortedness when the **file list is in the wrong order** on disk, using
+the min/max statistics that the Parquet writer already stored per row
+group. Implemented across two PRs on `PushdownSort`:
+[apache/datafusion#19064][#19064] (rule scaffolding), and
+[apache/datafusion#21182][#21182] (stats-based file reorder).
Review Comment:
Done — adopted suggestion verbatim.
##########
content/blog/2026-07-05-sort-pushdown.md:
##########
@@ -0,0 +1,625 @@
+---
+layout: post
+title: Sort Pushdown in DataFusion: Skip Sorts, Skip Decode, Skip I/O
+date: 2026-07-05
+author: Qi Zhu
+categories: [performance]
+---
+
+<!--
+{% comment %}
+Licensed to the Apache Software Foundation (ASF) under one or more
+contributor license agreements. See the NOTICE file distributed with
+this work for additional information regarding copyright ownership.
+The ASF licenses this file to you under the Apache License, Version 2.0
+(the "License"); you may not use this file except in compliance with
+the License. You may obtain a copy of the License at
+
+http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+{% endcomment %}
+-->
+
+[TOC]
+
+*Qi Zhu, [Massive](https://www.massive.com/)*
+
+**[Apache DataFusion] now automatically takes advantage of sortedness in the
+data — even when the data is only *partially* sorted, and even when
+DataFusion has not been told about the ordering ahead of time.** This post
+explains why that matters and walks through how DataFusion achieves it,
+through a combination of plan-time sort pushdown, runtime scan reordering,
+and mid-scan row-group pruning driven by [dynamic filters][dyn-filters-blog].
+
+[Apache DataFusion]: https://datafusion.apache.org/
+[dyn-filters-blog]:
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
+
+## Why sort pushdown matters
+
+Many real datasets are at least partly sorted on disk:
+
+- Time-series files are written in ingestion-time order.
+- Event logs are sharded and sorted by event id.
+- Partitioned tables have a natural ordering by partition key.
+- Modern data lakes based on [Apache Iceberg] and similar formats
+ often have to work with data **as it was written** — resorting the
+ whole table isn't an option.
+
+But that "pre-existing sortedness" is only useful if the query engine can
+**notice** it and **use** it. Two common failure modes:
+
+1. The engine doesn't know about the ordering — the writer didn't set
+ Parquet `sorting_columns`, and the table definition doesn't include a
+ [`WITH
ORDER`](https://datafusion.apache.org/user-guide/sql/ddl.html#create-external-table)
clause.
+2. The engine knows the *per-file* ordering, but the file *listing* on
+ disk is in a different order, so global sortedness can't be proven at
+ plan time.
+
+In both cases, an `ORDER BY` or `ORDER BY ... LIMIT N` query pays the
+cost of a full external `SortExec` — a pipeline-blocking operator that
+must see every input row before emitting anything, dominating both
+latency and peak memory on large scans.
+
+Min/max statistics used for *predicate* pushdown are well-known and
+widely implemented across databases. Using them to *reason about sort
+order* — deleting redundant sorts, biasing scan order toward the
+most-promising data — is less common. This post is about how DataFusion
+does the latter.
+
+[Apache Iceberg]: https://iceberg.apache.org/
+
+## What DataFusion could already do — and what was missing
+
+DataFusion has always been able to skip the sort in the **exact** case,
+using the machinery covered in [@akurmustafa's earlier post on
+ordering analysis][ordering-analysis]: when the table definition
+declares an ordering (via `WITH ORDER` or Parquet `sorting_columns`)
+**and** the on-disk file listing already matches that order, the
+existing `EnsureRequirements` rule sees that the scan's
+`output_ordering` satisfies the request and **removes the redundant
+`SortExec`** entirely.
+
+This post is about **everything else** — the messier real-world cases
+where sortedness exists but isn't provable up front:
+
+- Files listed in the "wrong" order on disk (each file internally
+ sorted, but the listing doesn't match).
+- Declared ordering with **overlapping** ranges across files.
+- **No** declared ordering at all.
+- `ORDER BY ... DESC` on ASC-sorted data.
+
+Three complementary techniques close each gap:
+
+1. **Statistics-based sort elimination** (`Exact` path). Extend the
+ optimizer to prove ordering from min/max statistics after
+ reordering the file list, then delete the `SortExec` entirely.
+2. **Runtime scan reorder** (`Inexact` path). Keep the `SortExec`, but
+ bias scan order so the *most-promising* data is read first —
+ `TopK`'s [dynamic filter][dyn-filters-blog] tightens quickly and
+ downstream data is pruned by statistics before it's read.
+3. **Runtime row-group dynamic pruning** ([#22450]). Inside the
+ parquet decoder loop, re-check the live `TopK` threshold at every
+ row-group boundary and physically remove pruned row groups before
+ any bytes are fetched.
+
+Together these compose into a **three-layer pruning stack**
+(file-level, row-group-level, row-level), all driven by the same
+`TopK` dynamic filter. Headline results:
+
+- **Sort elimination**: 2×–49× faster on ASC-LIMIT queries where the
+ file list was in the wrong disk order.
+- **Runtime row-group pruning ([#22450])**: 5 of 11 `topk_tpch`
+ queries run 3–4× faster with zero regressions; total runtime drops
+ −44%.
+
+The rest of this post walks through each technique in turn.
+
+[#22450]: https://github.com/apache/datafusion/pull/22450
+[#20839]: https://github.com/apache/datafusion/pull/20839
+[Apache Parquet]: https://parquet.apache.org/
+[ordering-analysis]:
https://datafusion.apache.org/blog/2025/03/11/ordering-analysis/
+
+## How DataFusion Tracks Ordering
+
+<img src="/blog/images/sort-pushdown/plan-diff.svg" alt="EXPLAIN before /
after: SortExec eliminated once ordering is Exact" width="100%"
class="img-fluid"/>
+
+DataFusion's
[`FileScanConfig`](https://docs.rs/datafusion-datasource/latest/datafusion_datasource/file_scan_config/struct.FileScanConfig.html)
carries an ordering claim for
+each scan's output, which is one of:
+
+- **`Exact`** — the optimizer is *certain* the output is in this order,
+ and removes redundant
[`SortExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort/struct.SortExec.html)
operators entirely.
+ `LIMIT N` becomes a static fetch on the source (the reader stops the
+ moment N rows are emitted).
+- **`Inexact`** — the optimizer believes the output is probably ordered
+ but cannot prove it. Downstream operators like
+
[`SortPreservingMergeExec`](https://docs.rs/datafusion-physical-plan/latest/datafusion_physical_plan/sorts/sort_preserving_merge/struct.SortPreservingMergeExec.html)
can still benefit, but the
+ explicit `SortExec` stays for correctness. In this case `TopK`'s
+ [dynamic filter][dyn-filters-blog] tightens as the heap fills, and
+ data whose min/max cannot beat the threshold is pruned before it is
+ fully read.
+
+For example, given a query that returns the 10 most recent trades:
+
+```sql
+SELECT ts, symbol, amount FROM trades ORDER BY ts DESC LIMIT 10;
+```
+
+- With no ordering knowledge, DataFusion scans everything and uses a
+ `TopK` heap to keep the running best 10.
+- With **`Exact`** ordering, DataFusion drops the sort entirely and
+ stops reading after emitting 10 rows.
+- With **`Inexact`** ordering, the `SortExec` stays but scans start
+ from the most-promising data, so the `TopK` threshold tightens fast
+ and the rest is pruned by statistics.
+
+The optimizer rule that upgrades a scan from `Unsupported` to
+`Exact`/`Inexact` — and that removes the resulting redundant
+`SortExec` — is
[`PushdownSort`](https://github.com/apache/datafusion/blob/main/datafusion/physical-optimizer/src/pushdown_sort.rs).
`PushdownSort`
+runs late, after `EnsureRequirements` has finalised the plan shape.
+It walks each `SortExec`, asks the child leaf via `try_pushdown_sort`
+which flavour the source can produce, and rewrites accordingly.
+
+## The `Exact` Path · Sort Elimination via Statistics
+
+<img src="/blog/images/sort-pushdown/phase1-file-reorder.svg" alt="File
reorder: rearranging files within a partition by min/max statistics so the file
list is in range order" width="100%" class="img-fluid" /><br/>
+*Figure: file reorder by per-file `min/max` puts the file list in range
+order without touching file contents.*
+
+DataFusion could already recognize the *exact* sortedness case (declared
+ordering + matching on-disk file list). The new capability is recognizing
+sortedness when the **file list is in the wrong order** on disk, using
+the min/max statistics that the Parquet writer already stored per row
+group. Implemented across two PRs on `PushdownSort`:
+[apache/datafusion#19064][#19064] (rule scaffolding), and
+[apache/datafusion#21182][#21182] (stats-based file reorder).
+
+[#19064]: https://github.com/apache/datafusion/pull/19064
+[#21182]: https://github.com/apache/datafusion/pull/21182
+
+For example, consider three files `a.parquet`, `b.parquet`,
+`c.parquet`. Each is internally sorted by `ts` and declares
+`WITH ORDER (ts ASC)`, but they were written by different jobs and end
+up listed alphabetically on disk (which does *not* match sort order).
+The old machinery has no way to prove global sortedness, so an
+`ORDER BY ts` query pays for a full external sort even though the
+underlying data is already sorted.
+
+`PushdownSort` fixes this in three steps at the file-scan node:
+
+1. **Sort the file list by per-file `min`** on the sort column.
+2. **Check adjacency**: does `file[i].max ≤ file[i+1].min` hold for
+ every adjacent pair? If yes, the sorted file list produces a globally
+ sorted stream.
+3. **Upgrade the source's ordering claim to `Exact`** and remove the
+ surrounding `SortExec`.
+
+<img src="/blog/images/sort-pushdown/phase2-stats-overlap.svg" alt="Detecting
non-overlapping ranges via min/max statistics" width="100%" class="img-fluid"
/><br/>
+*Figure: after reorder, the left case has non-overlapping ranges (safe
+to upgrade to `Exact`); the right case has overlaps (upgrade skipped,
+falls through to the `Inexact` path).*
+
+Two conservative bail-outs: (a) sort keys must be plain columns
Review Comment:
Done — removed the two conservative bail-outs paragraph.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
