Experimental adaptive adjacent probing for DuckDB ASOF joins — patch, workloads, and honest test evidence

00_README.md

Adaptive adjacent probing for DuckDB ASOF joins

This experimental DuckDB patch tries a short adjacent scan before falling back to DuckDB's existing exponential-plus-binary search.

The idea

An ASOF join answers questions such as:

• Which market quote was active when a trade happened?
• Which exchange rate was current when a payment arrived?
• Which machine configuration was active when a sensor reading was recorded?

For ordered, dense time-series data, consecutive left-side timestamps often match consecutive or nearby right-side rows. The unmodified implementation performs a logarithmic search for each match. This patch remembers whether the previous match advanced by at most four rows. If so, the next probe checks up to four adjacent rows first.

If the correct boundary is not found within those four checks, execution falls back to the original exponential-plus-binary search. The shortcut therefore targets dense local movement without removing the general search path.

What changed

The patch modifies only:

src/execution/operator/join/physical_asof_join.cpp

It adds task-local state named adjacent_probe_likely, a four-row adjacent-probe limit, exact comparisons on every adjacent step, and the unchanged logarithmic fallback.

Base DuckDB commit:

5366dc3925ce0f981c2110cf4bf8e39fa1dd6fde

Patch SHA-256:

c7aef68b0974162830f0ef8d16d60ad009fe719a58b12e814f0e110517921c45

How it was tested

The candidate was built in Release mode on arm64 macOS with Apple Clang 21 and CMake 3.31.3. The candidate binary SHA-256 was:

1f7a086c0c65f83a7760a08990a330df105f2b040710467c69d1bb1e8c936d55

Correctness checks included:

• Six frozen evaluator cases.
• Ten semantic/schema cases at one thread and four threads.
• A direct baseline-versus-candidate ASOF differential covering >=, >, <=, and <, duplicate timestamps, NULLs, equality prefixes, dense probes, and sparse probes.
• Exact output hashes for every timed workload.

Timing used two warm-up pairs followed by nine paired baseline/candidate trials. Each timed block executed its SQL workload ten times. Trial order was varied using fixed seeds. The primary exploratory metric was the median of the nine within-pair baseline_time / candidate_time ratios.

Workload	Rows/pattern	Paired median	Approx. runtime reduction	Candidate wins
Dense contiguous	1M left, 1M right; adjacent timestamps	1.1443x	12.6%	8/9
Sparse	1K left, 1M right; jumps of 1,000	1.0068x	0.7%	5/9
Held-out mixed	Dense runs separated by large jumps	1.0192x	1.9%	8/9
Held-out bursty	Mostly adjacent with medium/large gaps	1.0058x	0.6%	5/9

Honest conclusion

This is a promising narrow result, not a production-ready or general DuckDB speedup.

The dense synthetic workload showed a strong exploratory improvement, but the predeclared held-out promotion rule required at least 1.05x on both held-out workloads, or 1.10x on one with no regression on the other. The mixed and bursty workloads did not pass that gate. All timings above are therefore non-claim-bearing exploratory measurements.

The next useful test is a clean, quiet-machine benchmark on a representative trade/quote or other dense temporal workload, followed by Linux and customer-hardware validation. Do not infer customer savings from these synthetic results.

Files

• 01_adaptive_asof.patch — exact source patch with inline comments.
• 02_workloads.sql — the four performance workloads and the differential correctness workload.
• 03_results.json — compact evidence summary and claim limits.

Prepared and signed by GPT on 2026-08-13.

DuckDB is licensed under the MIT License. This experimental patch is provided for evaluation without warranty.

01_adaptive_asof.patch

diff --git a/src/execution/operator/join/physical_asof_join.cpp b/src/execution/operator/join/physical_asof_join.cpp
index 95f3692..b0168a7 100644
--- a/src/execution/operator/join/physical_asof_join.cpp
+++ b/src/execution/operator/join/physical_asof_join.cpp
@@ -882,6 +882,8 @@ public:
 	//	Predicate evaluation
 	idx_t lhs_match_count;
 	bool fetch_next_left;
+	//! Try a short adjacent scan only after the previous RHS advance was small.
+	bool adjacent_probe_likely = false;
 
 	SortKeyPrefixComparison prefix;
 };
@@ -970,6 +972,7 @@ void AsOfProbeBuffer::BeginLeftScan(TaskPtr task_p) {
 	// We are only probing the corresponding right side bin, which may be empty
 	// If it is empty, we leave the iterator as null so we can emit left matches
 	right_pos = 0;
+	adjacent_probe_likely = false;
 	if (right_group) {
 		right_outer = &asof_hash_group->right_outer;
 		if (right_group && right_group->Count()) {
@@ -1052,6 +1055,11 @@ void AsOfProbeBuffer::ResolveJoin(idx_t *matches) {
 
 	const auto count = lhs_scanner->NextSize();
 	const auto left_base = lhs_scanner->Scanned();
+	const auto right_count = right_group->Count();
+	// Dense time-series probes often advance one or two RHS rows. Remember that
+	// local stride, but abandon the adjacent path after a sparse jump so later
+	// probes retain the original logarithmic gallop/binary search.
+	static constexpr idx_t ADJACENT_PROBE_LIMIT = 4;
 	//	Searching for right <= left
 	for (idx_t i = 0; i < count; ++i) {
 		//	If right > left, then there is no match
@@ -1060,33 +1068,53 @@ void AsOfProbeBuffer::ResolveJoin(idx_t *matches) {
 			continue;
 		}
 
-		// Exponential search forward for a non-matching value using radix iterators
-		// (We use exponential search to avoid thrashing the block manager on large probes)
-		idx_t bound = 1;
-		idx_t begin = right_pos;
-		while (begin + bound < right_group->Count()) {
-			if (Compare(right_key[begin + bound], left_key[left_pos], strict)) {
-				//	If right <= left, jump ahead
-				bound *= 2;
-			} else {
-				break;
+		const auto search_begin = right_pos;
+		idx_t first = right_pos;
+		bool adjacent_probe_found_boundary = false;
+		if (adjacent_probe_likely) {
+			idx_t adjacent_steps = 0;
+			while (right_pos + 1 < right_count && adjacent_steps < ADJACENT_PROBE_LIMIT) {
+				if (!Compare(right_key[right_pos + 1], left_key[left_pos], strict)) {
+					adjacent_probe_found_boundary = true;
+					break;
+				}
+				++right_pos;
+				++adjacent_steps;
 			}
+			adjacent_probe_found_boundary |= right_pos + 1 == right_count;
 		}
+		if (adjacent_probe_found_boundary) {
+			first = right_pos;
+		} else {
+			// Exponential search forward for a non-matching value using radix iterators
+			// (We use exponential search to avoid thrashing the block manager on large probes)
+			idx_t bound = 1;
+			idx_t begin = right_pos;
+			while (begin + bound < right_count) {
+				if (Compare(right_key[begin + bound], left_key[left_pos], strict)) {
+					//	If right <= left, jump ahead
+					bound *= 2;
+				} else {
+					break;
+				}
+			}
 
-		//	Binary search for the first non-matching value using radix iterators
-		//	The previous value (which we know exists) is the match
-		auto first = begin + bound / 2;
-		auto last = MinValue<idx_t>(begin + bound, right_group->Count());
-		while (first < last) {
-			const auto mid = first + (last - first) / 2;
-			if (Compare(right_key[mid], left_key[left_pos], strict)) {
-				//	If right <= left, new lower bound
-				first = mid + 1;
-			} else {
-				last = mid;
+			//	Binary search for the first non-matching value using radix iterators
+			//	The previous value (which we know exists) is the match
+			first = begin + bound / 2;
+			auto last = MinValue<idx_t>(begin + bound, right_count);
+			while (first < last) {
+				const auto mid = first + (last - first) / 2;
+				if (Compare(right_key[mid], left_key[left_pos], strict)) {
+					//	If right <= left, new lower bound
+					first = mid + 1;
+				} else {
+					last = mid;
+				}
 			}
+			right_pos = --first;
 		}
-		right_pos = --first;
+		adjacent_probe_likely = right_pos - search_begin <= ADJACENT_PROBE_LIMIT;
 
 		//	Check partitions for strict equality
 		if (!prefix.columns.empty()) {

02_workloads.sql

-- H7b adaptive ASOF experimental workloads.
-- Run each section independently against an unmodified baseline binary and
-- a candidate binary built from 01_adaptive_asof.patch.

-- 1. Dense contiguous: the next match is normally one adjacent RHS row away.
WITH lhs AS (
    SELECT i::BIGINT AS ts
    FROM range(0, 1000000) AS t(i)
), rhs AS (
    SELECT i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 1000000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.ts >= rhs.ts;

-- 2. Sparse: consecutive probes jump 1,000 RHS rows.
WITH lhs AS (
    SELECT (i * 1000)::BIGINT AS ts
    FROM range(0, 1000) AS t(i)
), rhs AS (
    SELECT i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 1000000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.ts >= rhs.ts;

-- 3. Held-out mixed: long dense runs separated by large monotone jumps.
WITH lhs AS (
    SELECT ((i // 1000) * 5000 + (i % 1000))::BIGINT AS ts
    FROM range(0, 200000) AS t(i)
), rhs AS (
    SELECT i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 1000000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.ts >= rhs.ts;

-- 4. Held-out bursty: mostly adjacent probes with deterministic gaps.
WITH steps AS (
    SELECT i,
           CASE
               WHEN i % 1024 = 0 THEN 1000
               WHEN i % 32 = 0 THEN 16
               ELSE 1
           END::BIGINT AS step
    FROM range(0, 200000) AS t(i)
), lhs AS (
    SELECT SUM(step) OVER (
               ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
           )::BIGINT AS ts
    FROM steps
), rhs AS (
    SELECT i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 600000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.ts >= rhs.ts;

-- 5. Differential correctness: boundary directions, strictness, duplicates,
-- NULL values, equality prefixes, dense probes, and sparse probes.
PRAGMA threads=1;

CREATE TABLE l(id INTEGER, ts INTEGER);
CREATE TABLE r(id INTEGER, ts INTEGER, v VARCHAR);
INSERT INTO l VALUES
    (1, NULL), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 10),
    (2, 1), (2, 5), (2, 100);
INSERT INTO r VALUES
    (1, NULL, 'n'), (1, 0, 'a'), (1, 1, 'b1'), (1, 1, 'b2'),
    (1, 3, 'c'), (1, 9, 'd'), (2, 0, 'e'), (2, 4, 'f'), (2, 99, 'g');

SELECT 'ge' AS tag, l.id, l.ts, r.ts, r.v
FROM l ASOF LEFT JOIN r ON l.id = r.id AND l.ts >= r.ts
ORDER BY l.id, l.ts NULLS FIRST, r.v;

SELECT 'gt' AS tag, l.id, l.ts, r.ts, r.v
FROM l ASOF LEFT JOIN r ON l.id = r.id AND l.ts > r.ts
ORDER BY l.id, l.ts NULLS FIRST, r.v;

SELECT 'le' AS tag, l.id, l.ts, r.ts, r.v
FROM l ASOF LEFT JOIN r ON l.id = r.id AND l.ts <= r.ts
ORDER BY l.id, l.ts NULLS FIRST, r.v;

SELECT 'lt' AS tag, l.id, l.ts, r.ts, r.v
FROM l ASOF LEFT JOIN r ON l.id = r.id AND l.ts < r.ts
ORDER BY l.id, l.ts NULLS FIRST, r.v;

WITH lhs AS (
    SELECT (i % 31)::INTEGER AS id, i::BIGINT AS ts
    FROM range(0, 200000) AS t(i)
), rhs AS (
    SELECT (i % 31)::INTEGER AS id, i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 200000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.id = rhs.id AND lhs.ts >= rhs.ts;

WITH lhs AS (
    SELECT (i * 1000)::BIGINT AS ts
    FROM range(0, 1000) AS t(i)
), rhs AS (
    SELECT i::BIGINT AS ts, i::HUGEINT AS v
    FROM range(0, 1000000) AS t(i)
)
SELECT COUNT(*)::BIGINT AS n, SUM(rhs.v)::HUGEINT AS total
FROM lhs ASOF LEFT JOIN rhs ON lhs.ts >= rhs.ts;

03_results.json

{
  "schema": 1,
  "candidate": "H7b adaptive adjacent ASOF probe",
  "prepared_by": "GPT",
  "date": "2026-08-13",
  "duckdb_base_commit": "5366dc3925ce0f981c2110cf4bf8e39fa1dd6fde",
  "patch_sha256": "c7aef68b0974162830f0ef8d16d60ad009fe719a58b12e814f0e110517921c45",
  "candidate_binary_sha256": "1f7a086c0c65f83a7760a08990a330df105f2b040710467c69d1bb1e8c936d55",
  "platform": "macOS 26.5 arm64",
  "toolchain": {
    "compiler": "Apple Clang 21.0.0",
    "cmake": "3.31.3",
    "build_type": "Release",
    "build_parallelism": 2
  },
  "correctness": {
    "frozen_evaluator_cases": 6,
    "semantic_cases_threads_1": 10,
    "semantic_cases_threads_4": 10,
    "direct_asof_differential": "PASS",
    "timed_workload_output_hashes": "EXACT_MATCH"
  },
  "timing_method": {
    "warmup_pairs": 2,
    "timed_pairs": 9,
    "inner_iterations_per_block": 10,
    "metric": "median of within-pair baseline_seconds / candidate_seconds",
    "claim_status": "NON_CLAIM_BEARING_EXPLORATORY"
  },
  "results": [
    {
      "workload": "dense_contiguous",
      "paired_median_speedup": 1.1442629277827399,
      "approx_runtime_reduction_percent": 12.607498180279686,
      "candidate_wins": 8,
      "pairs": 9,
      "exact_output_hash_match": true
    },
    {
      "workload": "sparse",
      "paired_median_speedup": 1.0068106901530702,
      "approx_runtime_reduction_percent": 0.6764614997695428,
      "candidate_wins": 5,
      "pairs": 9,
      "exact_output_hash_match": true
    },
    {
      "workload": "heldout_mixed",
      "paired_median_speedup": 1.0191565858359493,
      "approx_runtime_reduction_percent": 1.8796508865183692,
      "candidate_wins": 8,
      "pairs": 9,
      "exact_output_hash_match": true
    },
    {
      "workload": "heldout_bursty",
      "paired_median_speedup": 1.0057696714013165,
      "approx_runtime_reduction_percent": 0.5736573257343003,
      "candidate_wins": 5,
      "pairs": 9,
      "exact_output_hash_match": true
    }
  ],
  "predeclared_promotion_gate": "At least 1.05x on both held-out workloads, or at least 1.10x on one and no regression below 1.00x on the other",
  "promotion_disposition": "DOES_NOT_ADVANCE",
  "claim_limit": "Promising on dense contiguous synthetic ASOF joins only. Not a general DuckDB speedup, production result, customer saving, or commercial claim."
}