Skip to content

Commit afc4c49

Browse files
thepinetreecloud-fan
authored andcommitted
[SPARK-43393][SQL] Address sequence expression overflow bug
### What changes were proposed in this pull request? Spark has a (long-standing) overflow bug in the `sequence` expression. Consider the following operations: ``` spark.sql("CREATE TABLE foo (l LONG);") spark.sql(s"INSERT INTO foo VALUES (${Long.MaxValue});") spark.sql("SELECT sequence(0, l) FROM foo;").collect() ``` The result of these operations will be: ``` Array[org.apache.spark.sql.Row] = Array([WrappedArray()]) ``` an unintended consequence of overflow. The sequence is applied to values `0` and `Long.MaxValue` with a step size of `1` which uses a length computation defined [here](https://github.com/apache/spark/blob/16411188c7ba6cb19c46a2bd512b2485a4c03e2c/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/collectionOperations.scala#L3451). In this calculation, with `start = 0`, `stop = Long.MaxValue`, and `step = 1`, the calculated `len` overflows to `Long.MinValue`. The computation, in binary looks like: ``` 0111111111111111111111111111111111111111111111111111111111111111 - 0000000000000000000000000000000000000000000000000000000000000000 ------------------------------------------------------------------ 0111111111111111111111111111111111111111111111111111111111111111 / 0000000000000000000000000000000000000000000000000000000000000001 ------------------------------------------------------------------ 0111111111111111111111111111111111111111111111111111111111111111 + 0000000000000000000000000000000000000000000000000000000000000001 ------------------------------------------------------------------ 1000000000000000000000000000000000000000000000000000000000000000 ``` The following [check](https://github.com/apache/spark/blob/16411188c7ba6cb19c46a2bd512b2485a4c03e2c/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/collectionOperations.scala#L3454) passes as the negative `Long.MinValue` is still `<= MAX_ROUNDED_ARRAY_LENGTH`. The following cast to `toInt` uses this representation and [truncates the upper bits](https://github.com/apache/spark/blob/16411188c7ba6cb19c46a2bd512b2485a4c03e2c/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/collectionOperations.scala#L3457) resulting in an empty length of `0`. Other overflows are similarly problematic. This PR addresses the issue by checking numeric operations in the length computation for overflow. ### Why are the changes needed? There is a correctness bug from overflow in the `sequence` expression. ### Does this PR introduce _any_ user-facing change? No. ### How was this patch tested? Tests added in `CollectionExpressionsSuite.scala`. Closes #41072 from thepinetree/spark-sequence-overflow. Authored-by: Deepayan Patra <[email protected]> Signed-off-by: Wenchen Fan <[email protected]>
1 parent 86da6b8 commit afc4c49

2 files changed

Lines changed: 83 additions & 20 deletions

File tree

‎sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/collectionOperations.scala‎

Lines changed: 32 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ import scala.collection.mutable
2323
import scala.reflect.ClassTag
2424

2525
import org.apache.spark.QueryContext
26+
import org.apache.spark.SparkException.internalError
2627
import org.apache.spark.sql.catalyst.InternalRow
2728
import org.apache.spark.sql.catalyst.analysis.{TypeCheckResult, TypeCoercion, UnresolvedAttribute, UnresolvedSeed}
2829
import org.apache.spark.sql.catalyst.analysis.TypeCheckResult.DataTypeMismatch
@@ -41,7 +42,6 @@ import org.apache.spark.sql.types._
4142
import org.apache.spark.sql.util.SQLOpenHashSet
4243
import org.apache.spark.unsafe.UTF8StringBuilder
4344
import org.apache.spark.unsafe.array.ByteArrayMethods
44-
import org.apache.spark.unsafe.array.ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH
4545
import org.apache.spark.unsafe.types.{ByteArray, CalendarInterval, UTF8String}
4646

4747
/**
@@ -3122,6 +3122,34 @@ case class Sequence(
31223122
}
31233123

31243124
object Sequence {
3125+
private def prettyName: String = "sequence"
3126+
3127+
def sequenceLength(start: Long, stop: Long, step: Long): Int = {
3128+
try {
3129+
val delta = Math.subtractExact(stop, start)
3130+
if (delta == Long.MinValue && step == -1L) {
3131+
// We must special-case division of Long.MinValue by -1 to catch potential unchecked
3132+
// overflow in next operation. Division does not have a builtin overflow check. We
3133+
// previously special-case div-by-zero.
3134+
throw new ArithmeticException("Long overflow (Long.MinValue / -1)")
3135+
}
3136+
val len = if (stop == start) 1L else Math.addExact(1L, (delta / step))
3137+
if (len > ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH) {
3138+
throw QueryExecutionErrors.createArrayWithElementsExceedLimitError(prettyName, len)
3139+
}
3140+
len.toInt
3141+
} catch {
3142+
// We handle overflows in the previous try block by raising an appropriate exception.
3143+
case _: ArithmeticException =>
3144+
val safeLen =
3145+
BigInt(1) + (BigInt(stop) - BigInt(start)) / BigInt(step)
3146+
if (safeLen > ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH) {
3147+
throw QueryExecutionErrors.createArrayWithElementsExceedLimitError(prettyName, safeLen)
3148+
}
3149+
throw internalError("Unreachable code reached.")
3150+
case e: Exception => throw e
3151+
}
3152+
}
31253153

31263154
private type LessThanOrEqualFn = (Any, Any) => Boolean
31273155

@@ -3493,13 +3521,7 @@ object Sequence {
34933521
|| (estimatedStep == num.zero && start == stop),
34943522
s"Illegal sequence boundaries: $start to $stop by $step")
34953523

3496-
val len = if (start == stop) 1L else 1L + (stop.toLong - start.toLong) / estimatedStep.toLong
3497-
3498-
require(
3499-
len <= MAX_ROUNDED_ARRAY_LENGTH,
3500-
s"Too long sequence: $len. Should be <= $MAX_ROUNDED_ARRAY_LENGTH")
3501-
3502-
len.toInt
3524+
sequenceLength(start.toLong, stop.toLong, estimatedStep.toLong)
35033525
}
35043526

35053527
private def genSequenceLengthCode(
@@ -3509,20 +3531,15 @@ object Sequence {
35093531
step: String,
35103532
estimatedStep: String,
35113533
len: String): String = {
3512-
val longLen = ctx.freshName("longLen")
3534+
val calcFn = classOf[Sequence].getName + ".sequenceLength"
35133535
s"""
35143536
|if (!(($estimatedStep > 0 && $start <= $stop) ||
35153537
| ($estimatedStep < 0 && $start >= $stop) ||
35163538
| ($estimatedStep == 0 && $start == $stop))) {
35173539
| throw new IllegalArgumentException(
35183540
| "Illegal sequence boundaries: " + $start + " to " + $stop + " by " + $step);
35193541
|}
3520-
|long $longLen = $stop == $start ? 1L : 1L + ((long) $stop - $start) / $estimatedStep;
3521-
|if ($longLen > $MAX_ROUNDED_ARRAY_LENGTH) {
3522-
| throw new IllegalArgumentException(
3523-
| "Too long sequence: " + $longLen + ". Should be <= $MAX_ROUNDED_ARRAY_LENGTH");
3524-
|}
3525-
|int $len = (int) $longLen;
3542+
|int $len = $calcFn((long) $start, (long) $stop, (long) $estimatedStep);
35263543
""".stripMargin
35273544
}
35283545
}

‎sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/CollectionExpressionsSuite.scala‎

Lines changed: 51 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ import org.apache.spark.sql.catalyst.util.IntervalUtils._
3535
import org.apache.spark.sql.errors.DataTypeErrorsBase
3636
import org.apache.spark.sql.internal.SQLConf
3737
import org.apache.spark.sql.types._
38-
import org.apache.spark.unsafe.array.ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH
38+
import org.apache.spark.unsafe.array.ByteArrayMethods
3939
import org.apache.spark.unsafe.types.UTF8String
4040

4141
class CollectionExpressionsSuite
@@ -795,10 +795,6 @@ class CollectionExpressionsSuite
795795

796796
// test sequence boundaries checking
797797

798-
checkExceptionInExpression[IllegalArgumentException](
799-
new Sequence(Literal(Int.MinValue), Literal(Int.MaxValue), Literal(1)),
800-
EmptyRow, s"Too long sequence: 4294967296. Should be <= $MAX_ROUNDED_ARRAY_LENGTH")
801-
802798
checkExceptionInExpression[IllegalArgumentException](
803799
new Sequence(Literal(1), Literal(2), Literal(0)), EmptyRow, "boundaries: 1 to 2 by 0")
804800
checkExceptionInExpression[IllegalArgumentException](
@@ -808,6 +804,56 @@ class CollectionExpressionsSuite
808804
checkExceptionInExpression[IllegalArgumentException](
809805
new Sequence(Literal(1), Literal(2), Literal(-1)), EmptyRow, "boundaries: 1 to 2 by -1")
810806

807+
// SPARK-43393: test Sequence overflow checking
808+
checkErrorInExpression[SparkRuntimeException](
809+
new Sequence(Literal(Int.MinValue), Literal(Int.MaxValue), Literal(1)),
810+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
811+
parameters = Map(
812+
"numberOfElements" -> (BigInt(Int.MaxValue) - BigInt { Int.MinValue } + 1).toString,
813+
"functionName" -> toSQLId("sequence"),
814+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
815+
"parameter" -> toSQLId("count")))
816+
checkErrorInExpression[SparkRuntimeException](
817+
new Sequence(Literal(0L), Literal(Long.MaxValue), Literal(1L)),
818+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
819+
parameters = Map(
820+
"numberOfElements" -> (BigInt(Long.MaxValue) + 1).toString,
821+
"functionName" -> toSQLId("sequence"),
822+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
823+
"parameter" -> toSQLId("count")))
824+
checkErrorInExpression[SparkRuntimeException](
825+
new Sequence(Literal(0L), Literal(Long.MinValue), Literal(-1L)),
826+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
827+
parameters = Map(
828+
"numberOfElements" -> ((0 - BigInt(Long.MinValue)) + 1).toString(),
829+
"functionName" -> toSQLId("sequence"),
830+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
831+
"parameter" -> toSQLId("count")))
832+
checkErrorInExpression[SparkRuntimeException](
833+
new Sequence(Literal(Long.MinValue), Literal(Long.MaxValue), Literal(1L)),
834+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
835+
parameters = Map(
836+
"numberOfElements" -> (BigInt(Long.MaxValue) - BigInt { Long.MinValue } + 1).toString,
837+
"functionName" -> toSQLId("sequence"),
838+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
839+
"parameter" -> toSQLId("count")))
840+
checkErrorInExpression[SparkRuntimeException](
841+
new Sequence(Literal(Long.MaxValue), Literal(Long.MinValue), Literal(-1L)),
842+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
843+
parameters = Map(
844+
"numberOfElements" -> (BigInt(Long.MaxValue) - BigInt { Long.MinValue } + 1).toString,
845+
"functionName" -> toSQLId("sequence"),
846+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
847+
"parameter" -> toSQLId("count")))
848+
checkErrorInExpression[SparkRuntimeException](
849+
new Sequence(Literal(Long.MaxValue), Literal(-1L), Literal(-1L)),
850+
errorClass = "COLLECTION_SIZE_LIMIT_EXCEEDED.PARAMETER",
851+
parameters = Map(
852+
"numberOfElements" -> (BigInt(Long.MaxValue) - BigInt { -1L } + 1).toString,
853+
"functionName" -> toSQLId("sequence"),
854+
"maxRoundedArrayLength" -> ByteArrayMethods.MAX_ROUNDED_ARRAY_LENGTH.toString(),
855+
"parameter" -> toSQLId("count")))
856+
811857
// test sequence with one element (zero step or equal start and stop)
812858

813859
checkEvaluation(new Sequence(Literal(1), Literal(1), Literal(-1)), Seq(1))

0 commit comments

Comments
 (0)