This is an automated email from the ASF dual-hosted git repository.

cloud-fan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/master by this push:
     new 3aa4fe9e45b3 [SPARK-60744][SQL] Read the right side once with a cursor 
in the sort-merge ASOF join
3aa4fe9e45b3 is described below

commit 3aa4fe9e45b3b06bfb162c4820e24c5c01c2da2d
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
    
    ### What changes were proposed in this pull request?
    `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.
    
    ### Why are the changes needed?
    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
    
    ### Does this PR introduce _any_ user-facing change?
    No. Query results stay the same. The join node in the SQL UI shows one new 
metric.
    
    ### How was this patch tested?
    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.
    
    ### Was this patch authored or co-authored using generative AI tooling?
    Generated-by: Claude Code
    
    Closes #59957 from LukaZdravic/asof-jvm-cursor.
    
    Authored-by: Luka Zdravić <[email protected]>
    Signed-off-by: Wenchen Fan <[email protected]>
---
 .../org/apache/spark/sql/internal/SQLConf.scala    |  16 +
 .../benchmarks/AsOfJoinBenchmark-jdk25-results.txt |  21 +-
 sql/core/benchmarks/AsOfJoinBenchmark-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 2dd7e84fff56..e56f75915c3c 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()
@@ -9881,6 +9894,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-jdk25-results.txt 
b/sql/core/benchmarks/AsOfJoinBenchmark-jdk25-results.txt
index 0217e1788f30..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)                            39527          39582 
         77          0.0     3952677.7       1.0X
-Sort-merge AS-OF join                                        53             66 
         12          0.2        5296.1     746.3X
+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)                           38087          38181  
       132          0.0     3808724.6       1.0X
-Sort-merge AS-OF join                                      122            134  
        10          0.1       12168.4     313.0X
+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)                            26714          26883 
        239          0.0     2671359.5       1.0X
-Sort-merge AS-OF join                                       942            959 
         15          0.0       94248.7      28.3X
+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/benchmarks/AsOfJoinBenchmark-results.txt 
b/sql/core/benchmarks/AsOfJoinBenchmark-results.txt
index c943ffd6c19b..79b5d618365f 100644
--- a/sql/core/benchmarks/AsOfJoinBenchmark-results.txt
+++ b/sql/core/benchmarks/AsOfJoinBenchmark-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)                            39014          39335 
        454          0.0     3901384.8       1.0X
-Sort-merge AS-OF join                                        49             69 
         15          0.2        4941.2     789.6X
+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)                           40047          40121  
       104          0.0     4004730.2       1.0X
-Sort-merge AS-OF join                                      120            124  
         3          0.1       11967.3     334.6X
+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)                            23948          24018 
         99          0.0     2394812.4       1.0X
-Sort-merge AS-OF join                                       870            876 
          7          0.0       86954.2      27.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/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]

Reply via email to