pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: Bitmap scan is undercosted? - boolean correlation
6+ messages / 3 participants
[nested] [flat]
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-03 04:04 Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 6+ messages in thread
From: Justin Pryzby @ 2017-12-03 04:04 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Sat, Dec 02, 2017 at 05:27:51PM -0800, Jeff Janes wrote:
> I think the non-extended stats code also has trouble with booleans.
> pg_stats gives me a correlation of 0.8 or higher for the flag column.
It's not due to the boolean though; you see the same thing if you do:
CREATE INDEX aaa_f ON aaa((flag::text));
ANALYZE aaa;
correlation | 0.81193
or:
ALTER TABLE aaa ADD flag2 int; UPDATE aaa SET flag2= flag::int
correlation | 0.81193
I think it's caused by having so few (2) values to correlate.
most_common_vals | {f,t}
most_common_freqs | {0.9014,0.0986}
correlation | 0.822792
It thinks there's somewhat-high correlation since it gets a list of x and y
values (integer positions by logical and physical sort order) and 90% of the x
list (logical value) are the same value ('t'), and the CTIDs are in order on
the new index, so 90% of the values are 100% correlated.
It improves (by which I mean here that it spits out a lower number) if it's not
a 90/10 split:
CREATE TABLE aaa5 AS SELECT (id%100)::int num, (id%10>5)::bool flag FROM generate_series(1, 10000000) id;
CREATE INDEX ON aaa5 (flag);
tablename | aaa5
attname | flag
correlation | 0.522184
Justin
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-03 23:21 Jeff Janes <jeff.janes@gmail.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 6+ messages in thread
From: Jeff Janes @ 2017-12-03 23:21 UTC (permalink / raw)
To: Justin Pryzby <pryzby@telsasoft.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby <pryzby@telsasoft.com> wrote:
> On Sat, Dec 02, 2017 at 05:27:51PM -0800, Jeff Janes wrote:
> > I think the non-extended stats code also has trouble with booleans.
> > pg_stats gives me a correlation of 0.8 or higher for the flag column.
>
> It's not due to the boolean though; you see the same thing if you do:
> CREATE INDEX aaa_f ON aaa((flag::text));
> ANALYZE aaa;
> correlation | 0.81193
>
> or:
> ALTER TABLE aaa ADD flag2 int; UPDATE aaa SET flag2= flag::int
> correlation | 0.81193
>
> I think it's caused by having so few (2) values to correlate.
>
> most_common_vals | {f,t}
> most_common_freqs | {0.9014,0.0986}
> correlation | 0.822792
>
> It thinks there's somewhat-high correlation since it gets a list of x and y
> values (integer positions by logical and physical sort order) and 90% of
> the x
> list (logical value) are the same value ('t'), and the CTIDs are in order
> on
> the new index, so 90% of the values are 100% correlated.
>
But there is no index involved (except in the case of the functional
index). The correlation of table columns to physical order of the table
doesn't depend on the existence of an index, or the physical order within
an index.
But I do see that ties within the logical order of the column values are
broken to agree with the physical order. That is wrong, right? Is there
any argument that this is desirable?
It looks like it could be fixed with a few extra double calcs per distinct
value. Considering we already sorted the sample values using SQL-callable
collation dependent comparators, I doubt a few C-level double calcs is
going to be meaningful.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-03 23:31 Tom Lane <tgl@sss.pgh.pa.us>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2017-12-03 23:31 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Justin Pryzby <pryzby@telsasoft.com>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
Jeff Janes <jeff.janes@gmail.com> writes:
> On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby <pryzby@telsasoft.com> wrote:
>> It thinks there's somewhat-high correlation since it gets a list of x
>> and y values (integer positions by logical and physical sort order) and
>> 90% of the x list (logical value) are the same value ('t'), and the
>> CTIDs are in order on the new index, so 90% of the values are 100%
>> correlated.
> But there is no index involved (except in the case of the functional
> index). The correlation of table columns to physical order of the table
> doesn't depend on the existence of an index, or the physical order within
> an index.
> But I do see that ties within the logical order of the column values are
> broken to agree with the physical order. That is wrong, right? Is there
> any argument that this is desirable?
Uh ... what do you propose doing instead? We'd have to do something with
ties, and it's not so obvious this way is wrong.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-04 00:27 Jeff Janes <jeff.janes@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 6+ messages in thread
From: Jeff Janes @ 2017-12-04 00:27 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Justin Pryzby <pryzby@telsasoft.com>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Dec 3, 2017 15:31, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
Jeff Janes <jeff.janes@gmail.com> writes:
> On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby <pryzby@telsasoft.com>
wrote:
>> It thinks there's somewhat-high correlation since it gets a list of x
>> and y values (integer positions by logical and physical sort order) and
>> 90% of the x list (logical value) are the same value ('t'), and the
>> CTIDs are in order on the new index, so 90% of the values are 100%
>> correlated.
> But there is no index involved (except in the case of the functional
> index). The correlation of table columns to physical order of the table
> doesn't depend on the existence of an index, or the physical order within
> an index.
> But I do see that ties within the logical order of the column values are
> broken to agree with the physical order. That is wrong, right? Is there
> any argument that this is desirable?
Uh ... what do you propose doing instead? We'd have to do something with
ties, and it's not so obvious this way is wrong.
Let them be tied. If there are 10 distinct values, number the values 0 to
9, and all rows of a given distinct values get the same number for the
logical order axis.
Calling the correlation 0.8 when it is really 0.0 seems obviously wrong to
me. Although if we switched btree to store duplicate values with tid as a
tie breaker, then maybe it wouldn't be as obviously wrong.
Cheers,
Jeff
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-05 18:50 Tom Lane <tgl@sss.pgh.pa.us>
parent: Jeff Janes <jeff.janes@gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2017-12-05 18:50 UTC (permalink / raw)
To: Jeff Janes <jeff.janes@gmail.com>; +Cc: Justin Pryzby <pryzby@telsasoft.com>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
Jeff Janes <jeff.janes@gmail.com> writes:
> On Dec 3, 2017 15:31, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
>> Jeff Janes <jeff.janes@gmail.com> writes:
>>> But I do see that ties within the logical order of the column values are
>>> broken to agree with the physical order. That is wrong, right? Is there
>>> any argument that this is desirable?
>> Uh ... what do you propose doing instead? We'd have to do something with
>> ties, and it's not so obvious this way is wrong.
> Let them be tied. If there are 10 distinct values, number the values 0 to
> 9, and all rows of a given distinct values get the same number for the
> logical order axis.
> Calling the correlation 0.8 when it is really 0.0 seems obviously wrong to
> me. Although if we switched btree to store duplicate values with tid as a
> tie breaker, then maybe it wouldn't be as obviously wrong.
I thought some more about this. What we really want the correlation stat
to do is help us estimate how randomly an index-ordered scan will access
the heap. If the values we've sampled are all unequal then there's no
particular issue. However, if we have some group of equal values, we
do not really know what order an indexscan will visit them in. The
existing correlation calculation is making the *most optimistic possible*
assumption, that such a group will be visited exactly in heap order ---
and that assumption isn't too defensible. IIRC, a freshly built b-tree
will behave that way, because the initial sort of a btree breaks ties
using heap TIDs; but we don't maintain that property during later
insertions. In any case, given that we do this calculation without regard
to any specific index, we can't reasonably expect to model exactly what
the index will do. It would be best to adopt some middle-of-the-road
assumption about what the heap visitation order will be for a set of
duplicate values: not exactly heap order, but I think we should not use
a worst-case assumption either, since the btree may retain some amount
of its initial ordering.
BTW, I disagree that "correlation = zero" is the right answer for this
particular example. If the btree is freshly built, then an index-order
scan would visit all the heap pages in sequence to fetch "f" rows, and
then visit them all in sequence again to fetch "t" rows, which is a whole
lot better than the purely random access that zero correlation implies.
So I think 0.8 or so is actually a perfectly reasonable answer when the
index is fresh. The trouble is just that it'd behoove us to derate that
answer somewhat for the probability that the index isn't fresh.
My first thought for a concrete fix was to use the mean position of
a group of duplicates for the purposes of the correlation calculation,
but on reflection that's clearly wrong. We do have an idea, from the
data we have, whether the duplicates are close together in the heap
or spread all over. Using only mean position would fail to distinguish
those cases, but really we'd better penalize the spread-all-over case.
I'm not sure how to do that.
Or we could leave this calculation alone and try to move towards keeping
equal values in TID order in btrees. Not sure about the downsides of
that, though.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Bitmap scan is undercosted? - boolean correlation
@ 2017-12-07 04:51 Jeff Janes <jeff.janes@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 6+ messages in thread
From: Jeff Janes @ 2017-12-07 04:51 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Justin Pryzby <pryzby@telsasoft.com>; Vitaliy Garnashevich <vgarnashevich@gmail.com>; pgsql-performance@lists.postgresql.org
On Tue, Dec 5, 2017 at 10:50 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Jeff Janes <jeff.janes@gmail.com> writes:
> > On Dec 3, 2017 15:31, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> >> Jeff Janes <jeff.janes@gmail.com> writes:
> >>> But I do see that ties within the logical order of the column values
> are
> >>> broken to agree with the physical order. That is wrong, right? Is
> there
> >>> any argument that this is desirable?
>
> >> Uh ... what do you propose doing instead? We'd have to do something
> with
> >> ties, and it's not so obvious this way is wrong.
>
> > Let them be tied. If there are 10 distinct values, number the values 0
> to
> > 9, and all rows of a given distinct values get the same number for the
> > logical order axis.
> > Calling the correlation 0.8 when it is really 0.0 seems obviously wrong
> to
> > me. Although if we switched btree to store duplicate values with tid as
> a
> > tie breaker, then maybe it wouldn't be as obviously wrong.
>
> I thought some more about this. What we really want the correlation stat
> to do is help us estimate how randomly an index-ordered scan will access
> the heap.
The correlation is used in another place, estimating how much of the table
we will visit in the first place. If the correlation is very high, then
scanning 10% of the index leaf pages means we will visit 10% of the table.
If the correlation is low, then we use Mackert and Lohman, and (in the case
of visiting 10% of the index) predict we will visit most of the table.
Assuming effective_cache_size is high, we will visit most of the table just
once, but still in a random order, because subsequent visits for the same
query will be found in the cache. Rather than visiting the various pages
repeatedly and not finding them in cache each time.
In addition to estimating how much of the table we visit, we also estimate
how "sequential like" those visits are. Which is the use that you
describe. Ideally for that use case, we would know for each distinct
value, how correlated the tids are with the leaf page ordering. If the
index is freshly built, that is very high. We visit 1/10 of the index,
which causes us to visit 100% of the table but in perfect order, plucking
1/10 of the tuples from each table page.
But visiting 100% of the table in physical order in order to pluck out 10%
of the tuples from each page is quite different than visiting 10% of the
table pages in physical order to pluck out 100% of the tuples from those
pages and 0% from the pages not visited.
...
BTW, I disagree that "correlation = zero" is the right answer for this
> particular example. If the btree is freshly built, then an index-order
> scan would visit all the heap pages in sequence to fetch "f" rows, and
> then visit them all in sequence again to fetch "t" rows, which is a whole
> lot better than the purely random access that zero correlation implies.
> So I think 0.8 or so is actually a perfectly reasonable answer when the
> index is fresh. The trouble is just that it'd behoove us to derate that
> answer somewhat for the probability that the index isn't fresh.
>
But, for the case of "how much of the table do we visit at all",
correlation = zero is the right answer, even if it isn't the right answer
for "how sequentially do we visit whatever we visit"
> My first thought for a concrete fix was to use the mean position of
> a group of duplicates for the purposes of the correlation calculation,
> but on reflection that's clearly wrong. We do have an idea, from the
> data we have, whether the duplicates are close together in the heap
> or spread all over. Using only mean position would fail to distinguish
> those cases, but really we'd better penalize the spread-all-over case.
> I'm not sure how to do that.
>
Departing from correlations, we could also try to estimate "How many
different table pages does each index leaf page reference". This could
capture functional dependencies which are strong, but not in the form of
linear correlations. (The current extended statistics only captures
dependencies between user columns, not between one user column and one
system column such as table slot)
For whatever its worth, here is my "let ties be ties" patch.
It breaks two regression tests due to plan changes, and both are cases
where maybe the plan ought to change for the very reason being discussed.
If I just put random gibberish into the correlation field, more regression
tests fail, so I think my implementation is not too far broken.
The accumulations into corr_ysum and corr_y2sum could trivially be pushed
down into the "if", and corr_xysum could as well with a little algebra.
But that seems like premature optimization for a proof-of-concept patch.
Cheers,
Jeff
Attachments:
[text/x-patch] correl.patch (2.1K, ../../CAMkU=1wABEn19sBkiSj5ZqmUjR5dcPc203avvth2vNhy72htrQ@mail.gmail.com/3-correl.patch)
download | inline diff:
diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index f952b3c..3369784 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -2309,6 +2309,8 @@ compute_scalar_stats(VacAttrStatsP stats,
bool is_varwidth = (!stats->attrtype->typbyval &&
stats->attrtype->typlen < 0);
double corr_xysum;
+ double corr_ysum;
+ double corr_y2sum;
SortSupportData ssup;
ScalarItem *values;
int values_cnt = 0;
@@ -2429,6 +2431,8 @@ compute_scalar_stats(VacAttrStatsP stats,
* be ordered by tupno).
*/
corr_xysum = 0;
+ corr_ysum = 0;
+ corr_y2sum = 0;
ndistinct = 0;
nmultiple = 0;
dups_cnt = 0;
@@ -2436,7 +2440,9 @@ compute_scalar_stats(VacAttrStatsP stats,
{
int tupno = values[i].tupno;
- corr_xysum += ((double) i) * ((double) tupno);
+ corr_xysum += ((double) ndistinct) * ((double) tupno);
+ corr_ysum += ((double) ndistinct);
+ corr_y2sum += ((double) ndistinct) * ((double) ndistinct);
dups_cnt++;
if (tupnoLink[tupno] == tupno)
{
@@ -2777,11 +2783,11 @@ compute_scalar_stats(VacAttrStatsP stats,
MemoryContextSwitchTo(old_context);
/*----------
- * Since we know the x and y value sets are both
+ * Since we know the x value sets are
* 0, 1, ..., values_cnt-1
- * we have sum(x) = sum(y) =
+ * we have sum(x) =
* (values_cnt-1)*values_cnt / 2
- * and sum(x^2) = sum(y^2) =
+ * and sum(x^2) =
* (values_cnt-1)*values_cnt*(2*values_cnt-1) / 6.
*----------
*/
@@ -2791,8 +2797,8 @@ compute_scalar_stats(VacAttrStatsP stats,
((double) values_cnt) * (double) (2 * values_cnt - 1) / 6.0;
/* And the correlation coefficient reduces to */
- corrs[0] = (values_cnt * corr_xysum - corr_xsum * corr_xsum) /
- (values_cnt * corr_x2sum - corr_xsum * corr_xsum);
+ corrs[0] = (values_cnt * corr_xysum - corr_xsum * corr_ysum) /
+ sqrt((values_cnt * corr_x2sum - corr_xsum) * (values_cnt * corr_y2sum - corr_ysum));
stats->stakind[slot_idx] = STATISTIC_KIND_CORRELATION;
stats->staop[slot_idx] = mystats->ltopr;
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2017-12-07 04:51 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2017-12-03 04:04 Re: Bitmap scan is undercosted? - boolean correlation Justin Pryzby <pryzby@telsasoft.com>
2017-12-03 23:21 ` Jeff Janes <jeff.janes@gmail.com>
2017-12-03 23:31 ` Tom Lane <tgl@sss.pgh.pa.us>
2017-12-04 00:27 ` Jeff Janes <jeff.janes@gmail.com>
2017-12-05 18:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2017-12-07 04:51 ` Jeff Janes <jeff.janes@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox