Skip to content

Commit 8c433af

Browse files
metesynnadaberkaysynnadamustafasrepoozankabak
committed
Global join selection (#183)
* Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * Initial comments on working * License update (#157) This extension adds Synnada license information to the existing one. * Adding comments * Update sort_hash_join.rs * After merge silent error * Change the query in HashJoin * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Update rat_exclude_files.txt * Clippy solving. * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * Sliding Nested Join Algorithm (#142) * Sliding Hash Join Algorithm (SWHJ) (#147) * Fix errors introduced during rebase * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * Sliding Nested Join Algorithm (#142) * Sliding Hash Join Algorithm (SWHJ) (#147) * Fix errors introduced during rebase * Keep Track of Global Ordering Requirement (#165) * Prunability of Join Filter Physical Expressions (#161) * BinaryExpr Equivalence (#116) * Fix errors introduced during rebase * Support multiple ordered columns on joins and expression graph (#163) * After merge * SlidingHashJoin and SlidingNestedLoopJoin planner integration (#171) * Before clippy fmt etc. * lazy loading tables * mini test * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * Sliding Nested Join Algorithm (#142) * Sliding Hash Join Algorithm (SWHJ) (#147) * Fix errors introduced during rebase * Keep Track of Global Ordering Requirement (#165) * Prunability of Join Filter Physical Expressions (#161) * BinaryExpr Equivalence (#116) * Fix errors introduced during rebase * Support multiple ordered columns on joins and expression graph (#163) * SlidingHashJoin and SlidingNestedLoopJoin planner integration (#171) * Add license, add contribution hash commits, minor changes * Before rebase merge * Add license, add contribution hash commits, minor changes, add scripts to automate hash generation,Delete docs yaml file * Update utils.rs * Print deletion * Update Cargo.lock * Refactor for review * Working without slt * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * Sliding Nested Join Algorithm (#142) * Sliding Hash Join Algorithm (SWHJ) (#147) * Fix errors introduced during rebase * Keep Track of Global Ordering Requirement (#165) * Prunability of Join Filter Physical Expressions (#161) * BinaryExpr Equivalence (#116) * Fix errors introduced during rebase * Support multiple ordered columns on joins and expression graph (#163) * SlidingHashJoin and SlidingNestedLoopJoin planner integration (#171) * Add license, add contribution hash commits, minor changes, add scripts to automate hash generation,Delete docs yaml file * Change in test folders * Update join_pipeline_selection.rs * Update utils.rs * Before clippy * Before SLT * Tests are passing and clippy OK. * [GITHUB ACTION] Refactor for license and actions (#148) * Delete datafusion main publication * Adding licence information, refactoring prunibility issues * Update SYNNADA-CONTRIBUTIONS.txt * Update rat_exclude_files.txt * Enhanced Pipeline Execution: Now Supporting Complex Query Plans for Improved Performance (#132) * Very initial test passing algorithm * Working except a minor bug in interval calculations * After clippy * Plan * initial implemantation * Before prune check ability is added. Order equivalence implementations will vanish after we send a seperate PR * minor changes * Fix bug, ordering equivalence random head * minor changes * Add ordering equivalence for sort merge join * Improvement on tests * Upstream changes * Add ordering equivalence for sort merge join * Fmt issues * Update comment * Add ordering equivalence support for hash join * Make 1 file * Code enhancements/comment improvements * Add projection cast handling * Fix output ordering for sort merge join * projection bug fix * Minor changes * minor changes * simplify sort_merge_join * Update equivalence implementation * Update test_utils.rs * Update cast implementation * More idiomatic code * After merge * Comments visisted * Add key swap according to the children orders * Refactoring * After merge refactor * Update sort_enforcement.rs * Update datafusion/core/src/physical_optimizer/join_selection.rs Co-authored-by: Mustafa Akur <[email protected]> * Comments are applied * Feature/determine prunability (#139) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition * Determine prunability of tables for join operations (#90) * ready to review * license added * simplifications * simplifications * sort expr's are taken separately for each table * we can return the sort info of the expression now * check filter conditions * simplifications * simplifications * functions are implemented for SortInfo calculations * node specialized tableSide functions * NotImplemented errors are added, test comments are added * Comment change * Simplify comparison node calculations * Simplfications and better commenting * is_prunable function is updated with new Prunability function * Indices of sort expressions are updated with intermediate schema columns of the filter * Unused function is removed * Future-proof index updating * An if let check is removed * simplifications * Simplifications * simplifications * Change if condition --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * fix the tables' unboundedness --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Comment improvements and minor code improvements * Splitting the order based join selection * Update rat_exclude_files.txt * Revert "Feature/determine prunability (#139)" This reverts commit cf56105. * Commented --------- Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Berkay Şahin <[email protected]> * Bug fix: Fix lexicographical column search among provided ordering (#156) * License update (#157) This extension adds Synnada license information to the existing one. * Sliding Nested Join Algorithm (#142) * Sliding Hash Join Algorithm (SWHJ) (#147) * Fix errors introduced during rebase * Keep Track of Global Ordering Requirement (#165) * Prunability of Join Filter Physical Expressions (#161) * BinaryExpr Equivalence (#116) * Fix errors introduced during rebase * Support multiple ordered columns on joins and expression graph (#163) * SlidingHashJoin and SlidingNestedLoopJoin planner integration (#171) * Add license, add contribution hash commits, minor changes, add scripts to automate hash generation,Delete docs yaml file * Resolve errors introduced during rebase * After merge * Update rat_exclude_files.txt * Comments visited * Synnada Streaming SQL Tests (#190) * Adds a new method to construct window function for the given input * For mustafa * Final * Update rat_exclude_files.txt * More commenting * Fix linter errors, compile errors after rebase, Update commit hashes * After merge refactors * Dir * Additional test for coverage * Update join_disable_repartition_joins.slt * Review changes, remove code duplicates * Update subdirectory hashes --------- Co-authored-by: Berkay Şahin <[email protected]> Co-authored-by: Mustafa Akur <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Mustafa Akur <[email protected]>
1 parent 6156c3c commit 8c433af

17 files changed

Lines changed: 5205 additions & 1203 deletions

File tree

‎datafusion/core/src/physical_optimizer/join_pipeline_selection.rs‎

Lines changed: 2623 additions & 763 deletions
Large diffs are not rendered by default.

‎datafusion/core/src/physical_optimizer/join_selection.rs‎

Lines changed: 119 additions & 261 deletions
Large diffs are not rendered by default.

‎datafusion/core/src/physical_optimizer/test_utils.rs‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -397,6 +397,25 @@ pub fn prunable_filter(left_index: ColumnIndex, right_index: ColumnIndex) -> Joi
397397
);
398398
JoinFilter::new(filter_expr, column_indices, intermediate_schema)
399399
}
400+
pub fn partial_prunable_filter(
401+
left_index: ColumnIndex,
402+
right_index: ColumnIndex,
403+
) -> JoinFilter {
404+
// Filter columns, ensure first batches will have matching rows.
405+
let intermediate_schema = Schema::new(vec![
406+
Field::new("0", DataType::Int32, true),
407+
Field::new("1", DataType::Int32, true),
408+
]);
409+
let column_indices = vec![left_index, right_index];
410+
let filter_expr = Arc::new(BinaryExpr::new(
411+
col("0", &intermediate_schema).unwrap(),
412+
Operator::Gt,
413+
col("1", &intermediate_schema).unwrap(),
414+
));
415+
416+
JoinFilter::new(filter_expr, column_indices, intermediate_schema)
417+
}
418+
400419
pub fn not_prunable_filter(
401420
left_index: ColumnIndex,
402421
right_index: ColumnIndex,

‎datafusion/core/src/physical_optimizer/utils.rs‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,10 @@ use std::fmt;
2121
use std::fmt::Formatter;
2222
use std::sync::Arc;
2323

24+
use crate::error::Result;
25+
use crate::physical_plan::aggregates::AggregateExec;
2426
use crate::physical_plan::coalesce_partitions::CoalescePartitionsExec;
25-
use crate::physical_plan::joins::{HashJoinExec, NestedLoopJoinExec};
27+
use crate::physical_plan::joins::{CrossJoinExec, HashJoinExec, NestedLoopJoinExec};
2628
use crate::physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
2729
use crate::physical_plan::repartition::RepartitionExec;
2830
use crate::physical_plan::sorts::sort::SortExec;
@@ -164,3 +166,13 @@ pub fn is_hash_join(plan: &Arc<dyn ExecutionPlan>) -> bool {
164166
pub fn is_nested_loop_join(plan: &Arc<dyn ExecutionPlan>) -> bool {
165167
plan.as_any().is::<NestedLoopJoinExec>()
166168
}
169+
170+
/// Checks whether the given operator is a [`CrossJoinExec`].
171+
pub fn is_cross_join(plan: &Arc<dyn ExecutionPlan>) -> bool {
172+
plan.as_any().is::<CrossJoinExec>()
173+
}
174+
175+
/// Checks whether the given operator is an [`AggregateExec`].
176+
pub fn is_aggregate(plan: &Arc<dyn ExecutionPlan>) -> bool {
177+
plan.as_any().is::<AggregateExec>()
178+
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -125,13 +125,13 @@ async fn join_change_in_planner() -> Result<()> {
125125
let formatted = displayable(physical_plan.as_ref()).indent(true).to_string();
126126
let expected = {
127127
[
128-
"SymmetricHashJoinExec: mode=Partitioned, join_type=Full, on=[(a2@1, a2@1)], filter=CAST(a1@0 AS Int64) > CAST(a1@1 AS Int64) + 3 AND CAST(a1@0 AS Int64) < CAST(a1@1 AS Int64) + 10",
128+
"SlidingHashJoinExec: join_type=Full, on=[(a2@1, a2@1)], filter=CAST(a1@0 AS Int64) > CAST(a1@1 AS Int64) + 3 AND CAST(a1@0 AS Int64) < CAST(a1@1 AS Int64) + 10",
129129
" CoalesceBatchesExec: target_batch_size=8192",
130-
" RepartitionExec: partitioning=Hash([a2@1], 8), input_partitions=8",
130+
" SortPreservingRepartitionExec: partitioning=Hash([a2@1], 8), input_partitions=8",
131131
" RepartitionExec: partitioning=RoundRobinBatch(8), input_partitions=1",
132132
// " CsvExec: file_groups={1 group: [[tempdir/left.csv]]}, projection=[a1, a2], has_header=false",
133133
" CoalesceBatchesExec: target_batch_size=8192",
134-
" RepartitionExec: partitioning=Hash([a2@1], 8), input_partitions=8",
134+
" SortPreservingRepartitionExec: partitioning=Hash([a2@1], 8), input_partitions=8",
135135
" RepartitionExec: partitioning=RoundRobinBatch(8), input_partitions=1",
136136
// " CsvExec: file_groups={1 group: [[tempdir/right.csv]]}, projection=[a1, a2], has_header=false"
137137
]

‎datafusion/physical-plan/src/joins/mod.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
pub use cross_join::CrossJoinExec;
2121
pub use hash_join::HashJoinExec;
2222
pub use nested_loop_join::NestedLoopJoinExec;
23+
pub use partitioned_hash_join::PartitionedHashJoinExec;
2324
pub use sliding_hash_join::{swap_sliding_hash_join, SlidingHashJoinExec};
2425
pub use sliding_nested_loop_join::{
2526
swap_sliding_nested_loop_join, SlidingNestedLoopJoinExec,
@@ -33,6 +34,7 @@ pub mod utils;
3334
mod cross_join;
3435
mod hash_join;
3536
mod nested_loop_join;
37+
mod partitioned_hash_join;
3638
mod sliding_hash_join;
3739
mod sliding_nested_loop_join;
3840
mod sliding_window_join_utils;

‎datafusion/physical-plan/src/joins/nested_loop_join.rs‎

Lines changed: 28 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -191,6 +191,22 @@ impl ExecutionPlan for NestedLoopJoinExec {
191191
distribution_from_join_type(&self.join_type)
192192
}
193193

194+
fn unbounded_output(&self, children: &[bool]) -> Result<bool> {
195+
let (left, right) = (children[0], children[1]);
196+
if left || right {
197+
plan_err!(
198+
"Join Error: The join with cannot be executed with unbounded inputs. {}",
199+
if left && right {
200+
"Currently, we do not support unbounded inputs on both sides."
201+
} else {
202+
"Please consider a different type of join."
203+
}
204+
)
205+
} else {
206+
Ok(false)
207+
}
208+
}
209+
194210
fn equivalence_properties(&self) -> EquivalenceProperties {
195211
join_equivalence_properties(
196212
self.left.equivalence_properties(),
@@ -744,21 +760,15 @@ mod tests {
744760
use std::sync::Arc;
745761

746762
use super::*;
747-
use crate::{
748-
common, expressions::Column, memory::MemoryExec, repartition::RepartitionExec,
749-
test::build_table_i32,
750-
};
763+
use crate::joins::test_utils::partitioned_nested_join_with_filter;
764+
use crate::joins::utils::JoinSide;
765+
use crate::{expressions::Column, memory::MemoryExec, repartition::RepartitionExec, test::build_table_i32};
751766

752767
use arrow::datatypes::{DataType, Field};
753768
use datafusion_common::{assert_batches_sorted_eq, assert_contains, ScalarValue};
754769
use datafusion_execution::runtime_env::{RuntimeConfig, RuntimeEnv};
755770
use datafusion_expr::Operator;
756771
use datafusion_physical_expr::expressions::{BinaryExpr, Literal};
757-
758-
use crate::physical_plan::joins::test_utils::partitioned_nested_join_with_filter;
759-
use crate::joins::utils::JoinSide;
760-
use datafusion_common::{assert_batches_sorted_eq, assert_contains, ScalarValue};
761-
use datafusion_physical_expr::expressions::Literal;
762772
use datafusion_physical_expr::PhysicalExpr;
763773

764774
fn build_table(
@@ -831,62 +841,13 @@ mod tests {
831841
JoinFilter::new(filter_expression, column_indices, intermediate_schema)
832842
}
833843

834-
async fn multi_partitioned_join_collect(
835-
left: Arc<dyn ExecutionPlan>,
836-
right: Arc<dyn ExecutionPlan>,
837-
join_type: &JoinType,
838-
join_filter: Option<JoinFilter>,
839-
context: Arc<TaskContext>,
840-
) -> Result<(Vec<String>, Vec<RecordBatch>)> {
841-
let partition_count = 4;
842-
let mut output_partition = 1;
843-
let distribution = distribution_from_join_type(join_type);
844-
// left
845-
let left = if matches!(distribution[0], Distribution::SinglePartition) {
846-
left
847-
} else {
848-
output_partition = partition_count;
849-
Arc::new(RepartitionExec::try_new(
850-
left,
851-
Partitioning::RoundRobinBatch(partition_count),
852-
)?)
853-
} as Arc<dyn ExecutionPlan>;
854-
855-
let right = if matches!(distribution[1], Distribution::SinglePartition) {
856-
right
857-
} else {
858-
output_partition = partition_count;
859-
Arc::new(RepartitionExec::try_new(
860-
right,
861-
Partitioning::RoundRobinBatch(partition_count),
862-
)?)
863-
} as Arc<dyn ExecutionPlan>;
864-
865-
// Use the required distribution for nested loop join to test partition data
866-
let nested_loop_join =
867-
NestedLoopJoinExec::try_new(left, right, join_filter, join_type)?;
868-
let columns = columns(&nested_loop_join.schema());
869-
let mut batches = vec![];
870-
for i in 0..output_partition {
871-
let stream = nested_loop_join.execute(i, context.clone())?;
872-
let more_batches = common::collect(stream).await?;
873-
batches.extend(
874-
more_batches
875-
.into_iter()
876-
.filter(|b| b.num_rows() > 0)
877-
.collect::<Vec<_>>(),
878-
);
879-
}
880-
Ok((columns, batches))
881-
}
882-
883844
#[tokio::test]
884845
async fn join_inner_with_filter() -> Result<()> {
885846
let task_ctx = Arc::new(TaskContext::default());
886847
let left = build_left_table();
887848
let right = build_right_table();
888849
let filter = prepare_join_filter();
889-
let (columns, batches) = multi_partitioned_join_collect(
850+
let (columns, batches) = partitioned_nested_join_with_filter(
890851
left,
891852
right,
892853
&JoinType::Inner,
@@ -915,7 +876,7 @@ mod tests {
915876
let right = build_right_table();
916877

917878
let filter = prepare_join_filter();
918-
let (columns, batches) = multi_partitioned_join_collect(
879+
let (columns, batches) = partitioned_nested_join_with_filter(
919880
left,
920881
right,
921882
&JoinType::Left,
@@ -946,7 +907,7 @@ mod tests {
946907
let right = build_right_table();
947908

948909
let filter = prepare_join_filter();
949-
let (columns, batches) = multi_partitioned_join_collect(
910+
let (columns, batches) = partitioned_nested_join_with_filter(
950911
left,
951912
right,
952913
&JoinType::Right,
@@ -977,7 +938,7 @@ mod tests {
977938
let right = build_right_table();
978939

979940
let filter = prepare_join_filter();
980-
let (columns, batches) = multi_partitioned_join_collect(
941+
let (columns, batches) = partitioned_nested_join_with_filter(
981942
left,
982943
right,
983944
&JoinType::Full,
@@ -1010,7 +971,7 @@ mod tests {
1010971
let right = build_right_table();
1011972

1012973
let filter = prepare_join_filter();
1013-
let (columns, batches) = multi_partitioned_join_collect(
974+
let (columns, batches) = partitioned_nested_join_with_filter(
1014975
left,
1015976
right,
1016977
&JoinType::LeftSemi,
@@ -1039,7 +1000,7 @@ mod tests {
10391000
let right = build_right_table();
10401001

10411002
let filter = prepare_join_filter();
1042-
let (columns, batches) = multi_partitioned_join_collect(
1003+
let (columns, batches) = partitioned_nested_join_with_filter(
10431004
left,
10441005
right,
10451006
&JoinType::LeftAnti,
@@ -1069,7 +1030,7 @@ mod tests {
10691030
let right = build_right_table();
10701031

10711032
let filter = prepare_join_filter();
1072-
let (columns, batches) = multi_partitioned_join_collect(
1033+
let (columns, batches) = partitioned_nested_join_with_filter(
10731034
left,
10741035
right,
10751036
&JoinType::RightSemi,
@@ -1098,7 +1059,7 @@ mod tests {
10981059
let right = build_right_table();
10991060

11001061
let filter = prepare_join_filter();
1101-
let (columns, batches) = multi_partitioned_join_collect(
1062+
let (columns, batches) = partitioned_nested_join_with_filter(
11021063
left,
11031064
right,
11041065
&JoinType::RightAnti,
@@ -1152,7 +1113,7 @@ mod tests {
11521113
let task_ctx = TaskContext::default().with_runtime(runtime);
11531114
let task_ctx = Arc::new(task_ctx);
11541115

1155-
let err = multi_partitioned_join_collect(
1116+
let err = partitioned_nested_join_with_filter(
11561117
left.clone(),
11571118
right.clone(),
11581119
&join_type,
@@ -1171,9 +1132,4 @@ mod tests {
11711132

11721133
Ok(())
11731134
}
1174-
1175-
/// Returns the column names on the schema
1176-
fn columns(schema: &Schema) -> Vec<String> {
1177-
schema.fields().iter().map(|f| f.name().clone()).collect()
1178-
}
11791135
}

0 commit comments

Comments
 (0)