Module join_enumerator 

DPccp join enumeration following Moerkotte and Neumann (2006).

Enumerates connected-subgraph / complement pairs of the JoinGraph in canonical order: each connected subgraph S is formed by extending a smaller connected subgraph with an adjacent vertex whose index exceeds min(S), ensuring each subgraph is emitted exactly once. Complexity is O(3^n) over the relation count; far below the n! of exhaustive enumeration. Falls back to a greedy O(n^3) heuristic when the graph has more than MAX_DP_RELATIONS relations.

Internally relation subsets are encoded as u64 bitmasks for O(1) hash-table lookup and set operations. Equijoins are costed as hash joins because that is the physical strategy available to the SQL execution pipeline. An index-join cost must never influence ordering unless the planner can prove that a compatible physical index join is executable.

Returns a JoinPlan tree where each Join node records the (left, right, edge, cost, cardinality) tuple. Disconnected join graphs are handled by solving each connected component independently and cross-joining them in cardinality-ascending order.

Structs

DPccp

DPccp join-order optimiser. Public so callers that need the cancellation-friendly stages (optimize, find_connected_components) can drive them directly.

JoinPlan

A (sub)plan for joining a set of relations. relations is the bitmask of relation indices in the plan; cardinality and cost are the running estimates, and left / right / join_edge are populated for internal nodes.

Constants

MAX_DP_RELATIONS

Beyond this count, exact enumeration switches to the greedy fallback.

Functions

enumerate_dpccp

Run DPccp over graph and return the cheapest join plan over the full relation set. Returns None for an empty graph.

enumerate_dpccp_with_cost_estimator

Run DPccp with an explicit physical cost estimator.