[SPARK-7289] Combine Limit and Sort to avoid total ordering

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.3.1
• Fix Version/s: 1.4.2, 1.5.0
• Component/s: SQL
• Target Version/s: 1.5.0
• Assignee: Wenchen Fan
• Reporter: Fei Wang
• Shepherd: Michael Armbrust
• Created: 30/Apr/15 23:28
• Updated: 18/Aug/15 04:23
• Resolved: 24/Jun/15 20:29

Description

Optimize following sql

select key from (select * from testData order by key) t limit 5

from

== Parsed Logical Plan ==
'Limit 5
'Project ['key]
'Subquery t
'Sort ['key ASC], true
'Project [*]
'UnresolvedRelation [testData], None

== Analyzed Logical Plan ==
Limit 5
Project key#0
Subquery t
Sort key#0 ASC, true
Project key#0,value#1
Subquery testData
LogicalRDD key#0,value#1, MapPartitionsRDD[1]

== Optimized Logical Plan ==
Limit 5
Project key#0
Sort key#0 ASC, true
LogicalRDD key#0,value#1, MapPartitionsRDD[1]
== Physical Plan ==
Limit 5
Project key#0
Sort key#0 ASC, true
Exchange (RangePartitioning key#0 ASC, 5), []
PhysicalRDD key#0,value#1, MapPartitionsRDD[1]

to

== Parsed Logical Plan ==
'Limit 5
'Project ['key]
'Subquery t
'Sort ['key ASC], true
'Project [*]
'UnresolvedRelation [testData], None

== Analyzed Logical Plan ==
Limit 5
Project key#0
Subquery t
Sort key#0 ASC, true
Project key#0,value#1
Subquery testData
LogicalRDD key#0,value#1, MapPartitionsRDD[1]

== Optimized Logical Plan ==
Project key#0
Limit 5
Sort key#0 ASC, true
LogicalRDD key#0,value#1, MapPartitionsRDD[1]

== Physical Plan ==
Project key#0
TakeOrdered 5, key#0 ASC
PhysicalRDD key#0,value#1, MapPartitionsRDD[1]

Issue Links

• links to: [Github] Pull Request #5821 (scwf)
• links to: [Github] Pull Request #6780 (cloud-fan)
• links to: [Github] Pull Request #8252 (yhuai)