Re: WIP: multivariate statistics / proof of concept

Hi,

attached is a WIP patch implementing multivariate statistics. The code
certainly is not "ready" - parts of it look as if written by a rogue
chimp who got bored of attempts to type the complete works of William
Shakespeare, and decided to try something different.

I also cut some corners to make it work, and those limitations need to
be fixed before the eventual commit (those are not difficult problems,
but were not necessary for a proof-of-concept patch).

It however seems to be working sufficiently well at this point, enough
to get some useful feedback. So here we go.

I expect to be busy over the next two weeks because of travel, so sorry
for somehow delayed responses. If you happen to attend pgconf.eu next
week (Oct 20-24), we can of course discuss this patch in person.

Goals and basics
----------------

The goal of this patch is allowing users to define multivariate
statistics (i.e. statistics on multiple columns), and improving
estimation when the columns are correlated.

Take for example a table like this:

CREATE TABLE test (a INT, b INT, c INT);
INSERT INTO test SELECT i/10000, i/10000, i/10000
FROM generate_series(1,1000000) s(i);
ANALYZE test;

and do a query like this:

SELECT * FROM test WHERE (a = 10) AND (b = 10) AND (c = 10);

which is estimated like this:

QUERY PLAN
---------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=1 width=12)
Filter: ((a = 10) AND (b = 10) AND (c = 10))
Planning time: 0.142 ms
(3 rows)

The query of course returns 10.000 rows, but the planner assumes the
columns are independent and thus multiplies the selectivities. And 1/100
for each column means 1/1000000 in total, which is 1 row.

This example is of course somehow artificial, but the problem is far
from uncommon, especially in denormalized datasets (e.g. star schema).
If you ever got an index scan instead of a sequential scan due to poor
estimate, resulting in a query running for hours instead of seconds, you
know the pain.

The patch allows you to do this:

ALTER TABLE test ADD STATISTICS ON (a, b, c);
ANALYZE test;

which then results in this estimate:

QUERY PLAN
------------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=9667 width=12)
Filter: ((a = 10) AND (b = 10) AND (c = 10))
Planning time: 0.110 ms
(3 rows)

This however is not free - both building such statistics (during
ANALYZE) and using it (during planning) costs some cycles. Even if we
optimize the hell out of it, it won't be entirely free.

One of the design goals in this patch is not to make the ANALYZE or
planning more expensive unless you add such statistics.

Those who add such statistics probably decided that the price is worth
the improved estimates, and lower risk of inefficient plans. If the
planning takes a few more miliseconds, it's probably worth it if you
risk queries running for minutes or hours because of misestimates.

It also does not guarantee the estimates to be always better. There will
be misestimates, although rather in the other direction (independence
assumption usually leads to underestimates, this may lead to
overestimates). However based on my experience from writing the patch I
be I believe it's possible to reasonably limit the extent of such errors
(just like in the single-column histograms, it's related to the bucket
size).

Of course, there will be cases when the old approach is lucky by
accident - there's not much we can do to beat luck. And we can't rely on
it either.

Design overview
---------------

The patch adds a new system catalog, called pg_mv_statistic, which is
used to keep track of requested statistics. There's also a pg_mv_stats
view, showing some basic info about the stats (not all the data).

There are three kinds of statistics

- list of most common combinations of values (MCV list)
- multi-dimensional histogram
- associative rules

The first two are extensions of the single-column stats we already have.
The MCV list is a trivial extension to multiple dimensions, just
tracking combinations and frequencies. The histogram is more complex -
the structure is quite simple (multi-dimensional rectangles) but there's
a lot of ways to build it. But even the current naive and simple
implementation seems to work quite well.

The last kind (associative rules) is an attempt to track "implications"
between columns. It is however an experiment and it's not really used in
the patch so I'll ignore it for now.

I'm not going to explain all the implementation details here - if you
want to learn more, the best way is probably by reading the changes in
those files (probably in this order):

src/include/utils/mvstats.h
src/backend/commands/analyze.c
src/backend/optimizer/path/clausesel.c

I tried to explain the ideas thoroughly in the comments, along with a
lot of TODO/FIXME items related to limitations, explained in the next
section.

Limitations
-----------

As I mentioned, the current patch has a number of practical limitations,
most importantly:

(a) only data types passed by value (no varlena types)
(b) only data types with sort (to be able to build histogram)
(c) no NULL values supported
(d) not handling DROP COLUMN or DROP TABLE and such
(e) limited to stats on 8 columns (max)
(f) optimizer uses single stats per table
(g) limited list of compatible WHERE clauses
(h) incomplete ADD STATISTICS syntax

The first three conditions are really a shortcut to a working patch, and
fixing them should not be difficult.

The limited number of columns is really just a sanity check. It's
possible to increase it, but I doubt stats on more columns will be
practical because of excessive size or poor accuracy.

A better approach is to support combining multiple stats, defined on
various subsets of columns. This is not implemented at the memoment, but
it's certainly on the roadmap. Currently the "smallest" stats covering
the most columns is selected.

Regarding the compatible WHERE clauses, the patch currently handles
conditions of the form

column OPERATOR constant

where operator is one of the comparison operators (=, <, >, =<, >=). In
the future it's possible to add support for more conditions, e.g.
"column IS NULL" or "column OPERATOR column".

The last point is really just "unfinished implementation" - the syntax I
propose is this:

ALTER TABLE ... ADD STATISTICS (options) ON (columns)

where the options influence the MCV list and histogram size, etc. The
options are recognized and may give you an idea of what it might do, but
it's not really used at the moment (except for storing in the
pg_mv_statistic catalog).

Examples
--------

Let's see a few examples of how to define the stats, and what difference
in estimates it makes:

CREATE TABLE test (a INT, b INT c INT);

-- same value in all columns
INSERT INTO test SELECT mod(i,100), mod(i,100), mod(i,100)
FROM generate_series(1,1000000) s(i);

ANALYZE test;

=============== no multivariate stats ============================

SELECT * FROM test WHERE a = 10 AND b = 10;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..20406.00 rows=101 width=12)
(actual time=0.007..60.902 rows=10000 loops=1)
Filter: ((a = 10) AND (b = 10))
Rows Removed by Filter: 990000
Planning time: 0.119 ms
Execution time: 61.164 ms
(5 rows)

SELECT * FROM test WHERE a = 10 AND b = 10 AND c = 10;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=1 width=12)
(actual time=0.010..56.780 rows=10000 loops=1)
Filter: ((a = 10) AND (b = 10) AND (c = 10))
Rows Removed by Filter: 990000
Planning time: 0.061 ms
Execution time: 56.994 ms
(5 rows)

=============== with multivariate stats ===========================

ALTER TABLE test ADD STATISTICS ON (a, b, c);
ANALYZE test;

SELECT * FROM test WHERE a = 10 AND b = 10;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..20406.00 rows=10767 width=12)
(actual time=0.007..58.981 rows=10000 loops=1)
Filter: ((a = 10) AND (b = 10))
Rows Removed by Filter: 990000
Planning time: 0.114 ms
Execution time: 59.214 ms
(5 rows)

SELECT * FROM test WHERE a = 10 AND b = 10 AND c = 10;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=10767 width=12)
(actual time=0.008..61.838 rows=10000 loops=1)
Filter: ((a = 10) AND (b = 10) AND (c = 10))
Rows Removed by Filter: 990000
Planning time: 0.088 ms
Execution time: 62.057 ms
(5 rows)

OK, that was rather significant improvement, but it's also trivial
dataset. Let's see something more complicated - the following table has
correlated columns with distributions skewed to 0.

CREATE TABLE test (a INT, b INT, c INT);
INSERT INTO test SELECT r*MOD(i,50),
pow(r,2)*MOD(i,100),
pow(r,4)*MOD(i,500)
FROM (SELECT random() AS r, i
FROM generate_series(1,1000000) s(i)) foo;
ANALYZE test;

SELECT * FROM test WHERE a = 0 AND b = 0;

=============== no multivariate stats ============================

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..20406.00 rows=9024 width=12)
(actual time=0.007..62.969 rows=49503 loops=1)
Filter: ((a = 0) AND (b = 0))
Rows Removed by Filter: 950497
Planning time: 0.057 ms
Execution time: 64.098 ms
(5 rows)

SELECT * FROM test WHERE a = 0 AND b = 0 AND c = 0;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=2126 width=12)
(actual time=0.008..63.862 rows=40770 loops=1)
Filter: ((a = 0) AND (b = 0) AND (c = 0))
Rows Removed by Filter: 959230
Planning time: 0.060 ms
Execution time: 64.794 ms
(5 rows)

=============== with multivariate stats ============================

ALTER TABLE test ADD STATISTICS ON (a, b, c);
ANALYZE test;

db=> SELECT * FROM pg_mv_stats;
schemaname | public
tablename | test
attnums | 1 2 3
mcvbytes | 25904
mcvinfo | nitems=809
histbytes | 568240
histinfo | nbuckets=13772

SELECT * FROM test WHERE a = 0 AND b = 0;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..20406.00 rows=47717 width=12)
(actual time=0.007..61.782 rows=49503 loops=1)
Filter: ((a = 0) AND (b = 0))
Rows Removed by Filter: 950497
Planning time: 3.181 ms
Execution time: 62.859 ms
(5 rows)

SELECT * FROM test WHERE a = 0 AND b = 0 AND c = 0;

QUERY PLAN
-------------------------------------------------------------------
Seq Scan on test (cost=0.00..22906.00 rows=40567 width=12)
(actual time=0.009..66.685 rows=40770 loops=1)
Filter: ((a = 0) AND (b = 0) AND (c = 0))
Rows Removed by Filter: 959230
Planning time: 0.188 ms
Execution time: 67.593 ms
(5 rows)

regards
Tomas

Tomas Vondra wrote:
> attached is a WIP patch implementing multivariate statistics.

I think that is pretty useful.
Oracle has an identical feature called "extended statistics".

That's probably an entirely different thing, but it would be very
nice to have statistics to estimate the correlation between columns
of different tables, to improve the estimate for the number of rows
in a join.

Yours,
Laurenz Albe

Hi!

On 13.10.2014 09:36, Albe Laurenz wrote:
> Tomas Vondra wrote:
>> attached is a WIP patch implementing multivariate statistics.
>
> I think that is pretty useful.
> Oracle has an identical feature called "extended statistics".
>
> That's probably an entirely different thing, but it would be very
> nice to have statistics to estimate the correlation between columns
> of different tables, to improve the estimate for the number of rows
> in a join.

I don't have a clear idea of how that should work, but from the quick
look at how join selectivity estimation is implemented, I believe two
things might be possible:

(a) using conditional probabilities

Say we have a join "ta JOIN tb ON (ta.x = tb.y)"

Currently, the selectivity is derived from stats on the two keys.
Essentially probabilities P(x), P(y), represented by the MCV lists.
But if there are additional WHERE conditions on the tables, and we
have suitable multivariate stats, it's possible to use conditional
probabilities.

E.g. if the query actually uses

... ta JOIN tb ON (ta.x = tb.y) WHERE ta.z = 10

and we have stats on (ta.x, ta.z), we can use P(x|z=10) instead.
If the two columns are correlated, this might be much different.

(b) using this for multi-column conditions

If the join condition involves multiple columns, e.g.

ON (ta.x = tb.y AND ta.p = tb.q)

and we happen to have stats on (ta.x,ta.p) and (tb.y,tb.q), we may
use this to compute the cardinality (pretty much as we do today).

But I haven't really worked on this so far, I suspect there are various
subtle issues and I certainly don't plan to address this in the first
phase of the patch.

Tomas

On Mon, Oct 13, 2014 at 11:00 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:

> Hi,
>
> attached is a WIP patch implementing multivariate statistics. The code
> certainly is not "ready" - parts of it look as if written by a rogue
> chimp who got bored of attempts to type the complete works of William
> Shakespeare, and decided to try something different.
>
>
I'm really glad you're working on this. I had been thinking of looking into
doing this myself.

> The last point is really just "unfinished implementation" - the syntax I
> propose is this:
>
> ALTER TABLE ... ADD STATISTICS (options) ON (columns)
>
> where the options influence the MCV list and histogram size, etc. The
> options are recognized and may give you an idea of what it might do, but
> it's not really used at the moment (except for storing in the
> pg_mv_statistic catalog).
>
>
>
I've not really gotten around to looking at the patch yet, but I'm also
wondering if it would be simple include allowing functional statistics too.
The pg_mv_statistic name seems to indicate multi columns, but how about
stats on date(datetime_column), or perhaps any non-volatile function. This
would help to solve the problem highlighted here
http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
. Without giving it too much thought, perhaps any expression that can be
indexed should be allowed to have stats? Would that be really difficult to
implement in comparison to what you've already done with the patch so far?

I'm quite interested in reviewing your work on this, but it appears that
some of your changes are not C89:

src\backend\commands\analyze.c(3774): error C2057: expected constant
expression [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(3774): error C2466: cannot allocate an
array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(3774): error C2133: 'indexes' : unknown
size [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4302): error C2057: expected constant
expression [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4302): error C2466: cannot allocate an
array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4302): error C2133: 'ndistincts' : unknown
size [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4775): error C2057: expected constant
expression [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4775): error C2466: cannot allocate an
array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
src\backend\commands\analyze.c(4775): error C2133: 'keys' : unknown size
[D:\Postgres\a\postgres.vcxproj]

The compiler I'm using is a bit too stupid to understand the C99 syntax.

I guess you'd need to palloc() these arrays instead in order to comply with
the project standards.

http://www.postgresql.org/docs/devel/static/install-requirements.html

I'm going to sign myself up to review this, so probably my first feedback
would be the compiling problem.

Regards

David Rowley

Dne 29 Říjen 2014, 10:41, David Rowley napsal(a):
>
> I've not really gotten around to looking at the patch yet, but I'm also
> wondering if it would be simple include allowing functional statistics
> too.
> The pg_mv_statistic name seems to indicate multi columns, but how about
> stats on date(datetime_column), or perhaps any non-volatile function. This
> would help to solve the problem highlighted here
> http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
> . Without giving it too much thought, perhaps any expression that can be
> indexed should be allowed to have stats? Would that be really difficult to
> implement in comparison to what you've already done with the patch so far?

I don't know, but it seems mostly orthogonal to what the patch aims to do.
If we add collecting statistics on expressions (on a single column), then I'd
expect it to be reasonably simple to add this to the multi-column case.

There are features like join stats or range type stats, that are probably
more directly related to the patch (but out of scope for the initial
version).

> I'm quite interested in reviewing your work on this, but it appears that
> some of your changes are not C89:
>
> src\backend\commands\analyze.c(3774): error C2057: expected constant
> expression [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(3774): error C2466: cannot allocate an
> array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(3774): error C2133: 'indexes' : unknown
> size [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4302): error C2057: expected constant
> expression [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4302): error C2466: cannot allocate an
> array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4302): error C2133: 'ndistincts' : unknown
> size [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4775): error C2057: expected constant
> expression [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4775): error C2466: cannot allocate an
> array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> src\backend\commands\analyze.c(4775): error C2133: 'keys' : unknown size
> [D:\Postgres\a\postgres.vcxproj]
>
> The compiler I'm using is a bit too stupid to understand the C99 syntax.
>
> I guess you'd need to palloc() these arrays instead in order to comply
> with
> the project standards.
>
> http://www.postgresql.org/docs/devel/static/install-requirements.html
>
> I'm going to sign myself up to review this, so probably my first feedback
> would be the compiling problem.

I'll look into that. The thing is I don't have access to MSVC, so it's a bit
difficult to spot / fix those issues :-(

regards
Tomas

On 29/10/14 10:41, David Rowley wrote:
> On Mon, Oct 13, 2014 at 11:00 AM, Tomas Vondra <tv(at)fuzzy(dot)cz
>
> The last point is really just "unfinished implementation" - the syntax I
> propose is this:
>
> ALTER TABLE ... ADD STATISTICS (options) ON (columns)
>
> where the options influence the MCV list and histogram size, etc. The
> options are recognized and may give you an idea of what it might do, but
> it's not really used at the moment (except for storing in the
> pg_mv_statistic catalog).
>
>
>
> I've not really gotten around to looking at the patch yet, but I'm also
> wondering if it would be simple include allowing functional statistics
> too. The pg_mv_statistic name seems to indicate multi columns, but how
> about stats on date(datetime_column), or perhaps any non-volatile
> function. This would help to solve the problem highlighted here
> http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
> . Without giving it too much thought, perhaps any expression that can be
> indexed should be allowed to have stats? Would that be really difficult
> to implement in comparison to what you've already done with the patch so
> far?
>

I would not over-complicate requirements for the first version of this,
I think it's already complicated enough.

Quick look at the patch suggests that it mainly needs discussion about
design and particular implementation choices, there is fair amount of
TODOs and FIXMEs. I'd like to look at it too but I doubt that I'll have
time to do in depth review in this CF.

--
Petr Jelinek http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Dne 29 Říjen 2014, 12:31, Petr Jelinek napsal(a):
> On 29/10/14 10:41, David Rowley wrote:
>> On Mon, Oct 13, 2014 at 11:00 AM, Tomas Vondra <tv(at)fuzzy(dot)cz
>>
>> The last point is really just "unfinished implementation" - the
>> syntax I
>> propose is this:
>>
>> ALTER TABLE ... ADD STATISTICS (options) ON (columns)
>>
>> where the options influence the MCV list and histogram size, etc.
>> The
>> options are recognized and may give you an idea of what it might do,
>> but
>> it's not really used at the moment (except for storing in the
>> pg_mv_statistic catalog).
>>
>>
>>
>> I've not really gotten around to looking at the patch yet, but I'm also
>> wondering if it would be simple include allowing functional statistics
>> too. The pg_mv_statistic name seems to indicate multi columns, but how
>> about stats on date(datetime_column), or perhaps any non-volatile
>> function. This would help to solve the problem highlighted here
>> http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
>> . Without giving it too much thought, perhaps any expression that can be
>> indexed should be allowed to have stats? Would that be really difficult
>> to implement in comparison to what you've already done with the patch so
>> far?
>>
>
> I would not over-complicate requirements for the first version of this,
> I think it's already complicated enough.

My thoughts, exactly. I'm not willing to put more features into the
initial version of the patch. Actually, I'm thinking about ripping out
some experimental features (particularly "hashed MCV" and "associative
rules").

> Quick look at the patch suggests that it mainly needs discussion about
> design and particular implementation choices, there is fair amount of
> TODOs and FIXMEs. I'd like to look at it too but I doubt that I'll have
> time to do in depth review in this CF.

Yes. I think it's a bit premature to discuss the code thoroughly at this
point - I'd like to discuss the general approach to the feature (i.e.
minimizing the impact on those not using it, etc.).

The most interesting part of the code are probably the comments,
explaining the design in more detail, known shortcomings and possible ways
to address them.

regards
Tomas

On Thu, Oct 30, 2014 at 12:48 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:

> Dne 29 Říjen 2014, 12:31, Petr Jelinek napsal(a):
> >> I've not really gotten around to looking at the patch yet, but I'm also
> >> wondering if it would be simple include allowing functional statistics
> >> too. The pg_mv_statistic name seems to indicate multi columns, but how
> >> about stats on date(datetime_column), or perhaps any non-volatile
> >> function. This would help to solve the problem highlighted here
> >>
> http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
> >> . Without giving it too much thought, perhaps any expression that can be
> >> indexed should be allowed to have stats? Would that be really difficult
> >> to implement in comparison to what you've already done with the patch so
> >> far?
> >>
> >
> > I would not over-complicate requirements for the first version of this,
> > I think it's already complicated enough.
>
> My thoughts, exactly. I'm not willing to put more features into the
> initial version of the patch. Actually, I'm thinking about ripping out
> some experimental features (particularly "hashed MCV" and "associative
> rules").
>
>
That's fair, but I didn't really mean to imply that you should go work on
that too and that it should be part of this patch..
I was thinking more along the lines of that I don't really agree with the
table name for the new stats and that at some later date someone will want
to add expression stats and we'd probably better come up design that would
be friendly towards that. At this time I can only think that the name of
the table might not suit well to expression stats, I'd hate to see someone
have to invent a 3rd table to support these when we could likely come up
with something that could be extended later and still make sense both today
and in the future.

I was just looking at how expression indexes are stored in pg_index and I
see that if it's an expression index that the expression is stored in
the indexprs column which is of type pg_node_tree, so quite possibly at
some point in the future the new stats table could just have an extra
column added, and for today, we'd just need to come up with a future proof
name... Perhaps pg_statistic_ext or pg_statisticx, and name functions and
source files something along those lines instead?

Regards

David Rowley

On Thu, Oct 30, 2014 at 12:21 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:

> Dne 29 Říjen 2014, 10:41, David Rowley napsal(a):
> > I'm quite interested in reviewing your work on this, but it appears that
> > some of your changes are not C89:
> >
> > src\backend\commands\analyze.c(3774): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2133: 'indexes' : unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2133: 'ndistincts' :
> unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2133: 'keys' : unknown size
> > [D:\Postgres\a\postgres.vcxproj]
> >
>
> I'll look into that. The thing is I don't have access to MSVC, so it's a
> bit
> difficult to spot / fix those issues :-(
>
>
It should be a pretty simple fix, just use the files and line numbers from
the above. It's just a problem that in those 3 places you're declaring an
array of a variable size, which is not allowed in C89. The thing to do
instead would just be to palloc() the size you need and the pfree() it when
you're done.

Regards

David Rowley

Dne 30 Říjen 2014, 10:17, David Rowley napsal(a):
> On Thu, Oct 30, 2014 at 12:48 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
>
>> Dne 29 Říjen 2014, 12:31, Petr Jelinek napsal(a):
>> >> I've not really gotten around to looking at the patch yet, but I'm
>> also
>> >> wondering if it would be simple include allowing functional
>> statistics
>> >> too. The pg_mv_statistic name seems to indicate multi columns, but
>> how
>> >> about stats on date(datetime_column), or perhaps any non-volatile
>> >> function. This would help to solve the problem highlighted here
>> >>
>> http://www.postgresql.org/message-id/CAApHDvp2vH=7O-gp-zAf7aWy+A-WHWVg7h3Vc6=5pf9Uf34DhQ@mail.gmail.com
>> >> . Without giving it too much thought, perhaps any expression that can
>> be
>> >> indexed should be allowed to have stats? Would that be really
>> difficult
>> >> to implement in comparison to what you've already done with the patch
>> so
>> >> far?
>> >>
>> >
>> > I would not over-complicate requirements for the first version of
>> this,
>> > I think it's already complicated enough.
>>
>> My thoughts, exactly. I'm not willing to put more features into the
>> initial version of the patch. Actually, I'm thinking about ripping out
>> some experimental features (particularly "hashed MCV" and "associative
>> rules").
>>
>>
> That's fair, but I didn't really mean to imply that you should go work on
> that too and that it should be part of this patch..
> I was thinking more along the lines of that I don't really agree with the
> table name for the new stats and that at some later date someone will want
> to add expression stats and we'd probably better come up design that would
> be friendly towards that. At this time I can only think that the name of
> the table might not suit well to expression stats, I'd hate to see someone
> have to invent a 3rd table to support these when we could likely come up
> with something that could be extended later and still make sense both
> today
> and in the future.
>
> I was just looking at how expression indexes are stored in pg_index and I
> see that if it's an expression index that the expression is stored in
> the indexprs column which is of type pg_node_tree, so quite possibly at
> some point in the future the new stats table could just have an extra
> column added, and for today, we'd just need to come up with a future proof
> name... Perhaps pg_statistic_ext or pg_statisticx, and name functions and
> source files something along those lines instead?

Ah, OK. I don't think the catalog name "pg_mv_statistic" is somehow
inappropriate for this purpose, though. IMHO the "multivariate" does not
mean "only columns" or "no expressions", it simply describes that the
approximated density function has multiple input variables, be it
attributes or expressions.

But maybe there's a better name.

Tomas

On 30.10.2014 10:23, David Rowley wrote:
> On Thu, Oct 30, 2014 at 12:21 AM, Tomas Vondra <tv(at)fuzzy(dot)cz
> <mailto:tv(at)fuzzy(dot)cz>> wrote:
>
> Dne 29 Říjen 2014, 10:41, David Rowley napsal(a):
> > I'm quite interested in reviewing your work on this, but it
> appears that
> > some of your changes are not C89:
> >
> > src\backend\commands\analyze.c(3774): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(3774): error C2133: 'indexes' :
> unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4302): error C2133: 'ndistincts' :
> unknown
> > size [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2057: expected constant
> > expression [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2466: cannot allocate an
> > array of constant size 0 [D:\Postgres\a\postgres.vcxproj]
> > src\backend\commands\analyze.c(4775): error C2133: 'keys' :
> unknown size
> > [D:\Postgres\a\postgres.vcxproj]
> >
>
> I'll look into that. The thing is I don't have access to MSVC, so
> it's a bit difficult to spot / fix those issues :-(
>
>
> It should be a pretty simple fix, just use the files and line
> numbers from the above. It's just a problem that in those 3 places
> you're declaring an array of a variable size, which is not allowed in
> C89. The thing to do instead would just be to palloc() the size you
> need and the pfree() it when you're done.

Attached is a patch that should fix these issues.

The bad news is there are a few installcheck failures (and were in the
previous patch, but I haven't noticed for some reason). Apparently,
there's some mixup in how the patch handles Var->varno in some causes,
causing issues with a handful of regression tests.

The problem is that is_mv_compatible (checking whether the condition is
compatible with multivariate stats) does this

if (! ((varRelid == 0) || (varRelid == var->varno)))
return false;

/* Also skip special varno values, and system attributes ... */
if ((IS_SPECIAL_VARNO(var->varno)) ||
(! AttrNumberIsForUserDefinedAttr(var->varattno)))
return false;

assuming that after this, varno represents an index into the range
table, and passes it out to the caller.

And the caller (collect_mv_attnums) does this:

RelOptInfo *rel = find_base_rel(root, varno);

which fails with errors like these:

ERROR: no relation entry for relid 0
ERROR: no relation entry for relid 1880

or whatever. What's even stranger is this:

regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# WHERE table_name = 'rw_view1';
ERROR: no relation entry for relid 0
regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# ;
regression=# SELECT table_name, is_updatable, is_insertable_into
regression-# FROM information_schema.views
regression-# WHERE table_name = 'rw_view1';
table_name | is_updatable | is_insertable_into
------------+--------------+--------------------
(0 rows)

regression=# explain SELECT table_name, is_updatable, is_insertable_into
FROM information_schema.views
WHERE table_name = 'rw_view1';
ERROR: no relation entry for relid 0

So, the query fails. After removing the WHERE clause it works, and this
somehow fixes the original query (with the WHERE clause). Nevertheless,
I still can't do explain on the query.

Clearly, I'm doing something wrong. I suspect it's caused either by
conditions involving function calls, or the fact that the view is a join
of multiple tables. But what?

For simple queries (single table, ...) it seems to be working fine.

regards
Tomas

On 12 October 2014 23:00, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:

> It however seems to be working sufficiently well at this point, enough
> to get some useful feedback. So here we go.

This looks interesting and useful.

What I'd like to check before a detailed review is that this has
sufficient applicability to be useful.

My understanding is that Q9 and Q18 of TPC-H have poor plans as a
result of multi-column stats errors.

Could you look at those queries and confirm that this patch can
produce better plans for them?

If so, I will work with you to review this patch.

One aspect of the patch that seems to be missing is a user declaration
of correlation, just as we have for setting n_distinct. It seems like
an even easier place to start to just let the user specify the stats
declaratively. That way we can split the patch into two parts. First,
allow multi column stats that are user declared. Then add user stats
collected by ANALYZE. The first part is possibly contentious and thus
a good initial focus. The second part will have lots of discussion, so
good to skip for a first version.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Dne 13 Listopad 2014, 12:31, Simon Riggs napsal(a):
> On 12 October 2014 23:00, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
>
>> It however seems to be working sufficiently well at this point, enough
>> to get some useful feedback. So here we go.
>
> This looks interesting and useful.
>
> What I'd like to check before a detailed review is that this has
> sufficient applicability to be useful.
>
> My understanding is that Q9 and Q18 of TPC-H have poor plans as a
> result of multi-column stats errors.
>
> Could you look at those queries and confirm that this patch can
> produce better plans for them?

Sure. I planned to do such verification/demonstration anyway, after
discussing the overall approach.

I planned to give it a try on TPC-DS, but I can start with the TPC-H
queries you propose. I'm not sure whether the poor estimates in Q9 & Q18
come from column correlation though - if it's due to some other issues
(e.g. conditions that are difficult to estimate), this patch can't do
anything with them. But it's a good start.

> If so, I will work with you to review this patch.

Thanks!

> One aspect of the patch that seems to be missing is a user declaration
> of correlation, just as we have for setting n_distinct. It seems like
> an even easier place to start to just let the user specify the stats
> declaratively. That way we can split the patch into two parts. First,
> allow multi column stats that are user declared. Then add user stats
> collected by ANALYZE. The first part is possibly contentious and thus
> a good initial focus. The second part will have lots of discussion, so
> good to skip for a first version.

I'm not a big fan of this approach, for a number of reasons.

Firstly, it only works for "simple" parameters that are trivial to specify
(say, Pearson's correlation coefficient), and the patch does not work with
those at all - it only works with histograms, MCV lists (and might work
with associative rules in the future). And we certainly can't ask users to
specify multivariate histograms - because it's very difficult to do, and
also because complex stats are more susceptible to get stale after adding
new data to the table.

Secondly, even if we add such "simple" parameters to the patch, we have to
come up with a way to apply those parameters to the estimates. The
problem is that as the parameters get simpler, it's less and less useful
to compute the stats.

Another question is whether it should support more than 2 columns ...

The only place where I think this might work are the associative rules.
It's simple to specify rules like ("ZIP code" implies "city") and we could
even do some simple check against the data to see if it actually makes
sense (and 'disable' the rule if not).

But maybe I got it wrong and you have something particular in mind? Can
you give an example of how it would work?

regards
Tomas

On 13.11.2014 14:11, Tomas Vondra wrote:
> Dne 13 Listopad 2014, 12:31, Simon Riggs napsal(a):
>> On 12 October 2014 23:00, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
>>
>>> It however seems to be working sufficiently well at this point, enough
>>> to get some useful feedback. So here we go.
>> This looks interesting and useful.
>>
>> What I'd like to check before a detailed review is that this has
>> sufficient applicability to be useful.
>>
>> My understanding is that Q9 and Q18 of TPC-H have poor plans as a
>> result of multi-column stats errors.
>>
>> Could you look at those queries and confirm that this patch can
>> produce better plans for them?
> Sure. I planned to do such verification/demonstration anyway, after
> discussing the overall approach.
>
> I planned to give it a try on TPC-DS, but I can start with the TPC-H
> queries you propose. I'm not sure whether the poor estimates in Q9 & Q18
> come from column correlation though - if it's due to some other issues
> (e.g. conditions that are difficult to estimate), this patch can't do
> anything with them. But it's a good start.
>
>> If so, I will work with you to review this patch.
> Thanks!
>
>> One aspect of the patch that seems to be missing is a user declaration
>> of correlation, just as we have for setting n_distinct. It seems like
>> an even easier place to start to just let the user specify the stats
>> declaratively. That way we can split the patch into two parts. First,
>> allow multi column stats that are user declared. Then add user stats
>> collected by ANALYZE. The first part is possibly contentious and thus
>> a good initial focus. The second part will have lots of discussion, so
>> good to skip for a first version.
> I'm not a big fan of this approach, for a number of reasons.
>
> Firstly, it only works for "simple" parameters that are trivial to specify
> (say, Pearson's correlation coefficient), and the patch does not work with
> those at all - it only works with histograms, MCV lists (and might work
> with associative rules in the future). And we certainly can't ask users to
> specify multivariate histograms - because it's very difficult to do, and
> also because complex stats are more susceptible to get stale after adding
> new data to the table.
>
> Secondly, even if we add such "simple" parameters to the patch, we have to
> come up with a way to apply those parameters to the estimates. The
> problem is that as the parameters get simpler, it's less and less useful
> to compute the stats.
>
> Another question is whether it should support more than 2 columns ...
>
> The only place where I think this might work are the associative rules.
> It's simple to specify rules like ("ZIP code" implies "city") and we could
> even do some simple check against the data to see if it actually makes
> sense (and 'disable' the rule if not).
and even this simple example has its limits, at least in Germany ZIP
codes are not unique for rural areas, where several villages have the
same ZIP code.

I guess there are just a few examples where columns are completely
functional dependent without any exceptions.
But of course, if the user gives this information just for optimization
the statistics, some exceptions don't matter.
If this information should be used for creating different execution
plans (e.g. on column A is an index and column B is functional
dependent, one could think about using this index on A and the
dependency instead of running through the whole table to find all tuples
that fit the query on column B), exceptions are a very important issue.
>
> But maybe I got it wrong and you have something particular in mind? Can
> you give an example of how it would work?
>
> regards
> Tomas
>
>
>

--
Dipl.-Math. Katharina Büchse
Friedrich-Schiller-Universität Jena
Institut für Informatik
Lehrstuhl für Datenbanken und Informationssysteme
Ernst-Abbe-Platz 2
07743 Jena
Telefon 03641/946367
Webseite http://users.minet.uni-jena.de/~re89qen/

Dne 13 Listopad 2014, 16:51, Katharina Büchse napsal(a):
> On 13.11.2014 14:11, Tomas Vondra wrote:
>
>> The only place where I think this might work are the associative rules.
>> It's simple to specify rules like ("ZIP code" implies "city") and we
>> could
>> even do some simple check against the data to see if it actually makes
>> sense (and 'disable' the rule if not).
>
> and even this simple example has its limits, at least in Germany ZIP
> codes are not unique for rural areas, where several villages have the
> same ZIP code.
>
> I guess there are just a few examples where columns are completely
> functional dependent without any exceptions.
> But of course, if the user gives this information just for optimization
> the statistics, some exceptions don't matter.
> If this information should be used for creating different execution
> plans (e.g. on column A is an index and column B is functional
> dependent, one could think about using this index on A and the
> dependency instead of running through the whole table to find all tuples
> that fit the query on column B), exceptions are a very important issue.

Yes, exactly. The aim of this patch is "only" improving estimates, not
removing conditions from the plan (e.g. checking only the ZIP code and not
the city name). That certainly can't be done solely based on approximate
statistics, and as you point out most real-world data either contain bugs
or are inherently imperfect (we have the same kind of ZIP/city
inconsistencies in Czech). That's not a big issue for estimates (assuming
only small fraction of rows violates the rule) though.

Tomas

Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
> Dne 13 Listopad 2014, 16:51, Katharina Büchse napsal(a):
>> On 13.11.2014 14:11, Tomas Vondra wrote:
>>
>>> The only place where I think this might work are the associative rules.
>>> It's simple to specify rules like ("ZIP code" implies "city") and we could
>>> even do some simple check against the data to see if it actually makes
>>> sense (and 'disable' the rule if not).
>>
>> and even this simple example has its limits, at least in Germany ZIP
>> codes are not unique for rural areas, where several villages have the
>> same ZIP code.

> as you point out most real-world data either contain bugs
> or are inherently imperfect (we have the same kind of ZIP/city
> inconsistencies in Czech).

You can have lots of fun with U.S. zip code, too. Just on the
nominally "Madison, Wisconsin" zip codes (those starting with 537),
there are several exceptions:

select zipcode, city, locationtype
from zipcode
where zipcode like '537%'
and Decommisioned = 'false'
and zipcodetype = 'STANDARD'
and locationtype in ('PRIMARY', 'ACCEPTABLE')
order by zipcode, city;

zipcode | city | locationtype
---------+-----------+--------------
53703 | MADISON | PRIMARY
53704 | MADISON | PRIMARY
53705 | MADISON | PRIMARY
53706 | MADISON | PRIMARY
53711 | FITCHBURG | ACCEPTABLE
53711 | MADISON | PRIMARY
53713 | FITCHBURG | ACCEPTABLE
53713 | MADISON | PRIMARY
53713 | MONONA | ACCEPTABLE
53714 | MADISON | PRIMARY
53714 | MONONA | ACCEPTABLE
53715 | MADISON | PRIMARY
53716 | MADISON | PRIMARY
53716 | MONONA | ACCEPTABLE
53717 | MADISON | PRIMARY
53718 | MADISON | PRIMARY
53719 | FITCHBURG | ACCEPTABLE
53719 | MADISON | PRIMARY
53725 | MADISON | PRIMARY
53726 | MADISON | PRIMARY
53744 | MADISON | PRIMARY
(21 rows)

If you eliminate the quals besides the zipcode column you get 61
rows and it gets much stranger, with legal municipalities that are
completely surrounded by Madison that the postal service would
rather you didn't use in addressing your envelopes, but they have
to deliver to anyway, and organizations inside Madison receiving
enough mail to (literally) have their own zip code -- where the
postal service allows the organization name as a deliverable
"city".

If you want to have your own fun with this data, you can download
it here:

http://federalgovernmentzipcodes.us/free-zipcode-database.csv

I was able to load it into PostgreSQL with this:

create table zipcode
(
recordnumber integer not null,
zipcode text not null,
zipcodetype text not null,
city text not null,
state text not null,
locationtype text not null,
lat double precision,
long double precision,
xaxis double precision not null,
yaxis double precision not null,
zaxis double precision not null,
worldregion text not null,
country text not null,
locationtext text,
location text,
decommisioned text not null,
taxreturnsfiled bigint,
estimatedpopulation bigint,
totalwages bigint,
notes text
);
comment on column zipcode.zipcode is 'Zipcode or military postal code(FPO/APO)';
comment on column zipcode.zipcodetype is 'Standard, PO BOX Only, Unique, Military(implies APO or FPO)';
comment on column zipcode.city is 'offical city name(s)';
comment on column zipcode.state is 'offical state, territory, or quasi-state (AA, AE, AP) abbreviation code';
comment on column zipcode.locationtype is 'Primary, Acceptable,Not Acceptable';
comment on column zipcode.lat is 'Decimal Latitude, if available';
comment on column zipcode.long is 'Decimal Longitude, if available';
comment on column zipcode.location is 'Standard Display (eg Phoenix, AZ ; Pago Pago, AS ; Melbourne, AU )';
comment on column zipcode.decommisioned is 'If Primary location, Yes implies historical Zipcode, No Implies current Zipcode; If not Primary, Yes implies Historical Placename';
comment on column zipcode.taxreturnsfiled is 'Number of Individual Tax Returns Filed in 2008';
copy zipcode from 'filepath' with (format csv, header);
alter table zipcode add primary key (recordnumber);
create unique index zipcode_city on zipcode (zipcode, city);

I bet there are all sorts of correlation possibilities with, for
example, latitude and longitude and other variables. With 81831
rows and so many correlations among the columns, it might be a
useful data set to test with.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 15.11.2014 18:49, Kevin Grittner
> If you eliminate the quals besides the zipcode column you get 61
> rows and it gets much stranger, with legal municipalities that are
> completely surrounded by Madison that the postal service would
> rather you didn't use in addressing your envelopes, but they have
> to deliver to anyway, and organizations inside Madison receiving
> enough mail to (literally) have their own zip code -- where the
> postal service allows the organization name as a deliverable
> "city".
>
> If you want to have your own fun with this data, you can download
> it here:
>
> http://federalgovernmentzipcodes.us/free-zipcode-database.csv
>
...
>
> I bet there are all sorts of correlation possibilities with, for
> example, latitude and longitude and other variables. With 81831
> rows and so many correlations among the columns, it might be a
> useful data set to test with.

Thanks for the link. I've been looking for a good dataset with such
data, and this one is by far the best one.

The current version of the patch supports only data types passed by
value (i.e. no varlena types - text, ), which means it's impossible to
build multivariate stats on some of the interesting columns (state,
city, ...).

I guess it's time to start working on removing this limitation.

Tomas

On Sun, Nov 16, 2014 at 3:35 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
> Thanks for the link. I've been looking for a good dataset with such
> data, and this one is by far the best one.
>
> The current version of the patch supports only data types passed by
> value (i.e. no varlena types - text, ), which means it's impossible to
> build multivariate stats on some of the interesting columns (state,
> city, ...).
>
> I guess it's time to start working on removing this limitation.
Tomas, what's your status on this patch? Are you planning to make it
more complicated than it is? For now I have switched it to a "Needs
Review" state because even your first version did not get advanced
review (that's quite big btw). I guess that we should switch it to the
next CF.
Regards,
--
Michael

On 8.12.2014 02:01, Michael Paquier wrote:
> On Sun, Nov 16, 2014 at 3:35 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
>> Thanks for the link. I've been looking for a good dataset with such
>> data, and this one is by far the best one.
>>
>> The current version of the patch supports only data types passed by
>> value (i.e. no varlena types - text, ), which means it's impossible to
>> build multivariate stats on some of the interesting columns (state,
>> city, ...).
>>
>> I guess it's time to start working on removing this limitation.
> Tomas, what's your status on this patch? Are you planning to make it
> more complicated than it is? For now I have switched it to a "Needs
> Review" state because even your first version did not get advanced
> review (that's quite big btw). I guess that we should switch it to the
> next CF.

Hello Michael,

I agree with moving the patch to the next CF - I'm working on the patch,
but I will take a bit more time to submit a new version and I can do
that in the next CF.

regards
Tomas

On 10/13/2014 01:00 AM, Tomas Vondra wrote:
> Hi,
>
> attached is a WIP patch implementing multivariate statistics.

Great! Really glad to see you working on this.

> + * FIXME This sample sizing is mostly OK when computing stats for
> + * individual columns, but when computing multi-variate stats
> + * for multivariate stats (histograms, mcv, ...) it's rather
> + * insufficient. For small number of dimensions it works, but
> + * for complex stats it'd be nice use sample proportional to
> + * the table (say, 0.5% - 1%) instead of a fixed size.

I don't think a fraction of the table is appropriate. As long as the
sample is random, the accuracy of a sample doesn't depend much on the
size of the population. For example, if you sample 1,000 rows from a
table with 100,000 rows, or 1000 rows from a table with 100,000,000
rows, the accuracy is pretty much the same. That doesn't change when you
go from a single variable to multiple variables.

You do need a bigger sample with multiple variables, however. My gut
feeling is that if you sample N rows for a single variable, with two
variables you need to sample N^2 rows to get the same accuracy. But it's
not proportional to the table size. (I have no proof for that, but I'm
sure there is literature on this.)

> + * Multivariate histograms
> + *
> + * Histograms are a collection of buckets, represented by n-dimensional
> + * rectangles. Each rectangle is delimited by an array of lower and
> + * upper boundaries, so that for for the i-th attribute
> + *
> + * min[i] <= value[i] <= max[i]
> + *
> + * Each bucket tracks frequency (fraction of tuples it contains),
> + * information about the inequalities, number of distinct values in
> + * each dimension (which is used when building the histogram) etc.
> + *
> + * The boundaries may be either inclusive or exclusive, or the whole
> + * dimension may be NULL.
> + *
> + * The buckets may overlap (assuming the build algorithm keeps the
> + * frequencies additive) or may not cover the whole space (i.e. allow
> + * gaps). This entirely depends on the algorithm used to build the
> + * histogram.

That sounds pretty exotic. These buckets are quite different from the
single-dimension buckets we currently have.

The paper you reference in partition_bucket() function, M.
Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating
Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference
1988: 28-36, actually doesn't mention overlapping buckets at all. I
haven't read the code in detail, but if it implements the algorithm from
that paper, there will be no overlap.

- Heikki

On 11.12.2014 17:53, Heikki Linnakangas wrote:
> On 10/13/2014 01:00 AM, Tomas Vondra wrote:
>> Hi,
>>
>> attached is a WIP patch implementing multivariate statistics.
>
> Great! Really glad to see you working on this.
>
>> + * FIXME This sample sizing is mostly OK when computing stats for
>> + * individual columns, but when computing multi-variate stats
>> + * for multivariate stats (histograms, mcv, ...) it's rather
>> + * insufficient. For small number of dimensions it works, but
>> + * for complex stats it'd be nice use sample proportional to
>> + * the table (say, 0.5% - 1%) instead of a fixed size.
>
> I don't think a fraction of the table is appropriate. As long as the
> sample is random, the accuracy of a sample doesn't depend much on
> the size of the population. For example, if you sample 1,000 rows
> from a table with 100,000 rows, or 1000 rows from a table with
> 100,000,000 rows, the accuracy is pretty much the same. That doesn't
> change when you go from a single variable to multiple variables.

I might be wrong, but I doubt that. First, I read a number of papers
while working on this patch, and all of them used samples proportional
to the data set. That's an indirect evidence, though.

> You do need a bigger sample with multiple variables, however. My gut
> feeling is that if you sample N rows for a single variable, with two
> variables you need to sample N^2 rows to get the same accuracy. But
> it's not proportional to the table size. (I have no proof for that,
> but I'm sure there is literature on this.)

Maybe. I think it's somehow related to the number of buckets (which
somehow determines the precision of the histogram). If you want 1000
buckets, the number of rows scanned needs to be e.g. 10x that. With
multi-variate histograms, we may shoot for more buckets (say, 100 in
each dimension).

>
>> + * Multivariate histograms
>> + *
>> + * Histograms are a collection of buckets, represented by n-dimensional
>> + * rectangles. Each rectangle is delimited by an array of lower and
>> + * upper boundaries, so that for for the i-th attribute
>> + *
>> + * min[i] <= value[i] <= max[i]
>> + *
>> + * Each bucket tracks frequency (fraction of tuples it contains),
>> + * information about the inequalities, number of distinct values in
>> + * each dimension (which is used when building the histogram) etc.
>> + *
>> + * The boundaries may be either inclusive or exclusive, or the whole
>> + * dimension may be NULL.
>> + *
>> + * The buckets may overlap (assuming the build algorithm keeps the
>> + * frequencies additive) or may not cover the whole space (i.e. allow
>> + * gaps). This entirely depends on the algorithm used to build the
>> + * histogram.
>
> That sounds pretty exotic. These buckets are quite different from
> the single-dimension buckets we currently have.
>
> The paper you reference in partition_bucket() function, M.
> Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating
> Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference
> 1988: 28-36, actually doesn't mention overlapping buckets at all. I
> haven't read the code in detail, but if it implements the algorithm
> from that paper, there will be no overlap.

The algorithm implemented in partition_bucket() is very simple and
naive, and it mostly resembles the algorithm described in the paper. I'm
sure there are differences, it's not a 1:1 implementation, but you're
right it produces non-overlapping buckets.

The point is that I envision more complex algorithms or different
histogram types, and some of them may produce overlapping buckets. Maybe
that's premature comment, and it will turn out it's not really necessary.

regards
Tomas

On Wed, Dec 10, 2014 at 5:15 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
> I agree with moving the patch to the next CF - I'm working on the patch,
> but I will take a bit more time to submit a new version and I can do
> that in the next CF.
OK cool. I just moved it by myself. I didn't see it yet registered in 2014-12.
Thanks,
--
Michael

On Mon, Dec 15, 2014 at 11:55 AM, Michael Paquier
<michael(dot)paquier(at)gmail(dot)com> wrote:
> On Wed, Dec 10, 2014 at 5:15 AM, Tomas Vondra <tv(at)fuzzy(dot)cz> wrote:
>> I agree with moving the patch to the next CF - I'm working on the patch,
>> but I will take a bit more time to submit a new version and I can do
>> that in the next CF.
> OK cool. I just moved it by myself. I didn't see it yet registered in 2014-12.
Marked as returned with feedback. No new version showed up in the last
month and this patch was waiting for input from author.
--
Michael

Hi,

attached is an updated version of the multivariate stats patch. This is
going to be a bit longer mail, so I'll put here a small ToC ;-)

1) patch split into 4 parts
2) where to start / documentation
3) state of the code
4) main changes/improvements
5) remaining limitations

The motivation and design ideas, explained in the first message of this
thread are still valid. It might be a good idea to read it first:

http://www.postgresql.org/message-id/flat/543AFA15(dot)4080608(at)fuzzy(dot)cz

BTW if you happen to go to FOSDEM [PGDay], I'll gladly give you an intro
into the patch in person, or discuss the patch in general.

1) Patch split into 4 parts
---------------------------
Firstly, the patch got broken into the following four pieces, to make
the reviews somewhat easier:

1) 0001-shared-infrastructure-and-functional-dependencies.patch

- infrastructure, shared by all the kinds of stats added
in the following patches (catalog, ALTER TABLE, ANALYZE ...)

- implementation of a simple statistics, tracking functional
dependencies between columns (previously called "associative
rules", but that's incorrect for several reasons)

- this does not modify the optimizer in any way

2) 0002-clause-reduction-using-functional-dependencies.patch

- applies the functional dependencies to optimizer (i.e. considers
the rules in clauselist_selectivity())

3) 0003-multivariate-MCV-lists.patch

- multivariate MCV lists (both ANALYZE and optimizer parts)

4) 0004-multivariate-histograms.patch

- multivariate histograms (both ANALYZE and optimizer parts)

You may look at the patches at github here:

https://github.com/tvondra/postgres/tree/multivariate-stats-squashed

The branch is not stable, i.e. I'll rebase / squash / force-push changes
in the future. (There's also multivariate-stats development branch with
unsquashed changes, but you don't want to look at that, trust me.)

The patches are not exactly small (being in the 50-100 kB range), but
that's mostly because of the amount of comments explaining the goals and
implementation details.

2) Where to start / documentation
---------------------------------
I strived to document all the pieces properly, mostly in the form of
comments. There's no sgml documentation at this point, which should
obviously change in the future.

Anyway, I'd suggest reading the first e-mail in this thread, explaining
the ideas, and then these comments:

1) functional dependencies (patch 0001)
- src/backend/utils/mvstats/dependencies.c

2) MCV lists (patch 0003)
- src/backend/utils/mvstats/mcv.c

3) histograms (patch 0004)
- src/backend/utils/mvstats/mcv.c

- also see clauselist_mv_selectivity_mcvlist() in clausesel.c
- also see clauselist_mv_selectivity_histogram() in clausesel.c

4) selectivity estimation (patches 0002-0004)
- all in src/backend/optimizer/path/clausesel.c
- clauselist_selectivity() - overview of how the stats are applied
- clauselist_apply_dependencies() - functional dependencies reduction
- clauselist_mv_selectivity_mcvlist() - MCV list estimation
- clauselist_mv_selectivity_histogram() - histogram estimation

3) State of the code
--------------------
I've spent a fair amount of time testing the patches, and while I
believe there are no segfaults or so, I know parts of the code need a
bit more love.

The part most in need of improvements / comments is probably the code in
clausesel.c - that seems a bit quirky. Reviews / comments regarding this
part of the code are very welcome - I'm sure there are many ways to
improve this part.

There are a few FIXMEs elsewhere (e.g. about memory allocation in the
(de)serialization code), but those are mostly well-defined issues that I
know how to address (at least I believe so).

4) Main changes/improvements
----------------------------
There are many significant improvements. The previous patch version was
in the 'proof of concept' category (missing pieces, knowingly broken in
some areas), the current patch should 'mostly work'.

The patch fixes two most annoying limitations of the first version:

(a) support for all data types (not just those passed by value)
(b) handles NULL values properly
(c) adds support for IS [NOT] NULL clauses

Aside from that the code was significantly improved, there are proper
regression tests and plenty of comments explaining the details.

5) Remaining limitations
------------------------

(a) limited to stats on 8 columns

This is mostly just a 'safeguard' restriction.

(b) only data types with '<' operator

I don't think this will change anytime soon, because all the
algorithms for building the stats rely on this. I don't see
this as a serious limitation though.

(c) not handling DROP COLUMN or DROP TABLE and so on

Currently this is not handled at all (so the regression tests
do an explicit DELETE from the pg_mv_statistic catalog).

Handling the DROP TABLE won't be difficult, it's similar to the
current stats. Handling ALTER TABLE ... DROP COLUMN will be much
more tricky I guess - should we drop all the stats referencing
that column, or should we just remove it from the stats? Or
should we keep it and treat it as NULL? Not sure what's the best
solution.

(d) limited list of compatible WHERE clauses

The initial patch handled only simple operator clauses

(Var op Constant)

where operator is one of ('<', '<=', '=', '>=', '>'). Now it also
handles IS [NOT] NULL clauses. Adding more clause types should
not be overly difficult - starting with more traditional
'BooleanTest' conditions, or even multi-column conditions
(Var op Var)

which are difficult to estimate using simple-column stats.

(e) optimizer uses single stats per table

This is still true and I don't think this will change soon. i do
have some ideas on how to merge multiple stats etc. but it's
certainly complex stuff, unlikely to happen within this CF. The
patch makes a lot of sense even without this particular feature,
because you can create multiple stats, each suitable for different
queries.

(f) no JOIN conditions

Similarly to the previous point, it's on the TODO but it's not
going to happen in this CF.

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

Patch 0001 needs changes for OIDs since my patch was
committed. The attached is compatible with current master.

And I tried this like this, and got the following error on
analyze. But unfortunately I don't have enough time to
investigate it now.

postgres=# create table t1 (a int, b int, c int);
insert into t1 (select a/ 10000, a / 10000, a / 10000 from generate_series(0, 99999) a);
postgres=# analyze t1;
ERROR: invalid memory alloc request size 1485176862

regards,

At Sat, 24 Jan 2015 21:21:39 +0100, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <54C3FED3(dot)1060600(at)2ndquadrant(dot)com>
> Hi,
>
> attached is an updated version of the multivariate stats patch. This is
> going to be a bit longer mail, so I'll put here a small ToC ;-)
>
> 1) patch split into 4 parts
> 2) where to start / documentation
> 3) state of the code
> 4) main changes/improvements
> 5) remaining limitations
>
> The motivation and design ideas, explained in the first message of this
> thread are still valid. It might be a good idea to read it first:
>
> http://www.postgresql.org/message-id/flat/543AFA15(dot)4080608(at)fuzzy(dot)cz
>
> BTW if you happen to go to FOSDEM [PGDay], I'll gladly give you an intro
> into the patch in person, or discuss the patch in general.
>
>
> 1) Patch split into 4 parts
> ---------------------------
> Firstly, the patch got broken into the following four pieces, to make
> the reviews somewhat easier:
>
> 1) 0001-shared-infrastructure-and-functional-dependencies.patch
>
> - infrastructure, shared by all the kinds of stats added
> in the following patches (catalog, ALTER TABLE, ANALYZE ...)
>
> - implementation of a simple statistics, tracking functional
> dependencies between columns (previously called "associative
> rules", but that's incorrect for several reasons)
>
> - this does not modify the optimizer in any way
> 2) 0002-clause-reduction-using-functional-dependencies.patch
>
> - applies the functional dependencies to optimizer (i.e. considers
> the rules in clauselist_selectivity())
>
> 3) 0003-multivariate-MCV-lists.patch
>
> - multivariate MCV lists (both ANALYZE and optimizer parts)
>
> 4) 0004-multivariate-histograms.patch
>
> - multivariate histograms (both ANALYZE and optimizer parts)
>
>
> You may look at the patches at github here:
>
> https://github.com/tvondra/postgres/tree/multivariate-stats-squashed
>
> The branch is not stable, i.e. I'll rebase / squash / force-push changes
> in the future. (There's also multivariate-stats development branch with
> unsquashed changes, but you don't want to look at that, trust me.)
>
> The patches are not exactly small (being in the 50-100 kB range), but
> that's mostly because of the amount of comments explaining the goals and
> implementation details.
>
>
> 2) Where to start / documentation
> ---------------------------------
> I strived to document all the pieces properly, mostly in the form of
> comments. There's no sgml documentation at this point, which should
> obviously change in the future.
>
> Anyway, I'd suggest reading the first e-mail in this thread, explaining
> the ideas, and then these comments:
>
> 1) functional dependencies (patch 0001)
> - src/backend/utils/mvstats/dependencies.c
>
> 2) MCV lists (patch 0003)
> - src/backend/utils/mvstats/mcv.c
>
> 3) histograms (patch 0004)
> - src/backend/utils/mvstats/mcv.c
>
> - also see clauselist_mv_selectivity_mcvlist() in clausesel.c
> - also see clauselist_mv_selectivity_histogram() in clausesel.c
>
> 4) selectivity estimation (patches 0002-0004)
> - all in src/backend/optimizer/path/clausesel.c
> - clauselist_selectivity() - overview of how the stats are applied
> - clauselist_apply_dependencies() - functional dependencies reduction
> - clauselist_mv_selectivity_mcvlist() - MCV list estimation
> - clauselist_mv_selectivity_histogram() - histogram estimation
>
>
> 3) State of the code
> --------------------
> I've spent a fair amount of time testing the patches, and while I
> believe there are no segfaults or so, I know parts of the code need a
> bit more love.
>
> The part most in need of improvements / comments is probably the code in
> clausesel.c - that seems a bit quirky. Reviews / comments regarding this
> part of the code are very welcome - I'm sure there are many ways to
> improve this part.
>
> There are a few FIXMEs elsewhere (e.g. about memory allocation in the
> (de)serialization code), but those are mostly well-defined issues that I
> know how to address (at least I believe so).
>
>
> 4) Main changes/improvements
> ----------------------------
> There are many significant improvements. The previous patch version was
> in the 'proof of concept' category (missing pieces, knowingly broken in
> some areas), the current patch should 'mostly work'.
>
> The patch fixes two most annoying limitations of the first version:
>
> (a) support for all data types (not just those passed by value)
> (b) handles NULL values properly
> (c) adds support for IS [NOT] NULL clauses
>
> Aside from that the code was significantly improved, there are proper
> regression tests and plenty of comments explaining the details.
>
>
> 5) Remaining limitations
> ------------------------
>
> (a) limited to stats on 8 columns
>
> This is mostly just a 'safeguard' restriction.
>
> (b) only data types with '<' operator
>
> I don't think this will change anytime soon, because all the
> algorithms for building the stats rely on this. I don't see
> this as a serious limitation though.
>
> (c) not handling DROP COLUMN or DROP TABLE and so on
>
> Currently this is not handled at all (so the regression tests
> do an explicit DELETE from the pg_mv_statistic catalog).
>
> Handling the DROP TABLE won't be difficult, it's similar to the
> current stats. Handling ALTER TABLE ... DROP COLUMN will be much
> more tricky I guess - should we drop all the stats referencing
> that column, or should we just remove it from the stats? Or
> should we keep it and treat it as NULL? Not sure what's the best
> solution.
>
> (d) limited list of compatible WHERE clauses
>
> The initial patch handled only simple operator clauses
>
> (Var op Constant)
>
> where operator is one of ('<', '<=', '=', '>=', '>'). Now it also
> handles IS [NOT] NULL clauses. Adding more clause types should
> not be overly difficult - starting with more traditional
> 'BooleanTest' conditions, or even multi-column conditions
> (Var op Var)
>
> which are difficult to estimate using simple-column stats.
>
> (e) optimizer uses single stats per table
>
> This is still true and I don't think this will change soon. i do
> have some ideas on how to merge multiple stats etc. but it's
> certainly complex stuff, unlikely to happen within this CF. The
> patch makes a lot of sense even without this particular feature,
> because you can create multiple stats, each suitable for different
> queries.
>
> (f) no JOIN conditions
>
> Similarly to the previous point, it's on the TODO but it's not
> going to happen in this CF.
>
>
> kind regards
>
> --
> Tomas Vondra http://www.2ndQuadrant.com/
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

On 20.3.2015 09:33, Kyotaro HORIGUCHI wrote:
> Hello,
>
>
> Patch 0001 needs changes for OIDs since my patch was
> committed. The attached is compatible with current master.

Thanks. I plan to submit a new version of the patch in a few days, with
significant progress in various directions. I'll have to rebase to
current master before submitting the new version anyway (which includes
fixing duplicate OIDs).

> And I tried this like this, and got the following error on
> analyze. But unfortunately I don't have enough time to
> investigate it now.
>
> postgres=# create table t1 (a int, b int, c int);
> insert into t1 (select a/ 10000, a / 10000, a / 10000 from
> generate_series(0, 99999) a);
> postgres=# analyze t1;
> ERROR: invalid memory alloc request size 1485176862

Interesting - particularly because this does not involve any
multivariate stats. I can't reproduce it with the current version of the
patch, so either it's unrelated, or I've fixed it since posting the last
version.

regards

--
Tomas Vondra http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

> > Patch 0001 needs changes for OIDs since my patch was
> > committed. The attached is compatible with current master.
>
> Thanks. I plan to submit a new version of the patch in a few days, with
> significant progress in various directions. I'll have to rebase to
> current master before submitting the new version anyway (which includes
> fixing duplicate OIDs).
>
> > And I tried this like this, and got the following error on
> > analyze. But unfortunately I don't have enough time to
> > investigate it now.
> >
> > postgres=# create table t1 (a int, b int, c int);
> > insert into t1 (select a/ 10000, a / 10000, a / 10000 from
> > generate_series(0, 99999) a);
> > postgres=# analyze t1;
> > ERROR: invalid memory alloc request size 1485176862
>
> Interesting - particularly because this does not involve any
> multivariate stats. I can't reproduce it with the current version of the
> patch, so either it's unrelated, or I've fixed it since posting the last
> version.

Sorry, not shown above, the *previous* t1 had been done "alter
table t1 add statistics (a, b, c)". Removing t1 didn't remove the
setting. reiniting cluster let me do that without error.

The steps throughout was as following.
===
create table t1 (a int, b int, c int);
alter table t1 add statistics (histogram) on (a, b, c);
drop table t1; -- This does not remove the above setting.
create table t1 (a int, b int, c int);
insert into t1 (select a/ 10000, a / 10000, a / 10000 from generate_series(0, 99999) a);insert into t1 ...
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello,

On 03/24/15 06:34, Kyotaro HORIGUCHI wrote:
>
> Sorry, not shown above, the *previous* t1 had been done "alter table
> t1 add statistics (a, b, c)". Removing t1 didn't remove the setting.
> reiniting cluster let me do that without error.

OK, thanks. My guess is this issue got already fixed in my working copy,
but I will double-check that.

Admittedly, the management of the stats (e.g. removing stats when the
table is dropped) is one of the incomplete parts. You have to delete the
rows manually from pg_mv_statistic.

--
--
Tomas Vondra http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

attached is a new version of the patch series. Aside from fixing various
issues (crashes, memory leaks). The patches are rebased to current
master, and I also attach a few SQL scripts I used for testing (nothing
fancy, just stress-testing all the parts the patch touches).

The main changes in the patches (requiring plenty of changes in the
other parts) are about these:

(1) combining multiple statistics on a table
--------------------------------------------

In the previous version of the patch, it was only possible to use a
single statistics on a table - when there was a statistics "covering"
all the conditions it worked fine, but that's not always the case.

The new patch is able to combine multiple statistics by decomposing the
probability (=selectivity) into conditional probabilities. Imagine
estimating selectivity of clauses

WHERE (a=1) AND (b=1) AND (c=1) AND (d=1)

with statistics on [a,b,c] and [b,c,d]. The selectivity may be split for
example like this:

P(a=1,b=1,c=1,d=1) = P(a=1,b=1,c=1) * P(d=1|a=1,b=1,c=1)

where P(a=1,b=1,c=1) may be estimated using statistics [a,b,c], and the
second may be simplified like this:

P(d=1|a=1,b=1,c=1) = P(d=1|b=1,c=1)

using the assumption "no multivariate stats => independent". Both these
probabilities match the existing statistics.

The idea is described a bit more in the part #5 of the patch.

(2) choosing the best combination of statistics
-----------------------------------------------

There may be more statistics on a table, and multiple possible ways to
use them to estimate the clauses (different ordering, overlapping
statistics, etc.).

The patch formulates this as an optimization task with two goals.

(a) cover as many clauses as possible
(b) reuse as many conditions (i.e. dependencies) as possible

and implements two algorithms to solve this: (a) exhaustive, walking
through all possible states (using dynamic programming), and (b) greedy,
choosing the best local solution in each step.

The time requirements for the exhaustive solution grows pretty quickly
with the number of clauses and statistics on a table (~ O(N!)). The
greedy is much faster, as it's ~O(N) and in fact much more time is spent
in actually processing the selected statistics (walking through the
histograms etc.).

I assume the exhaustive search may find a better solution in some cases
(that the greedy algorithm misses), but so far I've been unable to come
up with such example.

To make this easier to test, I've added GUC to switch between these
algorithms easily (set to 'greedy' by default)

mvstat_search = {'greedy', 'exhaustive'}

I assume this GUC will be removed eventually, after we figure out which
algorithm is the right one.

(3) estimation of more complex conditions (AND/OR clauses)
----------------------------------------------------------

I've added ability to estimate more complex clauses - combinations of
AND/OR clauses and such. It's somewhat incomplete at the moment, but
hopefully the ideas will be clear from the TODOs/FIXMEs along the way.

Let me know if you have any questions about this version of the patch,
or about the ideas it implements in general.

I also welcome real-world examples of poorly estimated queries, so that
I can test if these patches improve that particular case situation.

regards

--
Tomas Vondra http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Mon, Mar 30, 2015 at 5:26 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> Hello,
>
> attached is a new version of the patch series. Aside from fixing various
> issues (crashes, memory leaks). The patches are rebased to current
> master, and I also attach a few SQL scripts I used for testing (nothing
> fancy, just stress-testing all the parts the patch touches).
>

Hi Tomas,

I get cascading conflicts in pg_proc.h. It looked easy enough to fix,
except then I get compiler errors:

funcapi.c: In function 'get_func_trftypes':
funcapi.c:890: warning: unused variable 'procStruct'
utils/fmgrtab.o:(.rodata+0x10cf8): undefined reference to `_null_'
utils/fmgrtab.o:(.rodata+0x10d18): undefined reference to `_null_'
utils/fmgrtab.o:(.rodata+0x10d38): undefined reference to `_null_'
utils/fmgrtab.o:(.rodata+0x10d58): undefined reference to `_null_'
collect2: ld returned 1 exit status
make[2]: *** [postgres] Error 1
make[1]: *** [all-backend-recurse] Error 2
make: *** [all-src-recurse] Error 2
make: *** Waiting for unfinished jobs....
make: *** [temp-install] Error 2

Cheers,

Jeff

* Jeff Janes (jeff(dot)janes(at)gmail(dot)com) wrote:
> On Mon, Mar 30, 2015 at 5:26 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
> wrote:
> > attached is a new version of the patch series. Aside from fixing various
> > issues (crashes, memory leaks). The patches are rebased to current
> > master, and I also attach a few SQL scripts I used for testing (nothing
> > fancy, just stress-testing all the parts the patch touches).
>
> I get cascading conflicts in pg_proc.h. It looked easy enough to fix,
> except then I get compiler errors:

Yeah, those are because you didn't address the new column which was
added to pg_proc. You need to add another _null_ in the pg_proc.h lines
in the correct place, apparently on four lines.

Thanks!

Stephen

On Tue, Apr 28, 2015 at 9:13 AM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:

> * Jeff Janes (jeff(dot)janes(at)gmail(dot)com) wrote:
> > On Mon, Mar 30, 2015 at 5:26 PM, Tomas Vondra <
> tomas(dot)vondra(at)2ndquadrant(dot)com>
> > wrote:
> > > attached is a new version of the patch series. Aside from fixing
> various
> > > issues (crashes, memory leaks). The patches are rebased to current
> > > master, and I also attach a few SQL scripts I used for testing (nothing
> > > fancy, just stress-testing all the parts the patch touches).
> >
> > I get cascading conflicts in pg_proc.h. It looked easy enough to fix,
> > except then I get compiler errors:
>
> Yeah, those are because you didn't address the new column which was
> added to pg_proc. You need to add another _null_ in the pg_proc.h lines
> in the correct place, apparently on four lines.
>

Thanks. I think I tried that, but was still having trouble. But it turns
out that the trouble was for an unrelated reason, and I got it to compile
now.

Some of the fdw's need a patch as well in order to compile, see attached.

Cheers,

Jeff

Hi,

On 04/28/15 19:36, Jeff Janes wrote:
>
...
>
> Thanks. I think I tried that, but was still having trouble. But it
> turns out that the trouble was for an unrelated reason, and I got it
> to compile now.

Yeah, a new column was added to pg_proc the day after I submitted the
pacth. Will address that in a new version, hopefully in a few days.

>
> Some of the fdw's need a patch as well in order to compile, see
> attached.

Thanks, I forgot to tweak the clauselist_selectivity() calls contrib :-(

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attached is v6 of the multivariate stats, with a number of improvements:

1) fix of the contrib compile-time errors (reported by Jeff)

2) fix of pg_proc issues (reported by Jeff)

3) rebase to current master

4) fix a bunch of issues in the previous patches, due to referencing
some parts too early (e.g. histograms in the first patch, etc.)

5) remove the explicit DELETEs from pg_mv_statistic (in the regression
tests), this is now handled automatically by DROP TABLE etc.

6) number of performance optimizations in selectivity estimations:

(a) minimize calls to get_oprrest, significantly reducing
syscache calls

(b) significant reduction of palloc overhead in deserialization of
MCV lists and histograms

(c) use more compact serialized representation of MCV lists and
histograms, often removing ~50% of the size

(d) use histograms with limited deserialization, which also allows
caching function calls

(e) modified histogram bucket partitioning, resulting in more even
bucket distribution (i.e. producing buckets with more equal
density and about equal size of each dimension)

7) add functions for listing MCV list items and histogram buckets:

- pg_mv_mcvlist_items(oid)
- pg_mv_histogram_buckets(oid, type)

This is quite useful when analyzing the MCV lists / histograms.

8) improved support for OR clauses

9) allow calling pull_varnos() on expression trees containing
RestrictInfo nodes (not sure if this is the right fix, it's being
discussed in another thread)

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello, this might be somewhat out of place but strongly related
to this patch so I'll propose this here.

This is a proposal of new feature for this patch or asking for
your approval for my moving on this as a different (but very
close) project.

===

> Attached is v6 of the multivariate stats, with a number of
> improvements:
...
> 2) fix of pg_proc issues (reported by Jeff)
>
> 3) rebase to current master

Unfortunately, the v6 patch suffers some system oid conflicts
with recently added ones. And what more unfortunate for me is
that the code for functional dependencies looks undone:)

I mention this because I recently had a issue from strong
correlation between two columns in dbt3 benchmark. Two columns in
some table are in strong correlation but not in functional
dependencies, there are too many values and the distribution of
them is very uniform so MCV is no use for the table (histogram
has nothing to do with equal conditions). As the result, planner
estimates the number of rows largely wrong as expected especially
for joins.

I, then, had a try calculating the ratio between the product of
distinctness of every column and the distinctness of the set of
the columns, call it multivariate coefficient here, and found
that it looks greately useful for the small storage space, less
calculation, and simple code.

The attached first is a script to generate problematic tables.
And the second is a patch to make use of the mv coef on current
master. The patch is a very primitive POC so no syntactical
interfaces involved.

For the case of your first example,

> =# create table t (a int, b int, c int);
> =# insert into t (select a/10000, a/10000, a/10000
> from generate_series(0, 999999) a);
> =# analyze t;
> =# explain analyze select * from t where a = 1 and b = 1 and c = 1;
> Seq Scan on t (cost=0.00..22906.00 rows=1 width=12)
> (actual time=3.878..250.628 rows=10000 loops=1)

Make use of mv coefficient.

> =# insert into pg_mvcoefficient values ('t'::regclass, 1, 2, 3, 0);
> =# analyze t;
> =# explain analyze select * from t where a = 1 and b = 1 and c = 1;
> Seq Scan on t (cost=0.00..22906.00 rows=9221 width=12)
> (actual time=3.740..242.330 rows=10000 loops=1)

Row number estimation was largely improved.

Well, my example,

> $ perl gentbl.pl 10000 | psql postgres
> $ psql postgres
> =# explain analyze select * from t1 where a = 1 and b = 2501;
> Seq Scan on t1 (cost=0.00..6216.00 rows=1 width=8)
> (actual time=0.030..66.005 rows=8 loops=1)
>
> =# explain analyze select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b);
> Hash Join (cost=1177.00..11393.76 rows=76 width=16)
> (actual time=29.811..322.271 rows=320000 loops=1)

Too bad estimate for the join.

> =# insert into pg_mvcoefficient values ('t1'::regclass, 1, 2, 0, 0);
> =# analyze t1;
> =# explain analyze select * from t1 where a = 1 and b = 2501;
> Seq Scan on t1 (cost=0.00..6216.00 rows=8 width=8)
> (actual time=0.032..104.144 rows=8 loops=1)
>
> =# explain analyze select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b);
> Hash Join (cost=1177.00..11393.76 rows=305652 width=16)
> (actual time=40.642..325.679 rows=320000 loops=1)

It gives almost correct estimations.

I think the result above shows that the multivariate coefficient
is significant to imporove estimates when correlated colums are
involved.

Would you consider this in your patch? Otherwise I move on this
as a different project from yours if you don't mind. Except user
interface won't conflict with yours, I suppose. But finally they
should need some labor of consolidation.

regards,

> 1) fix of the contrib compile-time errors (reported by Jeff)
>
> 2) fix of pg_proc issues (reported by Jeff)
>
> 3) rebase to current master
>
> 4) fix a bunch of issues in the previous patches, due to referencing
> some parts too early (e.g. histograms in the first patch, etc.)
>
> 5) remove the explicit DELETEs from pg_mv_statistic (in the regression
> tests), this is now handled automatically by DROP TABLE etc.
>
> 6) number of performance optimizations in selectivity estimations:
>
> (a) minimize calls to get_oprrest, significantly reducing
> syscache calls
>
> (b) significant reduction of palloc overhead in deserialization of
> MCV lists and histograms
>
> (c) use more compact serialized representation of MCV lists and
> histograms, often removing ~50% of the size
>
> (d) use histograms with limited deserialization, which also allows
> caching function calls
>
> (e) modified histogram bucket partitioning, resulting in more even
> bucket distribution (i.e. producing buckets with more equal
> density and about equal size of each dimension)
>
> 7) add functions for listing MCV list items and histogram buckets:
>
> - pg_mv_mcvlist_items(oid)
> - pg_mv_histogram_buckets(oid, type)
>
> This is quite useful when analyzing the MCV lists / histograms.
>
> 8) improved support for OR clauses
>
> 9) allow calling pull_varnos() on expression trees containing
> RestrictInfo nodes (not sure if this is the right fix, it's being
> discussed in another thread)

--
Kyotaro Horiguchi
NTT Open Source Software Center

On 05/13/15 10:31, Kyotaro HORIGUCHI wrote:
> Hello, this might be somewhat out of place but strongly related
> to this patch so I'll propose this here.
>
> This is a proposal of new feature for this patch or asking for
> your approval for my moving on this as a different (but very
> close) project.
>
> ===
>
>> Attached is v6 of the multivariate stats, with a number of
>> improvements:
> ...
>> 2) fix of pg_proc issues (reported by Jeff)
>>
>> 3) rebase to current master
>
> Unfortunately, the v6 patch suffers some system oid conflicts
> with recently added ones. And what more unfortunate for me is
> that the code for functional dependencies looks undone:)

I'll fix the OID conflicts once the CF completes, which should be in a
few days I guess. Until then you can apply it on top of master from
about May 6 (that's when the v6 was created, and there should be no
conflicts).

Regarding the functional dependencies - you're right there's room for
improvement. For example it only works with dependencies between pairs
of columns, not multi-column dependencies. Is this what you mean by
incomplete?

> I mention this because I recently had a issue from strong
> correlation between two columns in dbt3 benchmark. Two columns in
> some table are in strong correlation but not in functional
> dependencies, there are too many values and the distribution of
> them is very uniform so MCV is no use for the table (histogram
> has nothing to do with equal conditions). As the result, planner
> estimates the number of rows largely wrong as expected especially
> for joins.

I think the other statistics types (esp. histograms) might be more
useful here, but I assume you haven't tried that because of the conflicts.

The current patch does not handle joins at all, though.

> I, then, had a try calculating the ratio between the product of
> distinctness of every column and the distinctness of the set of
> the columns, call it multivariate coefficient here, and found
> that it looks greately useful for the small storage space, less
> calculation, and simple code.

So when you have two columns A and B, you compute this:

ndistinct(A) * ndistinct(B)
---------------------------
ndistinct(A,B)

where ndistinc(...) means number of distinct values in the column(s)?

> The attached first is a script to generate problematic tables.
> And the second is a patch to make use of the mv coef on current
> master. The patch is a very primitive POC so no syntactical
> interfaces involved.
>
> For the case of your first example,
>
>> =# create table t (a int, b int, c int);
>> =# insert into t (select a/10000, a/10000, a/10000
>> from generate_series(0, 999999) a);
>> =# analyze t;
>> =# explain analyze select * from t where a = 1 and b = 1 and c = 1;
>> Seq Scan on t (cost=0.00..22906.00 rows=1 width=12)
>> (actual time=3.878..250.628 rows=10000 loops=1)
>
> Make use of mv coefficient.
>
>> =# insert into pg_mvcoefficient values ('t'::regclass, 1, 2, 3, 0);
>> =# analyze t;
>> =# explain analyze select * from t where a = 1 and b = 1 and c = 1;
>> Seq Scan on t (cost=0.00..22906.00 rows=9221 width=12)
>> (actual time=3.740..242.330 rows=10000 loops=1)
>
> Row number estimation was largely improved.

With my patch:

alter table t add statistics (mcv) on (a,b,c);
analyze t;
select * from pg_mv_stats;

tablename | attnums | mcvbytes | mcvinfo
-----------+---------+----------+------------
t | 1 2 3 | 2964 | nitems=100

explain (analyze,timing off)
select * from t where a = 1 and b = 1 and c = 1;

QUERY PLAN
------------------------------------------------------------
Seq Scan on t (cost=0.00..22906.00 rows=9533 width=12)
(actual rows=10000 loops=1)
Filter: ((a = 1) AND (b = 1) AND (c = 1))
Rows Removed by Filter: 990000
Planning time: 0.233 ms
Execution time: 93.212 ms
(5 rows)

alter table t drop statistics all;
alter table t add statistics (histogram) on (a,b,c);
analyze t;

explain (analyze,timing off)
select * from t where a = 1 and b = 1 and c = 1;

QUERY PLAN
--------------------------------------------------------------------
Seq Scan on t (cost=0.00..22906.00 rows=9667 width=12)
(actual rows=10000 loops=1)
Filter: ((a = 1) AND (b = 1) AND (c = 1))
Rows Removed by Filter: 990000
Planning time: 0.594 ms
Execution time: 109.917 ms
(5 rows)

So both the MCV list and histogram do quite a good work here, but there
are certainly cases when that does not work and the mvcoefficient works
better.

> Well, my example,
>
>> $ perl gentbl.pl 10000 | psql postgres
>> $ psql postgres
>> =# explain analyze select * from t1 where a = 1 and b = 2501;
>> Seq Scan on t1 (cost=0.00..6216.00 rows=1 width=8)
>> (actual time=0.030..66.005 rows=8 loops=1)
>>
>> =# explain analyze select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b);
>> Hash Join (cost=1177.00..11393.76 rows=76 width=16)
>> (actual time=29.811..322.271 rows=320000 loops=1)
>
> Too bad estimate for the join.
>
>> =# insert into pg_mvcoefficient values ('t1'::regclass, 1, 2, 0, 0);
>> =# analyze t1;
>> =# explain analyze select * from t1 where a = 1 and b = 2501;
>> Seq Scan on t1 (cost=0.00..6216.00 rows=8 width=8)
>> (actual time=0.032..104.144 rows=8 loops=1)
>>
>> =# explain analyze select * from t1 join t2 on (t1.a = t2.a and t1.b = t2.b);
>> Hash Join (cost=1177.00..11393.76 rows=305652 width=16)
>> (actual time=40.642..325.679 rows=320000 loops=1)
>
> It gives almost correct estimations.

The current patch does not handle joins, but it's one of the TODO items.

>
> I think the result above shows that the multivariate coefficient
> is significant to imporove estimates when correlated colums are
> involved.

Yes, it looks interesting. I'm wondering what are the "failure cases"
when the coefficient approach does not work. It seems to me it relies on
an assumption of consistency for all the ndistinct values. For example
lets assume you have two columns - A and B, each with 1000 distinct
values, and that each value in A has 100 matching values in B, so the
coefficient is ~10

1,000 * 1,000 / 100,000 = 10

Now, let's assume the distribution looks differently - with first 100
values in A matching all 1000 values of B, and the remaining 900 values
just a single B value. Then

1,000 * 1,000 / (100,000 + 900) = ~9,9

So a very different distribution, but almost the same coefficient.

Are there any other assumptions like this?

Also, does the coefficient work only for equality conditions only?

>
> Would you consider this in your patch? Otherwise I move on this
> as a different project from yours if you don't mind. Except user
> interface won't conflict with yours, I suppose. But finally they
> should need some labor of consolidation.

I think it's a neat idea, and I think it might be added to the patch. It
would fit in quite nicely, actually - I already do have other kinds of
stats for addition, but I'm not going to work on that in the near
future. It will require changes in some parts of the patch (selecting
the stats for a list of clauses) and I'd like to complete the current
patch first, and then add features in follow-up patches.

>
> regards,

regards
Tomas

Hello,

At Thu, 14 May 2015 12:35:50 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55547A86(dot)8020400(at)2ndquadrant(dot)com>
>
> On 05/13/15 10:31, Kyotaro HORIGUCHI wrote:
> > Hello, this might be somewhat out of place but strongly related
> > to this patch so I'll propose this here.
> >
> > This is a proposal of new feature for this patch or asking for
> > your approval for my moving on this as a different (but very
> > close) project.
> >
> > ===
> >
> >> Attached is v6 of the multivariate stats, with a number of
> >> improvements:
> > ...
> >> 2) fix of pg_proc issues (reported by Jeff)
> >>
> >> 3) rebase to current master
> >
> > Unfortunately, the v6 patch suffers some system oid conflicts
> > with recently added ones. And what more unfortunate for me is
> > that the code for functional dependencies looks undone:)
>
> I'll fix the OID conflicts once the CF completes, which should be in a
> few days I guess. Until then you can apply it on top of master from
> about May 6 (that's when the v6 was created, and there should be no
> conflicts).

I applied it with further fixing. It wasn't a problem :)

> Regarding the functional dependencies - you're right there's room for
> improvement. For example it only works with dependencies between pairs
> of columns, not multi-column dependencies. Is this what you mean by
> incomplete?

No, It overruns dependencies->deps because build_mv_dependencies
stores many elements into dependencies->deps[n] although it
really has a room for only one element. I suppose that you paused
writing it when you noticed that the number of required elements
is unknown before finising walk through all pairs of
values. palloc'ing numattrs^2 is reasonable enough as POC code
for now. Am I looking wrong version of patch?

- dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData))
+ dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData) +
+ sizeof(MVDependency) * numattrs * numattrs);

> > I mention this because I recently had a issue from strong
> > correlation between two columns in dbt3 benchmark. Two columns in
> > some table are in strong correlation but not in functional
> > dependencies, there are too many values and the distribution of
> > them is very uniform so MCV is no use for the table (histogram
> > has nothing to do with equal conditions). As the result, planner
> > estimates the number of rows largely wrong as expected especially
> > for joins.
>
> I think the other statistics types (esp. histograms) might be more
> useful here, but I assume you haven't tried that because of the
> conflicts.
>
> The current patch does not handle joins at all, though.

Well, that's one of the resons. But I understood that any
deterministic estimation cannot be applied for such distribution
when I saw what made the wrong estimation. eqsel and eqsel_join
finally relies on random match assumption on uniform distribution
when the value is not found in MCV list. And functional
dependencies stuff in your old patch (which works) (rightfully)
failed to find such relationship between the problematic
columns. So I tried ndistinct, which is not contained in your
patch to see how it works well.

> > I, then, had a try calculating the ratio between the product of
> > distinctness of every column and the distinctness of the set of
> > the columns, call it multivariate coefficient here, and found
> > that it looks greately useful for the small storage space, less
> > calculation, and simple code.
>
> So when you have two columns A and B, you compute this:
>
> ndistinct(A) * ndistinct(B)
> ---------------------------
> ndistinct(A,B)

Yes, I used the reciprocal of that, though.

> where ndistinc(...) means number of distinct values in the column(s)?

Yes.

> > The attached first is a script to generate problematic tables.
> > And the second is a patch to make use of the mv coef on current
> > master. The patch is a very primitive POC so no syntactical
> > interfaces involved.
...
> > Make use of mv coefficient.
> >
> >> =# insert into pg_mvcoefficient values ('t'::regclass, 1, 2, 3, 0);
> >> =# analyze t;
> >> =# explain analyze select * from t where a = 1 and b = 1 and c = 1;
> >> Seq Scan on t (cost=0.00..22906.00 rows=9221 width=12)
> >> (actual time=3.740..242.330 rows=10000 loops=1)
> >
> > Row number estimation was largely improved.
>
> With my patch:
>
> alter table t add statistics (mcv) on (a,b,c);
...
> Seq Scan on t (cost=0.00..22906.00 rows=9533 width=12)

Yes, your MV-MCV list should have one third of all possible (set
of) values so it works fine, I guess. But my original problem was
occurred on the condition that (the single column) MCVs contain
under 1% of possible values, MCV would not work for such cases,
but its very uniform distribution helps random assumption to
work.

> $ perl gentbl.pl 200000 | psql postgres
<takes a while..>
> posttres=# alter table t1 add statistics (mcv true) on (a, b);
> postgres=# analyze t1;
> postgres=# explain analyze select * from t1 where a = 1 and b = 2501;
> Seq Scan on t1 (cost=0.00..124319.00 rows=1 width=8)
> (actual time=0.051..1250.773 rows=8 loops=1)

The estimate "rows=1" is internally 2.4e-11, 3.33e+11 times
smaller than the real number. This will result in roughly the
same order of error for joins. This is because MV-MCV holds too
small part of the domain and then calculated using random
assumption. This won't be not saved by increasing
statistics_target to any sane amount.

> alter table t drop statistics all;
> alter table t add statistics (histogram) on (a,b,c);
...
> Seq Scan on t (cost=0.00..22906.00 rows=9667 width=12)

> So both the MCV list and histogram do quite a good work here,

I understand how you calculate selectivity for equality clauses
using histogram. And it calculates the result rows as 2.3e-11,
which is almost same as MV-MCV, and this comes the same cause
with it then yields the same result for joins.

> but there are certainly cases when that does not work and the
> mvcoefficient works better.

The condition mv-coef is effective where, as metioned above,
MV-MCV or MV-HISTO cannot hold sufficient part of the domain. The
appropriate combination of MV-MCV and mv-coef would be the same
as va_eq_(non_)const/eqjoinsel_inner for single column, which is,
applying mv-coef on the part of selectivity corresponding to
values not in MV-MCV. I have no idea to combinate it with
MV-HISTOGRAM right now.

> The current patch does not handle joins, but it's one of the TODO
> items.

Yes, but the result on the very large tables can be deduced from
the discussion above.

> > I think the result above shows that the multivariate coefficient
> > is significant to imporove estimates when correlated colums are
> > involved.
>
> Yes, it looks interesting. I'm wondering what are the "failure cases"
> when the coefficient approach does not work. It seems to me it relies
> on an assumption of consistency for all the ndistinct values. For
> example lets assume you have two columns - A and B, each with 1000
> distinct values, and that each value in A has 100 matching values in
> B, so the coefficient is ~10
>
> 1,000 * 1,000 / 100,000 = 10
>
> Now, let's assume the distribution looks differently - with first 100
> values in A matching all 1000 values of B, and the remaining 900
> values just a single B value. Then
>
> 1,000 * 1,000 / (100,000 + 900) = ~9,9
>
> So a very different distribution, but almost the same coefficient.
>
> Are there any other assumptions like this?

I think no for now. Just like the current var_eq_(non_)const and
eqjoinsel_inner does, since no clue for *the true* distribution
available, we have no choice other than stand on the random (on
uniform dist) assumption. And it gives not so bad estimates for
not so extreme distributions. It's of course not perfect but good
enough.

> Also, does the coefficient work only for equality conditions only?

The mvcoef is a parallel of ndistinct, (it is a bit wierd
expression though). So I guess it is appliable on the current
estimation codes where using ndistinct, almost of all of them
look to relate to equiality comparison.

> > Would you consider this in your patch? Otherwise I move on this
> > as a different project from yours if you don't mind. Except user
> > interface won't conflict with yours, I suppose. But finally they
> > should need some labor of consolidation.
>
> I think it's a neat idea, and I think it might be added to the
> patch. It would fit in quite nicely, actually - I already do have
> other kinds of stats for addition, but I'm not going to work on that
> in the near future. It will require changes in some parts of the patch
> (selecting the stats for a list of clauses) and I'd like to complete
> the current patch first, and then add features in follow-up patches.

I see. Let's work on this for now.

regares,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello,

On 05/15/15 08:29, Kyotaro HORIGUCHI wrote:
> Hello,
>
>> Regarding the functional dependencies - you're right there's room
>> for improvement. For example it only works with dependencies
>> between pairs of columns, not multi-column dependencies. Is this
>> what you mean by incomplete?
>
> No, It overruns dependencies->deps because build_mv_dependencies
> stores many elements into dependencies->deps[n] although it
> really has a room for only one element. I suppose that you paused
> writing it when you noticed that the number of required elements
> is unknown before finising walk through all pairs of
> values. palloc'ing numattrs^2 is reasonable enough as POC code
> for now. Am I looking wrong version of patch?
>
> - dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData))
> + dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData) +
> + sizeof(MVDependency) * numattrs * numattrs);

Ah! That's clearly a bug. Thanks for noticing that, will fix in the next
version of the patch.

>>> I mention this because I recently had a issue from strong
>>> correlation between two columns in dbt3 benchmark. Two columns
>>> in some table are in strong correlation but not in functional
>>> dependencies, there are too many values and the distribution of
>>> them is very uniform so MCV is no use for the table (histogram
>>> has nothing to do with equal conditions). As the result, planner
>>> estimates the number of rows largely wrong as expected
>>> especially for joins.
>>
>> I think the other statistics types (esp. histograms) might be more
>> useful here, but I assume you haven't tried that because of the
>> conflicts.
>>
>> The current patch does not handle joins at all, though.
>
> Well, that's one of the resons. But I understood that any
> deterministic estimation cannot be applied for such distribution
> when I saw what made the wrong estimation. eqsel and eqsel_join
> finally relies on random match assumption on uniform distribution
> when the value is not found in MCV list. And functional
> dependencies stuff in your old patch (which works) (rightfully)
> failed to find such relationship between the problematic
> columns. So I tried ndistinct, which is not contained in your
> patch to see how it works well.

Yes, that's certainly true. I think you're right that mv coefficient
might be quite useful in some cases.

>> With my patch:
>>
>> alter table t add statistics (mcv) on (a,b,c);
> ...
>> Seq Scan on t (cost=0.00..22906.00 rows=9533 width=12)
>
> Yes, your MV-MCV list should have one third of all possible (set
> of) values so it works fine, I guess. But my original problem was
> occurred on the condition that (the single column) MCVs contain
> under 1% of possible values, MCV would not work for such cases,
> but its very uniform distribution helps random assumption to
> work.

Actually, I think the MCV list should contain all the items, as it
decides the sample contains all the values from the data. The usual 1D
MCV list uses the same logic. But you're right that on a data set with
more MCV items and mostly uniform distribution, this won't work.

>
>> $ perl gentbl.pl 200000 | psql postgres
> <takes a while..>
>> posttres=# alter table t1 add statistics (mcv true) on (a, b);
>> postgres=# analyze t1;
>> postgres=# explain analyze select * from t1 where a = 1 and b = 2501;
>> Seq Scan on t1 (cost=0.00..124319.00 rows=1 width=8)
>> (actual time=0.051..1250.773 rows=8 loops=1)
>
> The estimate "rows=1" is internally 2.4e-11, 3.33e+11 times
> smaller than the real number. This will result in roughly the
> same order of error for joins. This is because MV-MCV holds too
> small part of the domain and then calculated using random
> assumption. This won't be not saved by increasing
> statistics_target to any sane amount.

Yes, the MCV lists don't do work well with data sets like this.

>> alter table t drop statistics all;
>> alter table t add statistics (histogram) on (a,b,c);
> ...
>> Seq Scan on t (cost=0.00..22906.00 rows=9667 width=12)
>
>> So both the MCV list and histogram do quite a good work here,
>
> I understand how you calculate selectivity for equality clauses
> using histogram. And it calculates the result rows as 2.3e-11,
> which is almost same as MV-MCV, and this comes the same cause
> with it then yields the same result for joins.
>
>> but there are certainly cases when that does not work and the
>> mvcoefficient works better.

+1

> The condition mv-coef is effective where, as metioned above,
> MV-MCV or MV-HISTO cannot hold sufficient part of the domain. The
> appropriate combination of MV-MCV and mv-coef would be the same
> as va_eq_(non_)const/eqjoinsel_inner for single column, which is,
> applying mv-coef on the part of selectivity corresponding to
> values not in MV-MCV. I have no idea to combinate it with
> MV-HISTOGRAM right now.
>
>> The current patch does not handle joins, but it's one of the TODO
>> items.
>
> Yes, but the result on the very large tables can be deduced from
> the discussion above.
>
>>> I think the result above shows that the multivariate coefficient
>>> is significant to imporove estimates when correlated colums are
>>> involved.
>>
>> Yes, it looks interesting. I'm wondering what are the "failure cases"
>> when the coefficient approach does not work. It seems to me it relies
>> on an assumption of consistency for all the ndistinct values. For
>> example lets assume you have two columns - A and B, each with 1000
>> distinct values, and that each value in A has 100 matching values in
>> B, so the coefficient is ~10
>>
>> 1,000 * 1,000 / 100,000 = 10
>>
>> Now, let's assume the distribution looks differently - with first 100
>> values in A matching all 1000 values of B, and the remaining 900
>> values just a single B value. Then
>>
>> 1,000 * 1,000 / (100,000 + 900) = ~9,9
>>
>> So a very different distribution, but almost the same coefficient.
>>
>> Are there any other assumptions like this?
>
> I think no for now. Just like the current var_eq_(non_)const and
> eqjoinsel_inner does, since no clue for *the true* distribution
> available, we have no choice other than stand on the random (on
> uniform dist) assumption. And it gives not so bad estimates for
> not so extreme distributions. It's of course not perfect but good
> enough.
>
>> Also, does the coefficient work only for equality conditions only?
>
> The mvcoef is a parallel of ndistinct, (it is a bit wierd
> expression though). So I guess it is appliable on the current
> estimation codes where using ndistinct, almost of all of them
> look to relate to equiality comparison.

ISTM the estimation of GROUP BY might benefit tremendously from this
statistics. That is, helping with cardinality estimation of analytical
queries, etc.

Also, we've only discussed 2-column coefficients. Would it be useful to
track those coefficients for large groups of columns? For example

ndistinct(A,B,C)
--------------------------------------------
ndistinct(A) * ndistinct(B) * ndistinct(C)

which might work better for queries like

SELECT a,b,c FROM t GROUP BY a,b,c;

>>> Would you consider this in your patch? Otherwise I move on this
>>> as a different project from yours if you don't mind. Except user
>>> interface won't conflict with yours, I suppose. But finally they
>>> should need some labor of consolidation.
>>
>> I think it's a neat idea, and I think it might be added to the
>> patch. It would fit in quite nicely, actually - I already do have
>> other kinds of stats for addition, but I'm not going to work on
>> that in the near future. It will require changes in some parts of
>> the patch (selecting the stats for a list of clauses) and I'd like
>> to complete the current patch first, and then add features in
>> follow-up patches.
>
> I see. Let's work on this for now.

Thanks!

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

On 05/15/15 08:29, Kyotaro HORIGUCHI wrote:
> Hello,
>
> At Thu, 14 May 2015 12:35:50 +0200, Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55547A86(dot)8020400(at)2ndquadrant(dot)com>
...
>
>> Regarding the functional dependencies - you're right there's room for
>> improvement. For example it only works with dependencies between pairs
>> of columns, not multi-column dependencies. Is this what you mean by
>> incomplete?
>
> No, It overruns dependencies->deps because build_mv_dependencies
> stores many elements into dependencies->deps[n] although it
> really has a room for only one element. I suppose that you paused
> writing it when you noticed that the number of required elements
> is unknown before finising walk through all pairs of
> values. palloc'ing numattrs^2 is reasonable enough as POC code
> for now. Am I looking wrong version of patch?
>
> - dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData))
> + dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData) +
> + sizeof(MVDependency) * numattrs * numattrs);

Actually, looking at this a bit more, I think the current behavior is
correct. I assume the line is from build_mv_dependencies(), but the
whole block looks like this:

if (dependencies == NULL)
{
dependencies = (MVDependencies)palloc0(sizeof(MVDependenciesData));
dependencies->magic = MVSTAT_DEPS_MAGIC;
}
else
dependencies = repalloc(dependencies,
offsetof(MVDependenciesData, deps) +
sizeof(MVDependency) * (dependencies->ndeps + 1));

which allocates space for a single element initially, and then extends
that when other dependencies are added.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

attached is v7 of the multivariate stats patch. The main improvement is
major refactoring of the clausesel.c portion - splitting the awfully
long spaghetti-style functions into smaller pieces, making it much more
understandable etc.

I do assume some of those pieces are unnecessary because there already
is a helper function with the same purpose (but I'm not aware of that).
But IMHO this piece of code begins to look reasonable (especially when
compared to the previous state).

The other major improvement it review of the comments (including FIXMEs
and TODOs), and removal of the obsolete / misplaced ones. And there was
plenty of those ...

These changes made this version ~20k smaller than v6.

The patch also rebases to current master, which I assume shall be quite
stable - so hopefully no more duplicate OIDs for a while.

There are 6 files attached, but only 0002-0006 are actually part of the
multivariate statistics patch itself. The first part makes it possible
to use pull_varnos() with expression trees containing RestrictInfo
nodes, but maybe this is not the right way to fix this (there's another
thread where this was discussed).

Also, the regression tests testing plan choice with multivariate stats
(e.g. that a bitmap index scan is chosen instead of index scan) fail
from time to time. I suppose this happens because the invalidation after
ANALYZE is not processed before executing the query, so the optimizer
does not see the stats, or something like that.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello, I started to work on this patch.

> attached is v7 of the multivariate stats patch. The main improvement
> is major refactoring of the clausesel.c portion - splitting the
> awfully long spaghetti-style functions into smaller pieces, making it
> much more understandable etc.

Thank you, it looks clearer. I have some comment for the brief
look at this. This patchset is relatively large so I will comment
on "per-notice" basis.. which means I'll send comment before
examining the entire of this patchset. Sorry in advance for the
desultory comments.

=======
General comments:

- You included unnecessary stuffs such like regression.diffs in
these patches.

- Now OID 3307 is used by pg_stat_file. I moved
pg_mv_stats_dependencies_info/show to 3311/3312.

- Single-variate stats have a mechanism to inject arbitrary
values as statistics, that is, get_relation_stats_hook and the
similar stuffs. I want the similar mechanism for multivariate
statistics, too.

0001:

- I also don't think it is right thing for expression_tree_walker
to recognize RestrictInfo since it is not a part of expression.

0003:

- In clauselist_selectivity, find_stats is uselessly called for
single clause. This should be called after the clauselist found
to consist more than one clause.

- Searching vars to be compared with mv-stat columns which
find_stats does should stop at disjunctions. But this patch
doesn't behave so and it should be an unwanted behavior. The
following steps shows that.

====
=# CREATE TABLE t1 (a int, b int, c int);
=# INSERT INTO t1 (SELECT a, a * 2, a * 3 FROM generate_series(0, 9999) a);
=# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
=# ALTER TABLE t1 ADD STATISTICS (HISTOGRAM) ON (a, b, c);
=# ANALZYE t1;
=# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
Seq Scan on t1 (cost=0.00..230.00 rows=268 width=12)
====
Rows changed unwantedly.

It seems not so simple thing as your code assumes.

> I do assume some of those pieces are unnecessary because there already
> is a helper function with the same purpose (but I'm not aware of
> that). But IMHO this piece of code begins to look reasonable
> (especially when compared to the previous state).

Year, such kind of work should be done later:p This patch is
not-so-invasive so as to make it undoable.

> The other major improvement it review of the comments (including
> FIXMEs and TODOs), and removal of the obsolete / misplaced ones. And
> there was plenty of those ...
>
> These changes made this version ~20k smaller than v6.
>
> The patch also rebases to current master, which I assume shall be
> quite stable - so hopefully no more duplicate OIDs for a while.
>
> There are 6 files attached, but only 0002-0006 are actually part of
> the multivariate statistics patch itself. The first part makes it
> possible to use pull_varnos() with expression trees containing
> RestrictInfo nodes, but maybe this is not the right way to fix this
> (there's another thread where this was discussed).

As mentioned above, checking if mv stats can be applied would be
more complex matter than now you are assuming. I also will
consider that.

> Also, the regression tests testing plan choice with multivariate stats
> (e.g. that a bitmap index scan is chosen instead of index scan) fail
> from time to time. I suppose this happens because the invalidation
> after ANALYZE is not processed before executing the query, so the
> optimizer does not see the stats, or something like that.

I saw that occurs, but have no idea how it occurs so far..

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello Horiguchi-san!

On 07/03/2015 07:30 AM, Kyotaro HORIGUCHI wrote:
> Hello, I started to work on this patch.
>
>> attached is v7 of the multivariate stats patch. The main improvement
>> is major refactoring of the clausesel.c portion - splitting the
>> awfully long spaghetti-style functions into smaller pieces, making it
>> much more understandable etc.
>
> Thank you, it looks clearer. I have some comment for the brief look
> at this. This patchset is relatively large so I will comment on
> "per-notice" basis.. which means I'll send comment before examining
> the entire of this patchset. Sorry in advance for the desultory
> comments.

Sure. If you run into something that's not clear enough, I'm happy to
explain that (I tried to cover all the important details in the
comments, but it's a large patch, indeed.)

> =======
> General comments:
>
> - You included unnecessary stuffs such like regression.diffs in
> these patches.

Ahhhh :-/ Will fix.

>
> - Now OID 3307 is used by pg_stat_file. I moved
> pg_mv_stats_dependencies_info/show to 3311/3312.

Will fix while rebasing to current master.

>
> - Single-variate stats have a mechanism to inject arbitrary
> values as statistics, that is, get_relation_stats_hook and the
> similar stuffs. I want the similar mechanism for multivariate
> statistics, too.

Fair point, although I'm not sure where should we place the hook, how
exactly should it be defined and how useful that would be in the end.
Can you give an example of how you'd use such hook?

I've never used get_relation_stats_hook, but if I get it right, the
plugins can use the hook to create the stats (for each column), either
from scratch or tweaking the existing stats.

I'm not sure how this should work with multivariate stats, though,
because there can be arbitrary number of stats for a column, and it
really depends on all the clauses (so examine_variable() seems a bit
inappropriate, as it only sees a single variable at a time).

Moreover, with multivariate stats

(a) there may be arbitrary number of stats for a column

(b) only some of the stats end up being used for the estimation

I see two or three possible places for calling such hook:

(a) at the very beginning, after fetching the list of stats

- sees all the existing stats on a table
- may add entirely new stats or tweak the existing ones

(b) after collecting the list of variables compatible with
multivariate stats

- like (a) and additionally knows which columns are interesting
for the query (but only with respect to the existing stats)

(c) after optimization (selection of the right combination if stats)

- like (b), but can't affect the optimization

But I can't really imagine anyone building multivariate stats on the
fly, in the hook.

It's more complicated, though, because the query may call
clauselist_selectivity multiple times, depending on how complex the
WHERE clauses are.

> 0001:
>
> - I also don't think it is right thing for expression_tree_walker
> to recognize RestrictInfo since it is not a part of expression.

Yes. In my working git repo, I've reworked this to use the second
option, i.e. adding RestrictInfo pull_(varno|varattno)_walker:

https://github.com/tvondra/postgres/commit/2dc79b914c759d31becd8ae670b37b79663a595f

Do you think this is the correct solution? If not, how to fix it?

>
> 0003:
>
> - In clauselist_selectivity, find_stats is uselessly called for
> single clause. This should be called after the clauselist found
> to consist more than one clause.

Ok, will fix.

>
> - Searching vars to be compared with mv-stat columns which
> find_stats does should stop at disjunctions. But this patch
> doesn't behave so and it should be an unwanted behavior. The
> following steps shows that.

Why should it stop at disjunctions? There's nothing wrong with using
multivariate stats to estimate OR-clauses, IMHO.

>
> ====
> =# CREATE TABLE t1 (a int, b int, c int);
> =# INSERT INTO t1 (SELECT a, a * 2, a * 3 FROM generate_series(0, 9999) a);
> =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
> Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
> =# ALTER TABLE t1 ADD STATISTICS (HISTOGRAM) ON (a, b, c);
> =# ANALZYE t1;
> =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
> Seq Scan on t1 (cost=0.00..230.00 rows=268 width=12)
> ====
> Rows changed unwantedly.

That has nothing to do with OR clauses, but rather with using a type of
statistics that does not fit the data and queries. Histograms are quite
inaccurate for discrete data and equality conditions - in this case the
clauses probably match one bucket, and so we use 1/2 the bucket as an
estimate. There's nothing wrong with that.

So let's use MCV instead:

ALTER TABLE t1 ADD STATISTICS (MCV) ON (a, b, c);
ANALYZE t1;
EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
QUERY PLAN
-----------------------------------------------------
Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
Filter: (((a = 1) AND (b = 2)) OR (c = 3))
(2 rows)

> It seems not so simple thing as your code assumes.

Maybe, but I don't see what assumption is invalid? I see nothing wrong
with the previous query.

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, Tomas. I'll kick the gas pedal.

> > Thank you, it looks clearer. I have some comment for the brief look
> > at this. This patchset is relatively large so I will comment on
> > "per-notice" basis.. which means I'll send comment before examining
> > the entire of this patchset. Sorry in advance for the desultory
> > comments.
>
> Sure. If you run into something that's not clear enough, I'm happy to
> explain that (I tried to cover all the important details in the
> comments, but it's a large patch, indeed.)

> > - Single-variate stats have a mechanism to inject arbitrary
> > values as statistics, that is, get_relation_stats_hook and the
> > similar stuffs. I want the similar mechanism for multivariate
> > statistics, too.
>
> Fair point, although I'm not sure where should we place the hook, how
> exactly should it be defined and how useful that would be in the
> end. Can you give an example of how you'd use such hook?

It's my secret, but is open:p. this is crucial for us to examine
many planner-related problems occurred in our customer in-vitro.

http://pgdbmsstats.osdn.jp/pg_dbms_stats-en.html

# Mmm, this doc is a bit too old..

One tool of ours does like following,

- Copy pg_statistics and some attributes of pg_class into some
table. Of course this is exportable.

- For example, in examine_simple_variable, using the hook
get_relation_stats_hook, inject the saved statistics in place
of the real statistics.

The hook point is placed where the parameters to specify what
statistics is needed are avaiable in compact shape, and all the
hook function should do is returning corresponding statistics
values.

So the parallel stuff for this mv stats will look like this.

MVStatisticInfo *
get_mv_statistics(PlannerInfo *root, relid);

or

MVStatisticInfo *
get_mv_statistics(PlannerInfo *root, relid, <bitmap or list of attnos>);

So by simplly applying this, the current clauselist_selectivity
code will turn into following.

> if (list_length(clauses) == 1)
> return clause_selectivity(....);
>
> Index varrelid = find_singleton_relid(root, clauses, varRelid);
>
> if (varrelid)
> {
> // Bitmapset attnums = collect_attnums(root, clauses, varrelid);
> if (get_mv_statistics_hook)
> stats = get_mv_statistics_hook(root, varrelid /*, attnums */);
> else
> statis = get_mv_statistics(root, varrelid /*, attnums*/);
>
> ....

In comparison to single statistics, statistics values might be
preferable to separate from definition.

> I've never used get_relation_stats_hook, but if I get it right, the
> plugins can use the hook to create the stats (for each column), either
> from scratch or tweaking the existing stats.

Mostly existing stats without change. I saw few hackers wanted to
provide predefined statistics for typical cases. I haven't see
anyone who tweaks existing stats.

> I'm not sure how this should work with multivariate stats, though,
> because there can be arbitrary number of stats for a column, and it
> really depends on all the clauses (so examine_variable() seems a bit
> inappropriate, as it only sees a single variable at a time).

Restriction clauses are not a problem. What is needed to replace
stats value is defining few APIs to retrieve them, and to
retrieve the stats values only in a way that compatible with the
API. It would be okay to be a substitute views for mv stats as an
extreme case but it is not good.

> Moreover, with multivariate stats
>
> (a) there may be arbitrary number of stats for a column
>
> (b) only some of the stats end up being used for the estimation
>
> I see two or three possible places for calling such hook:
>
> (a) at the very beginning, after fetching the list of stats
>
> - sees all the existing stats on a table
> - may add entirely new stats or tweak the existing ones

Getting all stats for a table would be okay but attnum list can
restrict the possibilities, as the second form of the example
APIs above. And we may forget the case of forged or tweaked
stats, they are their problem, not ours.

> (b) after collecting the list of variables compatible with
> multivariate stats
>
> - like (a) and additionally knows which columns are interesting
> for the query (but only with respect to the existing stats)

We should carefully design the API to be able to point the
pertinent stats for every situation. Mv stats is based on the
correlation of multiple columns so I think only relid and
attributes list are enough as the parameter.

| if (st.relid == param.relid && bms_equal(st.attnums, param.attnums))
| /* This is the stats to be wanted */

If we can filter the appropriate stats from all the stats using
clauselist, we definitely can make the appropriate parameter
(column set) prior to retrieving mv statistics. Isn't it correct?

> (c) after optimization (selection of the right combination if stats)
>
> - like (b), but can't affect the optimization
>
> But I can't really imagine anyone building multivariate stats on the
> fly, in the hook.
>
> It's more complicated, though, because the query may call
> clauselist_selectivity multiple times, depending on how complex the
> WHERE clauses are.
>
>
> > 0001:
> >
> > - I also don't think it is right thing for expression_tree_walker
> > to recognize RestrictInfo since it is not a part of expression.
>
> Yes. In my working git repo, I've reworked this to use the second
> option, i.e. adding RestrictInfo pull_(varno|varattno)_walker:
>
> https://github.com/tvondra/postgres/commit/2dc79b914c759d31becd8ae670b37b79663a595f
>
> Do you think this is the correct solution? If not, how to fix it?

The reason why I think it is not appropreate is that RestrictInfo
is not a part of expression.

Increasing selectivity of a condition by column correlation is
occurs only for a set of conjunctive clauses. OR operation
devides the sets. Is it agreeable? RestrictInfos can be nested
each other and we should be aware of the AND/OR operators. This
is what expression_tree_walker doesn't.

Perhaps we should provide the dedicate function such like
find_conjunctive_attr_set which does this,

- Check the type top expression of the clause

- If it is a RestrictInfo, check clause_relids then check
clause.

- If it is a bool OR, stop to search and return empty set of
attributes.

- If it is a bool AND, make further check of the components. A
list of RestrictInfo should be treaed as AND connection.

- If it is operator exression, collect used relids and attrs
walking the expression tree.

I should missing something but I think the outline is correct.

Addition to that we should carefully avoid duplicate correction
using the same mv statistics.

I haven't understood what choose_mv_satistics precisely but I
suppose what this function does would be split into the 'making
parameter to find stats' part and 'matching the parameter with
stats in order to retrieve desired stats' part. Could you
reconstruct this process into the form like this?

I feel it is too invasive, or exccesively intermix(?)ed.

> > 0003:
> >
> > - In clauselist_selectivity, find_stats is uselessly called for
> > single clause. This should be called after the clauselist found
> > to consist more than one clause.
>
> Ok, will fix.
>
> >
> > - Searching vars to be compared with mv-stat columns which
> > find_stats does should stop at disjunctions. But this patch
> > doesn't behave so and it should be an unwanted behavior. The
> > following steps shows that.
>
> Why should it stop at disjunctions? There's nothing wrong with using
> multivariate stats to estimate OR-clauses, IMHO.

Mv statistics represents how often *every combination of the
column values* occurs. Is it correct? Where the combination can
be replaced with coexists, that is AND. For example MV-MCV.

(a, b, c) freq
(1, 2, 3) 100
(1, 2, 5) 50
(1, 3, 8) 20
(1, 7, 2) 5
===============
total 175

| select * from t where a = 1 and b = 2 and c = 3;
| SELECT 100

This is correct,

| select * from t where a = 1 and b = 2 or c = 3;
| SELECT 100

This is *not* correct. The correct number of tuples is 150.
This is a simple example where OR breaks MV stats assumption.

> > ====
> > =# CREATE TABLE t1 (a int, b int, c int);
> > =# INSERT INTO t1 (SELECT a, a * 2, a * 3 FROM generate_series(0,
> > 9999) a);
> > =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
> > Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
> > =# ALTER TABLE t1 ADD STATISTICS (HISTOGRAM) ON (a, b, c);
> > =# ANALZYE t1;
> > =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
> > Seq Scan on t1 (cost=0.00..230.00 rows=268 width=12)
> > ====
> > Rows changed unwantedly.
>
> That has nothing to do with OR clauses, but rather with using a type
> of statistics that does not fit the data and queries. Histograms are
> quite inaccurate for discrete data and equality conditions - in this
> case the clauses probably match one bucket, and so we use 1/2 the
> bucket as an estimate. There's nothing wrong with that.
>
> So let's use MCV instead:

Hmm, it's not a problem what specific number is displayed as
rows. What is crucial is the fact that rows has changed even
though it shouldn't have changed. As I demonstrated above.

> ALTER TABLE t1 ADD STATISTICS (MCV) ON (a, b, c);
> ANALYZE t1;
> EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
> QUERY PLAN
> -----------------------------------------------------
> Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
> Filter: (((a = 1) AND (b = 2)) OR (c = 3))
> (2 rows)
>
> > It seems not so simple thing as your code assumes.
>
> Maybe, but I don't see what assumption is invalid? I see nothing wrong
> with the previous query.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hi,

On 07/07/2015 08:05 AM, Kyotaro HORIGUCHI wrote:
> Hi, Tomas. I'll kick the gas pedal.
>
>>> Thank you, it looks clearer. I have some comment for the brief look
>>> at this. This patchset is relatively large so I will comment on
>>> "per-notice" basis.. which means I'll send comment before examining
>>> the entire of this patchset. Sorry in advance for the desultory
>>> comments.
>>
>> Sure. If you run into something that's not clear enough, I'm happy to
>> explain that (I tried to cover all the important details in the
>> comments, but it's a large patch, indeed.)
>
>
>>> - Single-variate stats have a mechanism to inject arbitrary
>>> values as statistics, that is, get_relation_stats_hook and the
>>> similar stuffs. I want the similar mechanism for multivariate
>>> statistics, too.
>>
>> Fair point, although I'm not sure where should we place the hook,
>> how exactly should it be defined and how useful that would be in
>> the end. Can you give an example of how you'd use such hook?

...

>
> We should carefully design the API to be able to point the pertinent
> stats for every situation. Mv stats is based on the correlation of
> multiple columns so I think only relid and attributes list are
> enough as the parameter.
>
> | if (st.relid == param.relid && bms_equal(st.attnums, param.attnums))
> | /* This is the stats to be wanted */
>
> If we can filter the appropriate stats from all the stats using
> clauselist, we definitely can make the appropriate parameter (column
> set) prior to retrieving mv statistics. Isn't it correct?

Let me briefly explain how the current clauselist_selectivity
implementation works.

(1) check if there are multivariate statistics on the table - if not,
skip the multivariate parts altogether (the point of this is to
minimize impact on users who don't use the new feature)

(2) see if the are clauses compatible with multivariate stats - this
only checks "general compatibility" without actually checking the
existing stats (the point is to terminate early, if the clauses
are not compatible somehow - e.g. if the clauses reference only a
single attribute, use unsupported operators etc.)

(3) if there are multivariate stats and compatible clauses, the
function choose_mv_stats tries to find the best combination of
multivariate stats with respect to the clauses (details later)

(4) the clauses are estimated using the stats, the remaining clauses
are estimated using the current statistics (single attribute)

The only way to reliably inject new stats is by calling a hook before
(1), allowing it to arbitrarily modify the list of stats. Based on the
use cases you provided, I don't think it makes much sense to add
additional hooks in the other phases.

At this place it's however now known what clauses are compatible with
multivariate stats, or what attributes they are referencing. It might be
possible to simply call pull_varattnos() and pass it to the hook, except
that does not work with RestrictInfo :-/

Or maybe we could / should not put the hook into clauselist_selectivity
but somewhere else? Say, to get_relation_info where we actually read the
list of stats for the relation?

>>
>>
>>> 0001:
>>>
>>> - I also don't think it is right thing for expression_tree_walker
>>> to recognize RestrictInfo since it is not a part of expression.
>>
>> Yes. In my working git repo, I've reworked this to use the second
>> option, i.e. adding RestrictInfo pull_(varno|varattno)_walker:
>>
>> https://github.com/tvondra/postgres/commit/2dc79b914c759d31becd8ae670b37b79663a595f
>>
>> Do you think this is the correct solution? If not, how to fix it?
>
> The reason why I think it is not appropreate is that RestrictInfo
> is not a part of expression.
>
> Increasing selectivity of a condition by column correlation is
> occurs only for a set of conjunctive clauses. OR operation
> devides the sets. Is it agreeable? RestrictInfos can be nested
> each other and we should be aware of the AND/OR operators. This
> is what expression_tree_walker doesn't.

I still don't understand why you think we need to differentiate between
AND and OR operators. There's nothing wrong with estimating OR clauses
using multivariate statistics.

>
> Perhaps we should provide the dedicate function such like
> find_conjunctive_attr_set which does this,

Perhaps. The reason why I added support for RestrictInfo into the
existing walker implementations is that it seemed like the easiest way
to fix the issue. But if there are reasons why that's incorrect, then
inventing a new function is probably the right way.

>
> - Check the type top expression of the clause
>
> - If it is a RestrictInfo, check clause_relids then check
> clause.
>
> - If it is a bool OR, stop to search and return empty set of
> attributes.
>
> - If it is a bool AND, make further check of the components. A
> list of RestrictInfo should be treaed as AND connection.
>
> - If it is operator exression, collect used relids and attrs
> walking the expression tree.
>
> I should missing something but I think the outline is correct.

As I said before, there's nothing wrong with estimating OR clauses using
multivariate statistics. So OR and AND should be handled exactly the same.

I think you're missing the fact that it's not enough to look at the
relids from the RestrictInfo - we need to actually check what clauses
are used inside, i.e. we need to check the clauses.

That's because only some of the clauses are compatible with multivariate
stats, and only if all the clauses of the BoolExpr are "compatible" then
we can estimate the clause as a whole. If it's a mix of supported and
unsupported clauses, we can simply pass it to clauselist_selectivity
which will repeat the whole process with.

> Addition to that we should carefully avoid duplicate correction
> using the same mv statistics.

Sure. That's what choose_mv_statistics does.

>
> I haven't understood what choose_mv_satistics precisely but I
> suppose what this function does would be split into the 'making
> parameter to find stats' part and 'matching the parameter with
> stats in order to retrieve desired stats' part. Could you
> reconstruct this process into the form like this?

The goal of choose_mv_statistics does is very simple - given a list of
clauses, it tries to find the best combination of statistics, exploiting
as much information as possible.

So let's say you have clauses

WHERE a=1 AND b=1 AND c=1 AND d=1

but you only have statistics on [a,b], [b,c] and [b,c,d].

The simplest approach would be to use the 'largest' statistics, covering
the most columns from the clauses - in this case [b,c,d]. This is what
the initial patches do.

The last patch improves this significantly, by combining the statistics
using conditional probability. In this case it'd probably use all three
statistics, effectively decomposing the selectivity like this:

P(a=1,b=1,c=1,d=1) = P(a=1,b=1) * P(c=1|b=1) * P(d=1|b=1,c=1)
[a,b] [b,c] [b,c,d]

And each of those probabilities can be estimated using one of the stats.

> I feel it is too invasive, or exccesively intermix(?)ed.

I don't think it really fits your model - the hook has to be called much
sooner, effectively at the very beginning of the clauselist_selectivity
or even before that. Otherwise it might not get called at all (e.g. if
there are no multivariate stats on the table, this whole part will be
skipped).

>> Why should it stop at disjunctions? There's nothing wrong with using
>> multivariate stats to estimate OR-clauses, IMHO.
>
> Mv statistics represents how often *every combination of the
> column values* occurs. Is it correct? Where the combination can
> be replaced with coexists, that is AND. For example MV-MCV.
>
> (a, b, c) freq
> (1, 2, 3) 100
> (1, 2, 5) 50
> (1, 3, 8) 20
> (1, 7, 2) 5
> ===============
> total 175
>
> | select * from t where a = 1 and b = 2 and c = 3;
> | SELECT 100
>
> This is correct,
>
> | select * from t where a = 1 and b = 2 or c = 3;
> | SELECT 100
>
> This is *not* correct. The correct number of tuples is 150.
> This is a simple example where OR breaks MV stats assumption.

No, it does not.

I'm not sure where are the numbers coming from, though. So let's see how
this actually works with multivariate statistics. I'll create a table
with the 4 combinations you used in your example, but with 1000x more
rows, to make the estimates a bit more accurate:

CREATE TABLE t (a INT, b INT, c INT);

INSERT INTO t SELECT 1, 2, 3 FROM generate_series(1,100000);
INSERT INTO t SELECT 1, 2, 5 FROM generate_series(1,50000);
INSERT INTO t SELECT 1, 3, 8 FROM generate_series(1,20000);
INSERT INTO t SELECT 1, 7, 2 FROM generate_series(1,5000);

ALTER TABLE t ADD STATISTICS (mcv) ON (a,b,c);

ANALYZE t;

And now let's see the two queries:

EXPLAIN select * from t where a = 1 and b = 2 and c = 3;
QUERY PLAN
----------------------------------------------------------
Seq Scan on t (cost=0.00..4008.50 rows=100403 width=12)
Filter: ((a = 1) AND (b = 2) AND (c = 3))
(2 rows)

EXPLAIN select * from t where a = 1 and b = 2 or c = 3;
QUERY PLAN
----------------------------------------------------------
Seq Scan on t (cost=0.00..4008.50 rows=150103 width=12)
Filter: (((a = 1) AND (b = 2)) OR (c = 3))
(2 rows)

So the first query estimates 100k rows, the second one 150k rows.
Exactly as expected, because MCV lists are discrete, match perfectly the
data and behave exactly like your mental model.

If you try this with histograms though, you'll get the same estimate in
both cases:

ALTER TABLE t DROP STATISTICS ALL;
ALTER TABLE t ADD STATISTICS (histogram) ON (a,b,c);
ANALYZE t;

EXPLAIN select * from t where a = 1 and b = 2 and c = 3;
QUERY PLAN
---------------------------------------------------------
Seq Scan on t (cost=0.00..4008.50 rows=52707 width=12)
Filter: ((a = 1) AND (b = 2) AND (c = 3))
(2 rows)

EXPLAIN select * from t where a = 1 and b = 2 or c = 3;
QUERY PLAN
---------------------------------------------------------
Seq Scan on t (cost=0.00..4008.50 rows=52707 width=12)
Filter: (((a = 1) AND (b = 2)) OR (c = 3))
(2 rows)

That's unfortunate, but it has nothing to do with some assumptions of
multivariate statistics. The "problem" is that histograms are naturally
fuzzy, and both conditions hit the same bucket.

The solution is simple - don't use histograms for such discrete data.

>>> ====
>>> =# CREATE TABLE t1 (a int, b int, c int);
>>> =# INSERT INTO t1 (SELECT a, a * 2, a * 3 FROM generate_series(0,
>>> 9999) a);
>>> =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
>>> Seq Scan on t1 (cost=0.00..230.00 rows=1 width=12)
>>> =# ALTER TABLE t1 ADD STATISTICS (HISTOGRAM) ON (a, b, c);
>>> =# ANALZYE t1;
>>> =# EXPLAIN SELECT * FROM t1 WHERE a = 1 AND b = 2 OR c = 3;
>>> Seq Scan on t1 (cost=0.00..230.00 rows=268 width=12)
>>> ====
>>> Rows changed unwantedly.
>>
>> That has nothing to do with OR clauses, but rather with using a
>> type of statistics that does not fit the data and queries.
>> Histograms are quite inaccurate for discrete data and equality
>> conditions - in this case the clauses probably match one bucket,
>> and so we use 1/2 the bucket as an estimate. There's nothing wrong
>> with that.
>>
>> So let's use MCV instead:
>
> Hmm, it's not a problem what specific number is displayed as
> rows. What is crucial is the fact that rows has changed even
> though it shouldn't have changed. As I demonstrated above.

Again, that has nothing to do with any assumptions, and it certainly
does not demonstrate that OR clauses should not be handled by
multivariate statistics.

In this case, you're observing two effects.

(1) Natural inaccuracy of histograms when used for discrete data,
especially in combination with equality conditions (because
that's impossible to estimate accurately with histograms).

(2) The original estimate (without multivariate statistics) is only
seemingly accurate, because it falsely assumes independence.
It simply assumes that each condition matches 1/10000 of the
table, and multiplies that, getting ~0.00001 row estimate. This
is rounded up to 1, which is accidentally the exact value.

Let me demonstrate this on two examples - one with discrete data, one
with continuous distribution.

1) discrete data

CREATE TABLE t (a INT, b INT, c INT);
INSERT INTO t SELECT i/1000, 2*(i/1000), 3*(i/1000)
FROM generate_series(1, 1000000) s(i);
ANALYZE t;

-- no multivariate stats (so assumption of independence)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 and c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=1 width=12)
(actual time=0.290..59.120 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=966 width=12)
(actual time=0.434..117.643 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 6;

Seq Scan on t (cost=0.00..22906.00 rows=966 width=12)
(actual time=0.433..96.956 rows=2000 loops=1)

-- now let's add a histogram

ALTER TABLE t ADD STATISTICS (histogram) on (a,b,c);
ANALYZE t;

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 and c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=817 width=12)
(actual time=0.268..116.318 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=30333 width=12)
(actual time=0.435..93.232 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 6;

Seq Scan on t (cost=0.00..22906.00 rows=30333 width=12)
(actual time=0.434..122.930 rows=2000 loops=1)

-- now let's use a MCV list

ALTER TABLE t DROP STATISTICS ALL;
ALTER TABLE t ADD STATISTICS (mcv) on (a,b,c);
ANALYZE t;

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 and c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=767 width=12)
(actual time=0.268..70.604 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 3;

Seq Scan on t (cost=0.00..22906.00 rows=767 width=12)
(actual time=0.268..70.604 rows=1000 loops=1)

EXPLAIN ANALYZE select * from t where a = 1 and b = 2 or c = 6;

Seq Scan on t (cost=0.00..22906.00 rows=1767 width=12)
(actual time=0.428..100.607 rows=2000 loops=1)

The default estimate of AND query is rather bad. For OR clause, it's not
that bad (the OR selectivity is not that bad when it comes to
dependency, but it's not difficult to construct counter examples).

The histogram is not that good - for the OR queries it often results in
over-estimates (for equality conditions on discrete data).

But the MCV estimates are very accurate. The slight under-estimate is
probably caused by the block sampling we're using to get sample rows.

2) continuous data (I'll only show histograms)

CREATE TABLE t (a FLOAT, b FLOAT, c FLOAT);
INSERT INTO t SELECT r,
r + r*(random() - 0.5)/2,
r + r*(random() - 0.5)/2
FROM (SELECT random() as r
FROM generate_series(1,1000000)) foo;
ANALYZE t;

-- no multivariate stats
EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=28768 width=24)
(actual time=0.026..323.383 rows=273897 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=372362 width=24)
(actual time=0.026..375.005 rows=317533 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
Seq Scan on t (cost=0.00..23870.00 rows=192979 width=24)
(actual time=0.026..431.376 rows=393528 loops=1)

-- histograms
ALTER TABLE t ADD STATISTICS (histogram) on (a,b,c);
ANALYZE t;

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=267033 width=24)
(actual time=0.021..330.487 rows=273897 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=14317 width=24)
(actual time=0.027..906.321 rows=966870 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
Seq Scan on t (cost=0.00..23870.00 rows=20367 width=24)
(actual time=0.028..452.494 rows=393528 loops=1)

This seems wrong, because the estimate for the OR queries should not be
lower than the estimate for the first query (with just AND), and it
should not increase when increasing the boundary. I'd bet this is a bug
in how the inequalities are handled with histograms, or how the AND/OR
clauses are combined. I'll look into that.

But once again, there's nothing that would make OR clauses somehow
incompatible with multivariate stats.

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello Horiguchi-san!

On 07/07/2015 09:43 PM, Tomas Vondra wrote:
> -- histograms
> ALTER TABLE t ADD STATISTICS (histogram) on (a,b,c);
> ANALYZE t;
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
> Seq Scan on t (cost=0.00..23870.00 rows=267033 width=24)
> (actual time=0.021..330.487 rows=273897 loops=1)
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.3;
> Seq Scan on t (cost=0.00..23870.00 rows=14317 width=24)
> (actual time=0.027..906.321 rows=966870 loops=1)
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
> Seq Scan on t (cost=0.00..23870.00 rows=20367 width=24)
> (actual time=0.028..452.494 rows=393528 loops=1)
>
> This seems wrong, because the estimate for the OR queries should not be
> lower than the estimate for the first query (with just AND), and it
> should not increase when increasing the boundary. I'd bet this is a bug
> in how the inequalities are handled with histograms, or how the AND/OR
> clauses are combined. I'll look into that.

FWIW this was a stupid bug in update_match_bitmap_histogram(), which
initially handled only AND clauses, and thus assumed the "match" of a
bucket can only decrease. But for OR clauses this is exactly the
opposite (we assume no buckets match and add buckets matching at least
one of the clauses).

With this fixed, the estimates look like this:

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=267033 width=24)
(actual time=0.102..321.524 rows=273897 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=319400 width=24)
(actual time=0.103..386.089 rows=317533 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=956833 width=24)
(actual time=0.133..908.455 rows=966870 loops=1)

EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
Seq Scan on t (cost=0.00..23870.00 rows=393633 width=24)
(actual time=0.105..440.607 rows=393528 loops=1)

IMHO pretty accurate estimates - no issue with OR clauses.

I've pushed this to github [1] but I need to do some additional fixes. I
also had to remove some optimizations while fixing this, and will have
to reimplement those.

That's not to say that the handling of OR-clauses is perfectly correct.
After looking at clauselist_selectivity_or(), I believe it's a bit
broken and will need a bunch of fixes, as explained in the FIXMEs I
pushed to github.

[1] https://github.com/tvondra/postgres/tree/mvstats

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, Thanks for the detailed explaination. I misunderstood the
code (more honest speaking, din't look so close there). Then I
looked it closer.

At Wed, 08 Jul 2015 03:03:16 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <559C76D4(dot)2030805(at)2ndquadrant(dot)com>
> FWIW this was a stupid bug in update_match_bitmap_histogram(), which
> initially handled only AND clauses, and thus assumed the "match" of a
> bucket can only decrease. But for OR clauses this is exactly the
> opposite (we assume no buckets match and add buckets matching at least
> one of the clauses).
>
> With this fixed, the estimates look like this:
>

> IMHO pretty accurate estimates - no issue with OR clauses.

Ok, I understood the diferrence between what I thought and what
you say. The code is actually concious of OR clause but is looks
somewhat confused.

Currently choosing mv stats in clauselist_selectivity can be
outlined as following,

1. find_stats finds candidate mv stats containing *all*
attributes appeared in the whole clauses regardless of and/or
exprs by walking whole the clause tree.

Perhaps this is the measure to early bailout.

2.1. Within every disjunction elements, collect mv-related
attributes while checking whether the all leaf nodes (binop or
ifnull) are compatible by (eventually) walking whole the
clause tree.

2.2. Check if all the collected attribute are contained in
mv-stats columns.

3. Finally, clauseset_mv_selectivity_histogram() (and others).

This funciton applies every ExprOp onto every attribute in
every histogram backes and (tries to) make the boolean
operation of the result bitmaps.

I have some comments on the implement and I also try to find the
solution for them.

1. The flow above looks doing very similiar thins repeatedly.

2. I believe what the current code does can be simplified.

3. As you mentioned in comments, some additional infrastructure
needed.

After all, I think what we should do after this are as follows,
as the first step.

- Add the means to judge the selectivity operator(?) by other
than oprrest of the op of ExprOp. (You missed neqsel already)

I suppose one solution for this is adding oprmvstats taking
'm', 'h' and 'f' and their combinations. Or for the
convenience, it would be a fixed-length string like this.

oprname | oprmvstats
= | 'mhf'
<> | 'mhf'
< | 'mh-'
> | 'mh-'
>= | 'mh-'
<= | 'mh-'

This would make the code in clause_is_mv_compatible like this.

> oprmvstats = get_mvstatsset(expr->opno); /* bitwise representation */
> if (oprmvstats & types)
> {
> *attnums = bms_add_member(*attnums, var->varattno);
> return true;
> }
> return false;

- Current design just manage to work but it is too complicated
and hardly have affinity with the existing estimation
framework. I proposed separation of finding stats phase and
calculation phase, but I would like to propose transforming
RestrictInfo(and finding mvstat) phase and running the
transformed RestrictInfo phase after looking close to the
patch.

I think transforing RestrictInfo makes the situnation
better. Since it nedds different information, maybe it is
better to have new struct, say, RestrictInfoForEstimate
(boo!). Then provide mvstatssel() to use in the new struct.
The rough looking of the code would be like below.

clauselist_selectivity()
{
...
RestrictInfoForEstmate *esclause =
transformClauseListForEstimation(root, clauses, varRelid);
...

return clause_selectivity(esclause):
}

clause_selectivity(RestrictInfoForEstmate *esclause)
{
if (IsA(clause, RestrictInfo))...
if (IsA(clause, RestrictInfoForEstimate))
{
RestrictInfoForEstimate *ecl = (RestrictInfoForEstimate*) clause;
if (ecl->selfunc)
{
sx = ecl->selfunc(root, ecl);
}
}
if (IsA(clause, Var))...
}

transformClauseListForEstimation(...)
{
...

relid = collect_mvstats_info(root, clause, &attlist);
if (!relid) return;
if (get_mvstats_hook)
mvstats = (*get_mvstats_hoook) (root, relid, attset);
else
mvstats = find_mv_stats(root, relid, attset))
}
...

> I've pushed this to github [1] but I need to do some additional
> fixes. I also had to remove some optimizations while fixing this, and
> will have to reimplement those.
>
> That's not to say that the handling of OR-clauses is perfectly
> correct. After looking at clauselist_selectivity_or(), I believe it's
> a bit broken and will need a bunch of fixes, as explained in the
> FIXMEs I pushed to github.
>
> [1] https://github.com/tvondra/postgres/tree/mvstats

I don't see whether it is doable or not, and I suppose you're
unwilling to change the big picture, so I will consider the idea
and will show you the result, if it turns out to be possible and
promising.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hi,

On 07/13/2015 10:51 AM, Kyotaro HORIGUCHI wrote:
>
> Ok, I understood the diferrence between what I thought and what you
> say. The code is actually concious of OR clause but is looks somewhat
> confused.

I'm not sure which part is confused by the OR clauses, but it's
certainly possible. Initially it only handled AND clauses, and the
support for OR clauses was added later, so it's possible some parts are
not behaving correctly.

>
> Currently choosing mv stats in clauselist_selectivity can be
> outlined as following,
>
> 1. find_stats finds candidate mv stats containing *all*
> attributes appeared in the whole clauses regardless of and/or
> exprs by walking whole the clause tree.
>
> Perhaps this is the measure to early bailout.

Not entirely. The goal of find_stats() is to lookup all stats on the
'current' relation - it's coded the way it is because I had to deal with
varRelid=0 cases, in which case I have to inspect the Var nodes. But
maybe I got this wrong and there's much simpler way to do that?

It is an early bailout in the sense that if there are no multivariate
stats defined on the table, there's no point in doing any of the
following steps. So that we don't increase planning times for users not
using multivariate stats.

> 2.1. Within every disjunction elements, collect mv-related
> attributes while checking whether the all leaf nodes (binop or
> ifnull) are compatible by (eventually) walking whole the
> clause tree.

Generally, yes. The idea is to check whether there are clauses that
might be estimated using multivariate statistics, and whether the
clauses reference at least two different attributes. Imagine a query
like this:

SELECT * FROM t WHERE (a=1) AND (a>0) AND (a<100)

It makes no sense to process this using multivariate statistics, because
all the Var nodes reference a single attribute.

Similarly, the check is not just about the leaf nodes - to be able to
estimate a clause at this point, we have to be able to process the whole
tree, starting from the top-level clause. Although maybe that's no
longer true, now that support for OR clauses was added ... I wonder
whether there are other BoolExpr-like nodes, that might make the tree
incompatible with multivariate statistics (in the sense that the current
implementation does not know how to handle them).

Also note that even though the clause may be "incompatible" at this
level, it may get partially processed by multivariate statistics later.
For example with a query:

SELECT * FROM t WHERE (a=1 OR b=2 OR c ~* 'xyz') AND (q=1 OR r=4)

the first query is "incompatible" because it contains unsupported
operator '~*', but it will eventually be processed as BoolExpr node, and
should be split into two parts - (a=1 OR b=2) which is compatible, and
(c ~* 'xyz') which is incompatible.

This split should happen in clauselist_selectivity_or(), and the other
thing that may be interesting is that it uses (q=1 OR r=4) as a
condition. So if there's a statistics built on (a,b,q,r) we'll compute
conditional probability

P(a=1,b=2 | q=1,r=4)

>
> 2.2. Check if all the collected attribute are contained in
> mv-stats columns.

No, I think you got this wrong. We do not check that *all* the
attributes are contained in mvstats columns - we only need two such
columns (then there's a chance that the multivariate statistics will get
applied).

Anyway, both 2.1 and 2.2 are meant as a quick bailout, before doing the
most expensive part, which is choose_mv_statistics(). Which is however
missing in this list.

> 3. Finally, clauseset_mv_selectivity_histogram() (and others).
>
> This funciton applies every ExprOp onto every attribute in
> every histogram backes and (tries to) make the boolean
> operation of the result bitmaps.

Yes, but this only happens after choose_mv_statistics(), because that's
the code that decides which statistics will be used and in what order.

The list is also missing handling of the 'functional dependencies', so a
complete list of steps would look like this:

1) find_stats - lookup stats on the current relation (from RelOptInfo)

2) apply functional dependencies

a) check if there are equality clauses that may be reduced using
functional dependencies, referencing at least two columns

b) if yes, perform the clause reduction

3) apply MCV lists and histograms

a) check if there are clauses 'compatible' with those types of
statistics, again containing at least two columns

b) if yes, use choose_mv_statistics() to decide which statistics to
apply and in which order

c) apply the selected histograms and MCV lists

4) estimate the remaining clauses using the regular statistics

a) this is where the clauselist_mv_selectivity_histogram and other
are called

I tried to explain this in the comment before clauselist_selectivity(),
but maybe it's not detailed enough / missing some important details.

>
> I have some comments on the implement and I also try to find the
> solution for them.
>
>
> 1. The flow above looks doing very similiar thins repeatedly.

I worked hard to remove such code duplicities, and believe all the
current steps are necessary - for example 2(a) and 3(a) may seems
similar, but it's really necessary to do that twice.

>
> 2. I believe what the current code does can be simplified.

Possibly.

>
> 3. As you mentioned in comments, some additional infrastructure
> needed.
>
> After all, I think what we should do after this are as follows,
> as the first step.

OK.

>
> - Add the means to judge the selectivity operator(?) by other
> than oprrest of the op of ExprOp. (You missed neqsel already)

Yes, the way we use 'oprno' to determine how to estimate the selectivity
is a bit awkward. It's inspired by handling of range queries, and having
something better would be nice.

But I don't think this is the reason why I missed neqsel, and I don't
see this as a significant design issue at this point. But if we can come
up with a better solution, why not ...

> I suppose one solution for this is adding oprmvstats taking
> 'm', 'h' and 'f' and their combinations. Or for the
> convenience, it would be a fixed-length string like this.
>
> oprname | oprmvstats
> = | 'mhf'
> <> | 'mhf'
> < | 'mh-'
> > | 'mh-'
> >= | 'mh-'
> <= | 'mh-'
>
> This would make the code in clause_is_mv_compatible like this.
>
> > oprmvstats = get_mvstatsset(expr->opno); /* bitwise representation */
> > if (oprmvstats & types)
> > {
> > *attnums = bms_add_member(*attnums, var->varattno);
> > return true;
> > }
> > return false;

So this only determines the compatibility of operators with respect to
different types of statistics? How does that solve the neqsel case? It
will probably decide the clause is compatible, but it will later fail at
the actual estimation, no?

>
> - Current design just manage to work but it is too complicated
> and hardly have affinity with the existing estimation
> framework.

I respectfully disagree. I've strived to make it as affine to the
current implementation as possible - maybe it's possible to improve
that, but I believe there's a natural difference between the two types
of statistics. It may be somewhat simplified, but it will never be
exactly the same.

> I proposed separation of finding stats phase and
> calculation phase, but I would like to propose transforming
> RestrictInfo(and finding mvstat) phase and running the
> transformed RestrictInfo phase after looking close to the
> patch.

Those phases are already separated, as is illustrated by the steps
explained above.

So technically we might place a hook either right after the find_stats()
call, so that it's possible to process all the stats on the table, or
maybe after the choose_mv_statistics() call, so that we only process the
actually used stats.

>
> I think transforing RestrictInfo makes the situnation
> better. Since it nedds different information, maybe it is
> better to have new struct, say, RestrictInfoForEstimate
> (boo!). Then provide mvstatssel() to use in the new struct.
> The rough looking of the code would be like below.
>
> clauselist_selectivity()
> {
> ...
> RestrictInfoForEstmate *esclause =
> transformClauseListForEstimation(root, clauses, varRelid);
> ...
>
> return clause_selectivity(esclause):
> }
>
> clause_selectivity(RestrictInfoForEstmate *esclause)
> {
> if (IsA(clause, RestrictInfo))...
> if (IsA(clause, RestrictInfoForEstimate))
> {
> RestrictInfoForEstimate *ecl = (RestrictInfoForEstimate*) clause;
> if (ecl->selfunc)
> {
> sx = ecl->selfunc(root, ecl);
> }
> }
> if (IsA(clause, Var))...
> }
>
>
> transformClauseListForEstimation(...)
> {
> ...
>
> relid = collect_mvstats_info(root, clause, &attlist);
> if (!relid) return;
> if (get_mvstats_hook)
> mvstats = (*get_mvstats_hoook) (root, relid, attset);
> else
> mvstats = find_mv_stats(root, relid, attset))
> }
> ...

So you'd transform the clause tree first, replacing parts of the tree
(to be estimated by multivariate stats) by a new node type? That's an
interesting idea, I think ...

I can't really say whether it's a good approach, though. Can you explain
why do you think it'd make the situation better?

The one benefit I can think of is being able to look at the processed
tree and see which parts will be estimated using multivariate stats.

But we'd effectively have to do the same stuff (choosing the stats,
...), and if we move this pre-processing before clauselist_selectivity
(I assume that's the point), we'd end up repeating a lot of the code. Or
maybe not, I'm not sure.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, I'd like to show you the modified constitution of
multivariate statistics application logic. Please find the
attached. They apply on your v7 patch.

The code to find mv-applicable clause is moved out of the main
flow of clauselist_selectivity. As I said in the previous mail,
the new function transformRestrictInfoForEstimate (too bad name
but just for PoC:) scans clauselist and generates
RestrictStatsData struct which drives mv-aware selectivity
calculation. This struct isolates MV and non-MV estimation.

The struct RestrictStatData mainly consists of the following
three parts,

- clause to be estimated by current logic (MV is not applicable)
- clause to be estimated by MV-staistics.
- list of child RestrictStatDatas, which are to be run
recursively.

mvclause_selectivty() is the topmost function where mv stats
works. This structure effectively prevents main estimation flow
from being broken by modifying mvstats part. Although I haven't
measured but I'm positive the code is far reduced from yours.

I attached two patches to this message. The first one is to
rebase v7 patch to current(maybe) master and the second applies
the refactoring.

I'm a little anxious about performance but I think this makes the
process to apply mv-stats far clearer. Regtests for mvstats
succeeded asis except for fdep, which is not implememted in this
patch.

What do you think about this?

regards,

> Hi, Thanks for the detailed explaination. I misunderstood the
> code (more honest speaking, din't look so close there). Then I
> looked it closer.
>
>
> At Wed, 08 Jul 2015 03:03:16 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <559C76D4(dot)2030805(at)2ndquadrant(dot)com>
> > FWIW this was a stupid bug in update_match_bitmap_histogram(), which
> > initially handled only AND clauses, and thus assumed the "match" of a
> > bucket can only decrease. But for OR clauses this is exactly the
> > opposite (we assume no buckets match and add buckets matching at least
> > one of the clauses).
> >
> > With this fixed, the estimates look like this:
> >
>
> > IMHO pretty accurate estimates - no issue with OR clauses.
>
> Ok, I understood the diferrence between what I thought and what
> you say. The code is actually concious of OR clause but is looks
> somewhat confused.
>
> Currently choosing mv stats in clauselist_selectivity can be
> outlined as following,
>
> 1. find_stats finds candidate mv stats containing *all*
> attributes appeared in the whole clauses regardless of and/or
> exprs by walking whole the clause tree.
>
> Perhaps this is the measure to early bailout.
>
> 2.1. Within every disjunction elements, collect mv-related
> attributes while checking whether the all leaf nodes (binop or
> ifnull) are compatible by (eventually) walking whole the
> clause tree.
>
> 2.2. Check if all the collected attribute are contained in
> mv-stats columns.
>
> 3. Finally, clauseset_mv_selectivity_histogram() (and others).
>
> This funciton applies every ExprOp onto every attribute in
> every histogram backes and (tries to) make the boolean
> operation of the result bitmaps.
>
> I have some comments on the implement and I also try to find the
> solution for them.
>
>
> 1. The flow above looks doing very similiar thins repeatedly.
>
> 2. I believe what the current code does can be simplified.
>
> 3. As you mentioned in comments, some additional infrastructure
> needed.
>
> After all, I think what we should do after this are as follows,
> as the first step.
>
> - Add the means to judge the selectivity operator(?) by other
> than oprrest of the op of ExprOp. (You missed neqsel already)
>
> I suppose one solution for this is adding oprmvstats taking
> 'm', 'h' and 'f' and their combinations. Or for the
> convenience, it would be a fixed-length string like this.
>
> oprname | oprmvstats
> = | 'mhf'
> <> | 'mhf'
> < | 'mh-'
> > | 'mh-'
> >= | 'mh-'
> <= | 'mh-'
>
> This would make the code in clause_is_mv_compatible like this.
>
> > oprmvstats = get_mvstatsset(expr->opno); /* bitwise representation */
> > if (oprmvstats & types)
> > {
> > *attnums = bms_add_member(*attnums, var->varattno);
> > return true;
> > }
> > return false;
>
> - Current design just manage to work but it is too complicated
> and hardly have affinity with the existing estimation
> framework. I proposed separation of finding stats phase and
> calculation phase, but I would like to propose transforming
> RestrictInfo(and finding mvstat) phase and running the
> transformed RestrictInfo phase after looking close to the
> patch.
>
> I think transforing RestrictInfo makes the situnation
> better. Since it nedds different information, maybe it is
> better to have new struct, say, RestrictInfoForEstimate
> (boo!). Then provide mvstatssel() to use in the new struct.
> The rough looking of the code would be like below.
>
> clauselist_selectivity()
> {
> ...
> RestrictInfoForEstmate *esclause =
> transformClauseListForEstimation(root, clauses, varRelid);
> ...
>
> return clause_selectivity(esclause):
> }
>
> clause_selectivity(RestrictInfoForEstmate *esclause)
> {
> if (IsA(clause, RestrictInfo))...
> if (IsA(clause, RestrictInfoForEstimate))
> {
> RestrictInfoForEstimate *ecl = (RestrictInfoForEstimate*) clause;
> if (ecl->selfunc)
> {
> sx = ecl->selfunc(root, ecl);
> }
> }
> if (IsA(clause, Var))...
> }
>
>
> transformClauseListForEstimation(...)
> {
> ...
>
> relid = collect_mvstats_info(root, clause, &attlist);
> if (!relid) return;
> if (get_mvstats_hook)
> mvstats = (*get_mvstats_hoook) (root, relid, attset);
> else
> mvstats = find_mv_stats(root, relid, attset))
> }
> ...
>
> > I've pushed this to github [1] but I need to do some additional
> > fixes. I also had to remove some optimizations while fixing this, and
> > will have to reimplement those.
> >
> > That's not to say that the handling of OR-clauses is perfectly
> > correct. After looking at clauselist_selectivity_or(), I believe it's
> > a bit broken and will need a bunch of fixes, as explained in the
> > FIXMEs I pushed to github.
> >
> > [1] https://github.com/tvondra/postgres/tree/mvstats
>
> I don't see whether it is doable or not, and I suppose you're
> unwilling to change the big picture, so I will consider the idea
> and will show you the result, if it turns out to be possible and
> promising.

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hi,

On 07/16/2015 01:51 PM, Kyotaro HORIGUCHI wrote:
> Hi, I'd like to show you the modified constitution of
> multivariate statistics application logic. Please find the
> attached. They apply on your v7 patch.

Sadly I do have some trouble getting it to apply correctly :-(
So for now all my comments are based on just reading the code.

FWIW I've rebased my patch to the current master, it's available on
github as usual:

https://github.com/tvondra/postgres/commits/mvstats

> The code to find mv-applicable clause is moved out of the main
> flow of clauselist_selectivity. As I said in the previous mail,
> the new function transformRestrictInfoForEstimate (too bad name
> but just for PoC:) scans clauselist and generates
> RestrictStatsData struct which drives mv-aware selectivity
> calculation. This struct isolates MV and non-MV estimation.
>
> The struct RestrictStatData mainly consists of the following
> three parts,
>
> - clause to be estimated by current logic (MV is not applicable)
> - clause to be estimated by MV-staistics.
> - list of child RestrictStatDatas, which are to be run
> recursively.
>
> mvclause_selectivty() is the topmost function where mv stats
> works. This structure effectively prevents main estimation flow
> from being broken by modifying mvstats part. Although I haven't
> measured but I'm positive the code is far reduced from yours.
>
> I attached two patches to this message. The first one is to
> rebase v7 patch to current(maybe) master and the second applies
> the refactoring.
>
> I'm a little anxious about performance but I think this makes the
> process to apply mv-stats far clearer. Regtests for mvstats
> succeeded asis except for fdep, which is not implememted in this
> patch.
>
> What do you think about this?

I'm not sure, at this point. I'm having a hard time understanding how
exactly the code works - there are pretty much no comments explaining
the implementation, so it takes time to understand the code. This is
especially true about transformRestrictInfoForEstimate which is also
quite long. I understand it's a PoC, but comments would really help.

On a conceptual level, I think the idea to split the estimation into two
phases - enrich the expression tree with nodes with details about stats
etc, and then actually do the estimation in the second phase might be
interesting. Not because it's somehow clearer, but because it gives us a
chance to see the expression tree as a whole, with details about all the
stats (with the current code we process/estimate the tree
incrementally). But I don't really know how useful that would be.

I don't think the proposed change makes the process somehow clearer. I
know it's a PoC at this point, so I don't expect it to be perfect, but
for me the original code is certainly clearer. Of course, I'm biased as
I wrote the current code, and I (naturally) shaped it to match my ideas
during the development process, and I'm much more familiar with it.

Omitting the support for functional dependencies is a bit unfortunate, I
think. Is that merely to make the PoC simpler, or is there something
that makes it impossible to support that kind of stats?

Another thing that I noticed is that you completely removed the code
that combined multiple stats (and selected the best combination of
stats). In other words, you've reverted to the intermediate single
statistics approach, including removing the improved handling of OR
clauses and conditions. It's a bit difficult to judge the proposed
approach not knowing how well it supports those (quite crucial)
features. What if it can't support some them., or what if it makes the
code much more complicated (thus defeating the goal of making it more
clear)?

I share your concern about the performance impact - one thing is that
this new code might be slower than the original one, but a more serious
issue IMHO is that the performance impact will happen even for relations
with no multivariate stats at all. The original patch was very careful
about getting ~0% overhead in such cases, and if the new code does not
allow that, I don't see this approach as acceptable. We must not put
additional overhead on people not using multivariate stats.

But I think it's worth exploring this idea a bit more - can you rebase
it to the current patch version (as on github) and adding the missing
pieces (functional dependencies, multi-statistics estimation and passing
conditions)?

One more thing - I noticed you extended the pg_operator catalog with a
oprmvstat attribute, used to flag operators that are compatible with
multivariate stats. I'm not happy with the current approach (using
oprrest to do this decision), but I'm not really sure this is a good
solution either. The culprit is that it only answers one of the two
important questions - Is it compatible? How to perform the estimation?

So we'd have to rely on oprrest anyway, when actually performing the
estimation of a clause with "compatible" operator. And we'd have to keep
in sync two places (catalog and checks in file), and we'd have to update
the catalog after improving the implementation (adding support for
another operator).

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

At Sat, 25 Jul 2015 23:09:31 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55B3FB0B(dot)7000201(at)2ndquadrant(dot)com>
> Hi,
>
> On 07/16/2015 01:51 PM, Kyotaro HORIGUCHI wrote:
> > Hi, I'd like to show you the modified constitution of
> > multivariate statistics application logic. Please find the
> > attached. They apply on your v7 patch.
>
> Sadly I do have some trouble getting it to apply correctly :-(
> So for now all my comments are based on just reading the code.

Ah. My modification to rebase to the master for the time should
be culprit. Sorry for the dirty patch.

# I would recreate the patch if you complained before struggling
# with the thing..

The core of the modification is on closesel.c. I attached the
patched closesel.c.

> FWIW I've rebased my patch to the current master, it's available on
> github as usual:
>
> https://github.com/tvondra/postgres/commits/mvstats

Thanks.

> > The code to find mv-applicable clause is moved out of the main
> > flow of clauselist_selectivity. As I said in the previous mail,
> > the new function transformRestrictInfoForEstimate (too bad name
> > but just for PoC:) scans clauselist and generates
> > RestrictStatsData struct which drives mv-aware selectivity
> > calculation. This struct isolates MV and non-MV estimation.
> >
> > The struct RestrictStatData mainly consists of the following
> > three parts,
> >
> > - clause to be estimated by current logic (MV is not applicable)
> > - clause to be estimated by MV-staistics.
> > - list of child RestrictStatDatas, which are to be run
> > recursively.
> >
> > mvclause_selectivty() is the topmost function where mv stats
> > works. This structure effectively prevents main estimation flow
> > from being broken by modifying mvstats part. Although I haven't
> > measured but I'm positive the code is far reduced from yours.
> >
> > I attached two patches to this message. The first one is to
> > rebase v7 patch to current(maybe) master and the second applies
> > the refactoring.
> >
> > I'm a little anxious about performance but I think this makes the
> > process to apply mv-stats far clearer. Regtests for mvstats
> > succeeded asis except for fdep, which is not implememted in this
> > patch.
> >
> > What do you think about this?
>
> I'm not sure, at this point. I'm having a hard time understanding how
> exactly the code works - there are pretty much no comments explaining
> the implementation, so it takes time to understand the code. This is
> especially true about transformRestrictInfoForEstimate which is also
> quite long. I understand it's a PoC, but comments would really help.

The patch itself shold hardly readable because it's not from
master but from your last patch plus somthing.

My concern about the code at the time was following,

- You embedded the logic of multivariate estimation into
clauselist_selectivity. I think estimate using multivariate
statistics is quite different from the ordinary estimate based
on single column stats then they are logically separatable and
we should do so.

- You are taking top-down approach and it runs tree-walking to
check appliability of mv-stats for every stepping down in
clause tree. If the subtree found to be mv-applicable, split it
to two parts - mv-compatible and non-compatible. These steps
requires expression tree walking, which looks using too-much
CPU.

- You look to be considering the cases when users create many
multivariate statistics on attribute sets having
duplications. But it looks too-much for me. MV-stats are more
resource-eating so we can assume the minimum usage of that.

My suggestion in the patch is a bottom-up approach to find
mv-applicable portion(s) in the expression tree, which is the
basic way of planner overall. The approach requires no repetitive
run of tree walker, that is, pull_varnos. It could fail to find
the 'optimal' solution for complex situations but needs far less
calculation for almost the same return (I think..).

Even though it doesn't consider the functional dependency, the
reduce of the code shows the efficiency. It does not nothing
tricky.

> On a conceptual level, I think the idea to split the estimation into
> two phases - enrich the expression tree with nodes with details about
> stats etc, and then actually do the estimation in the second phase
> might be interesting. Not because it's somehow clearer, but because it
> gives us a chance to see the expression tree as a whole, with details
> about all the stats (with the current code we process/estimate the
> tree incrementally). But I don't really know how useful that would be.

It is difficult to say which approach is better sinch it is
affected by what we think important than other things. However I
concern about that your code substantially reconstructs the
expression (clause) tree midst of processing it. I believe it
should be a separate phase for simplicity. Of course additional
required resource is also should be considered but it is rather
reduced for this case.

> I don't think the proposed change makes the process somehow clearer. I
> know it's a PoC at this point, so I don't expect it to be perfect, but
> for me the original code is certainly clearer. Of course, I'm biased
> as I wrote the current code, and I (naturally) shaped it to match my
> ideas during the development process, and I'm much more familiar with
> it.

Mmm. we need someone else's opition:) What I think on this point
is described just above... OK, I try to describe this in other
words.

The embedded approach simply increases the state and code path
by, roughly, multiplication basis. The separate approcach adds
them in addition basis. I thinks this is the most siginificant
point of why I feel it 'clear'.

Of course, the acceptable complexity differs according to the
fundamental complexity, performance, required memory or someting
others but I feel it is too-much complexity for the objective.

> Omitting the support for functional dependencies is a bit unfortunate,
> I think. Is that merely to make the PoC simpler, or is there something
> that makes it impossible to support that kind of stats?

I don't think so. I ommited it simply because it would more time
to implement.

> Another thing that I noticed is that you completely removed the code
> that combined multiple stats (and selected the best combination of
> stats). In other words, you've reverted to the intermediate single
> statistics approach, including removing the improved handling of OR
> clauses and conditions.

Yeah, good catch :p I noticed that just after submitting the
patch that I retaion only one statistics at the second level from
the bottom but it is easily fixed by changing pruning timing. The
struct can hold multiple statistics anyway.

And I don't omit OR case. It is handled along with the AND
case. (in wrong way?)

> It's a bit difficult to judge the proposed
> approach not knowing how well it supports those (quite crucial)
> features. What if it can't support some them., or what if it makes the
> code much more complicated (thus defeating the goal of making it more
> clear)?

OR is supported, Fdep is maybe supportable, but all of them
occurs within the function with the entangled name
(transform..something). But I should put more consider on your
latest code before that.

> I share your concern about the performance impact - one thing is that
> this new code might be slower than the original one, but a more
> serious issue IMHO is that the performance impact will happen even for
> relations with no multivariate stats at all. The original patch was
> very careful about getting ~0% overhead in such cases,

I don't think so. find_stats runs pull_varnos and
transformRestric.. also uses pull_varnos to bail out at the top
level. They should have almost the same overhead for the case.

> and if the new
> code does not allow that, I don't see this approach as acceptable. We
> must not put additional overhead on people not using multivariate
> stats.
>
> But I think it's worth exploring this idea a bit more - can you rebase
> it to the current patch version (as on github) and adding the missing
> pieces (functional dependencies, multi-statistics estimation and
> passing conditions)?

With pleasure. Please wait for a while.

> One more thing - I noticed you extended the pg_operator catalog with a
> oprmvstat attribute, used to flag operators that are compatible with
> multivariate stats. I'm not happy with the current approach (using
> oprrest to do this decision), but I'm not really sure this is a good
> solution either. The culprit is that it only answers one of the two
> important questions - Is it compatible? How to perform the estimation?

Hostly saying, I also don't like this. But checking oprrest is
unpleasant much the same.

> So we'd have to rely on oprrest anyway, when actually performing the
> estimation of a clause with "compatible" operator. And we'd have to
> keep in sync two places (catalog and checks in file), and we'd have to
> update the catalog after improving the implementation (adding support
> for another operator).

Mmm. It depends on what the deveopers think about the definition
of oprrest. More practically, I'm worried whether it cannot be
other than eqsel for any equality operator. And the same for
comparison operators.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello Horiguchi-san,

On 07/27/2015 09:04 AM, Kyotaro HORIGUCHI wrote:
> Hello,
>
> At Sat, 25 Jul 2015 23:09:31 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55B3FB0B(dot)7000201(at)2ndquadrant(dot)com>
>> Hi,
>>
>> On 07/16/2015 01:51 PM, Kyotaro HORIGUCHI wrote:
>>> Hi, I'd like to show you the modified constitution of
>>> multivariate statistics application logic. Please find the
>>> attached. They apply on your v7 patch.
>>
>> Sadly I do have some trouble getting it to apply correctly :-(
>> So for now all my comments are based on just reading the code.
>
> Ah. My modification to rebase to the master for the time should
> be culprit. Sorry for the dirty patch.
>
> # I would recreate the patch if you complained before struggling
> # with the thing..
>
> The core of the modification is on closesel.c. I attached the
> patched closesel.c.

I don't see any attachment. Perhaps you forgot to actually attach it?

>
> My concern about the code at the time was following,
>
> - You embedded the logic of multivariate estimation into
> clauselist_selectivity. I think estimate using multivariate
> statistics is quite different from the ordinary estimate based
> on single column stats then they are logically separatable and
> we should do so.

I don't see them as very different, actually quite the opposite. The two
kinds of statistics are complementary and should naturally coexist.
Perhaps the current code is not perfect and a refactoring would make the
code more readable, but I don't think it's primary aim should be to
separate regular and multivariate stats.

>
> - You are taking top-down approach and it runs tree-walking to
> check appliability of mv-stats for every stepping down in
> clause tree. If the subtree found to be mv-applicable, split it
> to two parts - mv-compatible and non-compatible. These steps
> requires expression tree walking, which looks using too-much
> CPU.

I'm taking top-down approach because that's what the regular stats do,
and also because that's what allows implementing the features that I
think are interesting - ability to combine multiple stats in an
efficient way, pass conditions and such. I think those two features are
very useful and allow very interesting things.

The bottom-up would work too, probably - I mean, we could start from
leaves of the expression tree, and build the largest "subtree"
compatible with multivariate stats and then try to estimate it. I don't
see how we could pass conditions though, which works naturally in the
top-down approach.

Or maybe a combination of both - identify the "compatible" subtrees
first, then perform the top-down phase.

> - You look to be considering the cases when users create many
> multivariate statistics on attribute sets having
> duplications. But it looks too-much for me. MV-stats are more
> resource-eating so we can assume the minimum usage of that.

Not really. I don't expect huge numbers of multivariate stats to be
built on the tables.

But I think restricting the users to use a single multivariate
statistics per table would be a significant limitation. And once you
allow using multiple multivariate statistics for the set of clauses,
supporting over-lapping stats is not that difficult.

What it however makes possible is combining multiple "small" stats into
a larger one in a very efficient way - it assumes the overlap is
sufficient, of course. But if that's true you may build multiple small
(and very accurate) stats instead of one huge (or very inaccurate)
statistics.

This also makes it possible to handle complex combinations of clauses
that are compatible and incompatible with multivariate statistics, by
passing the conditions.

>
> My suggestion in the patch is a bottom-up approach to find
> mv-applicable portion(s) in the expression tree, which is the
> basic way of planner overall. The approach requires no repetitive
> run of tree walker, that is, pull_varnos. It could fail to find
> the 'optimal' solution for complex situations but needs far less
> calculation for almost the same return (I think..).
>
> Even though it doesn't consider the functional dependency, the
> reduce of the code shows the efficiency. It does not nothing
> tricky.

OK

>> On a conceptual level, I think the idea to split the estimation into
>> two phases - enrich the expression tree with nodes with details about
>> stats etc, and then actually do the estimation in the second phase
>> might be interesting. Not because it's somehow clearer, but because it
>> gives us a chance to see the expression tree as a whole, with details
>> about all the stats (with the current code we process/estimate the
>> tree incrementally). But I don't really know how useful that would be.
>
> It is difficult to say which approach is better sinch it is
> affected by what we think important than other things. However I
> concern about that your code substantially reconstructs the
> expression (clause) tree midst of processing it. I believe it
> should be a separate phase for simplicity. Of course additional
> required resource is also should be considered but it is rather
> reduced for this case.

What do you mean by "reconstruct the expression tree"? It's true I'm
walking the expression tree top-down, but how is that reconstructing?

>
>> I don't think the proposed change makes the process somehow clearer. I
>> know it's a PoC at this point, so I don't expect it to be perfect, but
>> for me the original code is certainly clearer. Of course, I'm biased
>> as I wrote the current code, and I (naturally) shaped it to match my
>> ideas during the development process, and I'm much more familiar with
>> it.
>
> Mmm. we need someone else's opition:) What I think on this point
> is described just above... OK, I try to describe this in other
> words.

I find your comments very valuable. I may not agree with some of them,
but I certainly appreciate your point of view. So thank you very much
for the time you spent reviewing this patch so far!

> The embedded approach simply increases the state and code path by,
> roughly, multiplication basis. The separate approcach adds them in
> addition basis. I thinks this is the most siginificant point of why I
> feel it 'clear'.
>
> Of course, the acceptable complexity differs according to the
> fundamental complexity, performance, required memory or someting
> others but I feel it is too-much complexity for the objective.

Yes, I think we might have slightly different objectives in mind.

Regarding the complexity - I am not too worried about spending more CPU
cycles on this, as long as it does not impact the case where people have
no multivariate statistics at all. That's because I expect people to use
this for large DSS/DWH data sets with lots of dependencies in the (often
denormalized) tables and complex conditions - in those cases the
planning difference is negligible, especially if the improved estimates
make the query run in seconds instead of hours.

This is why I was so careful to entirely skip the expensive processing
when where were no multivariate stats, and why I don't like the fact
that your approach makes this skip more difficult (or maybe impossible,
I'm not sure).

It's also true that most OLTP queries (especially the short ones, thus
most impacted by the increase of planning time) use rather short/simple
clause lists, so even the top-down approach should be very cheap.

>
>> Omitting the support for functional dependencies is a bit unfortunate,
>> I think. Is that merely to make the PoC simpler, or is there something
>> that makes it impossible to support that kind of stats?
>
> I don't think so. I ommited it simply because it would more time
> to implement.

OK, thanks for confirming this.

>
>> Another thing that I noticed is that you completely removed the code
>> that combined multiple stats (and selected the best combination of
>> stats). In other words, you've reverted to the intermediate single
>> statistics approach, including removing the improved handling of OR
>> clauses and conditions.
>
> Yeah, good catch :p I noticed that just after submitting the
> patch that I retaion only one statistics at the second level from
> the bottom but it is easily fixed by changing pruning timing. The
> struct can hold multiple statistics anyway.

Great!

>
> And I don't omit OR case. It is handled along with the AND
> case. (in wrong way?)

Oh, I see. I got a bit confused because you've removed the optimization
step (and conditions), and that needs to be handled a bit differently
for the OR clauses.

>
>> It's a bit difficult to judge the proposed
>> approach not knowing how well it supports those (quite crucial)
>> features. What if it can't support some them., or what if it makes the
>> code much more complicated (thus defeating the goal of making it more
>> clear)?
>
> OR is supported, Fdep is maybe supportable, but all of them
> occurs within the function with the entangled name
> (transform..something). But I should put more consider on your
> latest code before that.

Good. Likewise, I'd like to see more of your approach ;-)

>
>> I share your concern about the performance impact - one thing is that
>> this new code might be slower than the original one, but a more
>> serious issue IMHO is that the performance impact will happen even for
>> relations with no multivariate stats at all. The original patch was
>> very careful about getting ~0% overhead in such cases,
>
> I don't think so. find_stats runs pull_varnos and
> transformRestric.. also uses pull_varnos to bail out at the top
> level. They should have almost the same overhead for the case.

Understood. As I explained above, I'm not all that concerned about the
performance impact, as long as we make sure it only applies to people
using the multivariate stats.

I also think a combined approach - first a bottom-up step (identifying
the largest compatible subtrees & caching the varnos), then a top-down
step (doing the same optimization as implemented today) might minimize
the performance impact.

>
>> and if the new
>> code does not allow that, I don't see this approach as acceptable. We
>> must not put additional overhead on people not using multivariate
>> stats.
>>
>> But I think it's worth exploring this idea a bit more - can you rebase
>> it to the current patch version (as on github) and adding the missing
>> pieces (functional dependencies, multi-statistics estimation and
>> passing conditions)?
>
> With pleasure. Please wait for a while.

Sure. Take your time.

>
>> One more thing - I noticed you extended the pg_operator catalog with a
>> oprmvstat attribute, used to flag operators that are compatible with
>> multivariate stats. I'm not happy with the current approach (using
>> oprrest to do this decision), but I'm not really sure this is a good
>> solution either. The culprit is that it only answers one of the two
>> important questions - Is it compatible? How to perform the estimation?
>
> Hostly saying, I also don't like this. But checking oprrest is
> unpleasant much the same.

The patch is already quite massive, so let's use the same approach as
current stats, and leave this problem for another patch. If we come up
with a great idea, we can work on it, but I see this as a loosely
related annoyance rather than something this patch aims to address.

>> So we'd have to rely on oprrest anyway, when actually performing the
>> estimation of a clause with "compatible" operator. And we'd have to
>> keep in sync two places (catalog and checks in file), and we'd have to
>> update the catalog after improving the implementation (adding support
>> for another operator).
>
> Mmm. It depends on what the deveopers think about the definition
> of oprrest. More practically, I'm worried whether it cannot be
> other than eqsel for any equality operator. And the same for
> comparison operators.

OTOH if you define a new operator with oprrest=F_EQSEL, you're
effectively saying "It's OK to estimate this using regular eq/lt/gt
operators". If your operator is somehow incompatible with that, you
should not set oprrest=F_EQSEL.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 05/25/2015 11:43 PM, Tomas Vondra wrote:
> There are 6 files attached, but only 0002-0006 are actually part of the
> multivariate statistics patch itself.

All of these patches are huge. In order to review this in a reasonable
amount of time, we need to do this in several steps. So let's see what
would be the minimal set of these patches that could be reviewed and
committed, while still being useful.

The main patches are:

1. shared infrastructure and functional dependencies
2. clause reduction using functional dependencies
3. multivariate MCV lists
4. multivariate histograms
5. multi-statistics estimation

Would it make sense to commit only patches 1 and 2 first? Would that be
enough to get a benefit from this?

I have some doubts about the clause reduction and functional
dependencies part of this. It seems to treat functional dependency as a
boolean property, but even with the classic zipcode and city case, it's
not always an all or nothing thing. At least in some countries, there
can be zipcodes that span multiple cities. So zipcode=X does not
completely imply city=Y, although there is a strong correlation (if
that's the right term). How strong does the correlation need to be for
this patch to decide that zipcode implies city? I couldn't actually see
a clear threshold stated anywhere.

So rather than treating functional dependence as a boolean, I think it
would make more sense to put a 0.0-1.0 number to it. That means that you
can't do clause reduction like it's done in this patch, where you
actually remove clauses from the query for cost esimation purposes.
Instead, you need to calculate the selectivity for each clause
independently, but instead of just multiplying the selectivities
together, apply the "dependence factor" to it.

Does that make sense? I haven't really looked at the MCV, histogram and
"multi-statistics estimation" patches yet. Do those patches make the
clause reduction patch obsolete? Should we forget about the clause
reduction and functional dependency patch, and focus on those later
patches instead?

- Heikki

Hello, I certainly attached the file this time.

At Mon, 27 Jul 2015 23:54:08 +0200, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55B6A880(dot)3050801(at)2ndquadrant(dot)com>
> > The core of the modification is on closesel.c. I attached the
> > patched closesel.c.
>
> I don't see any attachment. Perhaps you forgot to actually attach it?

Very sorry to have forgotten to attach it. I attached the new
patch applicable on the head of mvstats branch of your
repository.

> > My concern about the code at the time was following,
> >
> > - You embedded the logic of multivariate estimation into
> > clauselist_selectivity. I think estimate using multivariate
> > statistics is quite different from the ordinary estimate based
> > on single column stats then they are logically separatable and
> > we should do so.
>
> I don't see them as very different, actually quite the opposite. The
> two kinds of statistics are complementary and should naturally
> coexist. Perhaps the current code is not perfect and a refactoring
> would make the code more readable, but I don't think it's primary aim
> should be to separate regular and multivariate stats.
>
> > - You are taking top-down approach and it runs tree-walking to
> > check appliability of mv-stats for every stepping down in
> > clause tree. If the subtree found to be mv-applicable, split it
> > to two parts - mv-compatible and non-compatible. These steps
> > requires expression tree walking, which looks using too-much
> > CPU.
>
> I'm taking top-down approach because that's what the regular stats do,
> and also because that's what allows implementing the features that I
> think are interesting - ability to combine multiple stats in an
> efficient way, pass conditions and such. I think those two features
> are very useful and allow very interesting things.
>
> The bottom-up would work too, probably - I mean, we could start from
> leaves of the expression tree, and build the largest "subtree"
> compatible with multivariate stats and then try to estimate it. I
> don't see how we could pass conditions though, which works naturally
> in the top-down approach.

By the way, the 'condition' looks to mean what will be received
by the parameter of clause(list)_selectivity with the same
name. But it is always NIL. Looking at the comment for
collect_mv_attnum, it is prepared for 'multitable statistics'. If
so, I think it's better removed from the current patch, because
it is useless now.

> Or maybe a combination of both - identify the "compatible" subtrees
> first, then perform the top-down phase.
>
> > - You look to be considering the cases when users create many
> > multivariate statistics on attribute sets having
> > duplications. But it looks too-much for me. MV-stats are more
> > resource-eating so we can assume the minimum usage of that.
>
> Not really. I don't expect huge numbers of multivariate stats to be
> built on the tables.
>
> But I think restricting the users to use a single multivariate
> statistics per table would be a significant limitation. And once you
> allow using multiple multivariate statistics for the set of clauses,
> supporting over-lapping stats is not that difficult.
>
> What it however makes possible is combining multiple "small" stats
> into a larger one in a very efficient way - it assumes the overlap is
> sufficient, of course. But if that's true you may build multiple small
> (and very accurate) stats instead of one huge (or very inaccurate)
> statistics.
>
> This also makes it possible to handle complex combinations of clauses
> that are compatible and incompatible with multivariate statistics, by
> passing the conditions.
>
> >
> > My suggestion in the patch is a bottom-up approach to find
> > mv-applicable portion(s) in the expression tree, which is the
> > basic way of planner overall. The approach requires no repetitive
> > run of tree walker, that is, pull_varnos. It could fail to find
> > the 'optimal' solution for complex situations but needs far less
> > calculation for almost the same return (I think..).
> >
> > Even though it doesn't consider the functional dependency, the
> > reduce of the code shows the efficiency. It does not nothing
> > tricky.
>
> OK

The functional dependency code looks immature in both the
detection phase and application phase in comparison to MCV and
histogram. Addition to that, as the comment in dependencies.c
says, fdep is not so significant (than MCV/HIST) because it is
usually carefully avoided and should be noticed and considered in
designing of application or the whole system.

Persisting to apply them all at once doesn't seem to be a good
strategy to be adopted earlier.

Or perhaps it might be better to register the dependency itself
than registering incomplete information (only the set of colums
involoved in the relationship) and try to detect the relationship
from the given values. I suppose those who can register the
columnset know the precise nature of the dependency in advance.

> >> On a conceptual level, I think the idea to split the estimation into
> >> two phases - enrich the expression tree with nodes with details about
> >> stats etc, and then actually do the estimation in the second phase
> >> might be interesting. Not because it's somehow clearer, but because it
> >> gives us a chance to see the expression tree as a whole, with details
> >> about all the stats (with the current code we process/estimate the
> >> tree incrementally). But I don't really know how useful that would be.
> >
> > It is difficult to say which approach is better sinch it is
> > affected by what we think important than other things. However I
> > concern about that your code substantially reconstructs the
> > expression (clause) tree midst of processing it. I believe it
> > should be a separate phase for simplicity. Of course additional
> > required resource is also should be considered but it is rather
> > reduced for this case.
>
> What do you mean by "reconstruct the expression tree"? It's true I'm
> walking the expression tree top-down, but how is that reconstructing?

For example clauselist_mv_split does. It separates mvclauses from
original clauselist and apply mv-stats at once and (parhaps) let
the rest be processed in the 'normal' route. I called this as
"reconstruct", which I tried to do explicity and separately.

> >> I don't think the proposed change makes the process somehow clearer. I
> >> know it's a PoC at this point, so I don't expect it to be perfect, but
> >> for me the original code is certainly clearer. Of course, I'm biased
> >> as I wrote the current code, and I (naturally) shaped it to match my
> >> ideas during the development process, and I'm much more familiar with
> >> it.
> >
> > Mmm. we need someone else's opition:) What I think on this point
> > is described just above... OK, I try to describe this in other
> > words.
>
> I find your comments very valuable. I may not agree with some of them,
> but I certainly appreciate your point of view. So thank you very much
> for the time you spent reviewing this patch so far!

Yeah, thank you for your patience and kindness.

> > The embedded approach simply increases the state and code path by,
> > roughly, multiplication basis. The separate approcach adds them in
> > addition basis. I thinks this is the most siginificant point of why I
> > feel it 'clear'.
> >
> > Of course, the acceptable complexity differs according to the
> > fundamental complexity, performance, required memory or someting
> > others but I feel it is too-much complexity for the objective.
>
> Yes, I think we might have slightly different objectives in mind.

Sure! Now I'm understand what is the point.

> Regarding the complexity - I am not too worried about spending more
> CPU cycles on this, as long as it does not impact the case where
> people have no multivariate statistics at all. That's because I expect
> people to use this for large DSS/DWH data sets with lots of
> dependencies in the (often denormalized) tables and complex conditions
> - in those cases the planning difference is negligible, especially if
> the improved estimates make the query run in seconds instead of hours.

I share the vision with you. If that is the case, the mv-stats
route should not be intrude the existing non-mv-stats route. I
feel you have too much intruded clauselist_selectivity all the
more.

If that is the case, my mv-distinct code has different objective
from you. It aims to save the misestimation from multicolumn
correlations more commonly occurs in OLTP usage.

> This is why I was so careful to entirely skip the expensive processing
> when where were no multivariate stats, and why I don't like the fact
> that your approach makes this skip more difficult (or maybe
> impossible, I'm not sure).

My code totally skips if transformRestrictionForEstimate returns
NULL and runs clauselist_selectivity as usual. I think almost the
same as yours.

However, if you think it I believe we should not only skipping
calculation but also hiding the additional code blocks which is
overwhelming the normal route. The one of major objectives of my
approach is that point.

> It's also true that most OLTP queries (especially the short ones, thus
> most impacted by the increase of planning time) use rather
> short/simple clause lists, so even the top-down approach should be
> very cheap.
>
> >> Omitting the support for functional dependencies is a bit unfortunate,
> >> I think. Is that merely to make the PoC simpler, or is there something
> >> that makes it impossible to support that kind of stats?
> >
> > I don't think so. I ommited it simply because it would more time
> > to implement.
>
> OK, thanks for confirming this.
>
> >
> >> Another thing that I noticed is that you completely removed the code
> >> that combined multiple stats (and selected the best combination of
> >> stats). In other words, you've reverted to the intermediate single
> >> statistics approach, including removing the improved handling of OR
> >> clauses and conditions.
> >
> > Yeah, good catch :p I noticed that just after submitting the
> > patch that I retaion only one statistics at the second level from
> > the bottom but it is easily fixed by changing pruning timing. The
> > struct can hold multiple statistics anyway.
>
> Great!

But sorry. I found that considering multiple stats at every level
cannot be done without exhaustive searching of combinations among
child clauses and needs additional data structure. It needs more
thoughs.. As mentioned later, top-down might be suitable for
this optimization.

> > And I don't omit OR case. It is handled along with the AND
> > case. (in wrong way?)
>
> Oh, I see. I got a bit confused because you've removed the
> optimization step (and conditions), and that needs to be handled a bit
> differently for the OR clauses.

Sorry to have forced you reading unapplicable patch:p

> >> It's a bit difficult to judge the proposed
> >> approach not knowing how well it supports those (quite crucial)
> >> features. What if it can't support some them., or what if it makes the
> >> code much more complicated (thus defeating the goal of making it more
> >> clear)?
> >
> > OR is supported, Fdep is maybe supportable, but all of them
> > occurs within the function with the entangled name
> > (transform..something). But I should put more consider on your
> > latest code before that.
>
> Good. Likewise, I'd like to see more of your approach ;-)
>
> >
> >> I share your concern about the performance impact - one thing is that
> >> this new code might be slower than the original one, but a more
> >> serious issue IMHO is that the performance impact will happen even for
> >> relations with no multivariate stats at all. The original patch was
> >> very careful about getting ~0% overhead in such cases,
> >
> > I don't think so. find_stats runs pull_varnos and
> > transformRestric.. also uses pull_varnos to bail out at the top
> > level. They should have almost the same overhead for the case.
>
> Understood. As I explained above, I'm not all that concerned about the
> performance impact, as long as we make sure it only applies to people
> using the multivariate stats.
>
> I also think a combined approach - first a bottom-up step (identifying
> the largest compatible subtrees & caching the varnos), then a top-down
> step (doing the same optimization as implemented today) might minimize
> the performance impact.

I almost reaching the same conclusion.

> >> and if the new
> >> code does not allow that, I don't see this approach as acceptable. We
> >> must not put additional overhead on people not using multivariate
> >> stats.
> >>
> >> But I think it's worth exploring this idea a bit more - can you rebase
> >> it to the current patch version (as on github) and adding the missing
> >> pieces (functional dependencies, multi-statistics estimation and
> >> passing conditions)?
> >
> > With pleasure. Please wait for a while.
>
> Sure. Take your time.
>
> >
> >> One more thing - I noticed you extended the pg_operator catalog with a
> >> oprmvstat attribute, used to flag operators that are compatible with
> >> multivariate stats. I'm not happy with the current approach (using
> >> oprrest to do this decision), but I'm not really sure this is a good
> >> solution either. The culprit is that it only answers one of the two
> >> important questions - Is it compatible? How to perform the estimation?
> >
> > Hostly saying, I also don't like this. But checking oprrest is
> > unpleasant much the same.
>
> The patch is already quite massive, so let's use the same approach as
> current stats, and leave this problem for another patch. If we come up
> with a great idea, we can work on it, but I see this as a loosely
> related annoyance rather than something this patch aims to address.

Agreed.

> >> So we'd have to rely on oprrest anyway, when actually performing the
> >> estimation of a clause with "compatible" operator. And we'd have to
> >> keep in sync two places (catalog and checks in file), and we'd have to
> >> update the catalog after improving the implementation (adding support
> >> for another operator).
> >
> > Mmm. It depends on what the deveopers think about the definition
> > of oprrest. More practically, I'm worried whether it cannot be
> > other than eqsel for any equality operator. And the same for
> > comparison operators.
>
> OTOH if you define a new operator with oprrest=F_EQSEL, you're
> effectively saying "It's OK to estimate this using regular eq/lt/gt
> operators". If your operator is somehow incompatible with that, you
> should not set oprrest=F_EQSEL.

In contrast, some function other than F_EQSEL might be compatible
with mv-statistics.

For all that, it's not my concern. Although I think they really
are effectively the same, I'm uneasy to use the field apparently
not intended (or suitable) to distinguish such kind of property
of operator.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hi,

On 07/30/2015 10:21 AM, Heikki Linnakangas wrote:
> On 05/25/2015 11:43 PM, Tomas Vondra wrote:
>> There are 6 files attached, but only 0002-0006 are actually part of the
>> multivariate statistics patch itself.
>
> All of these patches are huge. In order to review this in a reasonable
> amount of time, we need to do this in several steps. So let's see what
> would be the minimal set of these patches that could be reviewed and
> committed, while still being useful.
>
> The main patches are:
>
> 1. shared infrastructure and functional dependencies
> 2. clause reduction using functional dependencies
> 3. multivariate MCV lists
> 4. multivariate histograms
> 5. multi-statistics estimation
>
> Would it make sense to commit only patches 1 and 2 first? Would that be
> enough to get a benefit from this?

I agree that the patch can't be reviewed as a single chunk - that was
the idea when I split the original (single chunk) patch into multiple
smaller pieces.

And yes, I believe committing pieces 1&2 might be enough to get
something useful, which can then be improved by adding the "usual" MCV
and histogram stats on top of that.

> I have some doubts about the clause reduction and functional
> dependencies part of this. It seems to treat functional dependency as
> a boolean property, but even with the classic zipcode and city case,
> it's not always an all or nothing thing. At least in some countries,
> there can be zipcodes that span multiple cities. So zipcode=X does
> not completely imply city=Y, although there is a strong correlation
> (if that's the right term). How strong does the correlation need to
> be for this patch to decide that zipcode implies city? I couldn't
> actually see a clear threshold stated anywhere.
>
> So rather than treating functional dependence as a boolean, I think
> it would make more sense to put a 0.0-1.0 number to it. That means
> that you can't do clause reduction like it's done in this patch,
> where you actually remove clauses from the query for cost esimation
> purposes. Instead, you need to calculate the selectivity for each
> clause independently, but instead of just multiplying the
> selectivities together, apply the "dependence factor" to it.
>
> Does that make sense? I haven't really looked at the MCV, histogram
> and "multi-statistics estimation" patches yet. Do those patches make
> the clause reduction patch obsolete? Should we forget about the
> clause reduction and functional dependency patch, and focus on those
> later patches instead?

Perhaps. It's true that most real-world data sets are not 100% valid
with respect to functional dependencies - either because of natural
imperfections (multiple cities with the same ZIP code) or just noise in
the data (incorrect entries ...). And it's even mentioned in the code
comments somewhere, I guess.

But there are two main reasons why I chose not to extend the functional
dependencies with the [0.0-1.0] value you propose.

Firstly, functional dependencies were meant to be the simplest possible
implementation, illustrating how the "infrastructure" is supposed to
work (which is the main topic of the first patch).

Secondly, all kinds of statistics are "simplifications" of the actual
data. So I think it's not incorrect to ignore the exceptions up to some
threshold.

I also don't think this will make the estimates globally better. Let's
say you have 1% of rows that contradict the functional dependency - you
may either ignore them and have good estimates for 99% of the values and
incorrect estimates for 1%, or tweak the rule a bit and make the
estimates worse for 99% (and possibly better for 1%).

That being said, I'm not against improving the functional dependencies.
I already do have some improvements on my TODO - like for example
dependencies on more columns (not just A=>B but [A,B]=>C and such), but
I think we should not squash this into those two patches.

And yet another point - ISTM these cases might easily be handled better
by the statistics based on ndistinct coefficients, as proposed by
Kyotaro-san some time ago. That is, compute and track

ndistinct(A) * ndistinct(B) / ndistinct(A,B)

for all pairs of columns (or possibly larger groups). That seems to be
similar to the coefficient you propose.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hello,

On 07/30/2015 01:26 PM, Kyotaro HORIGUCHI wrote:
> Hello, I certainly attached the file this time.
>
>
> At Mon, 27 Jul 2015 23:54:08 +0200, Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in <55B6A880(dot)3050801(at)2ndquadrant(dot)com>
>
>> The bottom-up would work too, probably - I mean, we could start from
>> leaves of the expression tree, and build the largest "subtree"
>> compatible with multivariate stats and then try to estimate it. I
>> don't see how we could pass conditions though, which works naturally
>> in the top-down approach.
>
> By the way, the 'condition' looks to mean what will be received
> by the parameter of clause(list)_selectivity with the same
> name. But it is always NIL. Looking at the comment for
> collect_mv_attnum, it is prepared for 'multitable statistics'. If
> so, I think it's better removed from the current patch, because
> it is useless now.

I don't think so. Conditions certainly are not meant for multitable
statistics only (I don't see any comment suggesting that at
collect_mv_attnums), but are actually used with the current code.

For example try this:

create table t (a int, b int, c int);
insert into t select i/100, i/100, i/100
from generate_series(1,100000) s(i);
alter table t add statistics (mcv) on (a,b);
analyze t;

select * from t where a<10 and b < 10 and (a < 50 or b < 50 or c < 50);

What will happen when estimating this query is this:

(1) clauselist_selectivity is called, and sees a list of three clauses:

(a<10)
(b<10)
(a<50 OR b<50 OR c<50)

But there's only a single statistics on columns [a,b] so at this
point we can process only the first two clauses. So we'll do that,
computing

P(a<10, b<10)

and we'll pass the OR-clause to the clause_selectivity() call, along
with the two already estimated clauses as conditions.

(b) clause_selectivity will receive (a<50 OR b<50 OR c<50) as a clause
to estimate, and the two clauses as conditions, computing

P(a<50 OR b<50 OR c<50 | a<10, b<10)

The current estimate for the OR-clause is off, but I believe that's a
bug in the current implementation of clauselist_selectivity_or(), and
we've already discussed that some time ago.

>
> The functional dependency code looks immature in both the
> detection phase and application phase in comparison to MCV and
> histogram. Addition to that, as the comment in dependencies.c
> says, fdep is not so significant (than MCV/HIST) because it is
> usually carefully avoided and should be noticed and considered in
> designing of application or the whole system.

The code is certainly imperfect and needs improvements, no doubt about
that. I have certainly spent much more time on MCV/histograms.

I'm not sure about stating that functional dependencies are less
significant than MCV/HIST (I don't see any such statement in
dependencies.c). I might have thought that initially, when I opted to
implement fdeps as the simplest possible type of statistics, but I think
it's quite practical, actually.

I however disagree about the last point - it's true that in many cases
the databases are carefully normalized, which mostly makes functional
dependencies irrelevant. But this is only true for OLTP systems, while
the primary target of the patch are DSS/DWH systems. And in those
systems denormalization is a very common practice.

So I don't think fdeps are completely irrelevant - it's quite useful in
some scenarios, actually. Similarly to the ndistinct coefficient stats
that you proposed, for example.

>
> Persisting to apply them all at once doesn't seem to be a good
> strategy to be adopted earlier.

Why?

>
> Or perhaps it might be better to register the dependency itself
> than registering incomplete information (only the set of colums
> involoved in the relationship) and try to detect the relationship
> from the given values. I suppose those who can register the
> columnset know the precise nature of the dependency in advance.

I don't see how that could be done? I mean, you only have the constants
supplied in the query - how could you verify the functional dependency
based on just those values (or even decide the direction)?

>>
>> What do you mean by "reconstruct the expression tree"? It's true I'm
>> walking the expression tree top-down, but how is that reconstructing?
>
> For example clauselist_mv_split does. It separates mvclauses from
> original clauselist and apply mv-stats at once and (parhaps) let
> the rest be processed in the 'normal' route. I called this as
> "reconstruct", which I tried to do explicity and separately.

Ah, I see. Thanks for the explanation. I wouldn't call this
"reconstruction" though - I merely need to track which clauses to
estimate using multivariate stats (and which need to be estimated using
the regular stats). That's pretty much what RestrictStatData does, no?

>>
>> I find your comments very valuable. I may not agree with some of
>> them, but I certainly appreciate your point of view. So thank you
>> very much for the time you spent reviewing this patch so far!
>
> Yeah, thank you for your patience and kindness.

Likewise. It's very frustrating trying to understand complex code
written by someone else, and I appreciate your effort.

>> Regarding the complexity - I am not too worried about spending
>> more CPU cycles on this, as long as it does not impact the case
>> where people have no multivariate statistics at all. That's because
>> I expect people to use this for large DSS/DWH data sets with lots
>> of dependencies in the (often denormalized) tables and complex
>> conditions - in those cases the planning difference is negligible,
>> especially if the improved estimates make the query run in seconds
>> instead of hours.
>
> I share the vision with you. If that is the case, the mv-stats
> route should not be intrude the existing non-mv-stats route. I
> feel you have too much intruded clauselist_selectivity all the
> more.
>
> If that is the case, my mv-distinct code has different objective
> from you. It aims to save the misestimation from multicolumn
> correlations more commonly occurs in OLTP usage.

OK. Let's see if we can make it work for both use cases.

>
>> This is why I was so careful to entirely skip the expensive
>> processing when where were no multivariate stats, and why I don't
>> like the fact that your approach makes this skip more difficult (or
>> maybe impossible, I'm not sure).
>
> My code totally skips if transformRestrictionForEstimate returns
> NULL and runs clauselist_selectivity as usual. I think almost the
> same as yours.

Ah, OK. Perhaps I missed that as I've had trouble applying the patch.

>
> However, if you think it I believe we should not only skipping
> calculation but also hiding the additional code blocks which is
> overwhelming the normal route. The one of major objectives of my
> approach is that point.

My main concern at this point was planning time, so skipping the
calculation should be enough I believe. Hiding the additional code
blocks is a matter of aesthetics, and we can address that by moving it
to a separate method or such.

>
> But sorry. I found that considering multiple stats at every level
> cannot be done without exhaustive searching of combinations among
> child clauses and needs additional data structure. It needs more
> thoughs.. As mentioned later, top-down might be suitable for
> this optimization.

Do you think a combined approach - first bottom-up preprocessing, then
top-down optimization (using the results of the first phase to speed
things up) - might work?

>> Understood. As I explained above, I'm not all that concerned about
>> the performance impact, as long as we make sure it only applies to
>> people using the multivariate stats.
>>
>> I also think a combined approach - first a bottom-up step
>> (identifying the largest compatible subtrees & caching the varnos),
>> then a top-down step (doing the same optimization as implemented
>> today) might minimize the performance impact.
>
> I almost reaching the same conclusion.

Ah, so the answer to my last question is "yes". Now we only need to
actually code it ;-)

kind regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 07/30/2015 03:55 PM, Tomas Vondra wrote:
> On 07/30/2015 10:21 AM, Heikki Linnakangas wrote:
>> I have some doubts about the clause reduction and functional
>> dependencies part of this. It seems to treat functional dependency as
>> a boolean property, but even with the classic zipcode and city case,
>> it's not always an all or nothing thing. At least in some countries,
>> there can be zipcodes that span multiple cities. So zipcode=X does
>> not completely imply city=Y, although there is a strong correlation
>> (if that's the right term). How strong does the correlation need to
>> be for this patch to decide that zipcode implies city? I couldn't
>> actually see a clear threshold stated anywhere.
>>
>> So rather than treating functional dependence as a boolean, I think
>> it would make more sense to put a 0.0-1.0 number to it. That means
>> that you can't do clause reduction like it's done in this patch,
>> where you actually remove clauses from the query for cost esimation
>> purposes. Instead, you need to calculate the selectivity for each
>> clause independently, but instead of just multiplying the
>> selectivities together, apply the "dependence factor" to it.
>>
>> Does that make sense? I haven't really looked at the MCV, histogram
>> and "multi-statistics estimation" patches yet. Do those patches make
>> the clause reduction patch obsolete? Should we forget about the
>> clause reduction and functional dependency patch, and focus on those
>> later patches instead?
>
> Perhaps. It's true that most real-world data sets are not 100% valid
> with respect to functional dependencies - either because of natural
> imperfections (multiple cities with the same ZIP code) or just noise in
> the data (incorrect entries ...). And it's even mentioned in the code
> comments somewhere, I guess.
>
> But there are two main reasons why I chose not to extend the functional
> dependencies with the [0.0-1.0] value you propose.
>
> Firstly, functional dependencies were meant to be the simplest possible
> implementation, illustrating how the "infrastructure" is supposed to
> work (which is the main topic of the first patch).
>
> Secondly, all kinds of statistics are "simplifications" of the actual
> data. So I think it's not incorrect to ignore the exceptions up to some
> threshold.

The problem with a threshold is that around that threshold, even a small
change in the data set can drastically change the produced estimates.
For example, imagine that we know from the stats that zip code implies
city. But then someone adds a single row to the table with an odd zip
code & city combination, which pushes the estimator over the threshold,
and the columns are no longer considered dependent, and the estimates
are now completely different. We should avoid steep cliffs like that.

BTW, what is the threshold in the current patch?

- Heikki

Hi,

On 07/30/2015 06:58 PM, Heikki Linnakangas wrote:
>
> The problem with a threshold is that around that threshold, even a
> small change in the data set can drastically change the produced
> estimates. For example, imagine that we know from the stats that zip
> code implies city. But then someone adds a single row to the table
> with an odd zip code & city combination, which pushes the estimator
> over the threshold, and the columns are no longer considered
> dependent, and the estimates are now completely different. We should
> avoid steep cliffs like that.
>
> BTW, what is the threshold in the current patch?

There's not a simple threshold - the algorithm mining the functional
dependencies is a bit more complicated. I tried to explain it in the
comment before build_mv_dependencies (in dependencies.c), but let me
briefly summarize it here.

To mine dependency [A => B], build_mv_dependencies does this:

(1) sort the sample by {A,B}

(2) split the sample into groups with the same value of A

(3) for each group, decide if it's consistent with the dependency

(a) if the group is too small (less than 3 rows), ignore it

(a) if the group is consistent, update

n_supporting
n_supporting_rows

(b) if the group is inconsistent, update

n_contradicting
n_contradicting_rows

(4) decide whether the dependency is "valid" by checking

n_supporting_rows >= n_contradicting_rows * 10

The limit is rather arbitrary and yes - I can imagine a more complex
condition (e.g. looking at average number of tuples per group etc.), but
I haven't looked into that - the point was to use something very simple,
only to illustrate the infrastructure.

I think we might come up with some elaborate way of associating "degree"
with the functional dependency, but at that point we really loose the
simplicity, and also make it indistinguishable from the remaining
statistics (because it won't be possible to reduce the clauses like
this, before performing the regular estimation). Which is exactly what
makes the functional dependencies so neat and efficient, so I'm not
overly enthusiastic about doing that.

What seems more interesting is implementing the ndistinct coefficient
instead, as proposed by Kyotaro-san - that seems to have the nice
"smooth" behavior you desire, while keeping the simplicity.

Both statistics types (functional dependencies and ndistinct coeff) have
one weak point, though - they somehow assume the queries use
"compatible" values. For example if you use a query with

WHERE city = 'New York' AND zip = 'zip for Detroit'

they can't detect cases like this, because those statistics types are
oblivious to individual values. I don't see this as a fatal flaw, though
- it's rather a consequence of the nature of the stats. And I tend to
look at the functional dependencies the same way.

If you need stats without these "issues" you'll have to use MCV list or
a histogram. Trying to fix the simple statistics types is futile, IMHO.

regards
Tomas

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Fri, Jul 31, 2015 at 6:28 AM, Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> [series of arguments]
>
> If you need stats without these "issues" you'll have to use MCV list or a
> histogram. Trying to fix the simple statistics types is futile, IMHO.

Patch is marked as returned with feedback. There has been advanced
discussions and reviews as well.
--
Michael

Tomas,

> attached is v7 of the multivariate stats patch. The main improvement is
> major refactoring of the clausesel.c portion - splitting the awfully
> long spaghetti-style functions into smaller pieces, making it much more
> understandable etc.

So presumably v7 handles varlena attributes as well, yes? I have a
destruction test case for correlated column stats, so I'd like to test
your patch on it.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Hi,

On 09/24/2015 06:43 PM, Josh Berkus wrote:
> Tomas,
>
>> attached is v7 of the multivariate stats patch. The main improvement is
>> major refactoring of the clausesel.c portion - splitting the awfully
>> long spaghetti-style functions into smaller pieces, making it much more
>> understandable etc.
>
> So presumably v7 handles varlena attributes as well, yes? I have a
> destruction test case for correlated column stats, so I'd like to test
> your patch on it.

Yes, it should handle varlena OK. Let me know if you need help with
that, and I'd like to hear feedback - whether it fixed your test case or
not, etc.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi,

attached is v8 of the multivariate statistics patch (or rather a patch
series). The patch currently has 7 parts, but 0001 is just a fix of the
pull_varnos issue (possibly incorrect/temporary), and 0007 is just an
attempt to add the "multicolumn distinctness" (experimental for now).

There are three noteworthy changes:

1) Correct estimation of OR-clauses - this turned out to be a rather
minor change, thanks to simply transforming the OR-clauses to
AND-clauses, see clauselist_selectivity_or() for details.

2) Abandoning the ALTER TABLE ... ADD STATISTICS syntax and instead
adding separate commands CREATE STATISTICS / DROP STATISTICS, as
proposed in the "multicolumn distinctness" thread:

http://www.postgresql.org/message-id/20150828.173334.114731693.horiguchi.kyotaro@lab.ntt.co.jp

This seems a better approach than the ALTER TABLE one - not only it
nicely fixes the grammar issues, it also naturally extends to
multi-table statistics (despite we don't know how those should work
exactly).

The syntax is this:

CREATE STATISTICS name ON table (columns) WITH (options);

DROP STATISTICS name;

and the 'name' is optional (and if absent, should be generated just
like for indexes, but that's not implemented yet).

The remaining question is how unique the statistics name should be.
My initial plan was to make it unique within a table, but that of
course does not work well with the DROP STATISTICS (it'd have to
specify the table name also), and it'd also now work with statistics
on multiple tables (which is one of the reasons for abandoning ALTER
TABLE stuff).

So I think it should be unique across tables. Statistics are hardly
a global object, so it should be unique within a schema. I thought
that simply using the schema of the table would work, but that of
course breaks with multiple tables in different schemas. So the only
solution seems to be explicit schema for statistics.

3) I've also started hacking on adding the "multicolumn distinctness"
proposed by Horiguchi-san, but I haven't really got that working. It
seems to be a bit more complicated than I anticipated because of the
"only equality conditions" restriction. So the 0007 patch only
really adds basic syntax and trivial build.

I do have bunch of ideas/questions about this statistics type. For
example, should we compute just a single coefficient or the exact
combination of columns specified in CREATE STATISTICS, or perhaps
for some additional subsets? I.e. with

CREATE STATISTICS ON t (a,b,c) WITH (ndistinct);

should we compute just the coefficient for (a,b,c), or maybe also
for (a,b), (b,c) and (a,c)? For N columns there's O(2^N) such
combinations, but perhaps it's acceptable.

Having the coefficient for just the single combination specified in
CREATE STATISTICS makes the estimation difficult when some of the
columns are not specified. For example, with coefficient just for
(a,b,c), what should happen for (WHERE a=1 AND b=2)?

Should we simply ignore the statistics, or apply it anyway and
somehow compensate for the missing columns?

I've also started working on something like a paper, hopefully
explaining the ideas and implementation more clearly and consistently
than possible on a mailing list (thanks to charts, figures and such).
It's available here (both the .tex source and .pdf with the current
version):

https://bitbucket.org/tvondra/mvstats-paper/src

It's not exactly short (~30 pages), and it's certainly incomplete with a
plenty of TODO notes, but hopefully it's already useful and not entirely
bogus.

Comments and questions are welcome - both to the patch and paper.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi,

attached is v9 of the patch series, including mostly these changes:

1) CREATE STATISTICS cleanup

Firstly, I forgot to make the STATISTICS keyword unreserved again.
I've also removed additional stuff from the grammar that turned out
to be unnecessary / could be replaced with existing pieces.

2) making statistics schema-specific

Similarly to the other objects (e.g. types), statistics names are now
unique within a schema. This also means that the statistics may be
created using qualified name, and also may belong to a different
schema than a table.

It seems to me we probably also need to track owner, and only allow
the owner (or superuser / schema owner) to manipulate the statistics.

The initial intention was to inherit all this from the parent table,
but as we're designing this for the multi-table case, it's not
really working anymore.

3) adding IF [NOT] EXISTS to DROP STATISTICS / CREATE STATISTICS

4) basic documentation of the DDL commands

It's really simple at this point and some of the paragraphs are
still empty. I also think that we'll have to add stuff explaining
how to use statistics, not just docs for the DDL commands.

5) various fixes of the regression tests, related to the above

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 12/12/14 05:53, Heikki Linnakangas wrote:
> On 10/13/2014 01:00 AM, Tomas Vondra wrote:
>> Hi,
>>
>> attached is a WIP patch implementing multivariate statistics.
>
> Great! Really glad to see you working on this.
>
>> + * FIXME This sample sizing is mostly OK when computing stats for
>> + * individual columns, but when computing multi-variate stats
>> + * for multivariate stats (histograms, mcv, ...) it's rather
>> + * insufficient. For small number of dimensions it works, but
>> + * for complex stats it'd be nice use sample proportional to
>> + * the table (say, 0.5% - 1%) instead of a fixed size.
>
> I don't think a fraction of the table is appropriate. As long as the
> sample is random, the accuracy of a sample doesn't depend much on the
> size of the population. For example, if you sample 1,000 rows from a
> table with 100,000 rows, or 1000 rows from a table with 100,000,000
> rows, the accuracy is pretty much the same. That doesn't change when
> you go from a single variable to multiple variables.
>
> You do need a bigger sample with multiple variables, however. My gut
> feeling is that if you sample N rows for a single variable, with two
> variables you need to sample N^2 rows to get the same accuracy. But
> it's not proportional to the table size. (I have no proof for that,
> but I'm sure there is literature on this.)
[...]