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 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 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 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 v20 1/8] Row pattern recognition patch for raw parser. @ 2024-05-24 02:26 Tatsuo Ishii <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Tatsuo Ishii @ 2024-05-24 02:26 UTC (permalink / raw) --- src/backend/parser/gram.y | 222 ++++++++++++++++++++++++++++++-- src/include/nodes/parsenodes.h | 67 ++++++++++ src/include/parser/kwlist.h | 9 ++ src/include/parser/parse_node.h | 1 + 4 files changed, 288 insertions(+), 11 deletions(-) diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index 4d582950b7..ef6f25b2f8 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -679,6 +679,21 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); json_object_constructor_null_clause_opt json_array_constructor_null_clause_opt +%type <target> row_pattern_measure_item + row_pattern_definition +%type <node> opt_row_pattern_common_syntax + opt_row_pattern_skip_to + row_pattern_subset_item + row_pattern_term +%type <list> opt_row_pattern_measures + row_pattern_measure_list + row_pattern_definition_list + opt_row_pattern_subset_clause + row_pattern_subset_list + row_pattern_subset_rhs + row_pattern +%type <boolean> opt_row_pattern_initial_or_seek + first_or_last /* * Non-keyword token types. These are hard-wired into the "flex" lexer. @@ -722,7 +737,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE DATA_P DATABASE DAY_P DEALLOCATE DEC DECIMAL_P DECLARE DEFAULT DEFAULTS - DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC + DEFERRABLE DEFERRED DEFINE DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC DETACH DICTIONARY DISABLE_P DISCARD DISTINCT DO DOCUMENT_P DOMAIN_P DOUBLE_P DROP @@ -738,7 +753,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); HANDLER HAVING HEADER_P HOLD HOUR_P IDENTITY_P IF_P ILIKE IMMEDIATE IMMUTABLE IMPLICIT_P IMPORT_P IN_P INCLUDE - INCLUDING INCREMENT INDENT INDEX INDEXES INHERIT INHERITS INITIALLY INLINE_P + INCLUDING INCREMENT INDENT INDEX INDEXES INHERIT INHERITS INITIAL INITIALLY INLINE_P INNER_P INOUT INPUT_P INSENSITIVE INSERT INSTEAD INT_P INTEGER INTERSECT INTERVAL INTO INVOKER IS ISNULL ISOLATION @@ -751,7 +766,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); LEADING LEAKPROOF LEAST LEFT LEVEL LIKE LIMIT LISTEN LOAD LOCAL LOCALTIME LOCALTIMESTAMP LOCATION LOCK_P LOCKED LOGGED - MAPPING MATCH MATCHED MATERIALIZED MAXVALUE MERGE MERGE_ACTION METHOD + MAPPING MATCH MATCHED MATERIALIZED MAXVALUE MEASURES MERGE MERGE_ACTION METHOD MINUTE_P MINVALUE MODE MONTH_P MOVE NAME_P NAMES NATIONAL NATURAL NCHAR NESTED NEW NEXT NFC NFD NFKC NFKD NO @@ -763,8 +778,8 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); ORDER ORDINALITY OTHERS OUT_P OUTER_P OVER OVERLAPS OVERLAY OVERRIDING OWNED OWNER - PARALLEL PARAMETER PARSER PARTIAL PARTITION PARTITIONS PASSING PASSWORD PATH - PLACING PLAN PLANS POLICY + PARALLEL PARAMETER PARSER PARTIAL PARTITION PARTITIONS PASSING PASSWORD PAST + PATH PATTERN_P PERIOD PERMUTE PLACING PLAN PLANS POLICY POSITION PRECEDING PRECISION PRESERVE PREPARE PREPARED PRIMARY PRIOR PRIVILEGES PROCEDURAL PROCEDURE PROCEDURES PROGRAM PUBLICATION @@ -775,12 +790,13 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); RESET RESTART RESTRICT RETURN RETURNING RETURNS REVOKE RIGHT ROLE ROLLBACK ROLLUP ROUTINE ROUTINES ROW ROWS RULE - SAVEPOINT SCALAR SCHEMA SCHEMAS SCROLL SEARCH SECOND_P SECURITY SELECT + SAVEPOINT SCALAR SCHEMA SCHEMAS SCROLL SEARCH SECOND_P SECURITY SEEK SELECT SEQUENCE SEQUENCES + SERIALIZABLE SERVER SESSION SESSION_USER SET SETS SETOF SHARE SHOW SIMILAR SIMPLE SKIP SMALLINT SNAPSHOT SOME SPLIT SOURCE SQL_P STABLE STANDALONE_P START STATEMENT STATISTICS STDIN STDOUT STORAGE STORED STRICT_P STRING_P STRIP_P - SUBSCRIPTION SUBSTRING SUPPORT SYMMETRIC SYSID SYSTEM_P SYSTEM_USER + SUBSCRIPTION SUBSET SUBSTRING SUPPORT SYMMETRIC SYSID SYSTEM_P SYSTEM_USER TABLE TABLES TABLESAMPLE TABLESPACE TARGET TEMP TEMPLATE TEMPORARY TEXT_P THEN TIES TIME TIMESTAMP TO TRAILING TRANSACTION TRANSFORM @@ -889,6 +905,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); %nonassoc UNBOUNDED NESTED /* ideally would have same precedence as IDENT */ %nonassoc IDENT PARTITION RANGE ROWS GROUPS PRECEDING FOLLOWING CUBE ROLLUP SET KEYS OBJECT_P SCALAR VALUE_P WITH WITHOUT PATH + MEASURES AFTER INITIAL SEEK PATTERN_P %left Op OPERATOR /* multi-character ops and user-defined operators */ %left '+' '-' %left '*' '/' '%' @@ -16287,7 +16304,8 @@ over_clause: OVER window_specification ; window_specification: '(' opt_existing_window_name opt_partition_clause - opt_sort_clause opt_frame_clause ')' + opt_sort_clause opt_row_pattern_measures opt_frame_clause + opt_row_pattern_common_syntax ')' { WindowDef *n = makeNode(WindowDef); @@ -16295,10 +16313,12 @@ window_specification: '(' opt_existing_window_name opt_partition_clause n->refname = $2; n->partitionClause = $3; n->orderClause = $4; + n->rowPatternMeasures = $5; /* copy relevant fields of opt_frame_clause */ - n->frameOptions = $5->frameOptions; - n->startOffset = $5->startOffset; - n->endOffset = $5->endOffset; + n->frameOptions = $6->frameOptions; + n->startOffset = $6->startOffset; + n->endOffset = $6->endOffset; + n->rpCommonSyntax = (RPCommonSyntax *)$7; n->location = @1; $$ = n; } @@ -16322,6 +16342,31 @@ opt_partition_clause: PARTITION BY expr_list { $$ = $3; } | /*EMPTY*/ { $$ = NIL; } ; +/* + * ROW PATTERN_P MEASURES + */ +opt_row_pattern_measures: MEASURES row_pattern_measure_list { $$ = $2; } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_measure_list: + row_pattern_measure_item + { $$ = list_make1($1); } + | row_pattern_measure_list ',' row_pattern_measure_item + { $$ = lappend($1, $3); } + ; + +row_pattern_measure_item: + a_expr AS ColLabel + { + $$ = makeNode(ResTarget); + $$->name = $3; + $$->indirection = NIL; + $$->val = (Node *) $1; + $$->location = @1; + } + ; + /* * For frame clauses, we return a WindowDef, but only some fields are used: * frameOptions, startOffset, and endOffset. @@ -16481,6 +16526,143 @@ opt_window_exclusion_clause: | /*EMPTY*/ { $$ = 0; } ; +opt_row_pattern_common_syntax: +opt_row_pattern_skip_to opt_row_pattern_initial_or_seek + PATTERN_P '(' row_pattern ')' + opt_row_pattern_subset_clause + DEFINE row_pattern_definition_list + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ((RPCommonSyntax *)$1)->rpSkipTo; + n->rpSkipVariable = ((RPCommonSyntax *)$1)->rpSkipVariable; + n->initial = $2; + n->rpPatterns = $5; + n->rpSubsetClause = $7; + n->rpDefs = $9; + $$ = (Node *) n; + } + | /*EMPTY*/ { $$ = NULL; } + ; + +opt_row_pattern_skip_to: + AFTER MATCH SKIP TO NEXT ROW + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_NEXT_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + | AFTER MATCH SKIP PAST LAST_P ROW + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_PAST_LAST_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + | AFTER MATCH SKIP TO first_or_last ColId + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = $5? ST_FIRST_VARIABLE : ST_LAST_VARIABLE; + n->rpSkipVariable = $6; + $$ = (Node *) n; + } +/* + | AFTER MATCH SKIP TO LAST_P ColId %prec LAST_P + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_LAST_VARIABLE; + n->rpSkipVariable = $6; + $$ = n; + } + | AFTER MATCH SKIP TO ColId + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_VARIABLE; + n->rpSkipVariable = $5; + $$ = n; + } +*/ + | /*EMPTY*/ + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + /* temporary set default to ST_NEXT_ROW */ + n->rpSkipTo = ST_PAST_LAST_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + ; + +first_or_last: + FIRST_P { $$ = true; } + | LAST_P { $$ = false; } + ; + +opt_row_pattern_initial_or_seek: + INITIAL { $$ = true; } + | SEEK + { + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("SEEK is not supported"), + errhint("Use INITIAL."), + parser_errposition(@1))); + } + | /*EMPTY*/ { $$ = true; } + ; + +row_pattern: + row_pattern_term { $$ = list_make1($1); } + | row_pattern row_pattern_term { $$ = lappend($1, $2); } + ; + +row_pattern_term: + ColId { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "", (Node *)makeString($1), NULL, @1); } + | ColId '*' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "*", (Node *)makeString($1), NULL, @1); } + | ColId '+' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "+", (Node *)makeString($1), NULL, @1); } + | ColId '?' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "?", (Node *)makeString($1), NULL, @1); } + ; + +opt_row_pattern_subset_clause: + SUBSET row_pattern_subset_list { $$ = $2; } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_subset_list: + row_pattern_subset_item { $$ = list_make1($1); } + | row_pattern_subset_list ',' row_pattern_subset_item { $$ = lappend($1, $3); } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_subset_item: ColId '=' '(' row_pattern_subset_rhs ')' + { + RPSubsetItem *n = makeNode(RPSubsetItem); + n->name = $1; + n->rhsVariable = $4; + $$ = (Node *) n; + } + ; + +row_pattern_subset_rhs: + ColId { $$ = list_make1(makeStringConst($1, @1)); } + | row_pattern_subset_rhs ',' ColId { $$ = lappend($1, makeStringConst($3, @1)); } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_definition_list: + row_pattern_definition { $$ = list_make1($1); } + | row_pattern_definition_list ',' row_pattern_definition { $$ = lappend($1, $3); } + ; + +row_pattern_definition: + ColId AS a_expr + { + $$ = makeNode(ResTarget); + $$->name = $1; + $$->indirection = NIL; + $$->val = (Node *) $3; + $$->location = @1; + } + ; /* * Supporting nonterminals for expressions. @@ -17691,6 +17873,7 @@ unreserved_keyword: | INDEXES | INHERIT | INHERITS + | INITIAL | INLINE_P | INPUT_P | INSENSITIVE @@ -17719,6 +17902,7 @@ unreserved_keyword: | MATCHED | MATERIALIZED | MAXVALUE + | MEASURES | MERGE | METHOD | MINUTE_P @@ -17764,7 +17948,11 @@ unreserved_keyword: | PARTITIONS | PASSING | PASSWORD + | PAST | PATH + | PATTERN_P + | PERIOD + | PERMUTE | PLAN | PLANS | POLICY @@ -17817,6 +18005,7 @@ unreserved_keyword: | SEARCH | SECOND_P | SECURITY + | SEEK | SEQUENCE | SEQUENCES | SERIALIZABLE @@ -17845,6 +18034,7 @@ unreserved_keyword: | STRING_P | STRIP_P | SUBSCRIPTION + | SUBSET | SUPPORT | SYSID | SYSTEM_P @@ -18039,6 +18229,7 @@ reserved_keyword: | CURRENT_USER | DEFAULT | DEFERRABLE + | DEFINE | DESC | DISTINCT | DO @@ -18202,6 +18393,7 @@ bare_label_keyword: | DEFAULTS | DEFERRABLE | DEFERRED + | DEFINE | DEFINER | DELETE_P | DELIMITER @@ -18279,6 +18471,7 @@ bare_label_keyword: | INDEXES | INHERIT | INHERITS + | INITIAL | INITIALLY | INLINE_P | INNER_P @@ -18333,6 +18526,7 @@ bare_label_keyword: | MATCHED | MATERIALIZED | MAXVALUE + | MEASURES | MERGE | MERGE_ACTION | METHOD @@ -18390,7 +18584,11 @@ bare_label_keyword: | PARTITIONS | PASSING | PASSWORD + | PAST | PATH + | PATTERN_P + | PERIOD + | PERMUTE | PLACING | PLAN | PLANS @@ -18449,6 +18647,7 @@ bare_label_keyword: | SCROLL | SEARCH | SECURITY + | SEEK | SELECT | SEQUENCE | SEQUENCES @@ -18483,6 +18682,7 @@ bare_label_keyword: | STRING_P | STRIP_P | SUBSCRIPTION + | SUBSET | SUBSTRING | SUPPORT | SYMMETRIC diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index ddfed02db2..c8a2eed08f 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -550,6 +550,48 @@ typedef struct SortBy ParseLoc location; /* operator location, or -1 if none/unknown */ } SortBy; +/* + * AFTER MATCH row pattern skip to types in row pattern common syntax + */ +typedef enum RPSkipTo +{ + ST_NONE, /* AFTER MATCH omitted */ + ST_NEXT_ROW, /* SKIP TO NEXT ROW */ + ST_PAST_LAST_ROW, /* SKIP TO PAST LAST ROW */ + ST_FIRST_VARIABLE, /* SKIP TO FIRST variable name */ + ST_LAST_VARIABLE, /* SKIP TO LAST variable name */ + ST_VARIABLE /* SKIP TO variable name */ +} RPSkipTo; + +/* + * Row Pattern SUBSET clause item + */ +typedef struct RPSubsetItem +{ + NodeTag type; + char *name; /* Row Pattern SUBSET clause variable name */ + List *rhsVariable; /* Row Pattern SUBSET rhs variables (list of + * char *string) */ +} RPSubsetItem; + +/* + * RowPatternCommonSyntax - raw representation of row pattern common syntax + * + */ +typedef struct RPCommonSyntax +{ + NodeTag type; + RPSkipTo rpSkipTo; /* Row Pattern AFTER MATCH SKIP type */ + char *rpSkipVariable; /* Row Pattern Skip To variable name, if any */ + bool initial; /* true if <row pattern initial or seek> is + * initial */ + List *rpPatterns; /* PATTERN variables (list of A_Expr) */ + List *rpSubsetClause; /* row pattern subset clause (list of + * RPSubsetItem), if any */ + List *rpDefs; /* row pattern definitions clause (list of + * ResTarget) */ +} RPCommonSyntax; + /* * WindowDef - raw representation of WINDOW and OVER clauses * @@ -565,6 +607,9 @@ typedef struct WindowDef char *refname; /* referenced window name, if any */ List *partitionClause; /* PARTITION BY expression list */ List *orderClause; /* ORDER BY (list of SortBy) */ + List *rowPatternMeasures; /* row pattern measures (list of + * ResTarget) */ + RPCommonSyntax *rpCommonSyntax; /* row pattern common syntax */ int frameOptions; /* frame_clause options, see below */ Node *startOffset; /* expression for starting bound, if any */ Node *endOffset; /* expression for ending bound, if any */ @@ -1533,6 +1578,11 @@ typedef struct GroupingSet * the orderClause might or might not be copied (see copiedOrder); the framing * options are never copied, per spec. * + * "defineClause" is Row Pattern Recognition DEFINE clause (list of + * TargetEntry). TargetEntry.resname represents row pattern definition + * variable name. "patternVariable" and "patternRegexp" represents PATTERN + * clause. + * * The information relevant for the query jumbling is the partition clause * type and its bounds. */ @@ -1562,6 +1612,23 @@ typedef struct WindowClause Index winref; /* ID referenced by window functions */ /* did we copy orderClause from refname? */ bool copiedOrder pg_node_attr(query_jumble_ignore); + /* Row Pattern AFTER MACH SKIP clause */ + RPSkipTo rpSkipTo; /* Row Pattern Skip To type */ + char *rpSkipVariable; /* Row Pattern Skip To variable */ + bool initial; /* true if <row pattern initial or seek> is + * initial */ + /* Row Pattern DEFINE clause (list of TargetEntry) */ + List *defineClause; + /* Row Pattern DEFINE variable initial names (list of String) */ + List *defineInitial; + /* Row Pattern PATTERN variable name (list of String) */ + List *patternVariable; + + /* + * Row Pattern PATTERN regular expression quantifier ('+' or ''. list of + * String) + */ + List *patternRegexp; } WindowClause; /* diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h index f7fe834cf4..df49492629 100644 --- a/src/include/parser/kwlist.h +++ b/src/include/parser/kwlist.h @@ -129,6 +129,7 @@ PG_KEYWORD("default", DEFAULT, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("defaults", DEFAULTS, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("deferrable", DEFERRABLE, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("deferred", DEFERRED, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("define", DEFINE, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("definer", DEFINER, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delete", DELETE_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delimiter", DELIMITER, UNRESERVED_KEYWORD, BARE_LABEL) @@ -215,6 +216,7 @@ PG_KEYWORD("index", INDEX, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("indexes", INDEXES, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inherit", INHERIT, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inherits", INHERITS, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("initial", INITIAL, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("initially", INITIALLY, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inline", INLINE_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inner", INNER_P, TYPE_FUNC_NAME_KEYWORD, BARE_LABEL) @@ -273,6 +275,7 @@ PG_KEYWORD("match", MATCH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("matched", MATCHED, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("materialized", MATERIALIZED, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("maxvalue", MAXVALUE, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("measures", MEASURES, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("merge", MERGE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("merge_action", MERGE_ACTION, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("method", METHOD, UNRESERVED_KEYWORD, BARE_LABEL) @@ -338,7 +341,11 @@ PG_KEYWORD("partition", PARTITION, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("partitions", PARTITIONS, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("passing", PASSING, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("password", PASSWORD, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("past", PAST, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("path", PATH, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("pattern", PATTERN_P, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("period", PERIOD, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("permute", PERMUTE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("placing", PLACING, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("plan", PLAN, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("plans", PLANS, UNRESERVED_KEYWORD, BARE_LABEL) @@ -400,6 +407,7 @@ PG_KEYWORD("scroll", SCROLL, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("search", SEARCH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("second", SECOND_P, UNRESERVED_KEYWORD, AS_LABEL) PG_KEYWORD("security", SECURITY, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("seek", SEEK, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("select", SELECT, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("sequence", SEQUENCE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("sequences", SEQUENCES, UNRESERVED_KEYWORD, BARE_LABEL) @@ -434,6 +442,7 @@ PG_KEYWORD("strict", STRICT_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("string", STRING_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("strip", STRIP_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("subscription", SUBSCRIPTION, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("subset", SUBSET, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("substring", SUBSTRING, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("support", SUPPORT, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("symmetric", SYMMETRIC, RESERVED_KEYWORD, BARE_LABEL) diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h index 5b781d87a9..66935afff8 100644 --- a/src/include/parser/parse_node.h +++ b/src/include/parser/parse_node.h @@ -51,6 +51,7 @@ typedef enum ParseExprKind EXPR_KIND_WINDOW_FRAME_RANGE, /* window frame clause with RANGE */ EXPR_KIND_WINDOW_FRAME_ROWS, /* window frame clause with ROWS */ EXPR_KIND_WINDOW_FRAME_GROUPS, /* window frame clause with GROUPS */ + EXPR_KIND_RPR_DEFINE, /* DEFINE */ EXPR_KIND_SELECT_TARGET, /* SELECT target list item */ EXPR_KIND_INSERT_TARGET, /* INSERT target list item */ EXPR_KIND_UPDATE_SOURCE, /* UPDATE assignment source item */ -- 2.25.1 ----Next_Part(Fri_May_24_11_39_19_2024_763)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v20-0002-Row-pattern-recognition-patch-parse-analysis.patch" ^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2024-05-24 02:26 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 v1] 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]> 2019-01-01 22:17 [PATCH v3] 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]> 2024-05-24 02:26 [PATCH v20 1/8] Row pattern recognition patch for raw parser. Tatsuo Ishii <[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