[SPARK-8428] TimSort Comparison method violates its general contract with CLUSTER BY

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.4.0
• Fix Version/s: 1.6.2, 2.0.0
• Component/s: SQL

Environment

Oracle Java 7

• Target Version/s: 1.6.2, 2.0.0
• Assignee: Sameer Agarwal
• Reporter: Nathan McCarthy
• Created: 18/Jun/15 04:46
• Updated: 26/May/16 22:51
• Resolved: 26/May/16 22:51

Description

Running an SQL query that has a sub query and multiple left joins fails when there is a CLUSTER BY (which implies a sortBy). This gives the following stack trace;

Job aborted due to stage failure: Task 118 in stage 4.0 failed 4 times, most recent failure: Lost task 118.3 in stage 4.0 (TID 18392, node142): java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at org.apache.spark.util.collection.TimSort$SortState.mergeHi(TimSort.java:900)
	at org.apache.spark.util.collection.TimSort$SortState.mergeAt(TimSort.java:509)
	at org.apache.spark.util.collection.TimSort$SortState.mergeCollapse(TimSort.java:435)
	at org.apache.spark.util.collection.TimSort$SortState.access$200(TimSort.java:307)
	at org.apache.spark.util.collection.TimSort.sort(TimSort.java:135)
	at org.apache.spark.util.collection.Sorter.sort(Sorter.scala:37)
	at org.apache.spark.util.collection.PartitionedPairBuffer.partitionedDestructiveSortedIterator(PartitionedPairBuffer.scala:70)
	at org.apache.spark.util.collection.ExternalSorter.partitionedIterator(ExternalSorter.scala:690)
	at org.apache.spark.util.collection.ExternalSorter.iterator(ExternalSorter.scala:708)
	at org.apache.spark.sql.execution.ExternalSort$$anonfun$doExecute$6$$anonfun$apply$7.apply(basicOperators.scala:222)
	at org.apache.spark.sql.execution.ExternalSort$$anonfun$doExecute$6$$anonfun$apply$7.apply(basicOperators.scala:218)
	at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
	at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
	at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
	at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
	at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
	at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
	at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
	at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
	at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
	at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
	at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
	at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
	at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
	at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
	at org.apache.spark.scheduler.ResultTask.runTask(ResultTask.scala:63)
	at org.apache.spark.scheduler.Task.run(Task.scala:70)
	at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:213)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
	at java.lang.Thread.run(Thread.java:745)

Driver stacktrace:

The query looks like;

 val df = sqlContext.sql("""SELECT CID
|,	PW_END_DATE
|,	PROD_NBR_KEY
|,	SUM(CASE WHEN SUBST_IDX = 1 THEN L13W_SALE END) AS SUB1_L13W_SALE
|FROM
|(SELECT	BASE.CID
|,	BASE.PW_END_DATE
|,	BASE.PROD_NBR_KEY
|,	SUBN.SUBST_IDX
|,	CASE WHEN IDX.PW_END_DATE BETWEEN DATE_SUB(BASE.PW_END_DATE, 13*7 - 1) AND BASE.PW_END_DATE THEN IDX.TOT_AMT_INCLD_GST END AS L13W_SALE
|FROM TESTBASE BASE
|LEFT JOIN TABLX SUBN
|ON BASE.PROD_NBR_KEY = SUBN.PROD_NBR_KEY AND SUBN.SUBST_IDX <= 3
|LEFT JOIN TABLEF IDX
|ON BASE.CRN = IDX.CRN
|AND SUBN.CROSS_PROD_NBR = IDX.PROD_NBR_KEY
|) SUBSPREM
| GROUP BY CRN, PW_END_DATE, PROD_NBR_KEY""".stripMargin)

Issue Links

• duplicates: SPARK-13850 TimSort Comparison method violates its general contract
• is duplicated by: SPARK-6009 IllegalArgumentException thrown by TimSort when SQL ORDER BY RAND ()
• is related to: SPARK-6009 IllegalArgumentException thrown by TimSort when SQL ORDER BY RAND ()
• links to: [Github] Pull Request #13336 (sameeragarwal)