SteNicholas commented on code in PR #1314:
URL: https://github.com/apache/paimon-rust/pull/1314#discussion_r4453165951


##########
crates/integrations/datafusion/src/physical_plan/range_partitioning.rs:
##########
@@ -0,0 +1,418 @@
+// 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.
+
+use std::sync::Arc;
+
+use datafusion::arrow::compute::SortOptions;
+use datafusion::arrow::datatypes::{DataType, Schema, TimeUnit};
+use datafusion::arrow::row::{RowConverter, SortField};
+use datafusion::common::{ScalarValue, SplitPoint};
+use datafusion::physical_expr::expressions::Column;
+use datafusion::physical_expr::{LexOrdering, Partitioning, PhysicalSortExpr, 
RangePartitioning};
+use paimon::spec::{BinaryRow, DataField};
+use paimon::table::Table;
+use paimon::DataSplit;
+
+use super::scan::datum_to_scalar;
+
+/// Group whole splits by their typed partition keys, then combine adjacent key
+/// groups into at most the original number of execution partitions. Equal keys
+/// must never straddle a boundary: DataFusion can use this declaration to omit
+/// the exchange before a final aggregate or a co-partitioned join.
+///
+/// This describes distribution only. Files and rows within a range need not be
+/// sorted. Failure to prove any part of the contract leaves the original scan
+/// assignments and UnknownPartitioning intact.
+pub(super) fn range_partitioned_splits(
+    table: &Table,
+    schema: &Schema,
+    read_type: &[DataField],
+    partitions: &[Arc<[DataSplit]>],
+) -> Option<(Vec<Arc<[DataSplit]>>, Partitioning)> {
+    let fields = table.schema().partition_fields();
+    let options = table.schema().core_options();
+    if fields.is_empty()
+        || fields.len() != table.schema().partition_keys().len()
+        || partitions.len() < 2
+        || read_type.len() != schema.fields().len()
+        || options.query_auth_enabled()
+    {
+        return None;
+    }
+
+    // Native PK value aggregation can change non-key partition columns. Those
+    // values can remain in files even after the merge engine is changed, so 
the
+    // current engine alone cannot prove range membership. Full PK columns are
+    // immutable; format-table readers reconstruct partition columns from 
splits.
+    let primary_keys = table.schema().primary_keys();
+    if !options.is_format_table()

Review Comment:
   Could we add an integration test for `type=format-table` with partition 
columns absent from the physical files? This path relies on the format reader 
reconstructing those columns from the splits, while the new integration tests 
only create native tables. Using at least two distinct partition keys, please 
verify that the emitted rows belong to the declared ranges and that GROUP BY 
returns the correct result without an exchange.



##########
crates/integrations/datafusion/tests/range_partitioning.rs:
##########
@@ -0,0 +1,552 @@
+// 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.
+
+mod common;
+
+use std::sync::Arc;
+
+use arrow_array::{Array, Int32Array};
+use datafusion::common::ScalarValue;
+use datafusion::physical_plan::{
+    collect_partitioned, displayable, ExecutionPlan, ExecutionPlanProperties, 
Partitioning,
+};
+use paimon_datafusion::SQLContext;
+
+fn scan(plan: &Arc<dyn ExecutionPlan>) -> Arc<dyn ExecutionPlan> {
+    fn find(plan: &Arc<dyn ExecutionPlan>) -> Option<Arc<dyn ExecutionPlan>> {
+        if matches!(plan.name(), "PaimonTableScan" | "PaimonAuditLogScan") {
+            return Some(Arc::clone(plan));
+        }
+        plan.children().into_iter().find_map(find)
+    }
+    find(plan).expect("Paimon scan")
+}
+
+async fn plan(ctx: &SQLContext, query: &str) -> Arc<dyn ExecutionPlan> {
+    ctx.sql(query)
+        .await
+        .unwrap()
+        .create_physical_plan()
+        .await
+        .unwrap()
+}
+
+#[tokio::test]
+async fn 
integer_ranges_keep_equal_keys_together_and_avoid_aggregation_shuffle() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    common::exec(
+        &ctx,
+        "CREATE TABLE paimon.test_db.ranges (id INT, pt INT, value INT) 
PARTITIONED BY (pt)",
+    )
+    .await;
+    // Two commits put equal keys in distinct files/splits. Numeric order 
differs
+    // from directory-name order, and NULL must occupy the final range.
+    for values in [
+        "(1, 10, 6), (2, -10, 2), (3, 2, 4), (4, NULL, 5)",
+        "(5, 2, 40), (6, 10, 60), (7, -10, 20), (8, NULL, 50)",
+    ] {
+        common::exec(
+            &ctx,
+            &format!("INSERT INTO paimon.test_db.ranges VALUES {values}"),
+        )
+        .await;
+    }
+
+    let scan = scan(&plan(&ctx, "SELECT id, pt, value FROM 
paimon.test_db.ranges").await);
+    let Partitioning::Range(range) = scan.output_partitioning() else {
+        panic!(
+            "expected range partitioning, got {:?}",
+            scan.output_partitioning()
+        );
+    };
+    assert_eq!(range.partition_count(), 2);
+    assert_eq!(range.ordering()[0].expr.to_string(), "pt@1");
+    assert_eq!(
+        range.split_points()[0].values(),
+        &[ScalarValue::Int32(Some(10))]
+    );
+    assert!(
+        scan.output_ordering().is_none(),
+        "ranges do not imply sorted rows"
+    );
+    let partitions = collect_partitioned(scan, ctx.ctx().task_ctx())
+        .await
+        .unwrap();
+    let mut actual = Vec::new();
+    for batches in partitions {
+        let mut keys = Vec::new();
+        for batch in batches {
+            let pt = batch
+                .column(1)
+                .as_any()
+                .downcast_ref::<Int32Array>()
+                .unwrap();
+            keys.extend((0..pt.len()).map(|i| (!pt.is_null(i)).then(|| 
pt.value(i))));
+        }
+        keys.sort_by_key(|key| (key.is_none(), *key));
+        actual.push(keys);
+    }
+    assert_eq!(
+        actual,
+        vec![
+            vec![Some(-10), Some(-10), Some(2), Some(2)],
+            vec![Some(10), Some(10), None, None]
+        ]
+    );
+
+    let query = "SELECT CAST(coalesce(pt, -100) AS INT) AS id, CAST(sum(value) 
AS INT) AS value FROM paimon.test_db.ranges GROUP BY pt";
+    let physical = plan(&ctx, query).await;
+    let text = displayable(physical.as_ref()).indent(true).to_string();
+    assert!(!text.contains("RepartitionExec"), "{text}");
+    assert_eq!(
+        common::collect_id_value(&ctx, query).await,
+        vec![(-100, 55), (-10, 22), (2, 44), (10, 66)]
+    );
+    for (predicate, expected) in [
+        ("pt < 10", vec![(2, 2), (3, 4), (5, 40), (7, 20)]),
+        ("pt >= 10", vec![(1, 6), (6, 60)]),
+        ("pt IS NULL", vec![(4, 5), (8, 50)]),
+    ] {
+        assert_eq!(
+            common::collect_id_value(
+                &ctx,
+                &format!("SELECT id, value FROM paimon.test_db.ranges WHERE 
{predicate}")
+            )
+            .await,
+            expected
+        );
+    }
+    // Local sorting is still required, even though the partitions have ranges.
+    let sorted = plan(
+        &ctx,
+        "SELECT id, pt FROM paimon.test_db.ranges ORDER BY pt, id",
+    )
+    .await;
+    assert!(displayable(sorted.as_ref())
+        .indent(true)
+        .to_string()
+        .contains("SortExec"));
+}
+
+#[tokio::test]
+async fn 
aggregation_of_non_primary_partition_keys_keeps_unknown_distribution() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    common::exec(&ctx, "CREATE TABLE paimon.test_db.aggregated_ranges (id INT 
NOT NULL, pt INT, value INT, PRIMARY KEY (id)) PARTITIONED BY (pt) WITH 
('bucket' = '-1', 'merge-engine' = 'aggregation', 
'fields.pt.aggregate-function' = 'sum', 'fields.value.aggregate-function' = 
'sum')").await;
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.aggregated_ranges VALUES (1, 1, 10), (2, 
2, 30)",
+    )
+    .await;
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.aggregated_ranges VALUES (1, 1, 20)",
+    )
+    .await;
+    let query = "SELECT pt AS id, CAST(sum(value) AS INT) AS value FROM 
paimon.test_db.aggregated_ranges GROUP BY pt";
+    assert_eq!(common::collect_id_value(&ctx, query).await, vec![(2, 60)]);
+    let physical = plan(
+        &ctx,
+        "SELECT id, pt, value FROM paimon.test_db.aggregated_ranges",
+    )
+    .await;
+    assert!(matches!(
+        scan(&physical).output_partitioning(),
+        Partitioning::UnknownPartitioning(_)
+    ));
+}
+
+#[tokio::test]
+async fn 
partial_update_of_non_primary_partition_keys_keeps_unknown_distribution() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    common::exec(&ctx, "CREATE TABLE paimon.test_db.partial_ranges (id INT NOT 
NULL, pt INT, ver INT, value INT, PRIMARY KEY (id)) PARTITIONED BY (pt) WITH 
('bucket' = '-1', 'merge-engine' = 'partial-update', 
'fields.ver.sequence-group' = 'pt,value', 'fields.pt.aggregate-function' = 
'sum', 'fields.value.aggregate-function' = 'sum')").await;
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.partial_ranges VALUES (1, 1, 1, 10), (2, 
2, 1, 30)",
+    )
+    .await;
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.partial_ranges VALUES (1, 1, 2, 20)",
+    )
+    .await;
+    let query = "SELECT pt AS id, CAST(sum(value) AS INT) AS value FROM 
paimon.test_db.partial_ranges GROUP BY pt";
+    assert_eq!(common::collect_id_value(&ctx, query).await, vec![(2, 60)]);
+    let physical = plan(
+        &ctx,
+        "SELECT id, pt, value FROM paimon.test_db.partial_ranges",
+    )
+    .await;
+    assert!(matches!(
+        scan(&physical).output_partitioning(),
+        Partitioning::UnknownPartitioning(_)
+    ));
+}
+
+#[tokio::test]
+async fn 
historically_aggregated_non_primary_partition_keys_keep_unknown_distribution() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    common::exec(&ctx, "CREATE TABLE paimon.test_db.historical_ranges (id INT 
NOT NULL, pt INT, value INT, PRIMARY KEY (id)) PARTITIONED BY (pt) WITH 
('bucket' = '-1', 'merge-engine' = 'aggregation', 
'fields.pt.aggregate-function' = 'sum', 'fields.value.aggregate-function' = 
'sum')").await;
+    // Writer-side aggregation persists pt=2 in a file assigned to partition 1.
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.historical_ranges VALUES (1, 1, 10), (1, 
1, 20), (2, 2, 30)",
+    )
+    .await;
+    common::exec(
+        &ctx,
+        "ALTER TABLE paimon.test_db.historical_ranges SET ('merge-engine' = 
'deduplicate')",
+    )
+    .await;
+    let query = "SELECT pt AS id, CAST(sum(value) AS INT) AS value FROM 
paimon.test_db.historical_ranges GROUP BY pt";
+    assert_eq!(common::collect_id_value(&ctx, query).await, vec![(2, 60)]);
+    let physical = plan(
+        &ctx,
+        "SELECT id, pt, value FROM paimon.test_db.historical_ranges",
+    )
+    .await;
+    assert!(matches!(
+        scan(&physical).output_partitioning(),
+        Partitioning::UnknownPartitioning(_)
+    ));
+}
+
+#[tokio::test]
+async fn 
merge_engines_preserve_ranges_for_partition_columns_in_the_primary_key() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    for (name, engine, extra) in [
+        (
+            "aggregation_full_pk",
+            "aggregation",
+            ", 'fields.pt.aggregate-function' = 'sum'",
+        ),
+        (
+            "partial_full_pk",
+            "partial-update",
+            ", 'fields.ver.sequence-group' = 'value'",
+        ),
+    ] {
+        common::exec(&ctx, &format!("CREATE TABLE paimon.test_db.{name} (id 
INT NOT NULL, pt INT NOT NULL, ver INT, value INT, PRIMARY KEY (pt, id)) 
PARTITIONED BY (pt) WITH ('bucket' = '1', 'merge-engine' = '{engine}', 
'fields.value.aggregate-function' = 'sum'{extra})")).await;
+        common::exec(
+            &ctx,
+            &format!("INSERT INTO paimon.test_db.{name} VALUES (1, 1, 1, 10), 
(2, 2, 1, 30)"),
+        )
+        .await;
+        common::exec(
+            &ctx,
+            &format!("INSERT INTO paimon.test_db.{name} VALUES (1, 1, 2, 20)"),
+        )
+        .await;
+        let query = format!("SELECT pt AS id, CAST(sum(value) AS INT) AS value 
FROM paimon.test_db.{name} GROUP BY pt");
+        let physical = plan(&ctx, &query).await;
+        let text = displayable(physical.as_ref()).indent(true).to_string();
+        assert!(
+            matches!(
+                scan(&physical).output_partitioning(),
+                Partitioning::Range(_)
+            ),
+            "{text}"
+        );
+        assert!(!text.contains("RepartitionExec"), "{text}");
+        assert_eq!(
+            common::collect_id_value(&ctx, &query).await,
+            vec![(1, 30), (2, 30)],
+            "{engine}"
+        );
+    }
+}
+
+#[tokio::test]
+async fn joins_align_different_ranges_after_primary_key_updates() {
+    let (_tmp, ctx) = common::setup_sql_context().await;
+    common::exec(&ctx, "SET datafusion.execution.target_partitions = 2").await;
+    common::exec(&ctx, "CREATE TABLE paimon.test_db.pk_ranges (id INT NOT 
NULL, pt INT NOT NULL, value INT, PRIMARY KEY (pt, id)) PARTITIONED BY (pt) 
WITH ('bucket' = '2')").await;
+    common::exec(&ctx, "INSERT INTO paimon.test_db.pk_ranges VALUES (1, 1, 
10), (2, 2, 20), (3, 3, 30), (4, 4, 40)").await;
+    common::exec(
+        &ctx,
+        "INSERT INTO paimon.test_db.pk_ranges VALUES (2, 2, 200)",
+    )
+    .await;
+    common::exec(
+        &ctx,
+        "CREATE TABLE paimon.test_db.other_ranges (pt INT, value INT) 
PARTITIONED BY (pt)",
+    )
+    .await;
+    common::exec(&ctx, "INSERT INTO paimon.test_db.other_ranges VALUES (1, 
100), (2, 200), (3, 300), (4, 400), (5, 500), (6, 600)").await;
+
+    let left = scan(&plan(&ctx, "SELECT * FROM 
paimon.test_db.pk_ranges").await);
+    let right = scan(&plan(&ctx, "SELECT * FROM 
paimon.test_db.other_ranges").await);
+    let (Partitioning::Range(left), Partitioning::Range(right)) =
+        (left.output_partitioning(), right.output_partitioning())
+    else {
+        panic!("both inputs must have ranges");
+    };
+    assert_eq!(
+        left.split_points()[0].values(),
+        &[ScalarValue::Int32(Some(3))]
+    );
+    assert_eq!(
+        right.split_points()[0].values(),
+        &[ScalarValue::Int32(Some(4))]
+    );
+    for prefer_hash in [true, false] {
+        common::exec(
+            &ctx,
+            &format!("SET datafusion.optimizer.prefer_hash_join = 
{prefer_hash}"),
+        )
+        .await;
+        common::exec(
+            &ctx,
+            "SET datafusion.optimizer.hash_join_single_partition_threshold = 
0",
+        )
+        .await;
+        common::exec(
+            &ctx,
+            "SET 
datafusion.optimizer.hash_join_single_partition_threshold_rows = 0",
+        )
+        .await;
+        let query = "SELECT l.id, l.value + r.value AS value FROM 
paimon.test_db.pk_ranges l JOIN paimon.test_db.other_ranges r ON l.pt = r.pt";
+        let physical = plan(&ctx, query).await;
+        let text = displayable(physical.as_ref()).indent(true).to_string();
+        let join = if prefer_hash {
+            "HashJoinExec"
+        } else {
+            "SortMergeJoinExec"
+        };
+        assert!(text.contains(join), "{text}");
+        assert!(

Review Comment:
   Could we also add a join case where both inputs have identical range 
boundaries? This test covers the fallback that inserts a RepartitionExec for 
different boundaries, but it does not exercise the advertised exchange 
elimination for compatible joins. For both HashJoinExec and SortMergeJoinExec, 
please assert the expected result and the absence of RepartitionExec; the 
sort-merge case may still require local SortExec nodes.



-- 
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]

Reply via email to