Skip to content

Commit 44544cd

Browse files
perf: Optimize range partitioning across multi-key and asymmetric joins (#6342)
## What Coordinates range partitioning across MPP joins, prioritizing large relations and multi-key bridge tables, enables 1-sided asymmetric range adaptation, and incorporates upstream DataFusion improvements. ## Why - Tables declaring multiple partition keys (e.g. `user_id,topic_id`) could previously be claimed by small dimension joins during bottom-up traversal, locking them out of 0-shuffle co-partitioning with large fact tables. - Joining partitioned tables with unpartitioned ones can keep the larger table local (0 shuffles) and adapt only the smaller partner (1 shuffle), rather than forcing a 2-sided hash shuffle. - Tracked upstream as apache/datafusion#25302 - `JoinSelection` converts partitioned joins to `CollectLeft` (broadcast) based on row/byte thresholds alone, ignoring that physically co-partitioned inputs run task-locally with zero network cost. - Tracked upstream as apache/datafusion#25301 - Round-robin repartitioning added redundant partitions and stages in our single-threaded task model. ## How - `RangePartitioningRule`: Ranks candidate join edges globally by data volume (`min(left_rows, right_rows)`). Stamps asymmetric anchors only when strictly larger than their partner or when the partner is already committed to another key. - `RangeCoPartitionedJoinRule`: Placed before `EnsureRequirements` to flip `CollectLeft` back to `Partitioned` for range co-partitioned inputs and peel unnecessary repartition nodes. - Session config: Disabled `optimizer.enable_round_robin_repartition` in planner and worker sessions. ## Tests - Added `pg_search/tests/pg_regress/sql/mpp_range_partitioning.sql` exercising 2-table co-partitioning, multi-key bridge joins, aggregations, and asymmetric joins. - Benchmarks show up to 70% improvement on some range partitioned joins. --------- Co-authored-by: paradedb-github-app[bot] <282009505+paradedb-github-app[bot]@users.noreply.github.com>
1 parent 4a5c755 commit 44544cd

37 files changed

Lines changed: 1936 additions & 600 deletions

‎Cargo.lock‎

Lines changed: 71 additions & 103 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
header: performance
3+
---
4+
5+
Optimized range-partitioned joins to prioritize partitioning on larger tables and align asymmetric join streams, minimizing cross-worker shuffles.

‎docs/reference/configuration.mdx‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -28,17 +28,17 @@ ALTER ROLE app_user SET paradedb.vector_cluster_max_probe = 0.05;
2828

2929
These settings control whether ParadeDB proposes custom plans for eligible queries.
3030

31-
| Setting | Default | Context | Description |
32-
| ---------------------------------------------- | ------------- | ------- | --------------------------------------------------------------------------------------------------- |
33-
| `paradedb.enable_custom_scan` | `on` | user | Enables ParadeDB's base custom scan, which replaces table scans with ParadeDB index scans. |
34-
| `paradedb.enable_aggregate_custom_scan` | `on` | user | Enables the aggregate custom scan for eligible `pdb.agg` and `GROUP BY` queries. |
35-
| `paradedb.enable_join_custom_scan` | `on` | user | Enables the join custom scan, which pushes eligible joins into the ParadeDB executor. |
36-
| `paradedb.enable_custom_scan_without_operator` | `off` | user | Allows custom scans without a ParadeDB search operator when the whole `WHERE` clause can push down. |
37-
| `paradedb.enable_filter_pushdown` | `on` | user | Allows non-indexed predicates to use heap filtering after the ParadeDB scan. |
38-
| `paradedb.enable_range_partitioned_join` | `off` | user | Enables range co-partitioned joins for indexes configured with `partition_by`. |
39-
| `paradedb.enable_heuristic_selectivity` | `on` | user | Uses cheap planner selectivity estimates for expensive fuzzy, regex, and range query shapes. |
40-
| `paradedb.per_tuple_cost` | `100000000.0` | user | Planner cost multiplier that discourages using ParadeDB operators outside a supported index plan. |
41-
| `paradedb.explain_recursive_estimates` | `off` | user | Shows recursive document-count estimates in `EXPLAIN VERBOSE`; intended for debugging. |
31+
| Setting | Default | Context | Description |
32+
| ---------------------------------------------- | ------------- | ------- | -------------------------------------------------------------------------------------------------------------------------- |
33+
| `paradedb.enable_custom_scan` | `on` | user | Enables ParadeDB's base custom scan, which replaces table scans with ParadeDB index scans. |
34+
| `paradedb.enable_aggregate_custom_scan` | `on` | user | Enables the aggregate custom scan for eligible `pdb.agg` and `GROUP BY` queries. |
35+
| `paradedb.enable_join_custom_scan` | `on` | user | Enables the join custom scan, which pushes eligible joins into the ParadeDB executor. |
36+
| `paradedb.enable_custom_scan_without_operator` | `off` | user | Allows custom scans without a ParadeDB search operator when the whole `WHERE` clause can push down. |
37+
| `paradedb.enable_filter_pushdown` | `on` | user | Allows non-indexed predicates to use heap filtering after the ParadeDB scan. |
38+
| `paradedb.enable_range_partitioned_join` | `off` | user | Enables range co-partitioned joins and asymmetric range alignment for MPP joins on indexes configured with `partition_by`. |
39+
| `paradedb.enable_heuristic_selectivity` | `on` | user | Uses cheap planner selectivity estimates for expensive fuzzy, regex, and range query shapes. |
40+
| `paradedb.per_tuple_cost` | `100000000.0` | user | Planner cost multiplier that discourages using ParadeDB operators outside a supported index plan. |
41+
| `paradedb.explain_recursive_estimates` | `off` | user | Shows recursive document-count estimates in `EXPLAIN VERBOSE`; intended for debugging. |
4242

4343
## Top K
4444

‎nix/pg_search.nix‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@ buildPgrxExtension (finalAttrs: {
6565
# If maintainers forget to do so, Nix will throw an error message that begins
6666
# like this and then provides the correct new hash:
6767
# error: hash mismatch in fixed-output derivation '...'
68-
cargoHash = "sha256-J8l7PXqvhlKeFsC7kQYOlYtBkbbrwvxs3zIhoCyLe4o=";
68+
cargoHash = "sha256-HvBIZG73TPSHNhbjRVef3q+iEWo/xXwj/8eWJTE+pSE=";
6969

7070
inherit cargo-pgrx postgresql;
7171

‎pg_search/Cargo.toml‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -93,9 +93,9 @@ tokio-util = "0.7"
9393
bytes = { version = "1", features = ["serde"] }
9494
# Here and the equivalent in our datafusion-distributed fork will need to be updated in sync so that
9595
# both point to the same datafusion ref.
96-
datafusion = { version = "55.0.0", default-features = false }
97-
datafusion-proto = { version = "55.0.0", default-features = false }
98-
datafusion-distributed = { git = "https://github.com/paradedb/datafusion-distributed", tag = "snapshot-main-2026-08-20-204632", default-features = false }
96+
datafusion = { git = "https://github.com/paradedb/datafusion.git", branch = "paradedb.branch-55", default-features = false }
97+
datafusion-proto = { git = "https://github.com/paradedb/datafusion.git", branch = "paradedb.branch-55", default-features = false }
98+
datafusion-distributed = { git = "https://github.com/paradedb/datafusion-distributed.git", tag = "snapshot-main-2026-09-19-045947", default-features = false }
9999
futures = "0.3"
100100
async-stream = "0.3.6"
101101
prost = "0.14.3"

‎pg_search/src/gucs.rs‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,6 +249,15 @@ static HASH_JOIN_INLIST_PUSHDOWN_MAX_SIZE: GucSetting<i32> =
249249
static HASH_JOIN_INLIST_PUSHDOWN_MAX_DISTINCT_VALUES: GucSetting<i32> =
250250
GucSetting::<i32>::new(20_000);
251251

252+
/// Row count threshold below which DataFusion converts a partitioned HashJoinExec
253+
/// to CollectLeft (broadcast). Set to 0 to force Partitioned mode.
254+
static HASH_JOIN_SINGLE_PARTITION_THRESHOLD_ROWS: GucSetting<i32> =
255+
GucSetting::<i32>::new(128 * 1024);
256+
257+
/// Byte size threshold below which DataFusion converts a partitioned HashJoinExec
258+
/// to CollectLeft (broadcast). Set to 0 to force Partitioned mode.
259+
static HASH_JOIN_SINGLE_PARTITION_THRESHOLD: GucSetting<i32> = GucSetting::<i32>::new(1024 * 1024);
260+
252261
/// Kill-switch for galloping execution of `FastFieldTermSetQuery` on
253262
/// sorted segments. When `false`, the planner never returns the gallop
254263
/// strategy regardless of density, and pushed-down InList filters fall
@@ -684,6 +693,28 @@ pub fn init() {
684693
GucFlags::default(),
685694
);
686695

696+
GucRegistry::define_int_guc(
697+
c"paradedb.hash_join_single_partition_threshold_rows",
698+
c"Row count threshold below which DataFusion converts partitioned hash joins to CollectLeft (broadcast). Set to 0 to force Partitioned mode.",
699+
c"Row count threshold below which DataFusion converts partitioned hash joins to CollectLeft (broadcast). Set to 0 to force Partitioned mode.",
700+
&HASH_JOIN_SINGLE_PARTITION_THRESHOLD_ROWS,
701+
0,
702+
i32::MAX,
703+
GucContext::Userset,
704+
GucFlags::default(),
705+
);
706+
707+
GucRegistry::define_int_guc(
708+
c"paradedb.hash_join_single_partition_threshold",
709+
c"Byte size threshold below which DataFusion converts partitioned hash joins to CollectLeft (broadcast). Set to 0 to force Partitioned mode.",
710+
c"Byte size threshold below which DataFusion converts partitioned hash joins to CollectLeft (broadcast). Set to 0 to force Partitioned mode.",
711+
&HASH_JOIN_SINGLE_PARTITION_THRESHOLD,
712+
0,
713+
i32::MAX,
714+
GucContext::Userset,
715+
GucFlags::default(),
716+
);
717+
687718
// TermSet strategy density thresholds (issue #4895). The kill-switch
688719
// (paradedb.term_set_gallop_enabled) is the safety override if the
689720
// gallop optimization regresses unexpectedly; the three density
@@ -1056,6 +1087,14 @@ pub fn hash_join_inlist_pushdown_max_distinct_values() -> i32 {
10561087
HASH_JOIN_INLIST_PUSHDOWN_MAX_DISTINCT_VALUES.get()
10571088
}
10581089

1090+
pub fn hash_join_single_partition_threshold_rows() -> i32 {
1091+
HASH_JOIN_SINGLE_PARTITION_THRESHOLD_ROWS.get()
1092+
}
1093+
1094+
pub fn hash_join_single_partition_threshold() -> i32 {
1095+
HASH_JOIN_SINGLE_PARTITION_THRESHOLD.get()
1096+
}
1097+
10591098
pub fn term_set_gallop_enabled() -> bool {
10601099
TERM_SET_GALLOP_ENABLED.get()
10611100
}

‎pg_search/src/postgres/customscan/aggregatescan/datafusion_exec.rs‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1073,7 +1073,10 @@ async fn build_source_df(
10731073
// MPP-aware provider setup. Every source gets its segments sliced across PG
10741074
// parallel workers via `parallel_state.checkout_segment_for_source(plan_position)`
10751075
// when this is an MPP plan.
1076-
let source_idx = mpp_manifests.map(|_| plan_position);
1076+
let is_mpp = mpp_manifests.is_some()
1077+
|| (crate::postgres::customscan::mpp::glue::mpp_is_active()
1078+
&& ctx.state().config().target_partitions() > 1);
1079+
let source_idx = is_mpp.then_some(plan_position);
10771080
let mut provider = PgSearchTableProvider::new(scan_info, fields.clone(), source_idx);
10781081
// The leader claims segments out of the DSM pool the same manifests populate, so its own
10791082
// reader is built from the source's manifest. This plan never crosses the codec that

‎pg_search/src/postgres/customscan/aggregatescan/mod.rs‎

Lines changed: 4 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,6 @@ use crate::postgres::catalog::is_ltree_oid;
4848
use crate::postgres::customscan::datafusion::explain::{
4949
explain_physical_plan, get_plan_with_merged_metrics,
5050
};
51-
use datafusion::execution::TaskContext;
5251
use datafusion::physical_plan::ExecutionPlan;
5352

5453
use datafusion_distributed::{DistributedExt, DistributedTaskContext};
@@ -107,7 +106,9 @@ use crate::postgres::customscan::exec::{
107106
};
108107
use crate::postgres::customscan::explainer::Explainer;
109108
use crate::postgres::customscan::hook::query_has_paradedb_agg;
110-
use crate::postgres::customscan::joinscan::scan_state::{build_physical_plan, build_task_context};
109+
use crate::postgres::customscan::joinscan::scan_state::{
110+
build_physical_plan, build_task_context, clone_task_context_with_config,
111+
};
111112
use crate::postgres::customscan::projections::{create_placeholder_targetlist, placeholder_procid};
112113
use crate::postgres::customscan::solve_expr::SolvePostgresExpressions;
113114
use crate::postgres::customscan::{CreateUpperPathsHookArgs, CustomScan, range_table};
@@ -2062,11 +2063,7 @@ impl AggregateScan {
20622063
task_count: 1,
20632064
},
20642065
));
2065-
Arc::new(
2066-
TaskContext::default()
2067-
.with_session_config(cfg)
2068-
.with_runtime(task_ctx.runtime_env().clone()),
2069-
)
2066+
Arc::new(clone_task_context_with_config(&task_ctx, cfg))
20702067
};
20712068
let stream = {
20722069
let _guard = runtime.enter();

‎pg_search/src/postgres/customscan/datafusion/cardinality_agg.rs‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -46,11 +46,6 @@ pub fn tantivy_cardinality_udaf() -> Arc<AggregateUDF> {
4646
Arc::clone(&TANTIVY_CARDINALITY)
4747
}
4848

49-
/// Resolve the UDAF by name, for the plan codecs.
50-
pub fn udaf_by_name(name: &str) -> Option<Arc<AggregateUDF>> {
51-
(name == TANTIVY_CARDINALITY_NAME).then(tantivy_cardinality_udaf)
52-
}
53-
5449
/// The sketch as it travels between accumulators and to the caller.
5550
pub fn decode_sketch(bytes: &[u8]) -> Result<CardinalityCollector> {
5651
postcard::from_bytes(bytes)

‎pg_search/src/postgres/customscan/datafusion/mod.rs‎

Lines changed: 22 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,8 @@
2828
2929
use datafusion::common::ScalarValue;
3030
use datafusion::error::{DataFusionError, Result};
31-
use datafusion::logical_expr::AggregateUDF;
3231
use datafusion::logical_expr::function::AccumulatorArgs;
32+
use datafusion::logical_expr::{AggregateUDF, ScalarUDF};
3333
use datafusion::physical_plan::expressions::Literal;
3434
use std::sync::Arc;
3535

@@ -42,11 +42,28 @@ pub mod spill;
4242
pub mod timestamp_to_date;
4343
pub mod translator;
4444

45-
/// Resolve a pg_search aggregate UDAF by name, for the plan codecs. These
46-
/// functions are not in any session registry, so serialized plans (parallel
47-
/// and MPP dispatch) decode them through here.
45+
/// All pg_search aggregate UDAFs, registered into SessionState so plans referencing
46+
/// them can resolve them by name across plan serialization and dispatch.
47+
pub fn all_pg_search_udafs() -> Vec<Arc<AggregateUDF>> {
48+
vec![
49+
numeric_agg::numeric64_sum_udaf(),
50+
numeric_agg::numeric64_avg_udaf(),
51+
numeric_agg::numeric_bytes_sum_udaf(),
52+
numeric_agg::numeric_bytes_avg_udaf(),
53+
cardinality_agg::tantivy_cardinality_udaf(),
54+
]
55+
}
56+
57+
/// All stateless pg_search scalar UDFs registered into SessionState.
58+
pub fn all_pg_search_udfs() -> Vec<Arc<ScalarUDF>> {
59+
vec![timestamp_to_date::timestamp_to_date_udf()]
60+
}
61+
62+
/// Resolve a pg_search aggregate UDAF by name, for the plan codecs.
4863
pub fn udaf_by_name(name: &str) -> Option<Arc<AggregateUDF>> {
49-
numeric_agg::udaf_by_name(name).or_else(|| cardinality_agg::udaf_by_name(name))
64+
all_pg_search_udafs()
65+
.into_iter()
66+
.find(|udaf| udaf.name() == name)
5067
}
5168

5269
/// The literal argument at `index` of a UDAF call. A per-call setting travels

0 commit comments

Comments
 (0)