feat: custom join scan planning (with simple execution) by mdashti · Pull Request #3930 · paradedb/paradedb

mdashti · 2026-01-15T09:45:51Z

Ticket(s) Closed

Closes #N/A

What

Implements the planning infrastructure for JoinScan, a PostgreSQL custom scan operator for JOIN queries with BM25 full-text search predicates. Includes a basic execution implementation to validate the planning logic.

Why

When joining tables where one side has a BM25 search predicate and the query has a LIMIT, PostgreSQL's native planner doesn't know that Tantivy can efficiently return top-N results (in score order). This PR lays the groundwork for optimized join execution by:

Detecting join opportunities where BM25 indexes can accelerate the query
Extracting and serializing all necessary planning information for execution
Integrating with PostgreSQL's cost model and pathkey system

How

Planning (main focus):

Detects INNER JOINs with LIMIT where at least one side has a BM25 predicate
Extracts equi-join keys with type information (INTEGER, TEXT, UUID, NUMERIC, composite)
Extracts join-level predicates (OR/AND/NOT spanning both tables) into a serializable expression tree
Declares pathkeys for ORDER BY score to eliminate Sort nodes
Integrates with PostgreSQL's custom scan infrastructure (create_custom_path, plan_custom_path)

Execution (simple/unoptimized):

Basic driving-side hash join to validate planning correctness
TopN executor for streaming Tantivy results with LIMIT
Hash table with work_mem limit and nested loop fallback
Visibility checking for stale ctids after UPDATE

Tests

pg_regress:added test cases covering planning scenarios (join types, key types, predicates, cross joins, ORDER BY score)
Concurrent updates: Validates visibility handling under concurrent UPDATEs
Property-based (qgen): Generated queries comparing JoinScan results against PostgreSQL's native joins

- Add CompositeKey enum to store actual key values (not just hashes) - Add KeyValue struct to store copied datum bytes for any PostgreSQL type - Add JoinKeyInfo struct for runtime key extraction info - Update JoinKeyPair to include type_oid, typlen, typbyval - Update extract_join_conditions to capture type info from Vars - Replace i64 hash key with CompositeKey for correct equality comparison - Remove CROSS_JOIN_KEY constant in favor of CompositeKey::CrossJoin - Add extract_composite_key and copy_datum_to_key_value helper functions - Support varlena (TEXT, BYTEA), cstring, and fixed-length types This fixes: - Issue 1: Hash table key type limitation (was i64 only) - Issue 2: Single join key only (now supports composite keys) - Issue 3: Cross-join magic key collision (now uses distinct enum variant)

- Add extract_non_equijoin_quals helper to filter restrictlist - Initialize join_qual_state and join_qual_econtext in begin_custom_scan - Only create qual state when has_other_conditions is true - Skip equi-join conditions (Var = Var) that are handled by hash lookup This fixes Issue 4: join_qual_state was never initialized, causing non-equijoin predicates to be silently ignored during execution.

Previously, if extract_join_level_conditions failed, it would silently return None. Now it logs a debug1 message to help with troubleshooting why JoinScan wasn't proposed for a particular query.

These methods were never called - PostgreSQL's Limit node handles limiting. Remove the dead code rather than keeping it with #[allow(dead_code)].

Factor out the join-level predicate evaluation logic into a reusable helper method used by both hash join and nested loop execution paths. This eliminates ~40 lines of duplicated code.

stuhood

Thanks Moe!

This is awesome work, but it would be great to simplify/restrict it before landing.

mdashti

@stuhood Thanks for the review.

stuhood

Thanks a lot Moe!

Let's get it in and iterate.

) ## What This change swaps from the hash join execution method which was added in #3930 to explicitly using DataFusion's hash join. Future changes will introduce DataFusion's optimizer (by producing logical nodes rather than physical nodes) so that it can take advantage of the sorted segments which will be provided by #3988. ## Why As described in #3930, the implementation there was explicitly temporary. We will be leaning in to using DataFusion to execute columnar joins. ## Tests The regression tests and proptests pass, with one exception: numeric columns cannot safely be pulled up from fast fields currently (see #2968). Additionally, improved `qgen`'s handling of panics.

stuhood and others added 8 commits January 12, 2026 08:23

Add an initial joinscan skeleton.

3713358

Added join planning

d1ed42e

Added simple join exec v1

e92607e

Added simple join exec v2

8bd7b53

Added simple join exec v3

21c3048

Added simple join exec v4

c276848

nitz

5714342

nitz

971194c

mdashti changed the base branch from main to stuhood.join-scan-skeleton January 15, 2026 09:46

mdashti added the Do Not Cherry Pick PR should not be cherry-picked to other branches label Jan 15, 2026

mdashti added 20 commits January 14, 2026 23:52

added more tests

8e049e7

avoid flakiness

f46f725

handle cross joins

90c51eb

handle join-level search operator conditions

ec32b85

handle join-level search operator conditions - p2

b95b276

nitz

af528f0

nitz.

0098be4

Fixed ctid matching

26b2e8e

visibilit bug

4bb213e

Fixed vis check.

db2f773

Added comments.

3a6b978

Refactoring.

4fb0097

nitz.

3f6266e

reuse bms_iter

9fe6f78

code reuse.

a2527de

refactoring

83bb8da

refactoring

2c8fbe7

refactoring

51e63f0

mdashti added 7 commits January 20, 2026 22:37

fix(joinscan): add debug logging when predicate extraction fails

5ebfdcb

Previously, if extract_join_level_conditions failed, it would silently return None. Now it logs a debug1 message to help with troubleshooting why JoinScan wasn't proposed for a particular query.

refactor(joinscan): remove unused limit() and reached_limit() methods

a0ca73f

These methods were never called - PostgreSQL's Limit node handles limiting. Remove the dead code rather than keeping it with #[allow(dead_code)].

refactor(joinscan): extract evaluate_join_level_predicate helper

7e03b6d

Factor out the join-level predicate evaluation logic into a reusable helper method used by both hash join and nested loop execution paths. This eliminates ~40 lines of duplicated code.

nitz.

42686ca

Added docs.

7c0953a

imprpved exec impl: fewer clones on hot path

bc5b52d

nitz.

0d25c55

stuhood reviewed Jan 21, 2026

View reviewed changes

mdashti added 7 commits January 21, 2026 10:58

Apply PR comments

ed65d3b

Rename to MultiTablePredicate + nitz

74c6e5e

Apply PR comments: improve fast-field checking

9a99fdf

All conditions should be fast fields.

9d85efd

ORDER BY column should also be a fast field.

e3a9123

Fixed the FF requirement logic

89945a4

Limited qgen to 2way joins

fe31277

mdashti commented Jan 22, 2026

View reviewed changes

mdashti requested a review from stuhood January 22, 2026 01:21

stuhood approved these changes Jan 22, 2026

View reviewed changes

Merge branch 'main' into moe/join-planning

51461c0

mdashti force-pushed the moe/join-planning branch from 59eacbe to 51461c0 Compare January 22, 2026 17:33

mdashti added 4 commits January 22, 2026 09:45

All join participants and their fields should be indexed/fast.

1563eab

Removed heap scan.

5b84ea6

Applied PR comments.

ae027f6

Upated tests

8ffba0c

mdashti merged commit b47b50b into main Jan 22, 2026
18 checks passed

mdashti deleted the moe/join-planning branch January 22, 2026 21:16

This was referenced Jan 23, 2026

JOINs: M1: Implement planning of the joinscan #3985

Closed

Implement JOIN pushdown #2997

Closed

stuhood mentioned this pull request Jan 27, 2026

chore: Swap join scan execution to an unoptimized DataFusion plan #4003

Merged

Uh oh!

Conversation

mdashti commented Jan 15, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Ticket(s) Closed

What

Why

How

Tests

Uh oh!

stuhood left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mdashti left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

stuhood left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

mdashti commented Jan 15, 2026 •

edited

Loading