agora inbox for [email protected]help / color / mirror / Atom feed
[PATCH v3] Use correlation statistic in costing bitmap scans.. 8+ messages / 2 participants [nested] [flat]
* [PATCH v3] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, an uncorrelated bitmap (like modulus) which accesses a certain number of pages across the entire length of a table should have its cost estimate heavily weighted by random access, compared to an bitmap scan which accesses same number of pages across a small portion of the table. Note, Tom points out that there are cases where a column could be tightly-"clumped" without being hightly-ordered. Since we have correlation already, we use that until such time as someone implements a new statistic for clumpiness. --- src/backend/optimizer/path/costsize.c | 84 ++++++++++++++++++++++++++++------ src/backend/optimizer/path/indxpath.c | 8 ++-- src/include/nodes/pathnodes.h | 3 ++ src/include/optimizer/cost.h | 2 +- src/test/regress/expected/identity.out | 2 +- src/test/regress/expected/join.out | 42 ++++++++++------- src/test/regress/expected/select.out | 16 +++---- src/test/regress/sql/identity.sql | 2 +- 8 files changed, 110 insertions(+), 49 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index c5f6593..aaac29a 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -549,11 +549,12 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a + * bitmap scan doesn't care. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -986,12 +987,33 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation, cost_per_page2; cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + + // XXX: interpolate based on correlation from seq_page_cost to rand_page_cost? + // a highly correlated bitmap scan 1) likely reads fewer pages; and, + // 2) at higher "density" (more sequential). + // double correlation = get_indexpath_correlation(root, bitmapqual); + correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + cost_per_page2 = spc_seq_page_cost + + (1-correlation*correlation)*(spc_random_page_cost - spc_seq_page_cost); // XXX: *sqrt(pages_fetched/T) ? + // There are two variables: fraction of pages(T) and correlation. + // If T is high, giving sequential reads, we want low cost_per_page regardless of correlation. + // If correlation is high, we (probably) want low cost per page. + // ...the exception is if someone does an =ANY() query on a list of non-consecutive values. + // Something like start_time=ANY('2017-01-01', '2017-02-01',...) + // which reads small number of rows from pages all across the length of the table. + // But index scan doesn't seem to do address that at all, so leave it alone for now. + cost_per_page=Min(cost_per_page, cost_per_page2); + // cost_per_page=sqrt(cost_per_page*cost_per_page + cost_per_page2*cost_per_page2); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1035,15 +1057,16 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1057,11 +1080,13 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) { *cost = path->total_cost; *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1084,8 +1109,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1097,22 +1123,32 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec<=minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) + // ??? XXX && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1128,8 +1164,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1142,23 +1179,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec>=maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5510,8 +5556,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5520,7 +5569,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5534,7 +5583,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 37b257c..2a3db34 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1467,8 +1467,8 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) Selectivity nselec; Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1580,8 +1580,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 23a06d7..beaac03 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1181,6 +1181,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1261,6 +1262,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1274,6 +1276,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index b3d0b4f..9a28665 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, diff --git a/src/test/regress/expected/identity.out b/src/test/regress/expected/identity.out index 36a2393..67aacf5 100644 --- a/src/test/regress/expected/identity.out +++ b/src/test/regress/expected/identity.out @@ -316,7 +316,7 @@ SELECT * FROM itest6; 102 | (3 rows) -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2,3,4; table_name | column_name | is_identity | identity_generation ------------+-------------+-------------+--------------------- itest6 | a | YES | BY DEFAULT diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index b58d560..8299426 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -3144,22 +3144,26 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------------ Nested Loop -> Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Nested Loop - -> Seq Scan on onerow - -> Seq Scan on onerow onerow_1 - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Nested Loop + -> Seq Scan on onerow + -> Seq Scan on onerow onerow_1 -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -> Seq Scan on int4_tbl i1 Filter: (f1 = 0) -(13 rows) +(17 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 @@ -3212,18 +3216,22 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------ Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Seq Scan on int4_tbl i1 - Filter: (f1 = 0) - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Seq Scan on int4_tbl i1 + Filter: (f1 = 0) -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -(9 rows) +(13 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out index c441049..675bf63 100644 --- a/src/test/regress/expected/select.out +++ b/src/test/regress/expected/select.out @@ -861,17 +861,13 @@ RESET enable_indexscan; explain (costs off) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; - QUERY PLAN --------------------------------------------------------------------------------- + QUERY PLAN +--------------------------------------------- Bitmap Heap Scan on onek2 - Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0)) - Filter: (stringu1 < 'B'::name) - -> BitmapOr - -> Bitmap Index Scan on onek2_u2_prtl - Index Cond: (unique2 = 11) - -> Bitmap Index Scan on onek2_u1_prtl - Index Cond: (unique1 = 0) -(8 rows) + Recheck Cond: (stringu1 < 'B'::name) + Filter: ((unique2 = 11) OR (unique1 = 0)) + -> Bitmap Index Scan on onek2_u2_prtl +(4 rows) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; diff --git a/src/test/regress/sql/identity.sql b/src/test/regress/sql/identity.sql index 4b03d24..8dab134 100644 --- a/src/test/regress/sql/identity.sql +++ b/src/test/regress/sql/identity.sql @@ -191,7 +191,7 @@ INSERT INTO itest6 DEFAULT VALUES; INSERT INTO itest6 DEFAULT VALUES; SELECT * FROM itest6; -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2,3,4; ALTER TABLE itest6 ALTER COLUMN b SET INCREMENT BY 2; -- fail, not identity -- 2.7.4 --JYK4vJDZwFMowpUq-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v1] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, a correlated bitmap which accesses pages across a small portion of the table should have a cost estimate much less than an uncorrelated scan (like modulus) across the entire length of the table, the latter having a high component of random access. Note, Tom points out that there are cases where a column could be tightly-"clumped" without being highly-ordered. Since we have correlation already, we use that until such time as someone implements a new statistic for clumpiness. This patch only intends to make costing of bitmap heap scan on par with the same cost of index scan without bitmap. --- contrib/postgres_fdw/expected/postgres_fdw.out | 15 ++-- src/backend/optimizer/path/costsize.c | 94 +++++++++++++++++++++----- src/backend/optimizer/path/indxpath.c | 10 ++- src/include/nodes/pathnodes.h | 3 + src/include/optimizer/cost.h | 2 +- src/test/regress/expected/create_index.out | 16 ++--- src/test/regress/expected/join.out | 18 +++-- src/test/regress/sql/create_index.sql | 8 ++- 8 files changed, 118 insertions(+), 48 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index c915885..fb4c7f2 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -2257,11 +2257,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f -> Foreign Scan on public.ft1 Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.* Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE - -> Materialize + -> Sort Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* + Sort Key: ft2.c1 -> Foreign Scan on public.ft2 Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* - Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE + Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE -> Sort Output: ft4.c1, ft4.c2, ft4.c3, ft4.* Sort Key: ft4.c1 @@ -2276,7 +2277,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4" FOR UPDATE -> Index Scan using local_tbl_pkey on public.local_tbl Output: local_tbl.c1, local_tbl.c2, local_tbl.c3, local_tbl.ctid -(47 rows) +(48 rows) SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1 AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE; @@ -3318,10 +3319,12 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Sort Key: t1.c2 -> Nested Loop Output: t1.c2, qry.sum - -> Index Scan using t1_pkey on "S 1"."T 1" t1 + -> Bitmap Heap Scan on "S 1"."T 1" t1 Output: t1."C 1", t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8 - Index Cond: (t1."C 1" < 100) + Recheck Cond: (t1."C 1" < 100) Filter: (t1.c2 < 3) + -> Bitmap Index Scan on t1_pkey + Index Cond: (t1."C 1" < 100) -> Subquery Scan on qry Output: qry.sum, t2.c1 Filter: ((t1.c2 * 2) = qry.sum) @@ -3329,7 +3332,7 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Output: (sum((t2.c1 + t1."C 1"))), t2.c1 Relations: Aggregate on (public.ft2 t2) Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM "S 1"."T 1" GROUP BY 2 -(16 rows) +(18 rows) select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and t1."C 1" < 100 order by 1; c2 | sum diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index b5a0033..d39e12d 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -549,11 +549,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a bitmap scan + * can't start until the index scan completes, so only cares about its + * total cost. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -986,12 +988,31 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + double cost_per_page_corr; + /* + * Interpolate based on pages_fetched and correlation from seq_page_cost to rand_page_cost. + * A highly correlated bitmap scan 1) likely reads fewer pages (handled in + * compute_bitmap_pages); and, 2) at higher "density" (more sequential). + */ cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + cost_per_page_corr = spc_random_page_cost - + (spc_random_page_cost - spc_seq_page_cost) + * (1-correlation*correlation); + + /* + * We expect sequential reads and low cost_per_page when *either* + * T is high or correlation is high. + */ + cost_per_page = Min(cost_per_page,cost_per_page_corr); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1035,15 +1056,18 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; - *selec = ((IndexPath *) path)->indexselectivity; + if (selec) + *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) + *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1056,12 +1080,18 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) else if (IsA(path, BitmapAndPath)) { *cost = path->total_cost; - *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; - *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1084,8 +1114,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1097,22 +1128,31 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec <= minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1128,8 +1168,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1142,23 +1183,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec >= maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5510,8 +5560,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5520,7 +5573,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5534,7 +5587,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index f42926e..5d111fc 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1483,11 +1483,9 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) /* duplicate clauseids, keep the cheaper one */ Cost ncost; Cost ocost; - Selectivity nselec; - Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, NULL, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, NULL, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1599,8 +1597,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be19..19ddf5b 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1183,6 +1183,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1263,6 +1264,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1276,6 +1278,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index cb012ba..7d5edb5 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index 6446907..5bd8aae 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -1770,24 +1770,23 @@ DROP TABLE onek_with_null; -- -- Check bitmap index path planning -- +SET cpu_operator_cost=0; EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); + QUERY PLAN +------------------------------------------------------------------------------------------------- Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42))) + Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 42))) -> BitmapOr -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 1)) -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) +(7 rows) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 ---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+--------- 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx @@ -1818,6 +1817,7 @@ SELECT count(*) FROM tenk1 10 (1 row) +RESET cpu_operator_cost; -- -- Check behavior with duplicate index column contents -- diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 761376b..bc011ee 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -3584,24 +3584,28 @@ select b.unique1 from join int4_tbl i1 on b.thousand = f1 right join int4_tbl i2 on i2.f1 = b.tenthous order by 1; - QUERY PLAN ------------------------------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------------------------------- Sort Sort Key: b.unique1 - -> Nested Loop Left Join - -> Seq Scan on int4_tbl i2 + -> Hash Right Join + Hash Cond: (b.tenthous = i2.f1) -> Nested Loop Left Join Join Filter: (b.unique1 = 42) -> Nested Loop -> Nested Loop -> Seq Scan on int4_tbl i1 - -> Index Scan using tenk1_thous_tenthous on tenk1 b - Index Cond: ((thousand = i1.f1) AND (tenthous = i2.f1)) + -> Bitmap Heap Scan on tenk1 b + Recheck Cond: (thousand = i1.f1) + -> Bitmap Index Scan on tenk1_thous_tenthous + Index Cond: (thousand = i1.f1) -> Index Scan using tenk1_unique1 on tenk1 a Index Cond: (unique1 = b.unique2) -> Index Only Scan using tenk1_thous_tenthous on tenk1 c Index Cond: (thousand = a.thousand) -(15 rows) + -> Hash + -> Seq Scan on int4_tbl i2 +(19 rows) select b.unique1 from tenk1 a join tenk1 b on a.unique1 = b.unique2 diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql index 3c0c1cd..6607a7b 100644 --- a/src/test/regress/sql/create_index.sql +++ b/src/test/regress/sql/create_index.sql @@ -666,11 +666,13 @@ DROP TABLE onek_with_null; -- Check bitmap index path planning -- +SET cpu_operator_cost=0; + EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); EXPLAIN (COSTS OFF) SELECT count(*) FROM tenk1 @@ -678,6 +680,8 @@ SELECT count(*) FROM tenk1 SELECT count(*) FROM tenk1 WHERE hundred = 42 AND (thousand = 42 OR thousand = 99); +RESET cpu_operator_cost; + -- -- Check behavior with duplicate index column contents -- -- 2.7.4 --wayzTnRSUXKNfBqd-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v2] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, an uncorrelated bitmap (like modulus) which access a certain number of pages across the entire length of a table should have cost estimate heavily weighted by random access, compared to an bitmap scan which accesses same number of pages across a small portion of the table. Note, Tom points out that there are cases where a column could be tightly-clumped without being hightly-ordered. Since we have correlation already, we use that for now, and if someone creates a statistic for clumpiness, we'll re-evaluate at some later date. --- src/backend/optimizer/path/costsize.c | 84 ++++++++++++++++++++++++++++------- src/backend/optimizer/path/indxpath.c | 8 ++-- src/include/nodes/pathnodes.h | 3 ++ src/include/optimizer/cost.h | 2 +- 4 files changed, 77 insertions(+), 20 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index c5f6593..aaac29a 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -549,11 +549,12 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a + * bitmap scan doesn't care. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -986,12 +987,33 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation, cost_per_page2; cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + + // XXX: interpolate based on correlation from seq_page_cost to rand_page_cost? + // a highly correlated bitmap scan 1) likely reads fewer pages; and, + // 2) at higher "density" (more sequential). + // double correlation = get_indexpath_correlation(root, bitmapqual); + correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + cost_per_page2 = spc_seq_page_cost + + (1-correlation*correlation)*(spc_random_page_cost - spc_seq_page_cost); // XXX: *sqrt(pages_fetched/T) ? + // There are two variables: fraction of pages(T) and correlation. + // If T is high, giving sequential reads, we want low cost_per_page regardless of correlation. + // If correlation is high, we (probably) want low cost per page. + // ...the exception is if someone does an =ANY() query on a list of non-consecutive values. + // Something like start_time=ANY('2017-01-01', '2017-02-01',...) + // which reads small number of rows from pages all across the length of the table. + // But index scan doesn't seem to do address that at all, so leave it alone for now. + cost_per_page=Min(cost_per_page, cost_per_page2); + // cost_per_page=sqrt(cost_per_page*cost_per_page + cost_per_page2*cost_per_page2); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1035,15 +1057,16 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1057,11 +1080,13 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) { *cost = path->total_cost; *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1084,8 +1109,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1097,22 +1123,32 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec<=minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) + // ??? XXX && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1128,8 +1164,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1142,23 +1179,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec>=maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5510,8 +5556,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5520,7 +5569,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5534,7 +5583,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 37b257c..2a3db34 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1467,8 +1467,8 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) Selectivity nselec; Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1580,8 +1580,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 23a06d7..beaac03 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1181,6 +1181,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1261,6 +1262,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1274,6 +1276,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index b3d0b4f..9a28665 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, -- 2.7.4 --St7VIuEGZ6dlpu13-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v2] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, an uncorrelated bitmap (like modulus) which access a certain number of pages across the entire length of a table should have cost estimate heavily weighted by random access, compared to an bitmap scan which accesses same number of pages across a small portion of the table. Note, Tom points out that there are cases where a column could be tightly-clumped without being hightly-ordered. Since we have correlation already, we use that for now, and if someone creates a statistic for clumpiness, we'll re-evaluate at some later date. --- src/backend/optimizer/path/costsize.c | 84 ++++++++++++++++++++++++++++------- src/backend/optimizer/path/indxpath.c | 8 ++-- src/include/nodes/pathnodes.h | 3 ++ src/include/optimizer/cost.h | 2 +- 4 files changed, 77 insertions(+), 20 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index c5f6593..aaac29a 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -549,11 +549,12 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a + * bitmap scan doesn't care. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -986,12 +987,33 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation, cost_per_page2; cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + + // XXX: interpolate based on correlation from seq_page_cost to rand_page_cost? + // a highly correlated bitmap scan 1) likely reads fewer pages; and, + // 2) at higher "density" (more sequential). + // double correlation = get_indexpath_correlation(root, bitmapqual); + correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + cost_per_page2 = spc_seq_page_cost + + (1-correlation*correlation)*(spc_random_page_cost - spc_seq_page_cost); // XXX: *sqrt(pages_fetched/T) ? + // There are two variables: fraction of pages(T) and correlation. + // If T is high, giving sequential reads, we want low cost_per_page regardless of correlation. + // If correlation is high, we (probably) want low cost per page. + // ...the exception is if someone does an =ANY() query on a list of non-consecutive values. + // Something like start_time=ANY('2017-01-01', '2017-02-01',...) + // which reads small number of rows from pages all across the length of the table. + // But index scan doesn't seem to do address that at all, so leave it alone for now. + cost_per_page=Min(cost_per_page, cost_per_page2); + // cost_per_page=sqrt(cost_per_page*cost_per_page + cost_per_page2*cost_per_page2); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1035,15 +1057,16 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1057,11 +1080,13 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) { *cost = path->total_cost; *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1084,8 +1109,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1097,22 +1123,32 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec<=minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) + // ??? XXX && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1128,8 +1164,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1142,23 +1179,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec>=maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5510,8 +5556,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5520,7 +5569,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5534,7 +5583,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 37b257c..2a3db34 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1467,8 +1467,8 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) Selectivity nselec; Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1580,8 +1580,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 23a06d7..beaac03 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1181,6 +1181,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1261,6 +1262,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1274,6 +1276,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index b3d0b4f..9a28665 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, -- 2.7.4 --St7VIuEGZ6dlpu13 Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v2-0001-Use-correlation-statistic-in-costing-bitmap-scans.patch" ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v6 2/2] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, a correlated bitmap which accesses pages across a small portion of the table should have a cost estimate much less than an uncorrelated scan (like modulus) across the entire length of the table, the latter having a high component of random access. Note, Tom points out that there are cases where a column could be tightly-"clumped" without being highly-ordered. Since we have correlation already, we use that until such time as someone implements a new statistic for clumpiness. This patch only intends to make costing of bitmap heap scan on par with the same cost of index scan without bitmap. --- .../postgres_fdw/expected/postgres_fdw.out | 15 +-- src/backend/optimizer/path/costsize.c | 98 +++++++++++++++---- src/backend/optimizer/path/indxpath.c | 10 +- src/include/nodes/pathnodes.h | 3 + src/include/optimizer/cost.h | 2 +- src/test/regress/expected/create_index.out | 14 ++- src/test/regress/expected/join.out | 42 ++++---- src/test/regress/expected/plancache.out | 24 +++-- src/test/regress/expected/select.out | 16 ++- src/test/regress/sql/create_index.sql | 4 +- 10 files changed, 150 insertions(+), 78 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 2d88d06358..9a96f24d43 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -2261,11 +2261,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f -> Foreign Scan on public.ft1 Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.* Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE - -> Materialize + -> Sort Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* + Sort Key: ft2.c1 -> Foreign Scan on public.ft2 Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* - Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE + Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE -> Sort Output: ft4.c1, ft4.c2, ft4.c3, ft4.* Sort Key: ft4.c1 @@ -2280,7 +2281,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4" FOR UPDATE -> Index Scan using local_tbl_pkey on public.local_tbl Output: local_tbl.c1, local_tbl.c2, local_tbl.c3, local_tbl.ctid -(47 rows) +(48 rows) SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1 AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE; @@ -3322,10 +3323,12 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Sort Key: t1.c2 -> Nested Loop Output: t1.c2, qry.sum - -> Index Scan using t1_pkey on "S 1"."T 1" t1 + -> Bitmap Heap Scan on "S 1"."T 1" t1 Output: t1."C 1", t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8 - Index Cond: (t1."C 1" < 100) + Recheck Cond: (t1."C 1" < 100) Filter: (t1.c2 < 3) + -> Bitmap Index Scan on t1_pkey + Index Cond: (t1."C 1" < 100) -> Subquery Scan on qry Output: qry.sum, t2.c1 Filter: ((t1.c2 * 2) = qry.sum) @@ -3333,7 +3336,7 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Output: (sum((t2.c1 + t1."C 1"))), t2.c1 Relations: Aggregate on (public.ft2 t2) Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM "S 1"."T 1" GROUP BY 2 -(16 rows) +(18 rows) select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and t1."C 1" < 100 order by 1; c2 | sum diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 083448def7..db90451c73 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -562,11 +562,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a bitmap scan + * can't start until the index scan completes, so only cares about its + * total cost. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -1001,12 +1003,31 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + double cost_per_page_corr; + /* + * Interpolate based on pages_fetched and correlation from seq_page_cost to rand_page_cost. + * A highly correlated bitmap scan 1) likely reads fewer pages (handled in + * compute_bitmap_pages); and, 2) at higher "density" (more sequential). + */ cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + cost_per_page_corr = spc_random_page_cost - + (spc_random_page_cost - spc_seq_page_cost) + * (correlation*correlation); + + /* + * We expect sequential reads and low cost_per_page when *either* + * T is high or correlation is high. + */ + cost_per_page = Min(cost_per_page,cost_per_page_corr); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1050,15 +1071,18 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; - *selec = ((IndexPath *) path)->indexselectivity; + if (selec) + *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) + *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1071,12 +1095,18 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) else if (IsA(path, BitmapAndPath)) { *cost = path->total_cost; - *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; - *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1099,8 +1129,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1112,22 +1143,31 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec <= minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1143,8 +1183,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1157,23 +1198,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec >= maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5806,8 +5856,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5816,7 +5869,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5830,7 +5883,16 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + /* + * interpolate between MIN and MAX pages based on correlation**2 + * This is the same computation as in cost_index(). + */ + pages_fetched = pages_fetchedMAX - indexCorrelation*indexCorrelation*(pages_fetchedMAX - pages_fetchedMIN); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index bcb1bc6097..773277ce5b 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1454,11 +1454,9 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) /* duplicate clauseids, keep the cheaper one */ Cost ncost; Cost ocost; - Selectivity nselec; - Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, NULL, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, NULL, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1570,8 +1568,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 8f62d61702..4ff0b17ada 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1209,6 +1209,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1289,6 +1290,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1302,6 +1304,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 6141654e47..992eb4856d 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -80,7 +80,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index 93a8736a3f..bfb78ec8eb 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -1797,22 +1797,20 @@ DROP TABLE onek_with_null; -- EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); + QUERY PLAN +------------------------------------------------------------------------------------------------- Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42))) + Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 42))) -> BitmapOr -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 3)) -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) +(7 rows) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 ---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+--------- 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 6c9a5e26dd..d4b0443ba9 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -3144,22 +3144,26 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------------ Nested Loop -> Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Nested Loop - -> Seq Scan on onerow - -> Seq Scan on onerow onerow_1 - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Nested Loop + -> Seq Scan on onerow + -> Seq Scan on onerow onerow_1 -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -> Seq Scan on int4_tbl i1 Filter: (f1 = 0) -(13 rows) +(17 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 @@ -3212,18 +3216,22 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------ Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Seq Scan on int4_tbl i1 - Filter: (f1 = 0) - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Seq Scan on int4_tbl i1 + Filter: (f1 = 0) -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -(9 rows) +(13 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 diff --git a/src/test/regress/expected/plancache.out b/src/test/regress/expected/plancache.out index 4e59188196..1727173ccd 100644 --- a/src/test/regress/expected/plancache.out +++ b/src/test/regress/expected/plancache.out @@ -311,12 +311,14 @@ select name, generic_plans, custom_plans from pg_prepared_statements -- force generic plan set plan_cache_mode to force_generic_plan; explain (costs off) execute test_mode_pp(2); - QUERY PLAN ------------------------------ + QUERY PLAN +-------------------------------------------------- Aggregate - -> Seq Scan on test_mode - Filter: (a = $1) -(3 rows) + -> Bitmap Heap Scan on test_mode + Recheck Cond: (a = $1) + -> Bitmap Index Scan on test_mode_a_idx + Index Cond: (a = $1) +(5 rows) select name, generic_plans, custom_plans from pg_prepared_statements where name = 'test_mode_pp'; @@ -373,12 +375,14 @@ select name, generic_plans, custom_plans from pg_prepared_statements -- we should now get a really bad plan explain (costs off) execute test_mode_pp(2); - QUERY PLAN ------------------------------ + QUERY PLAN +-------------------------------------------------- Aggregate - -> Seq Scan on test_mode - Filter: (a = $1) -(3 rows) + -> Bitmap Heap Scan on test_mode + Recheck Cond: (a = $1) + -> Bitmap Index Scan on test_mode_a_idx + Index Cond: (a = $1) +(5 rows) -- but we can force a custom plan set plan_cache_mode to force_custom_plan; diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out index c441049f41..675bf632d0 100644 --- a/src/test/regress/expected/select.out +++ b/src/test/regress/expected/select.out @@ -861,17 +861,13 @@ RESET enable_indexscan; explain (costs off) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; - QUERY PLAN --------------------------------------------------------------------------------- + QUERY PLAN +--------------------------------------------- Bitmap Heap Scan on onek2 - Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0)) - Filter: (stringu1 < 'B'::name) - -> BitmapOr - -> Bitmap Index Scan on onek2_u2_prtl - Index Cond: (unique2 = 11) - -> Bitmap Index Scan on onek2_u1_prtl - Index Cond: (unique1 = 0) -(8 rows) + Recheck Cond: (stringu1 < 'B'::name) + Filter: ((unique2 = 11) OR (unique1 = 0)) + -> Bitmap Index Scan on onek2_u2_prtl +(4 rows) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql index b27643cad6..431864826d 100644 --- a/src/test/regress/sql/create_index.sql +++ b/src/test/regress/sql/create_index.sql @@ -693,9 +693,9 @@ DROP TABLE onek_with_null; EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); EXPLAIN (COSTS OFF) SELECT count(*) FROM tenk1 -- 2.17.0 --VV4b6MQE+OnNyhkM-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v5 2/2] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, a correlated bitmap which accesses pages across a small portion of the table should have a cost estimate much less than an uncorrelated scan (like modulus) across the entire length of the table, the latter having a high component of random access. Note, Tom points out that there are cases where a column could be tightly-"clumped" without being highly-ordered. Since we have correlation already, we use that until such time as someone implements a new statistic for clumpiness. This patch only intends to make costing of bitmap heap scan on par with the same cost of index scan without bitmap. --- .../postgres_fdw/expected/postgres_fdw.out | 15 +-- src/backend/optimizer/path/costsize.c | 94 +++++++++++++++---- src/backend/optimizer/path/indxpath.c | 10 +- src/include/nodes/pathnodes.h | 3 + src/include/optimizer/cost.h | 2 +- src/test/regress/expected/create_index.out | 16 ++-- src/test/regress/expected/identity.out | 2 +- src/test/regress/expected/join.out | 42 +++++---- src/test/regress/expected/plancache.out | 24 +++-- src/test/regress/expected/select.out | 16 ++-- src/test/regress/sql/create_index.sql | 8 +- src/test/regress/sql/identity.sql | 2 +- 12 files changed, 154 insertions(+), 80 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 62c2697920..22d06725c2 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -2269,11 +2269,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f -> Foreign Scan on public.ft1 Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.* Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE - -> Materialize + -> Sort Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* + Sort Key: ft2.c1 -> Foreign Scan on public.ft2 Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* - Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE + Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE -> Sort Output: ft4.c1, ft4.c2, ft4.c3, ft4.* Sort Key: ft4.c1 @@ -2288,7 +2289,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4" FOR UPDATE -> Index Scan using local_tbl_pkey on public.local_tbl Output: local_tbl.c1, local_tbl.c2, local_tbl.c3, local_tbl.ctid -(47 rows) +(48 rows) SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1 AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE; @@ -3330,10 +3331,12 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Sort Key: t1.c2 -> Nested Loop Output: t1.c2, qry.sum - -> Index Scan using t1_pkey on "S 1"."T 1" t1 + -> Bitmap Heap Scan on "S 1"."T 1" t1 Output: t1."C 1", t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8 - Index Cond: (t1."C 1" < 100) + Recheck Cond: (t1."C 1" < 100) Filter: (t1.c2 < 3) + -> Bitmap Index Scan on t1_pkey + Index Cond: (t1."C 1" < 100) -> Subquery Scan on qry Output: qry.sum, t2.c1 Filter: ((t1.c2 * 2) = qry.sum) @@ -3341,7 +3344,7 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Output: (sum((t2.c1 + t1."C 1"))), t2.c1 Relations: Aggregate on (public.ft2 t2) Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM "S 1"."T 1" GROUP BY 2 -(16 rows) +(18 rows) select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and t1."C 1" < 100 order by 1; c2 | sum diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index bdc23a075f..9cd314f0b5 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -550,11 +550,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a bitmap scan + * can't start until the index scan completes, so only cares about its + * total cost. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -989,12 +991,31 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + double cost_per_page_corr; + /* + * Interpolate based on pages_fetched and correlation from seq_page_cost to rand_page_cost. + * A highly correlated bitmap scan 1) likely reads fewer pages (handled in + * compute_bitmap_pages); and, 2) at higher "density" (more sequential). + */ cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + cost_per_page_corr = spc_random_page_cost - + (spc_random_page_cost - spc_seq_page_cost) + * (correlation*correlation); + + /* + * We expect sequential reads and low cost_per_page when *either* + * T is high or correlation is high. + */ + cost_per_page = Min(cost_per_page,cost_per_page_corr); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1038,15 +1059,18 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; - *selec = ((IndexPath *) path)->indexselectivity; + if (selec) + *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) + *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1059,12 +1083,18 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) else if (IsA(path, BitmapAndPath)) { *cost = path->total_cost; - *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; - *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1087,8 +1117,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1100,22 +1131,31 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec <= minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1131,8 +1171,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1145,23 +1186,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec >= maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5513,8 +5563,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5523,7 +5576,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5537,7 +5590,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..8ace2952e8 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1464,11 +1464,9 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) /* duplicate clauseids, keep the cheaper one */ Cost ncost; Cost ocost; - Selectivity nselec; - Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, NULL, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, NULL, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1580,8 +1578,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 0ceb809644..d407f85e6b 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1183,6 +1183,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1263,6 +1264,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1276,6 +1278,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index cb012ba198..7d5edb5411 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index ae95bb38a6..f2bc6bb214 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -1795,24 +1795,23 @@ DROP TABLE onek_with_null; -- -- Check bitmap index path planning -- +SET cpu_operator_cost=0; EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); + QUERY PLAN +------------------------------------------------------------------------------------------------- Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42))) + Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 42))) -> BitmapOr -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 3)) -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) +(7 rows) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 ---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+--------- 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx @@ -1843,6 +1842,7 @@ SELECT count(*) FROM tenk1 10 (1 row) +RESET cpu_operator_cost; -- -- Check behavior with duplicate index column contents -- diff --git a/src/test/regress/expected/identity.out b/src/test/regress/expected/identity.out index 7322b28765..b90d634b53 100644 --- a/src/test/regress/expected/identity.out +++ b/src/test/regress/expected/identity.out @@ -316,7 +316,7 @@ SELECT * FROM itest6; 102 | (3 rows) -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2; table_name | column_name | is_identity | identity_generation ------------+-------------+-------------+--------------------- itest6 | a | YES | BY DEFAULT diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 761376b007..80cfab8e88 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -3144,22 +3144,26 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------------ Nested Loop -> Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Nested Loop - -> Seq Scan on onerow - -> Seq Scan on onerow onerow_1 - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Nested Loop + -> Seq Scan on onerow + -> Seq Scan on onerow onerow_1 -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -> Seq Scan on int4_tbl i1 Filter: (f1 = 0) -(13 rows) +(17 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 @@ -3212,18 +3216,22 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------ Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Seq Scan on int4_tbl i1 - Filter: (f1 = 0) - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Seq Scan on int4_tbl i1 + Filter: (f1 = 0) -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -(9 rows) +(13 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 diff --git a/src/test/regress/expected/plancache.out b/src/test/regress/expected/plancache.out index 7d289b8c5e..40c243be9f 100644 --- a/src/test/regress/expected/plancache.out +++ b/src/test/regress/expected/plancache.out @@ -296,12 +296,14 @@ explain (costs off) execute test_mode_pp(2); -- force generic plan set plan_cache_mode to force_generic_plan; explain (costs off) execute test_mode_pp(2); - QUERY PLAN ------------------------------ + QUERY PLAN +-------------------------------------------------- Aggregate - -> Seq Scan on test_mode - Filter: (a = $1) -(3 rows) + -> Bitmap Heap Scan on test_mode + Recheck Cond: (a = $1) + -> Bitmap Index Scan on test_mode_a_idx + Index Cond: (a = $1) +(5 rows) -- get to generic plan by 5 executions set plan_cache_mode to auto; @@ -337,12 +339,14 @@ execute test_mode_pp(1); -- 5x -- we should now get a really bad plan explain (costs off) execute test_mode_pp(2); - QUERY PLAN ------------------------------ + QUERY PLAN +-------------------------------------------------- Aggregate - -> Seq Scan on test_mode - Filter: (a = $1) -(3 rows) + -> Bitmap Heap Scan on test_mode + Recheck Cond: (a = $1) + -> Bitmap Index Scan on test_mode_a_idx + Index Cond: (a = $1) +(5 rows) -- but we can force a custom plan set plan_cache_mode to force_custom_plan; diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out index c441049f41..675bf632d0 100644 --- a/src/test/regress/expected/select.out +++ b/src/test/regress/expected/select.out @@ -861,17 +861,13 @@ RESET enable_indexscan; explain (costs off) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; - QUERY PLAN --------------------------------------------------------------------------------- + QUERY PLAN +--------------------------------------------- Bitmap Heap Scan on onek2 - Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0)) - Filter: (stringu1 < 'B'::name) - -> BitmapOr - -> Bitmap Index Scan on onek2_u2_prtl - Index Cond: (unique2 = 11) - -> Bitmap Index Scan on onek2_u1_prtl - Index Cond: (unique1 = 0) -(8 rows) + Recheck Cond: (stringu1 < 'B'::name) + Filter: ((unique2 = 11) OR (unique1 = 0)) + -> Bitmap Index Scan on onek2_u2_prtl +(4 rows) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql index c3246cb296..7e09fc895e 100644 --- a/src/test/regress/sql/create_index.sql +++ b/src/test/regress/sql/create_index.sql @@ -691,11 +691,13 @@ DROP TABLE onek_with_null; -- Check bitmap index path planning -- +SET cpu_operator_cost=0; + EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); EXPLAIN (COSTS OFF) SELECT count(*) FROM tenk1 @@ -703,6 +705,8 @@ SELECT count(*) FROM tenk1 SELECT count(*) FROM tenk1 WHERE hundred = 42 AND (thousand = 42 OR thousand = 99); +RESET cpu_operator_cost; + -- -- Check behavior with duplicate index column contents -- diff --git a/src/test/regress/sql/identity.sql b/src/test/regress/sql/identity.sql index b4cdd21bdd..5814197e64 100644 --- a/src/test/regress/sql/identity.sql +++ b/src/test/regress/sql/identity.sql @@ -191,7 +191,7 @@ INSERT INTO itest6 DEFAULT VALUES; INSERT INTO itest6 DEFAULT VALUES; SELECT * FROM itest6; -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2; ALTER TABLE itest6 ALTER COLUMN b SET INCREMENT BY 2; -- fail, not identity -- 2.17.0 --16qp2B0xu0fRvRD7-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v4 2/2] Use correlation statistic in costing bitmap scans.. @ 2019-01-01 22:17 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Justin Pryzby @ 2019-01-01 22:17 UTC (permalink / raw) Same as for an index scan, a correlated bitmap which accesses pages across a small portion of the table should have a cost estimate much less than an uncorrelated scan (like modulus) across the entire length of the table, the latter having a high component of random access. Note, Tom points out that there are cases where a column could be tightly-"clumped" without being highly-ordered. Since we have correlation already, we use that until such time as someone implements a new statistic for clumpiness. This patch only intends to make costing of bitmap heap scan on par with the same cost of index scan without bitmap. --- contrib/postgres_fdw/expected/postgres_fdw.out | 15 ++-- src/backend/optimizer/path/costsize.c | 94 +++++++++++++++++++++----- src/backend/optimizer/path/indxpath.c | 10 ++- src/include/nodes/pathnodes.h | 3 + src/include/optimizer/cost.h | 2 +- src/test/regress/expected/create_index.out | 16 ++--- src/test/regress/expected/identity.out | 2 +- src/test/regress/expected/join.out | 42 +++++++----- src/test/regress/expected/select.out | 16 ++--- src/test/regress/sql/create_index.sql | 8 ++- src/test/regress/sql/identity.sql | 2 +- 11 files changed, 140 insertions(+), 70 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 0912d6c..732e66c 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -2269,11 +2269,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f -> Foreign Scan on public.ft1 Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.* Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE - -> Materialize + -> Sort Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* + Sort Key: ft2.c1 -> Foreign Scan on public.ft2 Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.* - Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE + Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE -> Sort Output: ft4.c1, ft4.c2, ft4.c3, ft4.* Sort Key: ft4.c1 @@ -2288,7 +2289,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4" FOR UPDATE -> Index Scan using local_tbl_pkey on public.local_tbl Output: local_tbl.c1, local_tbl.c2, local_tbl.c3, local_tbl.ctid -(47 rows) +(48 rows) SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1 AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE; @@ -3330,10 +3331,12 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Sort Key: t1.c2 -> Nested Loop Output: t1.c2, qry.sum - -> Index Scan using t1_pkey on "S 1"."T 1" t1 + -> Bitmap Heap Scan on "S 1"."T 1" t1 Output: t1."C 1", t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8 - Index Cond: (t1."C 1" < 100) + Recheck Cond: (t1."C 1" < 100) Filter: (t1.c2 < 3) + -> Bitmap Index Scan on t1_pkey + Index Cond: (t1."C 1" < 100) -> Subquery Scan on qry Output: qry.sum, t2.c1 Filter: ((t1.c2 * 2) = qry.sum) @@ -3341,7 +3344,7 @@ select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum fr Output: (sum((t2.c1 + t1."C 1"))), t2.c1 Relations: Aggregate on (public.ft2 t2) Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM "S 1"."T 1" GROUP BY 2 -(16 rows) +(18 rows) select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and t1."C 1" < 100 order by 1; c2 | sum diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index bdc23a0..9cd314f 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -550,11 +550,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, /* * Save amcostestimate's results for possible use in bitmap scan planning. - * We don't bother to save indexStartupCost or indexCorrelation, because a - * bitmap scan doesn't care about either. + * We don't bother to save indexStartupCost, because a bitmap scan + * can't start until the index scan completes, so only cares about its + * total cost. */ path->indextotalcost = indexTotalCost; path->indexselectivity = indexSelectivity; + path->indexCorrelation = indexCorrelation; /* all costs for touching index itself included here */ startup_cost += indexStartupCost; @@ -989,12 +991,31 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, * appropriate to charge spc_seq_page_cost apiece. The effect is * nonlinear, too. For lack of a better idea, interpolate like this to * determine the cost per page. + * Note this works at PAGE granularity, so even if we read 1% of a + * table's tuples, if we have to read nearly every page, it should be + * considered sequential. */ - if (pages_fetched >= 2.0) + if (pages_fetched >= 2.0) { + double correlation = ((IndexPath *)bitmapqual)->indexCorrelation; + double cost_per_page_corr; + /* + * Interpolate based on pages_fetched and correlation from seq_page_cost to rand_page_cost. + * A highly correlated bitmap scan 1) likely reads fewer pages (handled in + * compute_bitmap_pages); and, 2) at higher "density" (more sequential). + */ cost_per_page = spc_random_page_cost - (spc_random_page_cost - spc_seq_page_cost) * sqrt(pages_fetched / T); - else + cost_per_page_corr = spc_random_page_cost - + (spc_random_page_cost - spc_seq_page_cost) + * (correlation*correlation); + + /* + * We expect sequential reads and low cost_per_page when *either* + * T is high or correlation is high. + */ + cost_per_page = Min(cost_per_page,cost_per_page_corr); + } else cost_per_page = spc_random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -1038,15 +1059,18 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel, /* * cost_bitmap_tree_node - * Extract cost and selectivity from a bitmap tree node (index/and/or) + * Extract cost, selectivity, and correlation from a bitmap tree node (index/and/or) */ void -cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) +cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation) { if (IsA(path, IndexPath)) { *cost = ((IndexPath *) path)->indextotalcost; - *selec = ((IndexPath *) path)->indexselectivity; + if (selec) + *selec = ((IndexPath *) path)->indexselectivity; + if (correlation) + *correlation = ((IndexPath *) path)->indexCorrelation; /* * Charge a small amount per retrieved tuple to reflect the costs of @@ -1059,12 +1083,18 @@ cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) else if (IsA(path, BitmapAndPath)) { *cost = path->total_cost; - *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapAndPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapAndPath *) path)->bitmapcorrelation; } else if (IsA(path, BitmapOrPath)) { *cost = path->total_cost; - *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (selec) + *selec = ((BitmapOrPath *) path)->bitmapselectivity; + if (correlation) + *correlation = ((BitmapOrPath *) path)->bitmapcorrelation; } else { @@ -1087,8 +1117,9 @@ void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, minsubselec; ListCell *l; + double correlation; /* * We estimate AND selectivity on the assumption that the inputs are @@ -1100,22 +1131,31 @@ cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root) * definitely too simplistic? */ totalCost = 0.0; - selec = 1.0; + minsubselec = selec = 1.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec *= subselec; + /* For an AND node, use the correlation of its most-selective subpath */ + if (subselec <= minsubselec) { + correlation = subcorrelation; + minsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = selec; + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -1131,8 +1171,9 @@ void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) { Cost totalCost; - Selectivity selec; + Selectivity selec, maxsubselec; ListCell *l; + double correlation; /* * We estimate OR selectivity on the assumption that the inputs are @@ -1145,23 +1186,32 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root) * optimized out when the inputs are BitmapIndexScans. */ totalCost = 0.0; - selec = 0.0; + maxsubselec = selec = 0.0; + correlation = 0; foreach(l, path->bitmapquals) { Path *subpath = (Path *) lfirst(l); Cost subCost; Selectivity subselec; + double subcorrelation; - cost_bitmap_tree_node(subpath, &subCost, &subselec); + cost_bitmap_tree_node(subpath, &subCost, &subselec, &subcorrelation); selec += subselec; + /* For an OR node, use the correlation of its least-selective subpath */ + if (subselec >= maxsubselec) { + correlation = subcorrelation; + maxsubselec = subselec; + } + totalCost += subCost; if (l != list_head(path->bitmapquals) && !IsA(subpath, IndexPath)) totalCost += 100.0 * cpu_operator_cost; } path->bitmapselectivity = Min(selec, 1.0); + path->bitmapcorrelation = correlation; path->path.rows = 0; /* per above, not used */ path->path.startup_cost = totalCost; path->path.total_cost = totalCost; @@ -5513,8 +5563,11 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, { Cost indexTotalCost; Selectivity indexSelectivity; + double indexCorrelation; double T; - double pages_fetched; + double pages_fetched, + pages_fetchedMIN, + pages_fetchedMAX; double tuples_fetched; double heap_pages; long maxentries; @@ -5523,7 +5576,7 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * Fetch total cost of obtaining the bitmap, as well as its total * selectivity. */ - cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity, &indexCorrelation); /* * Estimate number of main-table pages fetched. @@ -5537,7 +5590,12 @@ compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, * the same as the Mackert and Lohman formula for the case T <= b (ie, no * re-reads needed). */ - pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + pages_fetchedMAX = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched); + + /* pages_fetchedMIN is for the perfectly correlated case (csquared=1) */ + pages_fetchedMIN = ceil(indexSelectivity * (double) baserel->pages); + + pages_fetched = pages_fetchedMAX + indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX); /* * Calculate the number of pages fetched from the heap. Then based on diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272..8ace295 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1464,11 +1464,9 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths) /* duplicate clauseids, keep the cheaper one */ Cost ncost; Cost ocost; - Selectivity nselec; - Selectivity oselec; - cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec); - cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec); + cost_bitmap_tree_node(pathinfo->path, &ncost, NULL, NULL); + cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, NULL, NULL); if (ncost < ocost) pathinfoarray[i] = pathinfo; } @@ -1580,8 +1578,8 @@ path_usage_comparator(const void *a, const void *b) Selectivity aselec; Selectivity bselec; - cost_bitmap_tree_node(pa->path, &acost, &aselec); - cost_bitmap_tree_node(pb->path, &bcost, &bselec); + cost_bitmap_tree_node(pa->path, &acost, &aselec, NULL); + cost_bitmap_tree_node(pb->path, &bcost, &bselec, NULL); /* * If costs are the same, sort by selectivity. diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be19..19ddf5b 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1183,6 +1183,7 @@ typedef struct IndexPath ScanDirection indexscandir; Cost indextotalcost; Selectivity indexselectivity; + double indexCorrelation; } IndexPath; /* @@ -1263,6 +1264,7 @@ typedef struct BitmapAndPath Path path; List *bitmapquals; /* IndexPaths and BitmapOrPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapAndPath; /* @@ -1276,6 +1278,7 @@ typedef struct BitmapOrPath Path path; List *bitmapquals; /* IndexPaths and BitmapAndPaths */ Selectivity bitmapselectivity; + double bitmapcorrelation; } BitmapOrPath; /* diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index cb012ba..7d5edb5 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -79,7 +79,7 @@ extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *bas Path *bitmapqual, double loop_count); extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root); extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root); -extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec, double *correlation); extern void cost_tidscan(Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info); extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root, diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index 6446907..5bd8aae 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -1770,24 +1770,23 @@ DROP TABLE onek_with_null; -- -- Check bitmap index path planning -- +SET cpu_operator_cost=0; EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); + QUERY PLAN +------------------------------------------------------------------------------------------------- Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42))) + Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 42))) -> BitmapOr -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 1)) -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on tenk1_thous_tenthous Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) +(7 rows) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 ---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+--------- 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx @@ -1818,6 +1817,7 @@ SELECT count(*) FROM tenk1 10 (1 row) +RESET cpu_operator_cost; -- -- Check behavior with duplicate index column contents -- diff --git a/src/test/regress/expected/identity.out b/src/test/regress/expected/identity.out index 36a2393..2642740 100644 --- a/src/test/regress/expected/identity.out +++ b/src/test/regress/expected/identity.out @@ -316,7 +316,7 @@ SELECT * FROM itest6; 102 | (3 rows) -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2; table_name | column_name | is_identity | identity_generation ------------+-------------+-------------+--------------------- itest6 | a | YES | BY DEFAULT diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 761376b..80cfab8 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -3144,22 +3144,26 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------------ Nested Loop -> Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Nested Loop - -> Seq Scan on onerow - -> Seq Scan on onerow onerow_1 - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Nested Loop + -> Seq Scan on onerow + -> Seq Scan on onerow onerow_1 -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -> Seq Scan on int4_tbl i1 Filter: (f1 = 0) -(13 rows) +(17 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 @@ -3212,18 +3216,22 @@ select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from left join tenk1 t2 on (subq1.y1 = t2.unique1) where t1.unique2 < 42 and t1.stringu1 > t2.stringu2; - QUERY PLAN ------------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------ Nested Loop Join Filter: (t1.stringu1 > t2.stringu2) - -> Nested Loop - -> Seq Scan on int4_tbl i1 - Filter: (f1 = 0) - -> Index Scan using tenk1_unique2 on tenk1 t1 - Index Cond: ((unique2 = (11)) AND (unique2 < 42)) + -> Hash Join + Hash Cond: (t1.unique2 = (11)) + -> Bitmap Heap Scan on tenk1 t1 + Recheck Cond: (unique2 < 42) + -> Bitmap Index Scan on tenk1_unique2 + Index Cond: (unique2 < 42) + -> Hash + -> Seq Scan on int4_tbl i1 + Filter: (f1 = 0) -> Index Scan using tenk1_unique1 on tenk1 t2 Index Cond: (unique1 = (3)) -(9 rows) +(13 rows) select t1.unique2, t1.stringu1, t2.unique1, t2.stringu2 from tenk1 t1 diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out index c441049..675bf63 100644 --- a/src/test/regress/expected/select.out +++ b/src/test/regress/expected/select.out @@ -861,17 +861,13 @@ RESET enable_indexscan; explain (costs off) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; - QUERY PLAN --------------------------------------------------------------------------------- + QUERY PLAN +--------------------------------------------- Bitmap Heap Scan on onek2 - Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0)) - Filter: (stringu1 < 'B'::name) - -> BitmapOr - -> Bitmap Index Scan on onek2_u2_prtl - Index Cond: (unique2 = 11) - -> Bitmap Index Scan on onek2_u1_prtl - Index Cond: (unique1 = 0) -(8 rows) + Recheck Cond: (stringu1 < 'B'::name) + Filter: ((unique2 = 11) OR (unique1 = 0)) + -> Bitmap Index Scan on onek2_u2_prtl +(4 rows) select unique1, unique2 from onek2 where (unique2 = 11 or unique1 = 0) and stringu1 < 'B'; diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql index 3c0c1cd..6607a7b 100644 --- a/src/test/regress/sql/create_index.sql +++ b/src/test/regress/sql/create_index.sql @@ -666,11 +666,13 @@ DROP TABLE onek_with_null; -- Check bitmap index path planning -- +SET cpu_operator_cost=0; + EXPLAIN (COSTS OFF) SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); SELECT * FROM tenk1 - WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42); + WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 42); EXPLAIN (COSTS OFF) SELECT count(*) FROM tenk1 @@ -678,6 +680,8 @@ SELECT count(*) FROM tenk1 SELECT count(*) FROM tenk1 WHERE hundred = 42 AND (thousand = 42 OR thousand = 99); +RESET cpu_operator_cost; + -- -- Check behavior with duplicate index column contents -- diff --git a/src/test/regress/sql/identity.sql b/src/test/regress/sql/identity.sql index 4b03d24..a19b99b 100644 --- a/src/test/regress/sql/identity.sql +++ b/src/test/regress/sql/identity.sql @@ -191,7 +191,7 @@ INSERT INTO itest6 DEFAULT VALUES; INSERT INTO itest6 DEFAULT VALUES; SELECT * FROM itest6; -SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6'; +SELECT table_name, column_name, is_identity, identity_generation FROM information_schema.columns WHERE table_name = 'itest6' ORDER BY 1,2; ALTER TABLE itest6 ALTER COLUMN b SET INCREMENT BY 2; -- fail, not identity -- 2.7.4 --gBdJBemW82xJqIAr-- ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v3 2/2] Error out if one iteration of non-direct DML affects more than one row on the foreign server @ 2025-07-18 14:52 Jehan-Guillaume de Rorthais <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Jehan-Guillaume de Rorthais @ 2025-07-18 14:52 UTC (permalink / raw) When a foreign table points to a partitioned table or an inheritance parent on the foreign server, a non-direct DML can affect multiple rows when only one row is intended to be affected. This happens because postgres_fdw uses only ctid to identify a row to work on. Though ctid uniquely identifies a row in a single table, in a partitioned table or in an inheritance hierarchy, there can be be multiple rows, in different partitions, with the same ctid. So a DML statement sent to the foreign server by postgres_fdw ends up affecting more than one rows, only one of which is intended to be affected. In such a case it's good to throw an error instead of corrupting remote database with unwanted UPDATE/DELETEs. Subsequent commits will try to fix this situation. Author: Ashutosh Bapat <[email protected]> Author: Kyotaro Horiguchi <[email protected]> Rebased by Jehan-Guillaume de Rorthais <[email protected]> --- .../postgres_fdw/expected/postgres_fdw.out | 26 ++++++++------ contrib/postgres_fdw/postgres_fdw.c | 36 +++++++++++++++---- 2 files changed, 46 insertions(+), 16 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 62019eaa881..b0ef54a2889 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -8984,10 +8984,11 @@ UPDATE fa SET aa = (CASE WHEN random() <= 1 THEN 'zzzz' ELSE NULL END) WHERE aa (5 rows) UPDATE fa SET aa = (CASE WHEN random() <= 1 THEN 'zzzz' ELSE NULL END) WHERE aa = 'aaa'; +ERROR: foreign server affected 2 rows when only one was expected SELECT tableoid::regclass, ctid, * FROM fa; - tableoid | ctid | aa -----------+-------+------ - fa | (0,2) | zzzz + tableoid | ctid | aa +----------+-------+----- + fa | (0,1) | aaa fa | (0,1) | bbb (2 rows) @@ -9008,11 +9009,13 @@ DELETE FROM fa WHERE aa = (CASE WHEN random() <= 1 THEN 'aaa' ELSE 'bbb' END); (6 rows) DELETE FROM fa WHERE aa = (CASE WHEN random() <= 1 THEN 'aaa' ELSE 'bbb' END); +ERROR: foreign server affected 2 rows when only one was expected SELECT tableoid::regclass, ctid, * FROM fa; - tableoid | ctid | aa + tableoid | ctid | aa ----------+-------+----- + fa | (0,1) | aaa fa | (0,1) | bbb -(1 row) +(2 rows) -- cleanup DROP FOREIGN TABLE fa; @@ -9048,10 +9051,11 @@ UPDATE fplt SET b = (CASE WHEN random() <= 1 THEN 10 ELSE 20 END) WHERE a = 1; (5 rows) UPDATE fplt SET b = (CASE WHEN random() <= 1 THEN 10 ELSE 20 END) WHERE a = 1; +ERROR: foreign server affected 2 rows when only one was expected SELECT tableoid::regclass, ctid, * FROM fplt; - tableoid | ctid | a | b -----------+-------+---+---- - fplt | (0,2) | 1 | 10 + tableoid | ctid | a | b +----------+-------+---+--- + fplt | (0,1) | 1 | 1 fplt | (0,1) | 2 | 2 (2 rows) @@ -9071,11 +9075,13 @@ DELETE FROM fplt WHERE a = (CASE WHEN random() <= 1 THEN 1 ELSE 10 END); (6 rows) DELETE FROM fplt WHERE a = (CASE WHEN random() <= 1 THEN 1 ELSE 10 END); +ERROR: foreign server affected 2 rows when only one was expected SELECT tableoid::regclass, ctid, * FROM fplt; tableoid | ctid | a | b ----------+-------+---+--- - fplt | (0,1) | 2 | 2 -(1 row) + fplt | (0,1) | 1 | 1 + fplt | (0,1) | 2 | 2 +(2 rows) DROP TABLE plt; DROP FOREIGN TABLE fplt; diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index e0a34b27c7c..09c87d0e5d8 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -4132,7 +4132,8 @@ execute_foreign_modify(EState *estate, ItemPointer ctid = NULL; const char **p_values; PGresult *res; - int n_rows; + int n_rows_returned; + int n_rows_affected; StringInfoData sql; /* The operation should be INSERT, UPDATE, or DELETE */ @@ -4213,27 +4214,50 @@ execute_foreign_modify(EState *estate, pgfdw_report_error(ERROR, res, fmstate->conn, true, fmstate->query); /* Check number of rows affected, and fetch RETURNING tuple if any */ + n_rows_affected = atoi(PQcmdTuples(res)); if (fmstate->has_returning) { Assert(*numSlots == 1); - n_rows = PQntuples(res); - if (n_rows > 0) + n_rows_returned = PQntuples(res); + if (n_rows_returned > 0) store_returning_result(fmstate, slots[0], res); + + // FIXME: shouldn't we check the max number of rows returned is one? } else - n_rows = atoi(PQcmdTuples(res)); + n_rows_returned = 0; /* And clean up */ PQclear(res); MemoryContextReset(fmstate->temp_cxt); - *numSlots = n_rows; + /* + * UPDATE & DELETE command can only affect one row, make sure this contract + * is respected. + * CMD_INSERT can insert multiple row when called from ForeignBatchInsert. + */ + if (operation != CMD_INSERT) + { + /* No rows should be returned if no rows were affected */ + if (n_rows_affected == 0 && n_rows_returned != 0) + elog(ERROR, "foreign server returned %d rows when no row was affected", + n_rows_returned); + + /* ERROR if more than one row was updated on the remote end */ + if (n_rows_affected > 1) + ereport(ERROR, + (errcode (ERRCODE_FDW_ERROR), /* XXX */ + errmsg ("foreign server affected %d rows when only one was expected", + n_rows_affected))); + } + + *numSlots = n_rows_returned; /* * Return NULL if nothing was inserted/updated/deleted on the remote end */ - return (n_rows > 0) ? slots : NULL; + return (n_rows_affected > 0) ? slots : NULL; } /* -- 2.50.0 --MP_/4ZRYdF7Ah.pt5w65PuZdaPz-- ^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2025-07-18 14:52 UTC | newest] Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2019-01-01 22:17 [PATCH v3] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v1] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v2] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v2] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v6 2/2] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v5 2/2] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2019-01-01 22:17 [PATCH v4 2/2] Use correlation statistic in costing bitmap scans.. Justin Pryzby <[email protected]> 2025-07-18 14:52 [PATCH v3 2/2] Error out if one iteration of non-direct DML affects more than one row on the foreign server Jehan-Guillaume de Rorthais <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox