[Enhancement] Optimize array_sortby for multi key columns

ZiheLiu commented 3 months ago

Why I'm doing:

Optimize the performance of array_sortby for multi key columns.

What I'm doing:

For now, each column of each row will call sort_and_tie_column(**range**) once. sort_and_tie_column is pretty heavy need , because it calls the virtual methods ColumnVisitor::accept and Column::visit, and create and destroy several STL containers such as tie and permutation.

Therefore, make each column only call sort_and_tie_column(ranges) once.

Test

t1 contains 20,000,000 rows and 1 bucket. Each array row contains 3 columns.

-- Order By One Column
select max(t1.res) from (select array_min(array_sortby(c1, c2)) as res from t1 ) as t1;
-- Order By Two Columns
select max(t1.res) from (select array_min(array_sortby(c1, c2,c3)) as res from t1 ) as t1;

Order By One Column: 1.115s.
Order By Two Columns:
- Before: 17.336s
- After: 2.843s

What type of PR is this:

[ ] BugFix
[ ] Feature
[x] Enhancement
[ ] Refactor
[ ] UT
[ ] Doc
[ ] Tool

Does this PR entail a change in behavior?

[ ] Yes, this PR will result in a change in behavior.
[x] No, this PR will not result in a change in behavior.

If yes, please specify the type of change:

[ ] Interface/UI changes: syntax, type conversion, expression evaluation, display information
[ ] Parameter changes: default values, similar parameters but with different default values
[ ] Policy changes: use new policy to replace old one, functionality automatically enabled
[ ] Feature removed
[ ] Miscellaneous: upgrade & downgrade compatibility, etc.

Checklist:

[x] I have added test cases for my bug fix or my new feature
[ ] This pr needs user documentation (for new or modified features or behaviors)
- [ ] I have added documentation for my new feature or new function
[ ] This is a backport pr

Bugfix cherry-pick branch check:

[x] I have checked the version labels which the pr will be auto-backported to the target branch
- [x] 3.3
- [ ] 3.2
- [ ] 3.1
- [ ] 3.0
- [ ] 2.5

github-actions[bot] commented 3 months ago

[FE Incremental Coverage Report]

:white_check_mark: pass : 0 / 0 (0%)

github-actions[bot] commented 3 months ago

[BE Incremental Coverage Report]

:white_check_mark: pass : 125 / 128 (97.66%)

file detail

	path	covered_line	new_line	coverage	not_covered_line_detail
:large_blue_circle:	be/src/exec/sorting/sort_column.cpp	61	64	95.31%	[150, 159, 208]
:large_blue_circle:	be/src/exec/sorting/sort_permute.cpp	2	2	100.00%	[]
:large_blue_circle:	be/src/exec/sorting/sort_helper.h	3	3	100.00%	[]
:large_blue_circle:	be/src/exprs/array_functions.cpp	59	59	100.00%	[]

github-actions[bot] commented 3 months ago

@Mergifyio backport branch-3.3

mergify[bot] commented 3 months ago

backport branch-3.3

✅ Backports have been created

* [#47827 [Enhancement] Optimize array_sortby for multi key columns (backport #47798)](https://github.com/StarRocks/starrocks/pull/47827) has been created for branch `branch-3.3`

StarRocks / starrocks