This is an automated email from the ASF dual-hosted git repository.
cloud-fan pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.x by this push:
new b1980ece408a [SPARK-60744][SQL] Read the right side once with a cursor
in the sort-merge ASOF join
b1980ece408a is described below
commit b1980ece408a9754a542b405ccdf61a6d53d441a
Author: Luka Zdravić <[email protected]>
AuthorDate: Thu Nov 5 22:25:04 2026 +0000
[SPARK-60744][SQL] Read the right side once with a cursor in the sort-merge
ASOF join
`SortMergeAsOfJoinExec` gets a cursor scan. For a backward or forward join,
it walks the right side once and keeps only the best right row so far. It does
not buffer the right-side group.
The operator checks once per query whether the join can use it. It needs
all of these:
- A backward or forward join, not nearest.
- No residual join condition left after pushdown.
- An as-of condition that compares the two sort keys, left side first, of
the same type. SQL always puts the left side first.
- A scalar key type, not STRUCT, ARRAY, TIME, nanosecond timestamp, or a
user-defined type.
Every other join keeps the buffered scan. The new internal config
`spark.sql.join.sortMergeAsOfJoin.cursorScan.enabled` (default `true`) turns
the cursor scan off. The new metric `number of cursor scan tasks` counts the
tasks that use it.
The buffered scan saves each right-side group, then rereads it from the
start for every left row. So a group with N left rows and M right rows can cost
up to N x M condition checks, and a large group spills to disk. Both sides are
already sorted by the as-of key, so the match only moves forward as the left
key grows. The cursor scan costs about N + M checks.
```sql
SELECT * FROM trades t LEFT ASOF JOIN quotes q
MATCH_CONDITION (t.ts >= q.ts) ON t.sym = q.sym
```
`AsOfJoinBenchmark` joins BIGINT keys on both sides and runs the sort-merge
join with the buffered scan and with the cursor scan. 10,000 rows on each side,
best time on the GitHub Actions benchmark runner (JDK 21,
`AsOfJoinBenchmark-results.txt`):
- 100 groups: 49 ms -> 32 ms
- 10 groups: 115 ms -> 27 ms
- No equi-key: 663 ms -> 19 ms
No. Query results stay the same. The join node in the SQL UI shows one new
metric.
New `SortMergeAsOfJoinScannerSuite` tests check that the cursor scan checks
the as-of condition only twice per left row, and which conditions
`supportsCursorScan` accepts and rejects.
New `AsOfJoinSortMergeSQLSuite` tests run each query with the cursor scan
off and on, and check both against the same expected rows. With a spill
threshold of one row, the cursor run must spill nothing. They cover ties, NULL
keys, scalar types, NaN and -0.0, expression sides, STRING against INT, mixed
TIMESTAMP_LTZ and TIMESTAMP_NTZ across a DST gap, and the joins that must keep
the buffered scan.
The existing DataFrame `joinAsOf` tests in `SortMergeAsOfJoinSuite` now run
with the cursor scan on. Its spill tests turn the cursor scan off, since it
never buffers.
New ANSI tests run with the cursor scan off and on. A left row whose key
has no right rows never fails, even when its MATCH_CONDITION side is an invalid
cast or overflows. When its key has right rows, both runs fail with the same
error. The backward, forward and right-side-first DataFrame tests in
`SortMergeAsOfJoinSuite` check that the cursor scan is used and nothing spills.
Generated-by: Claude Code
Closes #59957 from LukaZdravic/asof-jvm-cursor.
Authored-by: Luka Zdravić <[email protected]>
Signed-off-by: Wenchen Fan <[email protected]>
(cherry picked from commit 3aa4fe9e45b3b06bfb162c4820e24c5c01c2da2d)
Signed-off-by: Wenchen Fan <[email protected]>
Co-authored-by: Isaac <[email protected]>
---
.../org/apache/spark/sql/internal/SQLConf.scala | 16 +
.../benchmarks/AsOfJoinBenchmark-jdk21-results.txt | 21 +-
.../benchmarks/AsOfJoinBenchmark-jdk25-results.txt | 21 +-
.../execution/joins/SortMergeAsOfJoinExec.scala | 221 +++++++++-
.../spark/sql/AsOfJoinSortMergeSQLSuite.scala | 486 +++++++++++++++++++++
.../apache/spark/sql/SortMergeAsOfJoinSuite.scala | 66 ++-
.../execution/benchmark/AsOfJoinBenchmark.scala | 31 +-
.../joins/SortMergeAsOfJoinScannerSuite.scala | 259 ++++++++++-
8 files changed, 1068 insertions(+), 53 deletions(-)
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
index a05045d690fb..a5b0658d152e 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
@@ -1212,6 +1212,19 @@ object SQLConf {
.booleanConf
.createWithDefault(false)
+ val SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED =
+ buildConf("spark.sql.join.sortMergeAsOfJoin.cursorScan.enabled")
+ .internal()
+ .doc("When true, the sort-merge AS-OF join reads the right side once
with a cursor if " +
+ "the join is backward or forward, has no residual join condition, and
its as-of " +
+ "condition compares the two sort keys, left one first and of the same
type. Other " +
+ "joins, and joins on STRUCT, ARRAY, TIME, nanosecond timestamp or
user-defined type " +
+ "keys, buffer each right-side group and scan the buffer again for
every left row.")
+ .version("4.4.0")
+ .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+ .booleanConf
+ .createWithDefault(true)
+
val REQUIRE_ALL_CLUSTER_KEYS_FOR_CO_PARTITION =
buildConf("spark.sql.requireAllClusterKeysForCoPartition")
.internal()
@@ -9815,6 +9828,9 @@ class SQLConf extends Serializable with Logging with
SqlApiConf {
def sqlAsOfJoinEnabled: Boolean = getConf(SQL_ASOF_JOIN_ENABLED)
+ def sortMergeAsOfJoinCursorScanEnabled: Boolean =
+ getConf(SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED)
+
def enableRadixSort: Boolean = getConf(RADIX_SORT_ENABLED)
def isParquetSchemaMergingEnabled: Boolean =
getConf(PARQUET_SCHEMA_MERGING_ENABLED)
diff --git a/sql/core/benchmarks/AsOfJoinBenchmark-jdk21-results.txt
b/sql/core/benchmarks/AsOfJoinBenchmark-jdk21-results.txt
index 6b2620e14ef8..79b5d618365f 100644
--- a/sql/core/benchmarks/AsOfJoinBenchmark-jdk21-results.txt
+++ b/sql/core/benchmarks/AsOfJoinBenchmark-jdk21-results.txt
@@ -2,25 +2,28 @@
AS-OF Join Benchmark
================================================================================================
-OpenJDK 64-Bit Server VM 21.0.12+8-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 21.0.13.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join (left=10000, right=10000, groups=100): Best Time(ms) Avg
Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 37512 37670
223 0.0 3751200.6 1.0X
-Sort-merge AS-OF join 56 79
17 0.2 5646.2 664.4X
+Correlated subquery (baseline) 38507 38693
263 0.0 3850687.8 1.0X
+Sort-merge AS-OF join, buffered scan 49 76
15 0.2 4885.1 788.2X
+Sort-merge AS-OF join, cursor scan 32 43
10 0.3 3224.7 1194.1X
-OpenJDK 64-Bit Server VM 21.0.12+8-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 21.0.13.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join (left=10000, right=10000, groups=10): Best Time(ms) Avg Time(ms)
Stdev(ms) Rate(M/s) Per Row(ns) Relative
-------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 38859 39083
316 0.0 3885945.5 1.0X
-Sort-merge AS-OF join 134 153
14 0.1 13400.5 290.0X
+Correlated subquery (baseline) 39596 39689
132 0.0 3959578.9 1.0X
+Sort-merge AS-OF join, buffered scan 115 137
30 0.1 11501.3 344.3X
+Sort-merge AS-OF join, cursor scan 27 37
10 0.4 2698.8 1467.2X
-OpenJDK 64-Bit Server VM 21.0.12+8-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 21.0.13.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join no equi-key (left=10000, right=10000): Best Time(ms) Avg
Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 24135 24198
90 0.0 2413476.8 1.0X
-Sort-merge AS-OF join 948 957
8 0.0 94829.4 25.5X
+Correlated subquery (baseline) 26811 26867
79 0.0 2681083.8 1.0X
+Sort-merge AS-OF join, buffered scan 663 672
9 0.0 66325.8 40.4X
+Sort-merge AS-OF join, cursor scan 19 28
9 0.5 1949.8 1375.0X
diff --git a/sql/core/benchmarks/AsOfJoinBenchmark-jdk25-results.txt
b/sql/core/benchmarks/AsOfJoinBenchmark-jdk25-results.txt
index d24862a01e7f..a06835d535d0 100644
--- a/sql/core/benchmarks/AsOfJoinBenchmark-jdk25-results.txt
+++ b/sql/core/benchmarks/AsOfJoinBenchmark-jdk25-results.txt
@@ -2,25 +2,28 @@
AS-OF Join Benchmark
================================================================================================
-OpenJDK 64-Bit Server VM 25.0.4+7-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 25.0.5.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join (left=10000, right=10000, groups=100): Best Time(ms) Avg
Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 39669 39714
65 0.0 3966851.1 1.0X
-Sort-merge AS-OF join 51 69
11 0.2 5147.4 770.7X
+Correlated subquery (baseline) 39524 39771
349 0.0 3952429.4 1.0X
+Sort-merge AS-OF join, buffered scan 57 80
12 0.2 5707.9 692.4X
+Sort-merge AS-OF join, cursor scan 36 46
8 0.3 3611.0 1094.6X
-OpenJDK 64-Bit Server VM 25.0.4+7-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 25.0.5.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join (left=10000, right=10000, groups=10): Best Time(ms) Avg Time(ms)
Stdev(ms) Rate(M/s) Per Row(ns) Relative
-------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 38551 38612
86 0.0 3855093.8 1.0X
-Sort-merge AS-OF join 113 126
11 0.1 11329.9 340.3X
+Correlated subquery (baseline) 38638 38681
60 0.0 3863782.0 1.0X
+Sort-merge AS-OF join, buffered scan 108 134
31 0.1 10803.5 357.6X
+Sort-merge AS-OF join, cursor scan 31 40
10 0.3 3066.6 1260.0X
-OpenJDK 64-Bit Server VM 25.0.4+7-LTS on Linux 6.17.0-1022-azure
+OpenJDK 64-Bit Server VM 25.0.5.0.3+1-LTS on Linux 7.0.0-1017-azure
AMD EPYC 7763 64-Core Processor
AS-OF Join no equi-key (left=10000, right=10000): Best Time(ms) Avg
Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------
-Correlated subquery (baseline) 23087 23184
137 0.0 2308693.2 1.0X
-Sort-merge AS-OF join 871 881
9 0.0 87066.5 26.5X
+Correlated subquery (baseline) 24412 24477
92 0.0 2441186.7 1.0X
+Sort-merge AS-OF join, buffered scan 780 788
9 0.0 78013.4 31.3X
+Sort-merge AS-OF join, cursor scan 22 34
9 0.4 2223.1 1098.1X
diff --git
a/sql/core/src/main/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinExec.scala
b/sql/core/src/main/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinExec.scala
index b5b0bf568b66..ef1f8650ee52 100644
---
a/sql/core/src/main/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinExec.scala
+++
b/sql/core/src/main/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinExec.scala
@@ -31,9 +31,9 @@ import org.apache.spark.sql.catalyst.plans.physical._
import org.apache.spark.sql.catalyst.util.TypeUtils
import org.apache.spark.sql.execution._
import org.apache.spark.sql.execution.metric.{SQLMetric, SQLMetrics}
-import org.apache.spark.sql.types.{AnyTimestampNanoType, DataType, DateType,
DayTimeIntervalType,
- Decimal, DecimalType, DoubleType, FloatType, IntegralType, TimestampNTZType,
TimestampType,
- YearMonthIntervalType}
+import org.apache.spark.sql.types.{AnyTimestampNanoType, BinaryType,
BooleanType, DataType,
+ DateType, DayTimeIntervalType, Decimal, DecimalType, DoubleType, FloatType,
IntegralType,
+ NullType, NumericType, StringType, TimestampNTZType, TimestampType,
YearMonthIntervalType}
import org.apache.spark.unsafe.types.TimestampNanosVal
/**
@@ -44,10 +44,13 @@ import org.apache.spark.unsafe.types.TimestampNanosVal
*
* The right-side buffer uses [[ExternalAppendOnlyUnsafeRowArray]] which
* spills to disk when the in-memory threshold is exceeded, avoiding OOM
- * for skewed equi-key groups.
+ * for skewed equi-key groups. Joins that can use a cursor scan (see
+ * [[SortMergeAsOfJoinScanner.supportsCursorScan]]) read the right side once
+ * and buffer nothing.
*
* Note: When there are no equi-keys, both sides are collected into a
- * single partition (AllTuples) and the entire right side is buffered.
+ * single partition (AllTuples) and, without a cursor scan, the entire
+ * right side is buffered.
*/
case class SortMergeAsOfJoinExec(
leftKeys: Seq[Expression],
@@ -72,7 +75,8 @@ case class SortMergeAsOfJoinExec(
override lazy val metrics: Map[String, SQLMetric] = Map(
"numOutputRows" -> SQLMetrics.createMetric(sparkContext, "number of output
rows"),
- "spillSize" -> SQLMetrics.createSizeMetric(sparkContext, "spill size"))
+ "spillSize" -> SQLMetrics.createSizeMetric(sparkContext, "spill size"),
+ "numAsOfCursorTasks" -> SQLMetrics.createMetric(sparkContext, "number of
cursor scan tasks"))
override def supportCodegen: Boolean = false
@@ -106,6 +110,10 @@ case class SortMergeAsOfJoinExec(
val inMemoryThreshold = conf.sortMergeJoinExecBufferInMemoryThreshold
val sizeInBytesSpillThreshold =
conf.sortMergeJoinExecBufferSpillSizeThreshold
val spillThreshold = conf.sortMergeJoinExecBufferSpillThreshold
+ val numAsOfCursorTasks = longMetric("numAsOfCursorTasks")
+ val useCursorScan = conf.sortMergeAsOfJoinCursorScanEnabled &&
+ SortMergeAsOfJoinScanner.supportsCursorScan(
+ direction, asOfCondition, condition, leftSortExprs, rightSortExprs)
left.execute().zipPartitions(right.execute()) { (leftIter, rightIter) =>
val scanner = new SortMergeAsOfJoinScanner(
@@ -116,7 +124,8 @@ case class SortMergeAsOfJoinExec(
asOfCondition,
joinType, condition,
numOutputRows, spillSize, direction,
- inMemoryThreshold, sizeInBytesSpillThreshold, spillThreshold
+ inMemoryThreshold, sizeInBytesSpillThreshold, spillThreshold,
+ useCursorScan, numAsOfCursorTasks
)
TaskContext.get().addTaskCompletionListener[Unit](_ => scanner.close())
scanner.iterator
@@ -138,6 +147,9 @@ case class SortMergeAsOfJoinExec(
* - Backward (left.t >= right.t): the last satisfying row is the closest.
* - Forward (left.t <= right.t): the first satisfying row is the closest.
* - Nearest: the closest eligible rows before and after the left key are
compared.
+ *
+ * With `useCursorScan`, the scan does not buffer the group. It walks the
right input once and
+ * keeps only the best row so far (see [[findWithCursor]]).
*/
private[joins] class SortMergeAsOfJoinScanner(
leftIter: Iterator[InternalRow],
@@ -156,7 +168,9 @@ private[joins] class SortMergeAsOfJoinScanner(
direction: AsOfJoinDirection,
inMemoryThreshold: Int,
sizeInBytesSpillThreshold: Long,
- spillThreshold: Int) {
+ spillThreshold: Int,
+ useCursorScan: Boolean,
+ numAsOfCursorTasks: SQLMetric) {
private val joinedOutput = leftOutput ++ rightOutput
private val joinedRow = new JoinedRow()
@@ -201,6 +215,10 @@ private[joins] class SortMergeAsOfJoinScanner(
s"Unexpected nearest keys: $leftSortExprs and $rightSortExprs")
}
+ // Lazy, since only the cursor scan reads the keys.
+ private lazy val cursorKeys: (Expression, Expression) =
+ (bindReference(leftSortExprs.head, leftOutput),
bindReference(rightSortExprs.head, rightOutput))
+
// Materialize an all-null right row as UnsafeRow. GenericInternalRow cannot
be
// passed through identity UnsafeProjection when right columns are NOT NULL.
private val nullRightRow: InternalRow = {
@@ -216,14 +234,28 @@ private[joins] class SortMergeAsOfJoinScanner(
inMemoryThreshold, sizeInBytesSpillThreshold, spillThreshold,
sizeInBytesSpillThreshold)
private var rightGroupKey: UnsafeRow = _
+ // The next right row. It is the output row of `rightToUnsafe`, so reading
the right row after
+ // it overwrites it. Anything that keeps it longer must copy it.
private var rightPeek: UnsafeRow = _
private var rightDone: Boolean = !rightIter.hasNext
+ // Cursor scan state: the left equi-key of the current group, whether the
group has any right
+ // row, and its best right row so far. `cursorBest` is null or
`cursorBestBuffer`, which holds
+ // a copy of the best row and is reused for every new best row.
+ private var cursorGroupKey: UnsafeRow = _
+ private var cursorGroupHasRight: Boolean = false
+ private var cursorBest: UnsafeRow = _
+ private var cursorBestBuffer: UnsafeRow = _
+
// Projection to convert right rows to UnsafeRow for the buffer
private val rightToUnsafe = UnsafeProjection.create(rightOutput, rightOutput)
if (!rightDone) {
- rightPeek = rightToUnsafe(rightIter.next()).copy()
+ rightPeek = rightToUnsafe(rightIter.next())
+ }
+
+ if (useCursorScan) {
+ numAsOfCursorTasks += 1
}
def close(): Unit = {
@@ -262,9 +294,12 @@ private[joins] class SortMergeAsOfJoinScanner(
return resultProjection(joinedRow).copy()
}
} else {
- advanceRightTo(leftKey)
-
- val bestMatch = findBestInGroup(leftRow)
+ val bestMatch = if (useCursorScan) {
+ findWithCursor(leftRow, leftKey)
+ } else {
+ advanceRightTo(leftKey)
+ findBestInGroup(leftRow)
+ }
if (bestMatch != null) {
numOutputRows += 1
@@ -297,11 +332,7 @@ private[joins] class SortMergeAsOfJoinScanner(
val rightKey = rightKeyProj(rightPeek)
val cmp = ordering.compare(leftKey, rightKey)
if (cmp > 0) {
- rightPeek = if (rightIter.hasNext) {
- rightToUnsafe(rightIter.next()).copy()
- } else {
- rightDone = true; null
- }
+ advanceRightPeek()
} else if (cmp == 0) {
bufferRightGroup(leftKey, ordering)
return
@@ -325,17 +356,25 @@ private[joins] class SortMergeAsOfJoinScanner(
val rightKey = rightKeyProj(rightPeek)
if (ordering.compare(leftKey, rightKey) == 0) {
rightGroupBuffer.add(rightPeek)
- rightPeek = if (rightIter.hasNext) {
- rightToUnsafe(rightIter.next()).copy()
- } else {
- rightDone = true; null
- }
+ advanceRightPeek()
} else {
return
}
}
}
+ /**
+ * Moves `rightPeek` to the next right row, or to null at the end of the
right input. The row
+ * is not copied: the buffer copies the rows it keeps, and the cursor copies
its best row.
+ */
+ private def advanceRightPeek(): Unit = {
+ rightPeek = if (rightIter.hasNext) {
+ rightToUnsafe(rightIter.next())
+ } else {
+ rightDone = true; null
+ }
+ }
+
private def bufferAllRight(): Unit = {
rightGroupBuffer.clear()
if (rightPeek != null) {
@@ -434,6 +473,91 @@ private[joins] class SortMergeAsOfJoinScanner(
null
}
+ /**
+ * Finds the best right row for `leftRow` by moving a cursor over the right
input, or null.
+ *
+ * Left rows of a group come in ascending as-of key order. So a right row
that passes for one
+ * left row also passes for the next (backward), and a row that fails stays
failed (forward).
+ * The cursor never steps back: backward stops at the first failing row and
keeps it for the
+ * next left row, and forward drops each failing row, since no later left
row can match it.
+ */
+ private def findWithCursor(leftRow: InternalRow, leftKey: UnsafeRow):
InternalRow = {
+ // Without equi-keys, all rows form one group, so only the first left row
starts it.
+ if (cursorGroupKey == null || equiKeyOrdering.exists(_.compare(leftKey,
cursorGroupKey) != 0)) {
+ startCursorGroup(leftKey)
+ }
+ // Like the buffered scan, a group with no right rows never evaluates the
left as-of key,
+ // which can fail at runtime, for example on an invalid cast under ANSI.
+ if (!cursorGroupHasRight) return null
+
+ val (leftAsOfKey, rightAsOfKey) = cursorKeys
+ // A NULL left as-of key matches nothing. It must not move the cursor, or
forward would drop
+ // right rows that later left rows need.
+ if (leftAsOfKey.eval(leftRow) == null) return null
+
+ joinedRow.withLeft(leftRow)
+ if (direction == Forward && cursorBest != null) {
+ // The cursor is already past the best row, and every row before it
failed.
+ joinedRow.withRight(cursorBest)
+ if (holds(boundAsOfCond)) return cursorBest
+ cursorBest = null
+ }
+
+ // The group's right rows end at the first row of a later group.
+ while (rightPeek != null && compareToRightPeek(leftKey) == 0) {
+ if (rightAsOfKey.eval(rightPeek) == null) {
+ // A NULL right as-of key: no left row can match it.
+ advanceRightPeek()
+ } else {
+ joinedRow.withRight(rightPeek)
+ if (holds(boundAsOfCond)) {
+ // The next right row overwrites `rightPeek`, so keep a copy.
+ cursorBest = copyToCursorBestBuffer(rightPeek)
+ advanceRightPeek()
+ if (direction == Forward) return cursorBest
+ } else if (direction == Backward) {
+ return cursorBest
+ } else {
+ advanceRightPeek()
+ }
+ }
+ }
+ cursorBest
+ }
+
+ /**
+ * Starts the cursor group of `leftKey`. It skips the right rows of earlier
groups without
+ * evaluating either as-of key, then records whether the group has a right
row. A right row
+ * with a NULL as-of key counts, since the buffered scan evaluates the as-of
condition on it.
+ */
+ private def startCursorGroup(leftKey: UnsafeRow): Unit = {
+ cursorGroupKey = leftKey
+ cursorBest = null
+ while (rightPeek != null && compareToRightPeek(leftKey) > 0) {
+ advanceRightPeek()
+ }
+ cursorGroupHasRight = rightPeek != null && compareToRightPeek(leftKey) == 0
+ }
+
+ /**
+ * Copies `row` into `cursorBestBuffer` and returns the buffer. One buffer
is enough, since the
+ * cursor never needs the old best row once it has a new one.
+ */
+ private def copyToCursorBestBuffer(row: UnsafeRow): UnsafeRow = {
+ if (cursorBestBuffer == null) {
+ cursorBestBuffer = row.copy()
+ } else {
+ cursorBestBuffer.copyFrom(row)
+ }
+ cursorBestBuffer
+ }
+
+ /** Compares `leftKey` with the equi-key of `rightPeek`. Without equi-keys,
all rows tie. */
+ private def compareToRightPeek(leftKey: UnsafeRow): Int = equiKeyOrdering
match {
+ case Some(ordering) => ordering.compare(leftKey, rightKeyProj(rightPeek))
+ case None => 0
+ }
+
/** Finds the nearest row passing both conditions, preferring the
predecessor on equal gaps. */
private def findNearest(leftRow: InternalRow): InternalRow = {
val (leftKeyExpr, rightKeyExpr, keyOrdering) = nearestKeys
@@ -518,3 +642,56 @@ private[joins] class SortMergeAsOfJoinScanner(
if (lower.isNaN || upper.isNaN) 2 else if (lower.isInfinite ||
upper.isInfinite) 1 else 0
}
}
+
+private[execution] object SortMergeAsOfJoinScanner {
+
+ /**
+ * Whether the scan can read the right side once with a cursor, instead of
buffering each
+ * right-side group and scanning it again for every left row.
+ *
+ * This needs a backward or forward join with no residual condition, whose
as-of condition
+ * only compares the two sort keys. Both sides are sorted on exactly those
keys, so the right
+ * rows that pass the condition move forward as the left key grows. Anything
else, such as a
+ * tolerance, a tuple, or an operand cast that the sort key does not have,
keeps the buffer.
+ *
+ * The condition must name the left side first, since the cursor evaluates
the left key first.
+ * With the right side first, a NULL right key ends the condition before the
left key, which
+ * can fail under ANSI. Only a DataFrame join with reversed keys builds such
a condition.
+ */
+ def supportsCursorScan(
+ direction: AsOfJoinDirection,
+ asOfCondition: Expression,
+ residualCondition: Option[Expression],
+ leftSortExprs: Seq[Expression],
+ rightSortExprs: Seq[Expression]): Boolean = {
+ // The operands as (left, right): backward needs left >= right, forward
left <= right.
+ val operands = (direction, asOfCondition) match {
+ case (Backward, GreaterThanOrEqual(left, right)) => Some((left, right))
+ case (Backward, GreaterThan(left, right)) => Some((left, right))
+ case (Forward, LessThanOrEqual(left, right)) => Some((left, right))
+ case (Forward, LessThan(left, right)) => Some((left, right))
+ case _ => None
+ }
+ (leftSortExprs, rightSortExprs, operands) match {
+ case (Seq(leftKey), Seq(rightKey), Some((leftOperand, rightOperand))) =>
+ residualCondition.isEmpty &&
+ leftOperand.semanticEquals(leftKey) &&
+ rightOperand.semanticEquals(rightKey) &&
+ leftKey.dataType == rightKey.dataType &&
+ supportsCursorKey(leftKey.dataType)
+ case _ => false
+ }
+ }
+
+ /**
+ * The key types the cursor scan supports. STRUCT, ARRAY, TIME, nanosecond
timestamp and
+ * user-defined type keys keep the buffered scan for now, since the cursor
scan has no tests
+ * for them yet.
+ */
+ private def supportsCursorKey(dataType: DataType): Boolean = dataType match {
+ case _: NumericType | BooleanType | _: StringType | BinaryType | NullType
=> true
+ case DateType | TimestampType | TimestampNTZType => true
+ case _: YearMonthIntervalType | _: DayTimeIntervalType => true
+ case _ => false
+ }
+}
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/AsOfJoinSortMergeSQLSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/AsOfJoinSortMergeSQLSuite.scala
index f927388f659a..da6caa107c1b 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/AsOfJoinSortMergeSQLSuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/AsOfJoinSortMergeSQLSuite.scala
@@ -19,6 +19,9 @@ package org.apache.spark.sql
import java.sql.{Date, Timestamp}
+import scala.util.Random
+
+import org.apache.spark.SparkThrowable
import org.apache.spark.sql.catalyst.expressions.Cast
import org.apache.spark.sql.catalyst.plans.{AsOfJoinDirection, Backward,
Forward}
import org.apache.spark.sql.catalyst.plans.logical.AsOfJoin
@@ -27,6 +30,7 @@ import
org.apache.spark.sql.execution.adaptive.AdaptiveSparkPlanHelper
import org.apache.spark.sql.execution.joins.SortMergeAsOfJoinExec
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.test.SharedSparkSession
+import org.apache.spark.sql.types.{IntegerType, StringType, StructType}
/**
* SQL ASOF JOIN tests that exercise the sort-merge physical operator.
@@ -117,6 +121,43 @@ class AsOfJoinSortMergeSQLSuite extends QueryTest
}
}
+ /** The value of `metric` in the one SortMergeAsOfJoinExec of `df`, read
after `df` ran. */
+ private def asOfJoinMetric(df: DataFrame, metric: String): Long = {
+ val plan = df.queryExecution.executedPlan
+ val joins = collect(plan) { case j: SortMergeAsOfJoinExec => j }
+ assert(joins.length == 1, s"Expected one SortMergeAsOfJoinExec in
plan:\n$plan")
+ joins.head.metrics(metric).value
+ }
+
+ /**
+ * Checks `query` with the cursor scan off and on. A right group spills from
its second row,
+ * so a cursor scan that buffered rows would show a spill. One partition
puts every equi-key
+ * in one task, so the cursor scan also has to move between groups.
+ */
+ private def checkCursorScan(query: => DataFrame, expected: Seq[Row]): Unit =
{
+ withSQLConf(
+ SQLConf.SHUFFLE_PARTITIONS.key -> "1",
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ withSQLConf(SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key ->
"false") {
+ val buffered = query
+ checkAnswer(buffered, expected)
+ assert(asOfJoinMetric(buffered, "numAsOfCursorTasks") == 0)
+ }
+ val cursor = query
+ checkAnswer(cursor, expected)
+ assert(asOfJoinMetric(cursor, "numAsOfCursorTasks") > 0, "Expected the
cursor scan")
+ assert(asOfJoinMetric(cursor, "spillSize") == 0, "The cursor scan
buffered right rows")
+ }
+ }
+
+ /** Checks `query`, and that it keeps the buffered scan with the cursor scan
on. */
+ private def checkBufferedScan(query: => DataFrame, expected: Seq[Row]): Unit
= {
+ val df = query
+ checkAnswer(df, expected)
+ assert(asOfJoinMetric(df, "numAsOfCursorTasks") == 0, "Expected the
buffered scan")
+ }
+
test("INNER ASOF JOIN with TIMESTAMP MATCH_CONDITION") {
setupTradeQuoteViews()
checkSortMergeAsOf(
@@ -1393,4 +1434,449 @@ class AsOfJoinSortMergeSQLSuite extends QueryTest
|""".stripMargin),
Row(Seq(Row(1, 2))) :: Nil)
}
+
+ test("cursor scan: backward match moves forward across trades and keys") {
+ // B has no quotes, C has quotes but no trades, and NULL keys never match.
A best row kept
+ // from key A would give B a match.
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.sym, t.ts, q.tag
+ |FROM VALUES ('A', 2), ('A', 6), ('A', 7), ('B', 4), ('D', 5),
(NULL, 3) AS t(sym, ts)
+ |LEFT ASOF JOIN VALUES ('A', 1, 'a1'), ('A', 3, 'a3'), ('A', 5,
'a5'), ('A', 8, 'a8'),
+ | ('C', 1, 'c1'), ('D', 2, 'd2'), ('D', 6, 'd6'), (NULL, 1, 'n1')
AS q(sym, ts, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ | ON t.sym = q.sym
+ |""".stripMargin),
+ Row("A", 2, "a1") :: Row("A", 6, "a5") :: Row("A", 7, "a5") :: Row("B",
4, null) ::
+ Row("D", 5, "d2") :: Row(null, 3, null) :: Nil)
+ }
+
+ test("cursor scan: two ON keys, with NULL parts, start a new group on either
key") {
+ // (1, 1) and (1, 2) differ only in the second key. A cursor that compared
only the first
+ // key would give trade 5 the quote q1n, and trade 1 the later quote q12.
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 1, 1, 10), (2, 1, 2, 10), (3, 1, NULL, 10), (4, 2,
1, 10), (5, 1, 1, 3)
+ | AS t(id, a, b, ts)
+ |LEFT ASOF JOIN VALUES (1, 1, 5, 'q11'), (1, 2, 6, 'q12'), (1, NULL,
1, 'q1n'),
+ | (2, 2, 1, 'q22') AS q(a, b, ts, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ | ON t.a = q.a AND t.b = q.b
+ |""".stripMargin),
+ Row(1, "q11") :: Row(2, "q12") :: Row(3, null) :: Row(4, null) :: Row(5,
null) :: Nil)
+ }
+
+ test("cursor scan: a MATCH_CONDITION with the right side first still uses
the cursor scan") {
+ // The analyzer puts the left side first, so q.ts <= t.ts runs as t.ts >=
q.ts.
+ Seq(
+ "q.ts <= t.ts" -> Seq(Row(2, "q1"), Row(6, "q5")),
+ "q.ts >= t.ts" -> Seq(Row(2, "q3"), Row(6, null))
+ ).foreach { case (condition, expected) =>
+ withClue(s"$condition: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT t.ts, q.tag
+ |FROM VALUES (2), (6) AS t(ts)
+ |LEFT ASOF JOIN VALUES (1, 'q1'), (3, 'q3'), (5, 'q5') AS q(ts,
tag)
+ | MATCH_CONDITION ($condition)
+ |""".stripMargin),
+ expected)
+ }
+ }
+ }
+
+ test("cursor scan: forward match is kept while later trades still pass it") {
+ // A3 reuses q4, A6 must drop it, and B1 must not reuse q7 from key A.
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.sym, t.ts, q.tag
+ |FROM VALUES ('A', 2), ('A', 3), ('A', 6), ('B', 1), ('C', 9) AS
t(sym, ts)
+ |LEFT ASOF JOIN VALUES ('A', 1, 'q1'), ('A', 4, 'q4'), ('A', 7,
'q7'),
+ | ('B', 0, 'b0'), ('B', 2, 'b2'), ('C', 5, 'c5') AS q(sym, ts, tag)
+ | MATCH_CONDITION (t.ts <= q.ts)
+ | ON t.sym = q.sym
+ |""".stripMargin),
+ Row("A", 2, "q4") :: Row("A", 3, "q4") :: Row("A", 6, "q7") :: Row("B",
1, "b2") ::
+ Row("C", 9, null) :: Nil)
+ }
+
+ test("cursor scan: strict and non-strict MATCH_CONDITION ties") {
+ // The second of two equal trades must see the same right rows as the
first.
+ Seq(">=" -> "q5", ">" -> "q3", "<=" -> "q5", "<" -> "q7").foreach { case
(op, tag) =>
+ withClue(s"$op: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 5), (2, 5) AS t(id, ts)
+ |ASOF JOIN VALUES (3, 'q3'), (5, 'q5'), (7, 'q7') AS q(ts, tag)
+ | MATCH_CONDITION (t.ts $op q.ts)
+ |""".stripMargin),
+ Row(1, tag) :: Row(2, tag) :: Nil)
+ }
+ }
+ }
+
+ test("cursor scan: NULL as-of keys never match and do not move the cursor") {
+ // The NULL trade sorts first. If it moved a forward cursor, trade 2 would
lose q3.
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, NULL), (2, 2) AS t(id, ts)
+ |LEFT ASOF JOIN VALUES (NULL, 'qn'), (3, 'q3') AS q(ts, tag)
+ | MATCH_CONDITION (t.ts <= q.ts)
+ |""".stripMargin),
+ Row(1, null) :: Row(2, "q3") :: Nil)
+ // The NULL quote sorts first. If it stopped a backward cursor, trade 2
would get no match.
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, NULL), (2, 2) AS t(id, ts)
+ |LEFT ASOF JOIN VALUES (NULL, 'qn'), (1, 'q1') AS q(ts, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ |""".stripMargin),
+ Row(1, null) :: Row(2, "q1") :: Nil)
+ }
+
+ test("cursor scan: scalar MATCH_CONDITION types") {
+ val numbers = Seq("TINYINT", "SMALLINT", "INT", "BIGINT", "FLOAT",
"DOUBLE", "DECIMAL(38, 18)")
+ .map(t => (t, s"CAST(1 AS $t)", s"CAST(2 AS $t)", s"CAST(3 AS $t)"))
+ def lcase(value: String): String = s"'$value' COLLATE UTF8_LCASE"
+ val others = Seq(
+ ("STRING", "'a'", "'b'", "'c'"),
+ // Binary order is 'B' < 'a' < 'c', but UTF8_LCASE order is 'a' < 'B' <
'c'.
+ ("STRING COLLATE UTF8_LCASE", lcase("a"), lcase("B"), lcase("c")),
+ ("BINARY", "X'01'", "X'02'", "X'03'"),
+ ("DATE", "DATE'2026-01-01'", "DATE'2026-01-02'", "DATE'2026-01-03'"),
+ ("TIMESTAMP", "TIMESTAMP'2026-01-01 00:00:01'", "TIMESTAMP'2026-01-01
00:00:02'",
+ "TIMESTAMP'2026-01-01 00:00:03'"),
+ ("TIMESTAMP_NTZ", "TIMESTAMP_NTZ'2026-01-01 00:00:01'",
+ "TIMESTAMP_NTZ'2026-01-01 00:00:02'", "TIMESTAMP_NTZ'2026-01-01
00:00:03'"),
+ ("INTERVAL YEAR TO MONTH", "INTERVAL '1-1' YEAR TO MONTH", "INTERVAL
'1-2' YEAR TO MONTH",
+ "INTERVAL '1-3' YEAR TO MONTH"),
+ ("INTERVAL DAY TO SECOND", "INTERVAL '1 00:00:01' DAY TO SECOND",
+ "INTERVAL '1 00:00:02' DAY TO SECOND", "INTERVAL '1 00:00:03' DAY TO
SECOND"))
+ for {
+ (typeName, before, at, after) <- numbers ++ others
+ (op, tag) <- Seq(">=" -> "before", "<=" -> "after")
+ } {
+ withClue(s"$typeName $op: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT q.tag
+ |FROM VALUES ($at) AS t(k)
+ |ASOF JOIN VALUES ($before, 'before'), ($after, 'after') AS
q(k, tag)
+ | MATCH_CONDITION (t.k $op q.k)
+ |""".stripMargin),
+ Row(tag) :: Nil)
+ }
+ }
+ }
+
+ test("cursor scan: DOUBLE NaN and negative zero MATCH_CONDITION") {
+ // Spark orders -0.0 equal to 0.0, and NaN above every other value.
+ Seq(">=", "<=").foreach { op =>
+ withClue(s"$op: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 0.0D), (2, CAST('NaN' AS DOUBLE)) AS t(id, k)
+ |ASOF JOIN VALUES (-0.0D, 'negative zero'), (1.0D, 'one'),
+ | (CAST('NaN' AS DOUBLE), 'nan') AS q(k, tag)
+ | MATCH_CONDITION (t.k $op q.k)
+ |""".stripMargin),
+ Row(1, "negative zero") :: Row(2, "nan") :: Nil)
+ }
+ }
+ }
+
+ test("cursor scan: MATCH_CONDITION sides that are expressions of a column") {
+ // Each side sorts on its whole operand, so the cursor walks the operand
values in order,
+ // even when the operand reverses the column order.
+ Seq(
+ // (match condition, backward rows, forward rows)
+ ("t.k + 10 OP q.k", Seq(Row(1, 8), Row(5, 12)), Seq(Row(1, 12), Row(5,
20))),
+ ("-t.k OP q.k", Seq(Row(1, -3), Row(5, -6)), Seq(Row(1, 0), Row(5, -3))),
+ ("t.k OP -q.k", Seq(Row(1, 0), Row(5, -3)), Seq(Row(1, -3), Row(5, -6)))
+ ).foreach { case (condition, backwardRows, forwardRows) =>
+ Seq(">=" -> backwardRows, "<=" -> forwardRows).foreach { case (op,
expected) =>
+ val matchCondition = condition.replace("OP", op)
+ withClue(s"$matchCondition: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT t.k, q.k
+ |FROM VALUES (1), (5) AS t(k)
+ |LEFT ASOF JOIN VALUES (-6), (-3), (0), (3), (6), (8), (12),
(20) AS q(k)
+ | MATCH_CONDITION ($matchCondition)
+ |""".stripMargin),
+ expected)
+ }
+ }
+ }
+ }
+
+ test("cursor scan: STRING against INT MATCH_CONDITION casts the STRING side
to the " +
+ "comparison type") {
+ Seq(true, false).foreach { ansi =>
+ withSQLConf(SQLConf.ANSI_ENABLED.key -> ansi.toString) {
+ Seq(">=" -> 3, "<=" -> 7).foreach { case (op, expected) =>
+ withClue(s"ansi=$ansi, $op: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT q.n
+ |FROM VALUES ('5') AS t(s)
+ |ASOF JOIN VALUES (3), (7) AS q(n)
+ | MATCH_CONDITION (t.s $op q.n)
+ |""".stripMargin),
+ Row(expected) :: Nil)
+ }
+ }
+ }
+ }
+ }
+
+ test("cursor scan: a left row whose key has no right rows never evaluates
its as-of side") {
+ // Under ANSI, 'bad' cannot be cast to a number and Long.MaxValue * 1000
overflows. The
+ // buffered scan evaluates the as-of condition only on right rows with the
same key, so key
+ // B never fails the query. The cursor scan must not evaluate the left
side of key B either.
+ withSQLConf(SQLConf.ANSI_ENABLED.key -> "true") {
+ Seq(
+ ("('A', '1'), ('B', 'bad'), ('C', '3')",
+ "('A', 0, 'a0'), ('A', 2, 'a2'), ('C', 2, 'c2'), ('C', 4, 'c4')",
"t.v"),
+ ("('A', 1L), ('B', 9223372036854775807L), ('C', 3L)",
+ "('A', 0L, 'a0'), ('A', 2000L, 'a2'), ('C', 2000L, 'c2'), ('C',
4000L, 'c4')",
+ "t.v * 1000")
+ ).foreach { case (leftRows, rightRows, leftSide) =>
+ for {
+ (op, tagA, tagC) <- Seq((">=", "a0", "c2"), ("<=", "a2", "c4"))
+ (joinType, unmatched) <- Seq("LEFT" -> Seq(Row("B", null)), "INNER"
-> Nil)
+ } {
+ withClue(s"$leftSide $op q.v, $joinType: ") {
+ checkCursorScan(
+ sql(
+ s"""
+ |SELECT t.k, q.tag
+ |FROM VALUES $leftRows AS t(k, v)
+ |$joinType ASOF JOIN VALUES $rightRows AS q(k, v, tag)
+ | MATCH_CONDITION ($leftSide $op q.v) ON t.k = q.k
+ |""".stripMargin),
+ Seq(Row("A", tagA), Row("C", tagC)) ++ unmatched)
+ }
+ }
+ }
+ }
+ }
+
+ test("cursor scan: a failing as-of side fails the query when its key has
right rows") {
+ withSQLConf(SQLConf.ANSI_ENABLED.key -> "true") {
+ Seq(
+ ("('A', 'bad')", "('A', 1)", "t.v", "CAST_INVALID_INPUT"),
+ ("('A', 9223372036854775807L)", "('A', 1L)", "t.v * 1000",
"ARITHMETIC_OVERFLOW"),
+ // A right row with a NULL as-of key still counts, since the buffered
scan evaluates the
+ // as-of condition on it.
+ ("('A', 'bad')", "('A', CAST(NULL AS INT))", "t.v",
"CAST_INVALID_INPUT"),
+ ("('A', 9223372036854775807L)", "('A', CAST(NULL AS BIGINT))", "t.v *
1000",
+ "ARITHMETIC_OVERFLOW")
+ ).foreach { case (leftRows, rightRows, leftSide, errorCondition) =>
+ for {
+ op <- Seq(">=", "<=")
+ cursorScan <- Seq(false, true)
+ } {
+ withClue(s"$leftSide $op q.v, cursor scan $cursorScan: ") {
+ withSQLConf(
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key ->
cursorScan.toString) {
+ val e = intercept[RuntimeException] {
+ sql(
+ s"""
+ |SELECT t.k, q.v
+ |FROM VALUES $leftRows AS t(k, v)
+ |LEFT ASOF JOIN VALUES $rightRows AS q(k, v)
+ | MATCH_CONDITION ($leftSide $op q.v) ON t.k = q.k
+ |""".stripMargin).collect()
+ }
+ assert(e.asInstanceOf[SparkThrowable].getCondition ==
errorCondition, e)
+ }
+ }
+ }
+ }
+ }
+ }
+
+ test("cursor scan: random rows match a plain join with the cursor scan off
and on") {
+ // Right as-of keys are unique within each ON key, so a plain join with
MAX or MIN over
+ // (as-of key, tag) finds the one closest right row. Tags of random
length, NULL keys, and ON
+ // keys that only one side has check that neither scan drops, mixes up or
reuses a row.
+ val leftSchema = new StructType().add("id", IntegerType).add("k",
IntegerType)
+ .add("ts", IntegerType)
+ val rightSchema = new StructType().add("k", IntegerType).add("ts",
IntegerType)
+ .add("tag", StringType)
+ (1 to 3).foreach { seed =>
+ val random = new Random(seed)
+ def orNull(value: Int): Any = if (random.nextInt(10) == 0) null else
value
+ def tag(): String =
+ if (random.nextInt(8) == 0) null else
random.alphanumeric.take(random.nextInt(40)).mkString
+ // Left ON keys are 0 to 7 and right ON keys 2 to 9, so keys 0, 1, 8 and
9 have one side.
+ val leftRows = (0 until 200).map { id =>
+ Row(id, orNull(random.nextInt(8)), orNull(random.nextInt(100)))
+ }
+ val rightRows = (2 until 10).flatMap { k =>
+ random.shuffle((0 until 100).toList).take(30).map(ts => Row(k, ts,
tag()))
+ } ++ Seq(Row(null, 5, "NULL ON key"), Row(3, null, "NULL as-of key"))
+ withTempView("t", "q") {
+ spark.createDataFrame(spark.sparkContext.parallelize(leftRows),
leftSchema)
+ .createOrReplaceTempView("t")
+ spark.createDataFrame(spark.sparkContext.parallelize(rightRows),
rightSchema)
+ .createOrReplaceTempView("q")
+ for {
+ (op, closest) <- Seq(">=" -> "MAX", ">" -> "MAX", "<=" -> "MIN", "<"
-> "MIN")
+ joinType <- Seq("LEFT", "INNER")
+ } {
+ val expected = sql(
+ s"""
+ |SELECT id, m.ts, m.tag
+ |FROM (
+ | SELECT t.id, $closest(named_struct('ts', q.ts, 'tag',
q.tag)) AS m
+ | FROM t LEFT JOIN q ON t.k = q.k AND t.ts $op q.ts
+ | GROUP BY t.id)
+ |WHERE '$joinType' = 'LEFT' OR m.ts IS NOT NULL
+ |""".stripMargin).collect().toSeq
+ // The default spill thresholds, unlike checkCursorScan: with a
one-row threshold, the
+ // buffered scan would open one spill file per right row of the
group for every left row.
+ for (cursorScan <- Seq(false, true)) {
+ withClue(s"seed $seed, $joinType, t.ts $op q.ts, cursor scan
$cursorScan: ") {
+ withSQLConf(
+ SQLConf.SHUFFLE_PARTITIONS.key -> "1",
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key ->
cursorScan.toString) {
+ val df = sql(
+ s"""
+ |SELECT t.id, q.ts, q.tag
+ |FROM t $joinType ASOF JOIN q
+ | MATCH_CONDITION (t.ts $op q.ts) ON t.k = q.k
+ |""".stripMargin)
+ checkAnswer(df, expected)
+ assert((asOfJoinMetric(df, "numAsOfCursorTasks") > 0) ==
cursorScan)
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ test("cursor scan: mixed TIMESTAMP_LTZ and TIMESTAMP_NTZ sides across a DST
gap") {
+ // On 2024-03-10 Los Angeles skips 02:00 to 03:00, so NTZ 02:50 becomes
10:50Z, after
+ // 03:00 (10:00Z) and 03:15 (10:15Z). The NTZ order and the LTZ order
differ.
+ withSQLConf(SQLConf.SESSION_LOCAL_TIMEZONE.key -> "America/Los_Angeles") {
+ val ltzRows = "(TIMESTAMP_LTZ '2024-03-10 10:05:00Z', 1), " +
+ "(TIMESTAMP_LTZ '2024-03-10 10:55:00Z', 2)"
+ val ntzRows = "(TIMESTAMP_NTZ '2024-03-10 02:50:00', 1), " +
+ "(TIMESTAMP_NTZ '2024-03-10 03:00:00', 2), (TIMESTAMP_NTZ '2024-03-10
03:15:00', 3)"
+ def query(leftRows: String, rightRows: String, op: String): DataFrame =
sql(
+ s"""
+ |SELECT l.id, r.id
+ |FROM VALUES $leftRows AS l(ts, id)
+ |LEFT ASOF JOIN VALUES $rightRows AS r(ts, id)
+ | MATCH_CONDITION (l.ts $op r.ts)
+ |""".stripMargin)
+
+ // The NTZ quotes sort on their LTZ cast, the same value the condition
compares.
+ checkCursorScan(query(ltzRows, ntzRows, ">="), Row(1, 2) :: Row(2, 1) ::
Nil)
+ checkCursorScan(query(ltzRows, ntzRows, "<="), Row(1, 3) :: Row(2, null)
:: Nil)
+
+ // The NTZ trades sort on their raw NTZ value, but the condition
compares their LTZ cast.
+ // A cursor would walk them in the wrong order: it would give trade 2
the quote of trade 1.
+ checkBufferedScan(query(ntzRows, ltzRows, ">="),
+ Row(1, 1) :: Row(2, null) :: Row(3, 1) :: Nil)
+ checkBufferedScan(query(ntzRows, ltzRows, "<="),
+ Row(1, 2) :: Row(2, 1) :: Row(3, 2) :: Nil)
+ }
+ }
+
+ test("cursor scan: a right-only ON predicate is pushed down, so the cursor
scan applies") {
+ checkCursorScan(
+ sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 'A', 10) AS t(id, sym, ts)
+ |LEFT ASOF JOIN VALUES ('A', 1, 50, 'cheap'), ('A', 5, 500, 'pricey')
+ | AS q(sym, ts, price, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ | ON t.sym = q.sym AND q.price <= 100
+ |""".stripMargin),
+ Row(1, "cheap") :: Nil)
+ }
+
+ test("cursor scan: a residual ON predicate keeps the buffered scan") {
+ withSQLConf(
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ // The latest quote within the price limit is the older one. A scan that
keeps only the
+ // latest quote would miss it.
+ val twoSided = sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 'A', 10, 100) AS t(id, sym, ts, max_price)
+ |LEFT ASOF JOIN VALUES ('A', 1, 50, 'cheap'), ('A', 5, 500, 'pricey')
+ | AS q(sym, ts, price, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ | ON t.sym = q.sym AND q.price <= t.max_price
+ |""".stripMargin)
+ checkBufferedScan(twoSided, Row(1, "cheap") :: Nil)
+ assert(asOfJoinMetric(twoSided, "spillSize") > 0)
+
+ // A LEFT ASOF JOIN keeps a left-only ON predicate in the join.
+ checkBufferedScan(
+ sql(
+ """
+ |SELECT t.id, q.tag
+ |FROM VALUES (1, 'A', 10, true), (2, 'A', 12, false) AS t(id, sym,
ts, active)
+ |LEFT ASOF JOIN VALUES ('A', 1, 'q1'), ('A', 5, 'q5') AS q(sym,
ts, tag)
+ | MATCH_CONDITION (t.ts >= q.ts)
+ | ON t.sym = q.sym AND t.active
+ |""".stripMargin),
+ Row(1, "q5") :: Row(2, null) :: Nil)
+ }
+ }
+
+ test("cursor scan: tuple, STRUCT and mixed type MATCH_CONDITIONs keep the
buffered scan") {
+ checkBufferedScan(
+ sql(
+ """
+ |SELECT r.tag
+ |FROM VALUES (1, 5) AS t(a, b)
+ |ASOF JOIN VALUES (1, 3, 'r13'), (1, 7, 'r17') AS r(a, b, tag)
+ | MATCH_CONDITION ((t.a, t.b) >= (r.a, r.b))
+ |""".stripMargin),
+ Row("r13") :: Nil)
+ checkBufferedScan(
+ sql(
+ """
+ |SELECT r.tag
+ |FROM VALUES (named_struct('x', 5)) AS t(s)
+ |ASOF JOIN VALUES (named_struct('x', 3), 'r3'), (named_struct('x',
7), 'r7') AS r(s, tag)
+ | MATCH_CONDITION (t.s >= r.s)
+ |""".stripMargin),
+ Row("r3") :: Nil)
+ // The comparison casts the INT side to BIGINT, but that side sorts on the
INT column.
+ checkBufferedScan(
+ sql(
+ """
+ |SELECT r.tag
+ |FROM VALUES (5) AS t(k)
+ |ASOF JOIN VALUES (CAST(3 AS BIGINT), 'r3'), (CAST(7 AS BIGINT),
'r7') AS r(k, tag)
+ | MATCH_CONDITION (t.k >= r.k)
+ |""".stripMargin),
+ Row("r3") :: Nil)
+ }
}
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/SortMergeAsOfJoinSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/SortMergeAsOfJoinSuite.scala
index 5167dad1b699..d75a955be330 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/SortMergeAsOfJoinSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/SortMergeAsOfJoinSuite.scala
@@ -78,6 +78,27 @@ class SortMergeAsOfJoinSuite extends QueryTest
assert(op.get.metrics("spillSize").value > 0,
s"Expected the right-side buffer to spill (spillSize > 0), " +
s"got ${op.get.metrics("spillSize").value}")
+ assert(op.get.metrics("numAsOfCursorTasks").value == 0,
+ "Expected the buffered scan, but a task used the cursor scan")
+ }
+
+ /**
+ * Like checkAnswer, but also asserts that the join used the cursor scan. A
right group spills
+ * from its second row, so a cursor scan that buffered rows would show a
spill.
+ */
+ private def checkCursorScan(df: classic.DataFrame, expectedAnswer:
Seq[Row]): Unit = {
+ withSQLConf(
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ checkAnswer(df, expectedAnswer)
+ }
+ val op = collectFirst(df.queryExecution.executedPlan) {
+ case s: SortMergeAsOfJoinExec => s
+ }
+ assert(op.isDefined,
+ s"Expected SortMergeAsOfJoinExec in
plan:\n${df.queryExecution.executedPlan}")
+ assert(op.get.metrics("numAsOfCursorTasks").value > 0, "Expected the
cursor scan")
+ assert(op.get.metrics("spillSize").value == 0, "The cursor scan buffered
right rows")
}
/**
@@ -150,7 +171,7 @@ class SortMergeAsOfJoinSuite extends QueryTest
test("backward join - simple") {
val (df1, df2) = prepareForAsOfJoin()
- checkAnswer(
+ checkCursorScan(
df1.joinAsOf(
df2, df1.col("a"), df2.col("a"), usingColumns = Seq.empty,
joinType = "inner", tolerance = null,
@@ -193,7 +214,7 @@ class SortMergeAsOfJoinSuite extends QueryTest
test("forward join") {
val (df1, df2) = prepareForAsOfJoin()
- checkAnswer(
+ checkCursorScan(
df1.joinAsOf(
df2, df1.col("a"), df2.col("a"), usingColumns = Seq.empty,
joinType = "inner", tolerance = null,
@@ -1634,6 +1655,31 @@ class SortMergeAsOfJoinSuite extends QueryTest
}
}
+ test("reversed join keys keep the buffered scan, which skips a failing left
key") {
+ // The reversed condition reads the right key first and stops at its NULL,
so v * 1000 never
+ // overflows. The cursor reads the left key first, so it would fail the
query under ANSI.
+ withSQLConf(
+ SQLConf.SORT_MERGE_AS_OF_JOIN_ENABLED.key -> "true",
+ SQLConf.ANSI_ENABLED.key -> "true") {
+ val left = spark.sql("SELECT * FROM VALUES ('B', 9223372036854775807L)
AS t(k, v)")
+ val right = spark.sql("SELECT * FROM VALUES ('B', CAST(NULL AS BIGINT))
AS t(k, v)")
+ for (direction <- Seq("backward", "forward")) {
+ withClue(s"$direction: ") {
+ val reversed = left.joinAsOf(
+ other = right, leftAsOf = right.col("v"), rightAsOf =
left.col("v") * 1000,
+ usingColumns = Seq("k"), joinType = "left", tolerance = null,
+ allowExactMatches = true, direction = direction)
+ checkAnswer(reversed, Row("B", Long.MaxValue, null, null) :: Nil)
+ val op = collectFirst(reversed.queryExecution.executedPlan) {
+ case s: SortMergeAsOfJoinExec => s
+ }
+ assert(op.exists(_.metrics("numAsOfCursorTasks").value == 0),
+ s"Expected the buffered
scan:\n${reversed.queryExecution.executedPlan}")
+ }
+ }
+ }
+ }
+
gridTest("join keys can reference hidden USING columns")(Seq(false, true)) {
singlePass =>
withAsOfJoinAnalyzer(singlePass) {
withSQLConf(
@@ -2149,7 +2195,9 @@ class SortMergeAsOfJoinSuite extends QueryTest
// produces the same results as the in-memory path.
withSQLConf(
SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
- SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1",
+ // The cursor scan never buffers, so turn it off to test the spill.
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false") {
val (df1, df2) = prepareForAsOfJoin()
// No equi-key (bufferAllRight path)
checkAnswerAndSpill(
@@ -2179,7 +2227,9 @@ class SortMergeAsOfJoinSuite extends QueryTest
test("forward join - spill to disk") {
withSQLConf(
SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
- SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1",
+ // The cursor scan never buffers, so turn it off to test the spill.
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false") {
val (df1, df2) = prepareForAsOfJoin()
// No equi-key (bufferAllRight path)
checkAnswerAndSpill(
@@ -2263,7 +2313,9 @@ class SortMergeAsOfJoinSuite extends QueryTest
test("left outer join - spill to disk") {
withSQLConf(
SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
- SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1",
+ // The cursor scan never buffers, so turn it off to test the spill.
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false") {
val (df1, df2) = prepareForAsOfJoin()
checkAnswerAndSpill(
df1.joinAsOf(
@@ -2288,7 +2340,9 @@ class SortMergeAsOfJoinSuite extends QueryTest
// match that was not copied out would be clobbered before it is emitted.
withSQLConf(
SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_IN_MEMORY_THRESHOLD.key -> "1",
- SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1") {
+ SQLConf.SORT_MERGE_JOIN_EXEC_BUFFER_SPILL_THRESHOLD.key -> "1",
+ // The cursor scan never buffers, so turn it off to test the spill.
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false") {
val leftSchema = StructType(
StructField("grp", StringType) ::
StructField("ts", IntegerType) :: Nil)
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/execution/benchmark/AsOfJoinBenchmark.scala
b/sql/core/src/test/scala/org/apache/spark/sql/execution/benchmark/AsOfJoinBenchmark.scala
index b17dc5ef8644..5e7a0f1df040 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/execution/benchmark/AsOfJoinBenchmark.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/execution/benchmark/AsOfJoinBenchmark.scala
@@ -24,6 +24,7 @@ import org.apache.spark.sql.internal.SQLConf
/**
* Benchmark to measure AS-OF join performance: sort-merge operator vs
correlated subquery.
+ * The sort-merge operator runs with the buffered scan and with the cursor
scan.
* To run this benchmark:
* {{{
* 1. build/sbt "sql/Test/runMain <this class>"
@@ -58,7 +59,8 @@ object AsOfJoinBenchmark extends SqlBasedBenchmark {
).toDF().asInstanceOf[classic.DataFrame]
val right: classic.DataFrame = spark.range(rightRows).select(
(col("id") % numGroups).as("group_id"),
- (col("id") * 3 / 2).as("ts"),
+ // BIGINT like the left side, since the cursor scan needs both sort keys
of one type.
+ (col("id") * 3 / 2).cast("bigint").as("ts"),
lit("right_val").as("right_val")
).toDF().asInstanceOf[classic.DataFrame]
@@ -75,9 +77,19 @@ object AsOfJoinBenchmark extends SqlBasedBenchmark {
}
}
- benchmark.addCase("Sort-merge AS-OF join") { _ =>
+ benchmark.addCase("Sort-merge AS-OF join, buffered scan") { _ =>
withSQLConf(
SQLConf.SORT_MERGE_AS_OF_JOIN_ENABLED.key -> "true",
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false",
+ SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false") {
+ doAsOfJoin(left, right, Seq("group_id"))
+ }
+ }
+
+ benchmark.addCase("Sort-merge AS-OF join, cursor scan") { _ =>
+ withSQLConf(
+ SQLConf.SORT_MERGE_AS_OF_JOIN_ENABLED.key -> "true",
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "true",
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false") {
doAsOfJoin(left, right, Seq("group_id"))
}
@@ -93,7 +105,8 @@ object AsOfJoinBenchmark extends SqlBasedBenchmark {
lit("left_val").as("left_val")
).toDF().asInstanceOf[classic.DataFrame]
val right: classic.DataFrame = spark.range(rightRows).select(
- (col("id") * 3 / 2).as("ts"),
+ // BIGINT like the left side, since the cursor scan needs both sort keys
of one type.
+ (col("id") * 3 / 2).cast("bigint").as("ts"),
lit("right_val").as("right_val")
).toDF().asInstanceOf[classic.DataFrame]
@@ -110,9 +123,19 @@ object AsOfJoinBenchmark extends SqlBasedBenchmark {
}
}
- benchmark.addCase("Sort-merge AS-OF join") { _ =>
+ benchmark.addCase("Sort-merge AS-OF join, buffered scan") { _ =>
+ withSQLConf(
+ SQLConf.SORT_MERGE_AS_OF_JOIN_ENABLED.key -> "true",
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "false",
+ SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false") {
+ doAsOfJoin(left, right, Seq.empty)
+ }
+ }
+
+ benchmark.addCase("Sort-merge AS-OF join, cursor scan") { _ =>
withSQLConf(
SQLConf.SORT_MERGE_AS_OF_JOIN_ENABLED.key -> "true",
+ SQLConf.SORT_MERGE_AS_OF_JOIN_CURSOR_SCAN_ENABLED.key -> "true",
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false") {
doAsOfJoin(left, right, Seq.empty)
}
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinScannerSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinScannerSuite.scala
index 831e8e4ea136..9a69b8599958 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinScannerSuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/execution/joins/SortMergeAsOfJoinScannerSuite.scala
@@ -20,12 +20,15 @@ package org.apache.spark.sql.execution.joins
import java.util.concurrent.atomic.AtomicInteger
import org.apache.spark.{LocalSparkContext, SparkConf, SparkContext,
SparkFunSuite}
+import org.apache.spark.sql.YearUDT
import org.apache.spark.sql.catalyst.InternalRow
import org.apache.spark.sql.catalyst.expressions._
import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
-import org.apache.spark.sql.catalyst.plans.{Inner, Nearest}
+import org.apache.spark.sql.catalyst.plans.{AsOfJoinDirection, Backward,
Forward, Inner, LeftOuter,
+ Nearest}
import org.apache.spark.sql.execution.metric.SQLMetric
-import org.apache.spark.sql.types.{DataType, IntegerType}
+import org.apache.spark.sql.types._
+import org.apache.spark.unsafe.types.UTF8String
class SortMergeAsOfJoinScannerSuite extends SparkFunSuite with
LocalSparkContext {
@@ -53,7 +56,9 @@ class SortMergeAsOfJoinScannerSuite extends SparkFunSuite
with LocalSparkContext
direction = Nearest,
inMemoryThreshold = 256,
sizeInBytesSpillThreshold = Long.MaxValue,
- spillThreshold = 256)
+ spillThreshold = 256,
+ useCursorScan = false,
+ numAsOfCursorTasks = new SQLMetric("sum"))
try {
Iterator.single((scanner.iterator.map(_.getInt(1)).toList,
count.get()))
} finally {
@@ -65,6 +70,254 @@ class SortMergeAsOfJoinScannerSuite extends SparkFunSuite
with LocalSparkContext
assert(matchedKeys == List(100))
assert(evaluations == 11, s"evaluated the as-of condition $evaluations
times")
}
+
+ test("cursor scan evaluates the as-of condition twice per left row") {
+ val leftKey = AttributeReference("leftKey", IntegerType)()
+ val rightKey = AttributeReference("rightKey", IntegerType)()
+ val leftValues = 5 to 95 by 10
+ val rightValues = 0 to 100 by 10
+ Seq(
+ (Backward, GreaterThanOrEqual(leftKey, rightKey), (0 to 90 by
10).toList),
+ (Forward, LessThanOrEqual(leftKey, rightKey), (10 to 100 by 10).toList)
+ ).foreach { case (direction, condition, expected) =>
+ withClue(s"$direction: ") {
+ val (bufferedKeys, _, bufferedTasks) = runScan(
+ leftValues, rightValues, leftKey, rightKey, condition, direction,
useCursorScan = false)
+ assert(bufferedKeys == expected)
+ assert(bufferedTasks == 0)
+
+ // Each left row passes one new right row and fails one, so 10 left
rows need 20
+ // evaluations. A scan that restarts at the first right row needs 65.
+ val (cursorKeys, evaluations, cursorTasks) = runScan(
+ leftValues, rightValues, leftKey, rightKey, condition, direction,
useCursorScan = true)
+ assert(cursorKeys == expected)
+ assert(evaluations == 20, s"evaluated the as-of condition $evaluations
times")
+ assert(cursorTasks == 1)
+ }
+ }
+ }
+
+ test("cursor scan keeps its best right row while it reads the next right
rows") {
+ // Tags grow and shrink, so the reused best-row buffer has to resize and
drop older bytes.
+ val longTag = "a tag that is longer than the tags around it"
+ val rightRows = Seq(10 -> "a", 20 -> longTag, 30 -> "bb", 40 -> null, 50
-> "c" * 30)
+ val leftValues = Seq(5, 15, 15, 25, 35, 45, 55)
+ Seq(
+ // Backward keeps its best row while it reads the first failing row
after it.
+ (Backward, Seq(None, Some(10 -> "a"), Some(10 -> "a"), Some(20 ->
longTag),
+ Some(30 -> "bb"), Some(40 -> null), Some(50 -> "c" * 30))),
+ // Forward reads past its best row, then reuses it for the second left
row 15.
+ (Forward, Seq(Some(10 -> "a"), Some(20 -> longTag), Some(20 -> longTag),
Some(30 -> "bb"),
+ Some(40 -> null), Some(50 -> "c" * 30), None))
+ ).foreach { case (direction, expected) =>
+ Seq(false, true).foreach { useCursorScan =>
+ withClue(s"$direction, cursor scan $useCursorScan: ") {
+ assert(runTagScan(leftValues, rightRows, direction, useCursorScan)
== expected)
+ }
+ }
+ }
+ }
+
+ test("cursor scan accepts each comparison of the sort keys in the join
direction, left " +
+ "side first") {
+ val l = AttributeReference("l", IntegerType)()
+ val r = AttributeReference("r", IntegerType)()
+ Seq(
+ Backward -> GreaterThanOrEqual(l, r),
+ Backward -> GreaterThan(l, r),
+ Forward -> LessThanOrEqual(l, r),
+ Forward -> LessThan(l, r)
+ ).foreach { case (direction, condition) =>
+ assert(supportsCursorScan(direction, condition, None, Seq(l), Seq(r)),
+ s"$direction $condition")
+ }
+
+ // An operand may be any expression, as long as the side sorts on that
same expression.
+ val longL = Cast(l, LongType)
+ val longR = AttributeReference("r", LongType)()
+ assert(supportsCursorScan(
+ Backward, GreaterThanOrEqual(longL, longR), None, Seq(longL),
Seq(longR)))
+ }
+
+ test("cursor scan accepts scalar sort keys except TIME, nanosecond
timestamps and " +
+ "user-defined types") {
+ def supportsType(dataType: DataType): Boolean = {
+ val l = AttributeReference("l", dataType)()
+ val r = AttributeReference("r", dataType)()
+ supportsCursorScan(Backward, GreaterThanOrEqual(l, r), None, Seq(l),
Seq(r))
+ }
+ Seq(
+ BooleanType, ByteType, ShortType, IntegerType, LongType, FloatType,
DoubleType,
+ DecimalType(38, 18), StringType, StringType("UTF8_LCASE"), BinaryType,
NullType, DateType,
+ TimestampType, TimestampNTZType, YearMonthIntervalType(),
DayTimeIntervalType()
+ ).foreach(dataType => assert(supportsType(dataType), dataType))
+ Seq(
+ StructType(Seq(StructField("a", IntegerType))), ArrayType(IntegerType),
TimeType(),
+ TimestampLTZNanosType(9), TimestampNTZNanosType(9), new YearUDT
+ ).foreach(dataType => assert(!supportsType(dataType), dataType))
+ }
+
+ test("cursor scan rejects conditions that need the buffered scan") {
+ val l = AttributeReference("l", IntegerType)()
+ val r = AttributeReference("r", IntegerType)()
+ val l2 = AttributeReference("l2", IntegerType)()
+ val r2 = AttributeReference("r2", IntegerType)()
+ val longR = AttributeReference("r", LongType)()
+ val lcaseL = AttributeReference("l", StringType("UTF8_LCASE"))()
+ val stringR = AttributeReference("r", StringType)()
+ val backward = GreaterThanOrEqual(l, r)
+ Seq(
+ "a residual condition" ->
+ supportsCursorScan(Backward, backward, Some(LessThan(l2, r2)), Seq(l),
Seq(r)),
+ "a nearest join" ->
+ supportsCursorScan(Nearest, backward, None, Seq(l), Seq(r)),
+ "a backward join with a forward comparison" ->
+ supportsCursorScan(Backward, LessThanOrEqual(l, r), None, Seq(l),
Seq(r)),
+ "a forward join with a backward comparison" ->
+ supportsCursorScan(Forward, GreaterThanOrEqual(l, r), None, Seq(l),
Seq(r)),
+ "swapped as-of columns" ->
+ supportsCursorScan(Backward, GreaterThanOrEqual(r, l), None, Seq(l),
Seq(r)),
+ // A NULL right key would end these before the left key, which the
cursor evaluates first.
+ "a backward condition with the right side first" ->
+ supportsCursorScan(Backward, LessThanOrEqual(r, l), None, Seq(l),
Seq(r)),
+ "a strict backward condition with the right side first" ->
+ supportsCursorScan(Backward, LessThan(r, l), None, Seq(l), Seq(r)),
+ "a forward condition with the right side first" ->
+ supportsCursorScan(Forward, GreaterThanOrEqual(r, l), None, Seq(l),
Seq(r)),
+ "a strict forward condition with the right side first" ->
+ supportsCursorScan(Forward, GreaterThan(r, l), None, Seq(l), Seq(r)),
+ "a tolerance" ->
+ supportsCursorScan(Backward, And(backward, GreaterThanOrEqual(r,
Subtract(l, Literal(1)))),
+ None, Seq(l), Seq(r)),
+ "a constant operand" ->
+ supportsCursorScan(Backward, GreaterThanOrEqual(l, Literal(1)), None,
Seq(l), Seq(r)),
+ // The left side sorts on l, but -l falls as l grows, so a cursor would
walk the wrong way.
+ "an operand that its side does not sort on" ->
+ supportsCursorScan(Backward, GreaterThanOrEqual(UnaryMinus(l), r),
None, Seq(l), Seq(r)),
+ "two sort keys per side" ->
+ supportsCursorScan(Backward, backward, None, Seq(l, l2), Seq(r, r2)),
+ "sort keys of different types" ->
+ supportsCursorScan(Backward, GreaterThanOrEqual(l, longR), None,
Seq(l), Seq(longR)),
+ "sort keys of different collations" ->
+ supportsCursorScan(Backward, GreaterThanOrEqual(lcaseL, stringR), None,
+ Seq(lcaseL), Seq(stringR))
+ ).foreach { case (name, supported) => assert(!supported, name) }
+ }
+
+ private def supportsCursorScan(
+ direction: AsOfJoinDirection,
+ asOfCondition: Expression,
+ residualCondition: Option[Expression],
+ leftSortExprs: Seq[Expression],
+ rightSortExprs: Seq[Expression]): Boolean =
+ SortMergeAsOfJoinScanner.supportsCursorScan(
+ direction, asOfCondition, residualCondition, leftSortExprs,
rightSortExprs)
+
+ /**
+ * Runs one scan with no equi-keys in a task. Returns the right key that
each left row matched,
+ * how many times the scan evaluated the as-of condition, and the cursor
scan task count.
+ */
+ private def runScan(
+ leftValues: Seq[Int],
+ rightValues: Seq[Int],
+ leftKey: AttributeReference,
+ rightKey: AttributeReference,
+ asOfCondition: Expression,
+ direction: AsOfJoinDirection,
+ useCursorScan: Boolean): (List[Int], Int, Long) = {
+ if (sc == null) {
+ sc = new SparkContext("local", "SortMergeAsOfJoinScannerSuite", new
SparkConf(false))
+ }
+ sc.parallelize(Seq(0), 1)
+ .mapPartitions { _ =>
+ val count = new AtomicInteger()
+ val numAsOfCursorTasks = new SQLMetric("sum")
+ val scanner = new SortMergeAsOfJoinScanner(
+ leftIter = leftValues.iterator.map(value => InternalRow(value)),
+ rightIter = rightValues.iterator.map(value => InternalRow(value)),
+ leftOutput = Seq(leftKey),
+ rightOutput = Seq(rightKey),
+ leftKeys = Nil,
+ rightKeys = Nil,
+ leftSortExprs = Seq(leftKey),
+ rightSortExprs = Seq(rightKey),
+ asOfCondition = CountedEvaluation(asOfCondition, count),
+ joinType = Inner,
+ residualCondition = None,
+ numOutputRows = new SQLMetric("sum"),
+ spillSize = new SQLMetric("sum"),
+ direction = direction,
+ inMemoryThreshold = 256,
+ sizeInBytesSpillThreshold = Long.MaxValue,
+ spillThreshold = 256,
+ useCursorScan = useCursorScan,
+ numAsOfCursorTasks = numAsOfCursorTasks)
+ try {
+ val matchedKeys = scanner.iterator.map(_.getInt(1)).toList
+ Iterator.single((matchedKeys, count.get(), numAsOfCursorTasks.value))
+ } finally {
+ scanner.close()
+ }
+ }.collect().head
+ }
+
+ /**
+ * Runs a LEFT OUTER scan of INT left keys against right rows of (INT key,
STRING tag), and
+ * returns the matched right row of each left row. The right input reuses
one row object, as
+ * many operators do, so the scan has to copy each row it keeps.
+ */
+ private def runTagScan(
+ leftValues: Seq[Int],
+ rightRows: Seq[(Int, String)],
+ direction: AsOfJoinDirection,
+ useCursorScan: Boolean): Seq[Option[(Int, String)]] = {
+ if (sc == null) {
+ sc = new SparkContext("local", "SortMergeAsOfJoinScannerSuite", new
SparkConf(false))
+ }
+ sc.parallelize(Seq(0), 1)
+ .mapPartitions { _ =>
+ val leftKey = AttributeReference("leftKey", IntegerType)()
+ val rightKey = AttributeReference("rightKey", IntegerType)()
+ val tag = AttributeReference("tag", StringType)()
+ val reusedRow = new GenericInternalRow(2)
+ val scanner = new SortMergeAsOfJoinScanner(
+ leftIter = leftValues.iterator.map(value => InternalRow(value)),
+ rightIter = rightRows.iterator.map { case (key, value) =>
+ reusedRow.update(0, key)
+ reusedRow.update(1, UTF8String.fromString(value))
+ reusedRow
+ },
+ leftOutput = Seq(leftKey),
+ rightOutput = Seq(rightKey, tag),
+ leftKeys = Nil,
+ rightKeys = Nil,
+ leftSortExprs = Seq(leftKey),
+ rightSortExprs = Seq(rightKey),
+ asOfCondition = direction match {
+ case Backward => GreaterThanOrEqual(leftKey, rightKey)
+ case _ => LessThanOrEqual(leftKey, rightKey)
+ },
+ joinType = LeftOuter,
+ residualCondition = None,
+ numOutputRows = new SQLMetric("sum"),
+ spillSize = new SQLMetric("sum"),
+ direction = direction,
+ inMemoryThreshold = 256,
+ sizeInBytesSpillThreshold = Long.MaxValue,
+ spillThreshold = 256,
+ useCursorScan = useCursorScan,
+ numAsOfCursorTasks = new SQLMetric("sum"))
+ try {
+ val matches = scanner.iterator.map { row =>
+ val tagValue = if (row.isNullAt(2)) null else row.getString(2)
+ if (row.isNullAt(1)) None else Some(row.getInt(1) -> tagValue)
+ }.toList
+ Iterator.single(matches)
+ } finally {
+ scanner.close()
+ }
+ }.collect().head
+ }
}
private[joins] case class CountedEvaluation(child: Expression, counter:
AtomicInteger)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]