[
https://issues.apache.org/jira/browse/IMPALA-10961?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17495274#comment-17495274
]
ASF subversion and git services commented on IMPALA-10961:
----------------------------------------------------------
Commit fe04c500d7c32606c9024259a972f6843fab678e in impala's branch
refs/heads/master from noemi
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=fe04c50 ]
IMPALA-10961: Implementing adaptive 3-way quicksort in sorter
Based on a 3-way partitioning implementation by Kurt Deschler.
3-way quicksort performs much better on data with large number of
duplicates, but has a small regression in case of large NDV.
This adaptive implementation keeps the advantages of both 2-way
and 3-way quicksort. If duplicates are found during pivot selection
(among the 3 randomly selected candidates),the 3-way partitioning
function is called in SortHelper, otherwise partitioning goes 2-way.
Some benchmark results:
On a view created from 4 tpch_parquet lineitem tables
Full sort, 1 node, 1 run - no spills (only in-memory sort is changed)
Time of sorting adaptively during query execution compared to
the original implementation (sort node profile):
+----------------------------------------------+----------------+--------------------+
| Test | Original 2-way | Adaptive
Quicksort |
+----------------------------------------------+----------------+--------------------+
| select * order by l_linestatus, NDV=2: | 1 |
0.67 |
| select l_shipmode order by l_shipmode, NDV=7 | 1 |
0.42 |
| select * order by l_shipmode, NDV=7 | 1 |
0.57 |
| large NDV, unique data | 1 |
1 | (no difference)
+----------------------------------------------+----------------+--------------------+
Change-Id: I81e7b36a04a43de3b83e6aeee49ca0943f0bf202
Reviewed-on: http://gerrit.cloudera.org:8080/18184
Reviewed-by: Impala Public Jenkins <[email protected]>
Reviewed-by: Csaba Ringhofer <[email protected]>
Tested-by: Csaba Ringhofer <[email protected]>
> Implement 3-way quicksort in sorter
> -----------------------------------
>
> Key: IMPALA-10961
> URL: https://issues.apache.org/jira/browse/IMPALA-10961
> Project: IMPALA
> Issue Type: Improvement
> Components: Backend
> Reporter: Csaba Ringhofer
> Assignee: Noemi Pap-Takacs
> Priority: Major
> Labels: performance
> Attachments: checksorted.patch, qsort.cc
>
>
> Using 3-way partitioning in quicksort could massively speed up sorting if
> there is a large number of duplicate elements. This is very common in sorts
> before partitioned inserts.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
