You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by aokolnychyi <gi...@git.apache.org> on 2018/11/28 19:06:08 UTC
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
GitHub user aokolnychyi opened a pull request:
https://github.com/apache/spark/pull/23171
[SPARK-26205][SQL] Optimize In for bytes, shorts, ints
## What changes were proposed in this pull request?
This PR optimizes `In` expressions for byte, short, integer types. It is a follow-up on PR #21442 from @dbtsai.
Currently, `In` expressions are compiled into a sequence of if-else statement, which results in O(n) time complexity. `InSet` is an optimized version of `In`, which is supposed to improve the performance if the number of elements is big enough. However, `InSet` actually degrades the performance in many cases due to various reasons (`InSet` will be handled in [SPARK-26203](https://issues.apache.org/jira/browse/SPARK-26203) and [SPARK-26204](https://issues.apache.org/jira/browse/SPARK-26204)).
The main idea of this PR is to make use of `tableswitch` and `lookupswitch` bytecode instructions to speed up `In` expressions. In short, we can improve our time complexity from O(n) to O(1) or at least O(log n) by using Java `switch` statements. We will have O(1) time complexity if our case values are compact and `tableswitch` can be used. Otherwise, `lookupswitch` will give us O(log n). See [here](https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-3.html#jvms-3.10) and [here](https://stackoverflow.com/questions/10287700/difference-between-jvms-lookupswitch-and-tableswitch) for more information.
An important benefit of the proposed approach is that we do not have to pay an extra cost for autoboxing as in case of `InSet`. As a consequence, we can substantially outperform `InSet` even on 250+ elements.
This PR does not cover long values as Java `switch` statements cannot be used on them. However, we can have a follow-up PR with an approach similar to binary search.
## How was this patch tested?
### Correctness
There is a new test that verifies the logic of the proposed optimization.
### Performance Benchmarks
The performance impact was measured by the benchmarks below (an appropriate part of them will be included in [SPARK-26203](https://issues.apache.org/jira/browse/SPARK-26203)).
```
def compactBytesBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val name = s"$numItems compact bytes"
val values = (1 to numItems).map(v => s"CAST($v AS tinyint)")
val df = spark.range(1, numRows).select($"id".cast(ByteType))
benchmark(name, df, values, numRows, minNumIters)
}
def nonCompactBytesBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val step = (Byte.MaxValue.toInt - Byte.MinValue.toInt) / numItems
val maxValue = Byte.MinValue + numItems * step
val rangeSize = maxValue - Byte.MinValue
require(isLookupSwitch(rangeSize, numItems))
val name = s"$numItems non-compact bytes"
val values = (Byte.MinValue until maxValue by step).map(v => s"CAST($v AS tinyint)")
val df = spark.range(1, numRows).select($"id".cast(ByteType))
benchmark(name, df, values, numRows, minNumIters)
}
def compactShortsBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val name = s"$numItems compact shorts"
val values = (1 to numItems).map(v => s"CAST($v AS smallint)")
val df = spark.range(1, numRows).select($"id".cast(ShortType))
benchmark(name, df, values, numRows, minNumIters)
}
def nonCompactShortsBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val step = (Short.MaxValue.toInt - Short.MinValue.toInt) / numItems
val maxValue = Short.MinValue + numItems * step
val rangeSize = maxValue - Short.MinValue
require(isLookupSwitch(rangeSize, numItems))
val name = s"$numItems non-compact shorts"
val values = (Short.MinValue until maxValue by step).map(v => s"CAST($v AS smallint)")
val df = spark.range(1, numRows).select($"id".cast(ShortType))
benchmark(name, df, values, numRows, minNumIters)
}
def compactIntsBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val name = s"$numItems compact ints"
val values = (1 to numItems).map(v => 10000000 + v)
val df = spark.range(1, numRows).select($"id".cast(IntegerType))
benchmark(name, df, values, numRows, minNumIters)
}
def nonCompactIntsBenchmark(numItems: Int, numRows: Long, minNumIters: Int): Benchmark = {
val step = (Int.MaxValue.toLong - Int.MinValue.toLong) / numItems
val maxValue = Int.MinValue + numItems * step
val rangeSize = maxValue - Int.MinValue
require(isLookupSwitch(rangeSize, numItems))
val name = s"$numItems non-compact ints"
val values = Int.MinValue until maxValue.toInt by step.toInt
val df = spark.range(1, numRows).select($"id".cast(IntegerType))
benchmark(name, df, values, numRows, minNumIters)
}
def benchmark(
name: String,
df: DataFrame,
values: Seq[Any],
numRows: Long,
minNumIters: Int): Benchmark = {
val benchmark = new Benchmark(name, numRows, minNumIters, output = output)
df.createOrReplaceTempView("t")
val testClosure = () => {
val df = spark.sql(s"SELECT * FROM t WHERE id IN (${values mkString ","})")
df.queryExecution.toRdd.foreach(_ => Unit)
}
benchmark.addCase("In expression") { _ =>
withSQLConf(SQLConf.OPTIMIZER_INSET_CONVERSION_THRESHOLD.key -> values.size.toString) {
testClosure()
}
}
benchmark.addCase("InSet expression") { _ =>
withSQLConf(SQLConf.OPTIMIZER_INSET_CONVERSION_THRESHOLD.key -> "1") {
testClosure()
}
}
benchmark
}
// this logic is derived from com.sun.tools.javac.jvm.Gen.java
private def isLookupSwitch(rangeSize: Long, numLabels: Int): Boolean = {
val tableSpaceCost = 4 + rangeSize
val tableTimeCost = 3
val lookupSpaceCost = 3 + 2 * numLabels
val lookupTimeCost = numLabels
lookupSpaceCost + 3 * lookupTimeCost < tableSpaceCost + 3 * tableTimeCost
}
```
The actual benchmarking code looks like:
```
val numRows = 100000000
val minNumIters = 10
compactBytesBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
nonCompactBytesBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
compactBytesBenchmark(numItems = 25, numRows = numRows, minNumIters).run()
nonCompactBytesBenchmark(numItems = 25, numRows = numRows, minNumIters).run()
compactShortsBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
nonCompactShortsBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
compactShortsBenchmark(numItems = 50, numRows = numRows, minNumIters).run()
nonCompactShortsBenchmark(numItems = 50, numRows = numRows, minNumIters).run()
compactShortsBenchmark(numItems = 100, numRows = numRows, minNumIters).run()
nonCompactShortsBenchmark(numItems = 100, numRows = numRows, minNumIters).run()
compactIntsBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
nonCompactIntsBenchmark(numItems = 10, numRows = numRows, minNumIters).run()
compactIntsBenchmark(numItems = 100, numRows = numRows, minNumIters).run()
nonCompactIntsBenchmark(numItems = 100, numRows = numRows, minNumIters).run()
compactIntsBenchmark(numItems = 250, numRows = numRows, minNumIters).run()
nonCompactIntsBenchmark(numItems = 250, numRows = numRows, minNumIters).run()
```
#### Byte
**_Performance Summary_**
Proposed Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 230 ms | 73 ms | 87 ms |
| 25 | 290 ms | 110 ms | 117 ms |
Current Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 220 ms | 91 ms | 91 ms |
| 25 | 291 ms | 167 ms | 168 ms |
**_Raw Results_**
Proposed Solution
```
Running benchmark: 10 compact bytes
Running case: In expression
Stopped after 28 iterations, 2053 ms
Running case: InSet expression
Stopped after 15 iterations, 3277 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 68 / 73 1474.6 0.7 1.0X
InSet expression 216 / 218 463.9 2.2 0.3X
Running benchmark: 10 non-compact bytes
Running case: In expression
Stopped after 24 iterations, 2076 ms
Running case: InSet expression
Stopped after 15 iterations, 3340 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 84 / 87 1186.6 0.8 1.0X
InSet expression 217 / 223 460.7 2.2 0.4X
Running benchmark: 25 compact bytes
Running case: In expression
Stopped after 19 iterations, 2080 ms
Running case: InSet expression
Stopped after 15 iterations, 4285 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
25 compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 105 / 110 955.0 1.0 1.0X
InSet expression 273 / 286 365.8 2.7 0.4X
Running benchmark: 25 non-compact bytes
Running case: In expression
Stopped after 18 iterations, 2104 ms
Running case: InSet expression
Stopped after 15 iterations, 4449 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
25 non-compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 107 / 117 938.5 1.1 1.0X
InSet expression 284 / 297 352.3 2.8 0.4X
```
Current Solution
```
Running benchmark: 10 compact bytes
Running case: In expression
Stopped after 22 iterations, 2002 ms
Running case: InSet expression
Stopped after 15 iterations, 3601 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 86 / 91 1168.9 0.9 1.0X
InSet expression 226 / 240 442.5 2.3 0.4X
Running benchmark: 10 non-compact bytes
Running case: In expression
Stopped after 23 iterations, 2085 ms
Running case: InSet expression
Stopped after 15 iterations, 3265 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 86 / 91 1169.1 0.9 1.0X
InSet expression 213 / 218 469.5 2.1 0.4X
Running benchmark: 25 compact bytes
Running case: In expression
Stopped after 15 iterations, 2499 ms
Running case: InSet expression
Stopped after 15 iterations, 4326 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
25 compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 164 / 167 610.7 1.6 1.0X
InSet expression 282 / 288 354.2 2.8 0.6X
Running benchmark: 25 non-compact bytes
Running case: In expression
Stopped after 15 iterations, 2518 ms
Running case: InSet expression
Stopped after 15 iterations, 4404 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
25 non-compact bytes: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 164 / 168 611.5 1.6 1.0X
InSet expression 282 / 294 354.4 2.8 0.6X
```
**_Conclusion_**
As expected, we see that the proposed logic improves the performance on compact and non-compact sequences of byte values. While the performance on compact elements is better than on non-compact ones, we do not see that it is stable independently of the number of elements inside `In`. Hence, we cannot conclude O(1) time performance on compact byte values. Spark generates `(byte) 1`, `(byte) 100` to represent byte literals, so it can potentially be a reason for the non-linear time complexity.
We also see that the performance of the old approach on bytes is the same independently of data compactness (as expected).
#### Short
**_Performance Summary_**
Proposed Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 243 ms | 45 ms | 56 ms |
| 50 | 294 ms | 45 ms | 71 ms |
| 100 | 260 ms | 46 ms | 82 ms |
Current Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 248 ms | 71 ms | 69 ms |
| 50 | 295 ms | 169 ms | 173 ms |
| 100 | 265 ms | 335 ms | 370 ms |
**_Raw Results_**
Proposed Solution
```
Running benchmark: 10 compact shorts
Running case: In expression
Stopped after 45 iterations, 2032 ms
Running case: InSet expression
Stopped after 15 iterations, 3633 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 41 / 45 2430.9 0.4 1.0X
InSet expression 232 / 242 430.4 2.3 0.2X
Running benchmark: 10 non-compact shorts
Running case: In expression
Stopped after 36 iterations, 2012 ms
Running case: InSet expression
Stopped after 15 iterations, 3645 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 53 / 56 1880.2 0.5 1.0X
InSet expression 233 / 243 428.4 2.3 0.2X
Running benchmark: 50 compact shorts
Running case: In expression
Stopped after 45 iterations, 2007 ms
Running case: InSet expression
Stopped after 15 iterations, 4366 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
50 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 42 / 45 2368.9 0.4 1.0X
InSet expression 280 / 291 357.4 2.8 0.2X
Running benchmark: 50 non-compact shorts
Running case: In expression
Stopped after 29 iterations, 2053 ms
Running case: InSet expression
Stopped after 15 iterations, 4447 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
50 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 69 / 71 1451.0 0.7 1.0X
InSet expression 292 / 297 342.3 2.9 0.2X
Running benchmark: 100 compact shorts
Running case: In expression
Stopped after 44 iterations, 2032 ms
Running case: InSet expression
Stopped after 15 iterations, 3967 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 44 / 46 2248.6 0.4 1.0X
InSet expression 259 / 264 385.6 2.6 0.2X
Running benchmark: 100 non-compact shorts
Running case: In expression
Stopped after 25 iterations, 2060 ms
Running case: InSet expression
Stopped after 15 iterations, 3832 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 79 / 82 1267.6 0.8 1.0X
InSet expression 250 / 256 399.4 2.5 0.3X
```
Current Solution
```
Running benchmark: 10 compact shorts
Running case: In expression
Stopped after 29 iterations, 2051 ms
Running case: InSet expression
Stopped after 15 iterations, 3788 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 64 / 71 1553.8 0.6 1.0X
InSet expression 243 / 253 411.4 2.4 0.3X
Running benchmark: 10 non-compact shorts
Running case: In expression
Stopped after 30 iterations, 2055 ms
Running case: InSet expression
Stopped after 15 iterations, 3658 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 64 / 69 1572.3 0.6 1.0X
InSet expression 238 / 244 420.0 2.4 0.3X
Running benchmark: 50 compact shorts
Running case: In expression
Stopped after 15 iterations, 2532 ms
Running case: InSet expression
Stopped after 15 iterations, 4394 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
50 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 163 / 169 614.5 1.6 1.0X
InSet expression 288 / 293 346.8 2.9 0.6X
Running benchmark: 50 non-compact shorts
Running case: In expression
Stopped after 15 iterations, 2588 ms
Running case: InSet expression
Stopped after 15 iterations, 4554 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
50 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 168 / 173 594.0 1.7 1.0X
InSet expression 290 / 304 345.0 2.9 0.6X
Running benchmark: 100 compact shorts
Running case: In expression
Stopped after 15 iterations, 5021 ms
Running case: InSet expression
Stopped after 15 iterations, 4086 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 330 / 335 303.3 3.3 1.0X
InSet expression 259 / 272 386.8 2.6 1.3X
Running benchmark: 100 non-compact shorts
Running case: In expression
Stopped after 15 iterations, 5542 ms
Running case: InSet expression
Stopped after 15 iterations, 3921 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 non-compact shorts: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 351 / 370 284.9 3.5 1.0X
InSet expression 252 / 261 396.6 2.5 1.4X
```
**_Conclusion_**
The proposed optimization gives us even more benefits on shorts. As opposed to bytes, we see that the performance on compact data stays the same independently of the number of values inside `In`. Therefore, we see O(1) time complexity for compact data and a significant improvement even on non-compact data.
As on bytes, the performance of the old approach on shorts is the same independently of data compactness.
#### Int
**_Performance Summary_**
Proposed Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 230 ms | 43 ms | 36 ms |
| 100 | 240 ms | 45 ms | 99 ms |
| 250 | 250 ms | 49 ms | 109 ms |
Current Solution
| # values | InSet | In with compact data | In with non-compact data |
| ------------- |:-------------:| -----:| ---:|
| 10 | 225 ms | 93 ms | 74 ms |
| 100 | 240 ms | 624 ms | 608 ms |
| 250 | 250 ms | 1131 ms | 1120 ms |
**_Raw Results_**
Proposed Solution
```
Running benchmark: 10 compact ints
Running case: In expression
Stopped after 47 iterations, 2018 ms
Running case: InSet expression
Stopped after 15 iterations, 3404 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 41 / 43 2457.4 0.4 1.0X
InSet expression 224 / 227 446.5 2.2 0.2X
Running benchmark: 10 non-compact ints
Running case: In expression
Stopped after 56 iterations, 2021 ms
Running case: InSet expression
Stopped after 15 iterations, 3470 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 35 / 36 2853.6 0.4 1.0X
InSet expression 226 / 231 442.9 2.3 0.2X
Running benchmark: 100 compact ints
Running case: In expression
Stopped after 45 iterations, 2007 ms
Running case: InSet expression
Stopped after 15 iterations, 3766 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 43 / 45 2344.0 0.4 1.0X
InSet expression 239 / 251 417.8 2.4 0.2X
Running benchmark: 100 non-compact ints
Running case: In expression
Stopped after 21 iterations, 2077 ms
Running case: InSet expression
Stopped after 15 iterations, 3776 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 96 / 99 1040.2 1.0 1.0X
InSet expression 248 / 252 403.6 2.5 0.4X
Running benchmark: 250 compact ints
Running case: In expression
Stopped after 43 iterations, 2023 ms
Running case: InSet expression
Stopped after 15 iterations, 3673 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
250 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 45 / 47 2201.2 0.5 1.0X
InSet expression 241 / 245 414.7 2.4 0.2X
Running benchmark: 250 non-compact ints
Running case: In expression
Stopped after 19 iterations, 2073 ms
Running case: InSet expression
Stopped after 15 iterations, 3802 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
250 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 108 / 109 929.2 1.1 1.0X
InSet expression 247 / 254 405.4 2.5 0.4X
```
Current Solution
```
Running benchmark: 10 compact ints
Running case: In expression
Stopped after 22 iterations, 2050 ms
Running case: InSet expression
Stopped after 15 iterations, 3387 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 89 / 93 1123.1 0.9 1.0X
InSet expression 215 / 226 464.9 2.2 0.4X
Running benchmark: 10 non-compact ints
Running case: In expression
Stopped after 28 iterations, 2059 ms
Running case: InSet expression
Stopped after 15 iterations, 3364 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
10 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 72 / 74 1397.9 0.7 1.0X
InSet expression 216 / 224 463.3 2.2 0.3X
Running benchmark: 100 compact ints
Running case: In expression
Stopped after 15 iterations, 9360 ms
Running case: InSet expression
Stopped after 15 iterations, 3672 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 621 / 624 161.2 6.2 1.0X
InSet expression 234 / 245 428.2 2.3 2.7X
Running benchmark: 100 non-compact ints
Running case: In expression
Stopped after 15 iterations, 9113 ms
Running case: InSet expression
Stopped after 15 iterations, 3563 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
100 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 593 / 608 168.6 5.9 1.0X
InSet expression 230 / 238 435.5 2.3 2.6X
Running benchmark: 250 compact ints
Running case: In expression
Stopped after 15 iterations, 16970 ms
Running case: InSet expression
Stopped after 15 iterations, 3724 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
250 compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 1123 / 1131 89.0 11.2 1.0X
InSet expression 236 / 248 423.6 2.4 4.8X
Running benchmark: 250 non-compact ints
Running case: In expression
Stopped after 15 iterations, 16807 ms
Running case: InSet expression
Stopped after 15 iterations, 3788 ms
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.14
Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
250 non-compact ints: Best/Avg Time(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------
In expression 1097 / 1120 91.1 11.0 1.0X
InSet expression 246 / 253 407.2 2.5 4.5X
```
**_Conclusion_**
Similarly to previous types, Spark performs better on ints with the proposed optimization (up to 23x in some cases). Interestingly, the new approach can perform 5 times faster than `InSet` even on 250 elements. The reason for that is autoboxing, which will be addressed in a separate PR.
As on other types, the performance of the old approach on ints is the same independently of data compactness.
## Notes
- The performance difference was confirmed on OpenJDK 64-Bit Server VM 1.8.0_181-b13 on Linux 4.9.93-linuxkit-aufs.
- [This link] contains source code that decides between `tableswitch` and `lookupswitch`. The logic was re-used in the benchmarks. See the `isLookupSwitch` method.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/aokolnychyi/spark spark-26205
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/23171.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #23171
----
commit 1477f101951ed39b96f884ddd2d451e164c0cc43
Author: Anton Okolnychyi <ao...@...>
Date: 2018-11-13T01:48:19Z
[SPARK-26205][SQL] Optimize In for bytes, shorts, ints
----
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/23171
I thought InSwitch logically is the same as InSet, in which all the child expressions are literals?
On Mon, Dec 03, 2018 at 8:38 PM, Wenchen Fan < notifications@github.com > wrote:
>
>
>
> I think InSet is not an optimized version of In , but just a way to
> separate the implementation for different conditions (the length of the
> list). Maybe we should do the same thing here, create a InSwitch and
> convert In to it when meeting some conditions. One problem is, In and InSwitch
> is same in the interpreted version, maybe we should create a base class
> for them.
>
>
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub (
> https://github.com/apache/spark/pull/23171#issuecomment-443968486 ) , or mute
> the thread (
> https://github.com/notifications/unsubscribe-auth/AATvPDTQic0Ii5UD40m_Uj5kMVy4pNExks5u1fxPgaJpZM4Y4P4J
> ).
>
>
>
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237405465
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
+ val listGen = nonNullLiterals.map(_.genCode(ctx))
+ val valueGen = value.genCode(ctx)
+
+ val caseBranches = listGen.map(literal =>
+ s"""
+ |case ${literal.value}:
+ | ${ev.value} = true;
+ | break;
+ """.stripMargin)
+
+ ev.copy(code =
+ code"""
+ |${valueGen.code}
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.isNull} = ${valueGen.isNull};
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.value} = false;
+ |if (!${valueGen.isNull}) {
+ | switch (${valueGen.value}) {
+ | ${caseBranches.mkString("")}
+ | default:
+ | ${ev.isNull} = ${nullLiterals.nonEmpty};
+ | }
+ |}
+ """.stripMargin)
+ }
+
+ private def isSwitchCompatible: Boolean = list.forall {
+ case Literal(_, dt) => dt == ByteType || dt == ShortType || dt == IntegerType
--- End diff --
Can be simplified to?
```scala
private def isSwitchCompatible: Boolean = {
inSetConvertible && (value.dataType == ByteType || value.dataType == ShortType || value.dataType == IntegerType)
}
```
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/23171
Merged build finished. Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/23171
**[Test build #99393 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/99393/testReport)** for PR 23171 at commit [`1477f10`](https://github.com/apache/spark/commit/1477f101951ed39b96f884ddd2d451e164c0cc43).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by aokolnychyi <gi...@git.apache.org>.
Github user aokolnychyi commented on the issue:
https://github.com/apache/spark/pull/23171
As @rxin said, if we introduce a separate expression for the switch-based approach, then we will need to modify other places. For example, `DataSourceStrategy$translateFilter`. So, integrating into `In` or `InSet` seems safer.
I think we can move the switch-based logic to `InSet` and make `InSet` responsible for picking the most optimal execution path. We might need to modify the condition when we convert `In` to `InSet` as this will most likely depend on the underlying data type. I saw noticeable improvements starting from 5 elements when you compare the if-else approach to the switch-based one. Right now, the conversion happens for more than 10 elements.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by mgaido91 <gi...@git.apache.org>.
Github user mgaido91 commented on the issue:
https://github.com/apache/spark/pull/23171
yes @aokolnychyi , I agree that the work can be done later (not in the scope of this PR). We can maybe just open a new JIRA about it so we won't forget.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by dbtsai <gi...@git.apache.org>.
Github user dbtsai commented on the issue:
https://github.com/apache/spark/pull/23171
@cloud-fan as @aokolnychyi said, `switch` will still be faster than optimized `Set` without autoboxing when the number of elements are small. As a result, this PR is still very useful.
@mgaido91 `InSet` can be better when we implement properly without autoboxing for large numbers of elements controlled by `spark.sql.optimizer.inSetConversionThreshold`. Also, generating `In` with huge lists can cause a compile exception due to the method size limit as you pointed out. As a result, we should convert it into `InSet` for large set.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/23171
That probably means we should just optimize InSet to have the switch version though? Rather than do it in In?
On Mon, Dec 03, 2018 at 8:20 PM, Wenchen Fan < notifications@github.com > wrote:
>
>
>
> @ rxin ( https://github.com/rxin ) I proposed the same thing before, but
> one problem is that, we only convert In to InSet when the length of list
> reaches the threshold. If the switch way is faster than hash set when the
> list is small, it seems still worth to optimize In using switch.
>
>
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub (
> https://github.com/apache/spark/pull/23171#issuecomment-443965616 ) , or mute
> the thread (
> https://github.com/notifications/unsubscribe-auth/AATvPEkrUFJuT4FI167cCI9b0nfv16V4ks5u1fgNgaJpZM4Y4P4J
> ).
>
>
>
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/23171
I'm not a big fan of making the physical implementation of an expression very different depending on the situation. Why can't we just make InSet efficient and convert these cases to that?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by mgaido91 <gi...@git.apache.org>.
Github user mgaido91 commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237564039
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
+ val listGen = nonNullLiterals.map(_.genCode(ctx))
+ val valueGen = value.genCode(ctx)
+
+ val caseBranches = listGen.map(literal =>
+ s"""
+ |case ${literal.value}:
+ | ${ev.value} = true;
+ | break;
+ """.stripMargin)
+
+ ev.copy(code =
+ code"""
+ |${valueGen.code}
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.isNull} = ${valueGen.isNull};
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.value} = false;
+ |if (!${valueGen.isNull}) {
+ | switch (${valueGen.value}) {
+ | ${caseBranches.mkString("")}
--- End diff --
we should consider that if the number of items is very big, this can cause a compile exception due to the method size limit. So we should use the proper splitting methods for the code
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237402055
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
+ val listGen = nonNullLiterals.map(_.genCode(ctx))
+ val valueGen = value.genCode(ctx)
+
+ val caseBranches = listGen.map(literal =>
--- End diff --
style:
```scala
listGen.map { literal =>
...
}
```
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by aokolnychyi <gi...@git.apache.org>.
Github user aokolnychyi commented on the issue:
https://github.com/apache/spark/pull/23171
To sum up, I would set the goal of this PR is to make `In` expressions as efficient as possible for bytes/shorts/ints. Then we can do benchmarks for `In` vs `InSet` in [SPARK-26203](https://issues.apache.org/jira/browse/SPARK-26203) and try to come up with a solution for `InSet` in [SPARK-26204](https://issues.apache.org/jira/browse/SPARK-26204). By the time we solve [SPARK-26204](https://issues.apache.org/jira/browse/SPARK-26204), we will have a clear undestanding of pros and cons in `In` and `InSet` and would be able to determine the right thresholds.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by mgaido91 <gi...@git.apache.org>.
Github user mgaido91 commented on the issue:
https://github.com/apache/spark/pull/23171
@dbtsai I see, it would be great, though, to check which is this threshold. My understanding is that the current solution has better performance even for several hundreds of items. If this number is some thousands and since this depends on the datatype (so it is hard to control by the users with a single config), it is arguable which is the best solution: I don't think it is very common to have thousands of elements, while for lower numbers (more common) we would use the less efficient solution.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/23171
Basically logically there are only two expressions: In which handles arbitrary expressions, and InSet which handles expressions with literals. Both could work: (1) we provide two separate expressions for InSet, one using switch, and one using hashset, or (2) we just provide one InSet and internally in InSet have two implementations ...
The downside with creating different expressions for the same logical expression is that potentially the downstream optimization rules would need to match more.
On Mon, Dec 03, 2018 at 10:52 PM, DB Tsai < notifications@github.com > wrote:
>
>
>
> @ rxin ( https://github.com/rxin ) switch in Java is still significantly
> faster than hash set even without boxing / unboxing problems when the
> number of elements are small. We were thinking about to have two
> implementations in InSet , and pick up switch if the number of elements are
> small, or otherwise pick up hash set one. But this is the same complexity
> as having two implements in In as this PR.
>
>
>
> @ cloud-fan ( https://github.com/cloud-fan ) do you suggest to create an OptimizeIn
> which has switch and hash set implementations based on the length of the
> elements and remove InSet ? Basically, what we were thinking above.
>
>
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub (
> https://github.com/apache/spark/pull/23171#issuecomment-443991336 ) , or mute
> the thread (
> https://github.com/notifications/unsubscribe-auth/AATvPKtGyx5jWxgtO1y5WsiXYDAQqRQ4ks5u1hvJgaJpZM4Y4P4J
> ).
>
>
>
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by cloud-fan <gi...@git.apache.org>.
Github user cloud-fan commented on the issue:
https://github.com/apache/spark/pull/23171
How about, we create an `OptimizedIn`, and convert `In` to `OptimizedIn` if the list is all literals? `OptimizedIn` will pick `switch` or hash set based on the length of the list.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/23171
Merged build finished. Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by dbtsai <gi...@git.apache.org>.
Github user dbtsai commented on the issue:
https://github.com/apache/spark/pull/23171
@rxin `switch` in Java is still significantly faster than hash set even without boxing / unboxing problems when the number of elements are small. We were thinking about to have two implementations in `InSet`, and pick up `switch` if the number of elements are small, or otherwise pick up hash set one. But this is the same complexity as having two implements in `In` as this PR.
@cloud-fan do you suggest to create an `OptimizeIn` which has `switch` and hash set implementations based on the length of the elements and remove `InSet`? Basically, what we were thinking above.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by dbtsai <gi...@git.apache.org>.
Github user dbtsai commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237227892
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
--- End diff --
If there is null in the list, it will be only one. As a result, we may not need to use `nullLiterals`.
```scala
val containNullInList = ...
val nonNullLiterals = ...
```
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by dbtsai <gi...@git.apache.org>.
Github user dbtsai commented on the issue:
https://github.com/apache/spark/pull/23171
The approach looks great, and can significantly improve the performance. For Long, I agree that we should also implement binary search approach for `O(logn)` look up.
Wondering which one will be faster, binary search using arrays or rewrite the `if-else` in binary search form.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by aokolnychyi <gi...@git.apache.org>.
Github user aokolnychyi commented on the issue:
https://github.com/apache/spark/pull/23171
@dbtsai @mgaido91 I think we can come back to this question once [SPARK-26203](https://issues.apache.org/jira/browse/SPARK-26203) is resolved. That JIRA will give us enough information about each data type.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by aokolnychyi <gi...@git.apache.org>.
Github user aokolnychyi commented on the issue:
https://github.com/apache/spark/pull/23171
@cloud-fan, yeah, let’s see if this PR is useful.
The original idea wasn’t to avoid fixing autoboxing in `InSet`. `In` was tested on 250 numbers to prove O(1) time complexity on compact values and outline problems with `InSet`. After this change, `In` will be faster than `InSet` but this is not the goal. Overall, the intent was to have a tiny and straightforward change that would optimize `In` expressions even if the number of elements is less than “spark.sql.optimizer.inSetConversionThreshold” and Spark does not use `InSet`.
Once we solve autoboxing issues in `InSet`, we would need to benchmark against this approach.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by cloud-fan <gi...@git.apache.org>.
Github user cloud-fan commented on the issue:
https://github.com/apache/spark/pull/23171
I'm wondering if this is still useful after we fix the boxing issue in `InSet`. We can write a binary hash set for primitive types, like `LongToUnsafeRowMap`, which should have better performance.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by cloud-fan <gi...@git.apache.org>.
Github user cloud-fan commented on the issue:
https://github.com/apache/spark/pull/23171
@rxin I proposed the same thing before, but one problem is that, we only convert `In` to `InSet` when the length of list reaches the threshold. If the `switch` way is faster than hash set when the list is small, it seems still worth to optimize `In` using `switch`.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/23171
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/testing-k8s-prb-make-spark-distribution-unified/5467/
Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/23171
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/99393/
Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by cloud-fan <gi...@git.apache.org>.
Github user cloud-fan commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237519018
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
--- End diff --
maybe we can follow `InSet`, define a `hasNul` ahead, and filter out null values from the list before processing.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts,...
Posted by dbtsai <gi...@git.apache.org>.
Github user dbtsai commented on a diff in the pull request:
https://github.com/apache/spark/pull/23171#discussion_r237226275
--- Diff: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala ---
@@ -335,6 +343,41 @@ case class In(value: Expression, list: Seq[Expression]) extends Predicate {
""".stripMargin)
}
+ private def genCodeWithSwitch(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+ val (nullLiterals, nonNullLiterals) = list.partition {
+ case Literal(null, _) => true
+ case _ => false
+ }
+ val listGen = nonNullLiterals.map(_.genCode(ctx))
+ val valueGen = value.genCode(ctx)
+
+ val caseBranches = listGen.map(literal =>
+ s"""
+ |case ${literal.value}:
+ | ${ev.value} = true;
+ | break;
+ """.stripMargin)
+
+ ev.copy(code =
+ code"""
+ |${valueGen.code}
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.isNull} = ${valueGen.isNull};
+ |${CodeGenerator.JAVA_BOOLEAN} ${ev.value} = false;
+ |if (!${valueGen.isNull}) {
+ | switch (${valueGen.value}) {
+ | ${caseBranches.mkString("")}
+ | default:
+ | ${ev.isNull} = ${nullLiterals.nonEmpty};
+ | }
+ |}
+ """.stripMargin)
+ }
+
+ private def isSwitchCompatible: Boolean = list.forall {
+ case Literal(_, dt) => dt == ByteType || dt == ShortType || dt == IntegerType
--- End diff --
```scala
case Literal(_, dt) if dt == ByteType || dt == ShortType || dt == IntegerType => true
```
is easier to read?
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by cloud-fan <gi...@git.apache.org>.
Github user cloud-fan commented on the issue:
https://github.com/apache/spark/pull/23171
I think `InSet` is not an optimized version of `In`, but just a way to separate the implementation for different conditions (the length of the list). Maybe we should do the same thing here, create a `InSwitch` and convert `In` to it when meeting some conditions. One problem is, `In` and `InSwitch` is same in the interpreted version, maybe we should create a base class for them.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by gatorsmile <gi...@git.apache.org>.
Github user gatorsmile commented on the issue:
https://github.com/apache/spark/pull/23171
Also cc @ueshin
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by aokolnychyi <gi...@git.apache.org>.
Github user aokolnychyi commented on the issue:
https://github.com/apache/spark/pull/23171
@gatorsmile @cloud-fan @dongjoon-hyun @viirya
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #23171: [SPARK-26205][SQL] Optimize In for bytes, shorts, ints
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/23171
**[Test build #99393 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/99393/testReport)** for PR 23171 at commit [`1477f10`](https://github.com/apache/spark/commit/1477f101951ed39b96f884ddd2d451e164c0cc43).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org