On Fri, Nov 06, 2020 at 01:51:26PM +0000, Anastasia Lubennikova wrote:
> I wonder why this patch hangs so long without a review. Maybe it will help to
> move discussion forward, if you provide more examples of queries that can
> benefit from this imporovement?
Thanks for looking.
The explanation is that the planner currently gives index scans a cost
"discount" for correlation. Jeff Janes has pointed out that there are two
discounts: 1) fewer pages are read; and, 2) lower cost-per-page. This patch
aims to give bitmap scans the same benefits. A "dense" bitmap will read fewer
pages, more sequentially.
Tom pointed out that the "correlation" isn't a perfect metric for this, since
the index might be "clumpy" without being well-ordered, which doesn't matter
for bitmap scans, which access in physical order anyway. In those cases, the
correlation logic would fail to reduce the estimated cost of bitmap scan, even
though the actual cost is less (same as now). This is true, but my goal is to
give bitmap scans at least the same benefit as index scans, even if there's
additional "discounts" which aren't yet being considered.
This was an issue for me in the past when the planner chose a to scan a index,
but it was slower than projected (for reasons unrelated to this patch). Making
bitmap cost account for high correlation was one step towards addressing that.
Since then, we switched to brin indexes, which force bitmap scans.
https://www.postgresql.org/message-id/flat/20160524173914.GA11880%40telsasoft.com
Here's an example.
CREATE TABLE t AS SELECT a,b FROM generate_series(1,999) a,
generate_series(1,999) b ORDER BY a+b/9.9;
CREATE INDEX ON t(a);
postgres=# SELECT attname, correlation FROM pg_stats WHERE tablename ='t';
a | 0.9951819
b | 0.10415093
postgres=# explain analyze SELECT * FROM t WHERE a BETWEEN 55 AND 77;
Index Scan using t_a_idx on t (cost=0.42..810.89 rows=22683 width=8) (actual
time=0.292..66.657 rows=22977 loops=1)
vs (without my patch, with SET enable_indexscan=off);
Bitmap Heap Scan on t (cost=316.93..5073.17 rows=22683 width=8) (actual
time=10.810..26.633 rows=22977 loops=1)
vs (with my patch, with SET enable_indexscan=off):
postgres=# explain analyze SELECT * FROM t WHERE a BETWEEN 55 AND 77;
Bitmap Heap Scan on t (cost=316.93..823.84 rows=22683 width=8) (actual
time=10.742..33.279 rows=22977 loops=1)
So bitmap scan is cheaper, but the cost estimate is a lot higher. My patch
improves but doesn't completely "fix" that - bitmap scan is still costed as
more expensive, but happens to be. This is probably not even a particularly
good example, as it's a small table cached in RAM. There's always going to be
cases like this, certainly near the costs where the plan changes "shape". I
think a cost difference of 10 here is very reasonable (cpu_oper_cost,
probably), but a cost difference of 5x is not.
There's not many regression tests changed. Probably partially because bitmap
scans have an overhead (the heap scan cannot start until after the index scan
finishes), and we avoid large tests.
If there's no interest in the patch, I guess we should just close it rather
than letting it rot.
> The first patch is simply a refactoring and don't see any possible objections
> against it.
> The second patch also looks fine to me. The logic is understandable and the
> code is neat.
>
> It wouldn't hurt to add a comment for this computation, though.
> + pages_fetched = pages_fetchedMAX +
> indexCorrelation*indexCorrelation*(pages_fetchedMIN - pages_fetchedMAX);
You're right. It's like this:
// interpolate between c==0: pages_fetched=max and c==1: pages_fetched=min
pages_fetched = min + (max-min)*(1-c**2)
pages_fetched = min + max*(1-c**2) - min*(1-c**2)
pages_fetched = max*(1-c**2) + min - min*(1-c**2)
pages_fetched = max*(1-c**2) + min*(c**2)
pages_fetched = max - max*c**2 + min*(c**2)
pages_fetched = max + min*(c**2) - max*c**2
pages_fetched = max + c**2 * (min-max)
I'm not sure if there's a reason why it's written like that, but (min-max)
looks odd, so I wrote it like:
pages_fetched = max - c**2 * (max-min)
> The new status of this patch is: Waiting on Author
>From af1e640af2b1a80430191a38b80dde1f2b750757 Mon Sep 17 00:00:00 2001
From: Justin Pryzby <pryz...@telsasoft.com>
Date: Wed, 8 Jan 2020 19:23:51 -0600
Subject: [PATCH v6 1/2] Make more clear the computation of min/max IO..
..and specifically the double use and effect of correlation.
Avoid re-use of the "pages_fetched" variable
---
src/backend/optimizer/path/costsize.c | 47 ++++++++++++++-------------
1 file changed, 25 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index f1dfdc1a4a..083448def7 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -503,12 +503,13 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
csquared;
double spc_seq_page_cost,
spc_random_page_cost;
- Cost min_IO_cost,
+ double min_pages_fetched, /* The min and max page count based on index correlation */
+ max_pages_fetched;
+ Cost min_IO_cost, /* The min and max cost based on index correlation */
max_IO_cost;
QualCost qpqual_cost;
Cost cpu_per_tuple;
double tuples_fetched;
- double pages_fetched;
double rand_heap_pages;
double index_pages;
@@ -591,7 +592,8 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
* (just after a CLUSTER, for example), the number of pages fetched should
* be exactly selectivity * table_size. What's more, all but the first
* will be sequential fetches, not the random fetches that occur in the
- * uncorrelated case. So if the number of pages is more than 1, we
+ * uncorrelated case (the index is expected to read fewer pages, *and* each
+ * page read is cheaper). So if the number of pages is more than 1, we
* ought to charge
* spc_random_page_cost + (pages_fetched - 1) * spc_seq_page_cost
* For partially-correlated indexes, we ought to charge somewhere between
@@ -616,17 +618,17 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
* pro-rate the costs for one scan. In this case we assume all the
* fetches are random accesses.
*/
- pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
+ max_pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
baserel->pages,
(double) index->pages,
root);
if (indexonly)
- pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
+ max_pages_fetched = ceil(max_pages_fetched * (1.0 - baserel->allvisfrac));
- rand_heap_pages = pages_fetched;
+ rand_heap_pages = max_pages_fetched;
- max_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
+ max_IO_cost = (max_pages_fetched * spc_random_page_cost) / loop_count;
/*
* In the perfectly correlated case, the number of pages touched by
@@ -638,17 +640,17 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
* where such a plan is actually interesting, only one page would get
* fetched per scan anyway, so it shouldn't matter much.)
*/
- pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
+ min_pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
- pages_fetched = index_pages_fetched(pages_fetched * loop_count,
+ min_pages_fetched = index_pages_fetched(min_pages_fetched * loop_count,
baserel->pages,
(double) index->pages,
root);
if (indexonly)
- pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
+ min_pages_fetched = ceil(min_pages_fetched * (1.0 - baserel->allvisfrac));
- min_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
+ min_IO_cost = (min_pages_fetched * spc_random_page_cost) / loop_count;
}
else
{
@@ -656,30 +658,31 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
* Normal case: apply the Mackert and Lohman formula, and then
* interpolate between that and the correlation-derived result.
*/
- pages_fetched = index_pages_fetched(tuples_fetched,
+
+ /* For the perfectly uncorrelated case (csquared=0) */
+ max_pages_fetched = index_pages_fetched(tuples_fetched,
baserel->pages,
(double) index->pages,
root);
if (indexonly)
- pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
+ max_pages_fetched = ceil(max_pages_fetched * (1.0 - baserel->allvisfrac));
- rand_heap_pages = pages_fetched;
+ rand_heap_pages = max_pages_fetched;
- /* max_IO_cost is for the perfectly uncorrelated case (csquared=0) */
- max_IO_cost = pages_fetched * spc_random_page_cost;
+ max_IO_cost = max_pages_fetched * spc_random_page_cost;
- /* min_IO_cost is for the perfectly correlated case (csquared=1) */
- pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
+ /* For the perfectly correlated case (csquared=1) */
+ min_pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
if (indexonly)
- pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
+ min_pages_fetched = ceil(min_pages_fetched * (1.0 - baserel->allvisfrac));
- if (pages_fetched > 0)
+ if (min_pages_fetched > 0)
{
min_IO_cost = spc_random_page_cost;
- if (pages_fetched > 1)
- min_IO_cost += (pages_fetched - 1) * spc_seq_page_cost;
+ if (min_pages_fetched > 1)
+ min_IO_cost += (min_pages_fetched - 1) * spc_seq_page_cost;
}
else
min_IO_cost = 0;
--
2.17.0
>From 2a17c1ce20d53b8140fe9403a22fbee6efc02770 Mon Sep 17 00:00:00 2001
From: Justin Pryzby <pryz...@telsasoft.com>
Date: Tue, 1 Jan 2019 16:17:28 -0600
Subject: [PATCH v6 2/2] Use correlation statistic in costing bitmap scans..
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
