Skip to content

Commit 891a800

Browse files
authored
Avoid generate duplicate sort Keys from Window Expressions, fix bug when decide Window Expressions ordering (#4643)
* Avoid generate duplicate sort Keys from Window Expressions, fix bug when decide Window Expressions ordering * fix test comment * fix UT * fix UT * Fix create Sort Columns from Partition Columns in WindowExpr, add more UTs for Null String sort testing * fix clippy check * tiny change * merge with upstream, fix issue
1 parent dba34fc commit 891a800

7 files changed

Lines changed: 422 additions & 28 deletions

File tree

‎datafusion/core/src/physical_plan/planner.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -564,12 +564,12 @@ impl DefaultPhysicalPlanner {
564564
}
565565
_ => unreachable!(),
566566
};
567-
let sort_keys = get_sort_keys(&window_expr[0]);
567+
let sort_keys = get_sort_keys(&window_expr[0])?;
568568
if window_expr.len() > 1 {
569569
debug_assert!(
570570
window_expr[1..]
571571
.iter()
572-
.all(|expr| get_sort_keys(expr) == sort_keys),
572+
.all(|expr| get_sort_keys(expr).unwrap() == sort_keys),
573573
"all window expressions shall have the same sort keys, as guaranteed by logical planning"
574574
);
575575
}

‎datafusion/core/tests/sql/select.rs‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -835,6 +835,88 @@ async fn query_on_string_dictionary() -> Result<()> {
835835
Ok(())
836836
}
837837

838+
#[tokio::test]
839+
async fn sort_on_window_null_string() -> Result<()> {
840+
let d1: DictionaryArray<Int32Type> =
841+
vec![Some("one"), None, Some("three")].into_iter().collect();
842+
let d2: StringArray = vec![Some("ONE"), None, Some("THREE")].into_iter().collect();
843+
let d3: LargeStringArray =
844+
vec![Some("One"), None, Some("Three")].into_iter().collect();
845+
846+
let batch = RecordBatch::try_from_iter(vec![
847+
("d1", Arc::new(d1) as ArrayRef),
848+
("d2", Arc::new(d2) as ArrayRef),
849+
("d3", Arc::new(d3) as ArrayRef),
850+
])
851+
.unwrap();
852+
853+
let ctx = SessionContext::with_config(SessionConfig::new().with_target_partitions(2));
854+
ctx.register_batch("test", batch)?;
855+
856+
let sql =
857+
"SELECT d1, row_number() OVER (partition by d1) as rn1 FROM test order by d1 asc";
858+
859+
let actual = execute_to_batches(&ctx, sql).await;
860+
// NULLS LAST
861+
let expected = vec![
862+
"+-------+-----+",
863+
"| d1 | rn1 |",
864+
"+-------+-----+",
865+
"| one | 1 |",
866+
"| three | 1 |",
867+
"| | 1 |",
868+
"+-------+-----+",
869+
];
870+
assert_batches_eq!(expected, &actual);
871+
872+
let sql = "SELECT d2, row_number() OVER (partition by d2) as rn1 FROM test";
873+
let actual = execute_to_batches(&ctx, sql).await;
874+
// NULLS LAST
875+
let expected = vec![
876+
"+-------+-----+",
877+
"| d2 | rn1 |",
878+
"+-------+-----+",
879+
"| ONE | 1 |",
880+
"| THREE | 1 |",
881+
"| | 1 |",
882+
"+-------+-----+",
883+
];
884+
assert_batches_eq!(expected, &actual);
885+
886+
let sql =
887+
"SELECT d2, row_number() OVER (partition by d2 order by d2 desc) as rn1 FROM test";
888+
889+
let actual = execute_to_batches(&ctx, sql).await;
890+
// NULLS FIRST
891+
let expected = vec![
892+
"+-------+-----+",
893+
"| d2 | rn1 |",
894+
"+-------+-----+",
895+
"| | 1 |",
896+
"| THREE | 1 |",
897+
"| ONE | 1 |",
898+
"+-------+-----+",
899+
];
900+
assert_batches_eq!(expected, &actual);
901+
902+
// FIXME sort on LargeUtf8 String has bug.
903+
// let sql =
904+
// "SELECT d3, row_number() OVER (partition by d3) as rn1 FROM test";
905+
// let actual = execute_to_batches(&ctx, sql).await;
906+
// let expected = vec![
907+
// "+-------+-----+",
908+
// "| d3 | rn1 |",
909+
// "+-------+-----+",
910+
// "| | 1 |",
911+
// "| One | 1 |",
912+
// "| Three | 1 |",
913+
// "+-------+-----+",
914+
// ];
915+
// assert_batches_eq!(expected, &actual);
916+
917+
Ok(())
918+
}
919+
838920
#[tokio::test]
839921
async fn filter_with_time32second() -> Result<()> {
840922
let ctx = SessionContext::new();

‎datafusion/core/tests/sql/window.rs‎

Lines changed: 114 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1642,7 +1642,120 @@ async fn test_window_agg_sort() -> Result<()> {
16421642
assert_eq!(
16431643
expected, actual_trim_last,
16441644
"\n\nexpected:\n\n{:#?}\nactual:\n\n{:#?}\n\n",
1645-
expected, actual
1645+
expected, actual_trim_last
1646+
);
1647+
Ok(())
1648+
}
1649+
1650+
#[tokio::test]
1651+
async fn over_order_by_sort_keys_sorting_prefix_compacting() -> Result<()> {
1652+
let ctx = SessionContext::with_config(SessionConfig::new().with_target_partitions(2));
1653+
register_aggregate_csv(&ctx).await?;
1654+
1655+
let sql = "SELECT c2, MAX(c9) OVER (ORDER BY c2), SUM(c9) OVER (), MIN(c9) OVER (ORDER BY c2, c9) from aggregate_test_100";
1656+
1657+
let msg = format!("Creating logical plan for '{}'", sql);
1658+
let plan = ctx.create_logical_plan(sql).expect(&msg);
1659+
let state = ctx.state();
1660+
let logical_plan = state.optimize(&plan)?;
1661+
let physical_plan = state.create_physical_plan(&logical_plan).await?;
1662+
let formatted = displayable(physical_plan.as_ref()).indent().to_string();
1663+
// Only 1 SortExec was added
1664+
let expected = {
1665+
vec![
1666+
"ProjectionExec: expr=[c2@3 as c2, MAX(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c2 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@1 as MAX(aggregate_test_100.c9), SUM(aggregate_test_100.c9) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING@0 as SUM(aggregate_test_100.c9), MIN(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c2 ASC NULLS LAST, aggregate_test_100.c9 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as MIN(aggregate_test_100.c9)]",
1667+
" WindowAggExec: wdw=[SUM(aggregate_test_100.c9): Ok(Field { name: \"SUM(aggregate_test_100.c9)\", data_type: UInt64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(NULL)), end_bound: Following(UInt64(NULL)) }]",
1668+
" WindowAggExec: wdw=[MAX(aggregate_test_100.c9): Ok(Field { name: \"MAX(aggregate_test_100.c9)\", data_type: UInt32, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Range, start_bound: Preceding(UInt32(NULL)), end_bound: CurrentRow }]",
1669+
" WindowAggExec: wdw=[MIN(aggregate_test_100.c9): Ok(Field { name: \"MIN(aggregate_test_100.c9)\", data_type: UInt32, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Range, start_bound: Preceding(UInt32(NULL)), end_bound: CurrentRow }]",
1670+
" SortExec: [c2@0 ASC NULLS LAST,c9@1 ASC NULLS LAST]"
1671+
]
1672+
};
1673+
1674+
let actual: Vec<&str> = formatted.trim().lines().collect();
1675+
let actual_len = actual.len();
1676+
let actual_trim_last = &actual[..actual_len - 1];
1677+
assert_eq!(
1678+
expected, actual_trim_last,
1679+
"\n\nexpected:\n\n{:#?}\nactual:\n\n{:#?}\n\n",
1680+
expected, actual_trim_last
1681+
);
1682+
Ok(())
1683+
}
1684+
1685+
/// FIXME: for now we are not detecting prefix of sorting keys in order to re-arrange with global and save one SortExec
1686+
#[tokio::test]
1687+
async fn over_order_by_sort_keys_sorting_global_order_compacting() -> Result<()> {
1688+
let ctx = SessionContext::with_config(SessionConfig::new().with_target_partitions(2));
1689+
register_aggregate_csv(&ctx).await?;
1690+
1691+
let sql = "SELECT c2, MAX(c9) OVER (ORDER BY c9, c2), SUM(c9) OVER (), MIN(c9) OVER (ORDER BY c2, c9) from aggregate_test_100 ORDER BY c2";
1692+
let msg = format!("Creating logical plan for '{}'", sql);
1693+
let plan = ctx.create_logical_plan(sql).expect(&msg);
1694+
let state = ctx.state();
1695+
let logical_plan = state.optimize(&plan)?;
1696+
let physical_plan = state.create_physical_plan(&logical_plan).await?;
1697+
let formatted = displayable(physical_plan.as_ref()).indent().to_string();
1698+
// 3 SortExec are added
1699+
let expected = {
1700+
vec![
1701+
"SortExec: [c2@0 ASC NULLS LAST]",
1702+
" CoalescePartitionsExec",
1703+
" ProjectionExec: expr=[c2@3 as c2, MAX(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST, aggregate_test_100.c2 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@1 as MAX(aggregate_test_100.c9), SUM(aggregate_test_100.c9) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING@0 as SUM(aggregate_test_100.c9), MIN(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c2 ASC NULLS LAST, aggregate_test_100.c9 ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as MIN(aggregate_test_100.c9)]",
1704+
" RepartitionExec: partitioning=RoundRobinBatch(2)",
1705+
" WindowAggExec: wdw=[SUM(aggregate_test_100.c9): Ok(Field { name: \"SUM(aggregate_test_100.c9)\", data_type: UInt64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(NULL)), end_bound: Following(UInt64(NULL)) }]",
1706+
" WindowAggExec: wdw=[MAX(aggregate_test_100.c9): Ok(Field { name: \"MAX(aggregate_test_100.c9)\", data_type: UInt32, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Range, start_bound: Preceding(UInt32(NULL)), end_bound: CurrentRow }]",
1707+
" SortExec: [c9@2 ASC NULLS LAST,c2@1 ASC NULLS LAST]",
1708+
" WindowAggExec: wdw=[MIN(aggregate_test_100.c9): Ok(Field { name: \"MIN(aggregate_test_100.c9)\", data_type: UInt32, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Range, start_bound: Preceding(UInt32(NULL)), end_bound: CurrentRow }]",
1709+
" SortExec: [c2@0 ASC NULLS LAST,c9@1 ASC NULLS LAST]",
1710+
]
1711+
};
1712+
1713+
let actual: Vec<&str> = formatted.trim().lines().collect();
1714+
let actual_len = actual.len();
1715+
let actual_trim_last = &actual[..actual_len - 1];
1716+
assert_eq!(
1717+
expected, actual_trim_last,
1718+
"\n\nexpected:\n\n{:#?}\nactual:\n\n{:#?}\n\n",
1719+
expected, actual_trim_last
1720+
);
1721+
Ok(())
1722+
}
1723+
1724+
#[tokio::test]
1725+
async fn test_window_partition_by_order_by() -> Result<()> {
1726+
let ctx = SessionContext::with_config(SessionConfig::new().with_target_partitions(2));
1727+
register_aggregate_csv(&ctx).await?;
1728+
1729+
let sql = "SELECT \
1730+
SUM(c4) OVER(PARTITION BY c1, c2 ORDER BY c2 ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING),\
1731+
COUNT(*) OVER(PARTITION BY c1 ORDER BY c2 ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) \
1732+
FROM aggregate_test_100";
1733+
1734+
let msg = format!("Creating logical plan for '{}'", sql);
1735+
let plan = ctx.create_logical_plan(sql).expect(&msg);
1736+
let state = ctx.state();
1737+
let logical_plan = state.optimize(&plan)?;
1738+
let physical_plan = state.create_physical_plan(&logical_plan).await?;
1739+
let formatted = displayable(physical_plan.as_ref()).indent().to_string();
1740+
// Only 1 SortExec was added
1741+
let expected = {
1742+
vec![
1743+
"ProjectionExec: expr=[SUM(aggregate_test_100.c4) PARTITION BY [aggregate_test_100.c1, aggregate_test_100.c2] ORDER BY [aggregate_test_100.c2 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING@0 as SUM(aggregate_test_100.c4), COUNT(UInt8(1)) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c2 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING@1 as COUNT(UInt8(1))]",
1744+
" WindowAggExec: wdw=[SUM(aggregate_test_100.c4): Ok(Field { name: \"SUM(aggregate_test_100.c4)\", data_type: Int64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(1)), end_bound: Following(UInt64(1)) }, COUNT(UInt8(1)): Ok(Field { name: \"COUNT(UInt8(1))\", data_type: Int64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(1)), end_bound: Following(UInt64(1)) }]",
1745+
" SortExec: [c1@0 ASC NULLS LAST,c2@1 ASC NULLS LAST]",
1746+
" CoalesceBatchesExec: target_batch_size=4096",
1747+
" RepartitionExec: partitioning=Hash([Column { name: \"c1\", index: 0 }], 2)",
1748+
" RepartitionExec: partitioning=RoundRobinBatch(2)",
1749+
]
1750+
};
1751+
1752+
let actual: Vec<&str> = formatted.trim().lines().collect();
1753+
let actual_len = actual.len();
1754+
let actual_trim_last = &actual[..actual_len - 1];
1755+
assert_eq!(
1756+
expected, actual_trim_last,
1757+
"\n\nexpected:\n\n{:#?}\nactual:\n\n{:#?}\n\n",
1758+
expected, actual_trim_last
16461759
);
16471760
Ok(())
16481761
}

‎datafusion/expr/src/logical_plan/builder.rs‎

Lines changed: 23 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ use crate::expr_rewriter::{
2222
normalize_cols, rewrite_sort_cols_by_aggs,
2323
};
2424
use crate::type_coercion::binary::comparison_coercion;
25-
use crate::utils::{columnize_expr, exprlist_to_fields, from_plan};
25+
use crate::utils::{columnize_expr, compare_sort_expr, exprlist_to_fields, from_plan};
2626
use crate::{and, binary_expr, Operator};
2727
use crate::{
2828
logical_plan::{
@@ -43,6 +43,7 @@ use datafusion_common::{
4343
ToDFSchema,
4444
};
4545
use std::any::Any;
46+
use std::cmp::Ordering;
4647
use std::collections::{HashMap, HashSet};
4748
use std::convert::TryFrom;
4849
use std::sync::Arc;
@@ -250,16 +251,29 @@ impl LogicalPlanBuilder {
250251
) -> Result<LogicalPlan> {
251252
let mut plan = input;
252253
let mut groups = group_window_expr_by_sort_keys(&window_exprs)?;
253-
// sort by sort_key len descending, so that more deeply sorted plans gets nested further
254-
// down as children; to further mimic the behavior of PostgreSQL, we want stable sort
255-
// and a reverse so that tieing sort keys are reversed in order; note that by this rule
256-
// if there's an empty over, it'll be at the top level
257-
groups.sort_by(|(key_a, _), (key_b, _)| key_a.len().cmp(&key_b.len()));
258-
groups.reverse();
254+
// To align with the behavior of PostgreSQL, we want the sort_keys sorted as same rule as PostgreSQL that first
255+
// we compare the sort key themselves and if one window's sort keys are a prefix of another
256+
// put the window with more sort keys first. so more deeply sorted plans gets nested further down as children.
257+
// The sort_by() implementation here is a stable sort.
258+
// Note that by this rule if there's an empty over, it'll be at the top level
259+
groups.sort_by(|(key_a, _), (key_b, _)| {
260+
for (first, second) in key_a.iter().zip(key_b.iter()) {
261+
let key_ordering = compare_sort_expr(first, second, plan.schema());
262+
match key_ordering {
263+
Ordering::Less => {
264+
return Ordering::Less;
265+
}
266+
Ordering::Greater => {
267+
return Ordering::Greater;
268+
}
269+
Ordering::Equal => {}
270+
}
271+
}
272+
key_b.len().cmp(&key_a.len())
273+
});
259274
for (_, exprs) in groups {
260275
let window_exprs = exprs.into_iter().cloned().collect::<Vec<_>>();
261-
// the partition and sort itself is done at physical level, see physical_planner's
262-
// fn create_initial_plan
276+
// the partition and sort itself is done at physical level, see the BasicEnforcement rule
263277
plan = LogicalPlanBuilder::from(plan)
264278
.window(window_exprs)?
265279
.build()?;

0 commit comments

Comments
 (0)