// Copyright (c) 2023-2026 ParadeDB, Inc. // // This file is part of ParadeDB - Postgres for Search and Analytics // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU Affero General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU Affero General Public License for more details. // // You should have received a copy of the GNU Affero General Public License // along with this program. If not, see . use pretty_assertions::assert_eq; use rstest::*; use serde_json::Value; use sqlx::PgConnection; use tests::fixtures::*; #[derive(Clone, Copy)] struct PlanCase { name: &'static str, query: &'static str, expected_workers: Option, } fn explain(conn: &mut PgConnection, query: &str) -> Value { let (plan,) = format!("EXPLAIN (FORMAT JSON) {query}").fetch_one::<(Value,)>(conn); plan } fn root_plan(plan: &Value) -> &Value { plan.pointer("/0/Plan") .unwrap_or_else(|| panic!("EXPLAIN JSON should have /0/Plan: {plan:#?}")) } fn total_cost(plan: &Value) -> f64 { root_plan(plan) .get("Total Cost") .and_then(Value::as_f64) .unwrap_or_else(|| panic!("EXPLAIN JSON should have a Total Cost: {plan:#?}")) } fn max_workers_planned(node: &Value) -> Option { let here = node.get("Workers Planned").and_then(Value::as_i64); node.get("Plans") .and_then(Value::as_array) .into_iter() .flatten() .filter_map(max_workers_planned) .fold(here, |max, workers| Some(max.unwrap_or(0).max(workers))) } fn contains_topk_exec(node: &Value) -> bool { node.get("Exec Method").and_then(Value::as_str) == Some("TopKScanExecState") || node .get("Plans") .and_then(Value::as_array) .into_iter() .flatten() .any(contains_topk_exec) } fn assert_plan_case(conn: &mut PgConnection, case: PlanCase) { let plan = explain(conn, case.query); let root = root_plan(&plan); assert!( contains_topk_exec(root), "{} should use TopKScanExecState:\n{plan:#?}", case.name ); assert_eq!( max_workers_planned(root), case.expected_workers, "{} worker count mismatch:\n{plan:#?}", case.name ); } /// Structural parallel knobs only, leaving PostgreSQL's cost GUCs (`parallel_setup_cost`, /// `cpu_operator_cost`, ...) at their defaults. Worker decisions asserted under this regime /// are exactly the plans a real user gets. `min_parallel_table_scan_size = 0` keeps a /// parallel path on the table so the model's *serial* choice is what's tested — not /// PostgreSQL declining to consider parallelism at all on a tiny table. fn set_default_costs(conn: &mut PgConnection) { r#" SET max_parallel_workers_per_gather = 2; SET max_parallel_workers = 8; SET min_parallel_table_scan_size = 0; SET paradedb.global_mutable_segment_rows = 0; SET paradedb.min_rows_per_worker = 300000; "# .execute(conn); } /// Same structural knobs as `set_default_costs`, but with the parallel cost GUCs scaled /// down — a cheap `parallel_setup_cost` and an inflated `cpu_operator_cost` — so the cost /// model's *parallel* branch is reachable on a CI-sized fixture. At real costs the #4664 /// repro needed millions of docs to clear Gather overhead; here we assert only the model's /// *relative* choice (these shapes parallelize, the serial cases above do not). The /// absolute default-cost crossover is validated separately by `topk_parallel_bench.sh` /// (4M rows, real costs). fn set_scaled_costs(conn: &mut PgConnection) { set_default_costs(conn); // The TopK work term is `Query::cost * cpu_index_tuple_cost`; inflate that per-doc // constant (and lower the Gather floor) to reach the parallel branch on a small fixture. r#" SET parallel_setup_cost = 100; SET cpu_index_tuple_cost = 0.05; "# .execute(conn); } fn setup_topk_desc_large(conn: &mut PgConnection) { r#" DROP TABLE IF EXISTS topk_desc_large CASCADE; CREATE TABLE topk_desc_large ( id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, body TEXT NOT NULL ); CREATE INDEX topk_desc_large_idx ON topk_desc_large USING bm25 (id, body) WITH ( key_field = 'id', target_segment_count = 4, mutable_segment_rows = 5000, layer_sizes = '10TB', background_layer_sizes = '10TB' ); INSERT INTO topk_desc_large (body) SELECT CASE WHEN g % 3 = 0 THEN 'alpha beta' ELSE 'gamma delta' END FROM generate_series(1, 5000) g; INSERT INTO topk_desc_large (body) SELECT CASE WHEN g % 3 = 0 THEN 'alpha beta' ELSE 'gamma delta' END FROM generate_series(1, 5000) g; INSERT INTO topk_desc_large (body) SELECT CASE WHEN g % 3 = 0 THEN 'alpha beta' ELSE 'gamma delta' END FROM generate_series(1, 5000) g; INSERT INTO topk_desc_large (body) SELECT CASE WHEN g % 3 = 0 THEN 'alpha beta' ELSE 'gamma delta' END FROM generate_series(1, 5000) g; ANALYZE topk_desc_large; "# .execute(conn); } fn setup_many_segments(conn: &mut PgConnection) { r#" DROP TABLE IF EXISTS topk_desc_many_segs CASCADE; CREATE TABLE topk_desc_many_segs ( id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, body TEXT NOT NULL ); CREATE INDEX topk_desc_many_segs_idx ON topk_desc_many_segs USING bm25 (id, body) WITH ( key_field = 'id', target_segment_count = 32, mutable_segment_rows = 1000, layer_sizes = '10TB', background_layer_sizes = '10TB' ); "# .execute(conn); for _ in 0..32 { r#" INSERT INTO topk_desc_many_segs (body) SELECT CASE WHEN g = 1 THEN 'rare token' ELSE 'common other' END FROM generate_series(1, 1000) g; "# .execute(conn); } "ANALYZE topk_desc_many_segs;".execute(conn); } fn setup_topk_asc_small(conn: &mut PgConnection) { r#" DROP TABLE IF EXISTS topk_asc_small CASCADE; CREATE TABLE topk_asc_small ( id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, body TEXT NOT NULL ); CREATE INDEX topk_asc_small_idx ON topk_asc_small USING bm25 (id, body) WITH ( key_field = 'id', target_segment_count = 4, mutable_segment_rows = 1000, layer_sizes = '10TB', background_layer_sizes = '10TB' ); INSERT INTO topk_asc_small (body) SELECT 'common word' FROM generate_series(1, 1000); INSERT INTO topk_asc_small (body) SELECT 'special token' FROM generate_series(1, 5); ANALYZE topk_asc_small; "# .execute(conn); } fn setup_multi_term(conn: &mut PgConnection) { r#" DROP TABLE IF EXISTS topk_desc_multi_term CASCADE; CREATE TABLE topk_desc_multi_term ( id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, body TEXT NOT NULL ); CREATE INDEX topk_desc_multi_term_idx ON topk_desc_multi_term USING bm25 (id, body) WITH ( key_field = 'id', target_segment_count = 4, mutable_segment_rows = 5000, layer_sizes = '10TB', background_layer_sizes = '10TB' ); INSERT INTO topk_desc_multi_term (body) SELECT 'alpha beta gamma delta epsilon' FROM generate_series(1, 5000); INSERT INTO topk_desc_multi_term (body) SELECT 'alpha beta gamma delta epsilon' FROM generate_series(1, 5000); INSERT INTO topk_desc_multi_term (body) SELECT 'alpha beta gamma delta epsilon' FROM generate_series(1, 5000); INSERT INTO topk_desc_multi_term (body) SELECT 'alpha beta gamma delta epsilon' FROM generate_series(1, 5000); ANALYZE topk_desc_multi_term; "# .execute(conn); } fn setup_unanalyzed(conn: &mut PgConnection) { r#" DROP TABLE IF EXISTS topk_unanalyzed CASCADE; CREATE TABLE topk_unanalyzed ( id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY, body TEXT NOT NULL ); CREATE INDEX topk_unanalyzed_idx ON topk_unanalyzed USING bm25 (id, body) WITH ( key_field = 'id', target_segment_count = 4, mutable_segment_rows = 100, layer_sizes = '10TB', background_layer_sizes = '10TB' ); INSERT INTO topk_unanalyzed (body) SELECT 'alpha beta' FROM generate_series(1, 100); INSERT INTO topk_unanalyzed (body) SELECT 'alpha beta' FROM generate_series(1, 100); "# .execute(conn); } #[rstest] fn cost_based_topk_plan_shapes(mut conn: PgConnection) { setup_topk_desc_large(&mut conn); setup_many_segments(&mut conn); setup_topk_asc_small(&mut conn); setup_unanalyzed(&mut conn); // ---- Serial decisions, asserted at PostgreSQL's DEFAULT cost GUCs, so these are the // plans a real user gets. The #4664 fix lives here: a single-term score-DESC TopK stays // serial because Block-WAND prunes the lone posting list (work ~ 0, independent of cost // knobs). The general-path shapes (window agg, unordered, parameterized LIMIT) are serial // via the #3055 row cap / LIMIT cap on this CI-sized fixture — none depend on the scaled // knobs the parallel cases below use. set_default_costs(&mut conn); for case in [ PlanCase { name: "score_desc_large_match_small_limit_is_serial", query: "SELECT id FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, PlanCase { name: "score_desc_score_projection_preserves_serial_choice", query: "SELECT id, paradedb.score(id) FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, PlanCase { name: "score_desc_many_segments_rare_match_is_serial_by_default", query: "SELECT id FROM topk_desc_many_segs WHERE body @@@ 'rare' ORDER BY paradedb.score(id) DESC LIMIT 20", expected_workers: None, }, // Score-ASC can't prune (Block-WAND finds the highest scores, not the // lowest), so it must score every match — but with only ~5 matches the // scan work is far below the Gather threshold, so serial wins. PlanCase { name: "score_asc_tiny_match_is_serial", query: "SELECT id FROM topk_asc_small WHERE body @@@ 'special' ORDER BY paradedb.score(id) ASC LIMIT 10", expected_workers: None, }, // Field-sorted TopK still has to scan every match before sorting, but // ~5 matches is well below the Gather threshold, so serial wins. PlanCase { name: "field_sort_tiny_match_is_serial", query: "SELECT id FROM topk_asc_small WHERE body @@@ 'special' ORDER BY id ASC LIMIT 10", expected_workers: None, }, PlanCase { name: "unordered_topk_small_limit_is_serial", query: "SELECT id FROM topk_desc_large WHERE body @@@ 'gamma' LIMIT 10", expected_workers: None, }, // Window aggregates genuinely bail to the general path (`compute_nworkers`), // not the cost model. With #4457 reverted, the general path applies the // #3055 row cap to sorted output, so on this ~20K-row fixture (below the // 300K `min_rows_per_worker`) it is serial. PlanCase { name: "window_aggregate_routes_to_general_path_serial_on_small_data", query: "SELECT id, paradedb.score(id), pdb.agg('{\"terms\": {\"field\": \"body\", \"size\": 5}}', false) OVER () AS body_facets FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, // Same, but with the window aggregate nested inside a function call: the // planner hook's replacement pass descends into FuncExpr arguments, so // the window_agg() placeholder ends up nested inside jsonb_pretty() // rather than at the top of the target entry. Only a recursive // target-list walk detects it, and it must route to the general path // exactly like the top-level form above. PlanCase { name: "nested_window_aggregate_routes_to_general_path_serial_on_small_data", query: "SELECT id, paradedb.score(id), jsonb_pretty( pdb.agg('{\"terms\": {\"field\": \"body\", \"size\": 5}}', false) OVER () ) AS body_facets FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, PlanCase { name: "unanalyzed_small_limit_is_serial", query: "SELECT id FROM topk_unanalyzed WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, // The headline #4664 fix: a single-term score-DESC TopK stays serial at any LIMIT, // because Block-WAND prunes the single posting list and keeps serial scoring cheap. // Today every score-sorted scan parallelizes; on a 4M-row corpus that costs this // shape up to ~2x, since serial beats parallel at every LIMIT measured. PlanCase { name: "score_desc_single_term_large_limit_stays_serial", query: "SELECT id FROM topk_desc_many_segs WHERE body @@@ 'common' ORDER BY paradedb.score(id) DESC LIMIT 1000", expected_workers: None, }, PlanCase { name: "secondary_sort_key_is_serial", query: "SELECT id FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC, id ASC LIMIT 10", expected_workers: None, }, ] { assert_plan_case(&mut conn, case); } // The runtime-bound forms below need a generic plan so the Param survives to planning. "SET plan_cache_mode = force_generic_plan;".execute(&mut conn); // Parameterized LIMIT: not a prunable candidate (the LIMIT is a runtime Param), so it goes // through the cost model with an estimated LIMIT. On this small fixture the scan work is below // the Gather threshold, so it is serial. r#" PREPARE topk_desc_param_limit(int) AS SELECT id FROM topk_desc_large WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT $1; "# .execute(&mut conn); assert_plan_case( &mut conn, PlanCase { name: "parameterized_limit_is_serial_on_small_data", query: "EXECUTE topk_desc_param_limit(10)", expected_workers: None, }, ); // Runtime-bound WHERE predicate (`@@@ $1`), UNSORTED: the predicate has no plan-time value to // open a scorer for, so the cost model can't run. An unsorted scan can skip segments once the // LIMIT is met, so it defers to the row-based heuristic, which is serial on this small fixture. r#" PREPARE unsorted_param_pred(text) AS SELECT id FROM topk_desc_large WHERE body @@@ $1 LIMIT 10; "# .execute(&mut conn); assert_plan_case( &mut conn, PlanCase { name: "runtime_bound_predicate_unsorted_defers_to_row_heuristic_serial", query: "EXECUTE unsorted_param_pred('alpha')", expected_workers: None, }, ); "RESET plan_cache_mode;".execute(&mut conn); // ---- Parallel decisions. The cost model parallelizes only when scan work clears Gather // overhead, which at real costs needs scale. Scale the parallel knobs down to reach that branch // on this small fixture; this asserts the model's *relative* choice (these shapes parallelize, // the serial ones above do not). They all route through the cost model (`cost_test`), not the // row-cap path. See `set_scaled_costs`. set_scaled_costs(&mut conn); for case in [ PlanCase { name: "score_asc_large_match_parallelizes", query: "SELECT id FROM topk_desc_large WHERE body @@@ 'gamma' ORDER BY paradedb.score(id) ASC LIMIT 10", expected_workers: Some(2), }, PlanCase { name: "field_sort_large_match_parallelizes", query: "SELECT id FROM topk_desc_large WHERE body @@@ 'gamma' ORDER BY id ASC LIMIT 10", expected_workers: Some(2), }, PlanCase { name: "phrase_query_parallelizes", query: "SELECT id FROM topk_desc_large WHERE body @@@ pdb.phrase(ARRAY['alpha', 'beta']) ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: Some(2), }, PlanCase { name: "must_conjunction_parallelizes", query: "SELECT id FROM topk_desc_large WHERE id @@@ paradedb.boolean( must => ARRAY[ paradedb.term('body', 'alpha'), paradedb.term('body', 'beta') ] ) ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: Some(2), }, // A dense term_set (here alpha ∪ gamma = every row) has no Block-WAND-pruning // weight, so it must reach the cost model and parallelize -- regression guard // against term_set being mis-classified prunable and forced serial. PlanCase { name: "term_set_dense_parallelizes", query: "SELECT id FROM topk_desc_large WHERE body @@@ paradedb.term_set(terms => ARRAY[ paradedb.term('body', 'alpha'), paradedb.term('body', 'gamma') ]) ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: Some(2), }, // UNSORTED scans are cost-modeled too (no ORDER BY). A cheap term serializes (a small // LIMIT finds its rows in a sliver of the docset), but an expensive phrase must drive its // matches to find a full LIMIT, so its work clears the Gather threshold and it parallelizes. PlanCase { name: "unsorted_expensive_phrase_parallelizes", query: "SELECT id FROM topk_desc_large WHERE body @@@ pdb.phrase(ARRAY['alpha', 'beta']) LIMIT 100", expected_workers: Some(2), }, ] { assert_plan_case(&mut conn, case); } // Runtime-bound WHERE predicate (`@@@ $1`), SORTED: can't be costed, but a sorted scan must // visit every segment, so workers always help -- it parallelizes via the no-cost fallback // (the fix for parameterized score-DESC paging queries that previously serialized). "SET plan_cache_mode = force_generic_plan;".execute(&mut conn); r#" PREPARE sorted_param_pred(text) AS SELECT id FROM topk_desc_large WHERE body @@@ $1 ORDER BY paradedb.score(id) DESC LIMIT 10; "# .execute(&mut conn); assert_plan_case( &mut conn, PlanCase { name: "runtime_bound_predicate_sorted_parallelizes", query: "EXECUTE sorted_param_pred('gamma')", expected_workers: Some(2), }, ); "RESET plan_cache_mode;".execute(&mut conn); // Unanalyzed table with a NON-prunable shape (score ASC): no match count, so the cost model // can't run and it defers to the row-based heuristic. With no row stats the heuristic applies // no caps, so it parallelizes by structure alone -- matching the pre-cost-model behavior. // (The prunable `unanalyzed_small_limit` case above stays serial via the short-circuit, which // runs before this fallback, so this case is what actually exercises the unanalyzed path.) assert_plan_case( &mut conn, PlanCase { name: "unanalyzed_nonprunable_defers_to_row_heuristic_parallel", query: "SELECT id FROM topk_unanalyzed WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) ASC LIMIT 10", expected_workers: Some(2), }, ); } #[rstest] fn dense_multi_term_query_accounts_for_term_union_traversal(mut conn: PgConnection) { // Both cases share the scaled-cost regime on purpose: the contrast (single term serial, // term union parallel) must come from the query *shape*, not from different GUCs. set_scaled_costs(&mut conn); setup_multi_term(&mut conn); let matches = r#" SELECT count(*) AS matches FROM topk_desc_multi_term WHERE body ||| 'alpha' UNION ALL SELECT count(*) AS matches FROM topk_desc_multi_term WHERE body ||| 'alpha beta gamma delta epsilon' ORDER BY matches "# .fetch::<(i64,)>(&mut conn); assert_eq!(matches.len(), 2); let (single_term_matches,) = matches[0]; let (term_union_matches,) = matches[1]; assert_eq!(single_term_matches, term_union_matches); for case in [ PlanCase { name: "dense_single_term_stays_serial", query: "SELECT id FROM topk_desc_multi_term WHERE body ||| 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: None, }, PlanCase { name: "dense_multi_term_term_union_chooses_parallel", query: "SELECT id FROM topk_desc_multi_term WHERE body ||| 'alpha beta gamma delta epsilon' ORDER BY paradedb.score(id) DESC LIMIT 10", expected_workers: Some(2), }, ] { assert_plan_case(&mut conn, case); } } #[rstest] fn no_limit_costed_both_accounts_for_scan_work(mut conn: PgConnection) { set_scaled_costs(&mut conn); setup_multi_term(&mut conn); "SET paradedb.enable_aggregate_custom_scan = false;".execute(&mut conn); // Same scan in both cases, so the only thing that differs is how many rows cross the Gather -- // isolating the transport cost as the serial-vs-parallel driver. let count_plan = explain( &mut conn, "SELECT COUNT(*) FROM topk_desc_multi_term WHERE body @@@ 'alpha'", ); let count_root = root_plan(&count_plan); assert_eq!( max_workers_planned(count_root), Some(2), "COUNT(*) should go parallel: the Partial Aggregate collapses rows before the Gather, so the \ costed scan work splits across workers with almost nothing to transport:\n{count_plan:#?}" ); let select_plan = explain( &mut conn, "SELECT * FROM topk_desc_multi_term WHERE body @@@ 'alpha'", ); let select_root = root_plan(&select_plan); assert_eq!( max_workers_planned(select_root), None, "bulk SELECT should serialize: every matched row crosses the Gather, so transport outweighs \ the scan-work split:\n{select_plan:#?}" ); } /// A prunable score-DESC TopK costs the scan by output rows, not its full drive cost: Block-WAND /// prunes it sublinear, so folding `drive_cost` into the path cost would overstate the work. A /// non-prunable score-ASC TopK over the *same* term and match set is identical except for the /// excluded `drive_cost`, so it must cost strictly more -- equal cost means the exclusion is gone. #[rstest] fn prunable_topk_cost_excludes_drive_work(mut conn: PgConnection) { set_scaled_costs(&mut conn); // Force serial so the comparison is the bare scan cost, not a Gather plan on either side. "SET max_parallel_workers_per_gather = 0;".execute(&mut conn); setup_multi_term(&mut conn); // Same single term and match set; only the sort direction differs. Block-WAND prunes score DESC // (cost excludes drive_cost) but not score ASC (cost includes it). let prunable = total_cost(&explain( &mut conn, "SELECT id FROM topk_desc_multi_term WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) DESC LIMIT 10", )); let non_prunable = total_cost(&explain( &mut conn, "SELECT id FROM topk_desc_multi_term WHERE body @@@ 'alpha' ORDER BY paradedb.score(id) ASC LIMIT 10", )); assert!( prunable < non_prunable, "prunable score-DESC TopK ({prunable}) must cost strictly less than the otherwise-identical \ non-prunable score-ASC ({non_prunable}); equal cost means drive_cost is no longer excluded" ); }