PATCH: multivariate histograms and MCV lists

classic Classic list List threaded Threaded
109 messages Options
1234 ... 6
Reply | Threaded
Open this post in threaded view
|

PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
Hi all,

For PostgreSQL 10 we managed to get the basic CREATE STATISTICS bits in
(grammar, infrastructure, and two simple types of statistics). See:

     https://commitfest.postgresql.org/13/852/

This patch presents a rebased version of the remaining parts, adding
more complex statistic types (MCV lists and histograms), and hopefully
some additional improvements.

The code was rebased on top of current master, and I've made various
improvements to match how the committed parts were reworked. So the
basic idea and shape remains the same, the tweaks are mostly small.


regards

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


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

0001-Multivariate-MCV-list-statistics.patch (118K) Download Attachment
0002-Multivariate-histograms.patch (174K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Adrien Nayrat
On 08/14/2017 12:48 AM, Tomas Vondra wrote:

> Hi all,
>
> For PostgreSQL 10 we managed to get the basic CREATE STATISTICS bits in
> (grammar, infrastructure, and two simple types of statistics). See:
>
>     https://commitfest.postgresql.org/13/852/
>
> This patch presents a rebased version of the remaining parts, adding more
> complex statistic types (MCV lists and histograms), and hopefully some
> additional improvements.
>
> The code was rebased on top of current master, and I've made various
> improvements to match how the committed parts were reworked. So the basic idea
> and shape remains the same, the tweaks are mostly small.
>
>
> regards
>
>
>
>
Hello,

There is no check of "statistics type/kind" in pg_stats_ext_mcvlist_items and
pg_histogram_buckets.

select stxname,stxkind from pg_statistic_ext ;
  stxname  | stxkind
-----------+---------
 stts3     | {h}
 stts2     | {m}

So you can call :

SELECT * FROM pg_mcv_list_items((SELECT oid FROM pg_statistic_ext WHERE stxname
= 'stts3'));

SELECT * FROM pg_histogram_buckets((SELECT oid FROM pg_statistic_ext WHERE
stxname = 'stts2'), 0);

Both crashes.

Unfotunately, I don't have the knowledge to produce a patch :/

Small fix in documentation, patch attached.


Thanks!

--
Adrien NAYRAT

http://dalibo.com - http://dalibo.org

doc.patch (2K) Download Attachment
signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4


On 08/17/2017 12:06 PM, Adrien Nayrat wrote:>

> Hello,
>
> There is no check of "statistics type/kind" in
> pg_stats_ext_mcvlist_items and pg_histogram_buckets.
>
> select stxname,stxkind from pg_statistic_ext ; stxname  | stxkind
> -----------+--------- stts3     | {h} stts2     | {m}
>
> So you can call :
>
> SELECT * FROM pg_mcv_list_items((SELECT oid FROM pg_statistic_ext
> WHERE stxname = 'stts3'));
>
> SELECT * FROM pg_histogram_buckets((SELECT oid FROM pg_statistic_ext
> WHERE stxname = 'stts2'), 0);
>
> Both crashes.
>

Thanks for the report, this is clearly a bug. I don't think we need to
test the stxkind, but rather a missing check that the requested type is
actually built.

> Unfotunately, I don't have the knowledge to produce a patch :/
>
> Small fix in documentation, patch attached.
>

Thanks, will fix.

regards

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


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
Hi,

Attached is an updated version of the patch, fixing the issues reported
by Adrien Nayrat, and also a bunch of issues pointed out by valgrind.

regards

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


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

0001-MCV-lists.patch.gz (42K) Download Attachment
0002-multivariate-histograms.patch.gz (62K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
Attached is an updated version of the patch, dealing with fallout of
821fb8cdbf700a8aadbe12d5b46ca4e61be5a8a8 which touched the SGML
documentation for CREATE STATISTICS.

regards

On 09/07/2017 10:07 PM, Tomas Vondra wrote:
> Hi,
>
> Attached is an updated version of the patch, fixing the issues reported
> by Adrien Nayrat, and also a bunch of issues pointed out by valgrind.
>
> regards
>

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


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

0001-multivariate-MCV-lists.patch.gz (42K) Download Attachment
0002-multivariate-histograms.patch.gz (62K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4

> On Sep 12, 2017, at 2:06 PM, Tomas Vondra <[hidden email]> wrote:
>
> Attached is an updated version of the patch, dealing with fallout of
> 821fb8cdbf700a8aadbe12d5b46ca4e61be5a8a8 which touched the SGML
> documentation for CREATE STATISTICS.

Your patches need updating.

Tom's commit 471d55859c11b40059aef7dd82f82b3a0dc338b1 changed
src/bin/psql/describe.c, which breaks your 0001-multivariate-MCV-lists.patch.gz
file.

I reviewed the patch a few months ago, and as I recall, it looked good to me.
I should review it again before approving it, though.

mark



--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
Hi,

Attached is an updated version of the patch, adopting the psql describe
changes introduced by 471d55859c11b.

regards

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

0001-multivariate-MCV-lists.patch.gz (42K) Download Attachment
0002-multivariate-histograms.patch.gz (62K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4

> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>
> Hi,
>
> Attached is an updated version of the patch, adopting the psql describe
> changes introduced by 471d55859c11b.
>
> regards
>
> --
> Tomas Vondra                  http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>

Thanks, Tomas, again for your work on this feature.

Applying just the 0001-multivariate-MCV-lists.patch to the current master, and
then extending the stats_ext.sql test as follows, I am able to trigger an error,
"ERROR:  operator 4294934272 is not a valid ordering operator".

 

diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index e9902ced5c..5083dc05e6 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -402,4 +402,22 @@ EXPLAIN (COSTS OFF)
 EXPLAIN (COSTS OFF)
  SELECT * FROM mcv_lists WHERE a IS NULL AND b IS NULL AND c IS NULL;
 
-RESET random_page_cost;
+DROP TABLE mcv_lists;
+
+CREATE TABLE mcv_lists (
+    a NUMERIC[],
+   b NUMERIC[]
+);
+CREATE STATISTICS mcv_lists_stats (mcv) ON a, b FROM mcv_lists;
+INSERT INTO mcv_lists (a, b)
+   (SELECT array_agg(gs::numeric) AS a, array_agg(gs::numeric) AS b
+       FROM generate_series(1,1000) gs
+   );
+ANALYZE mcv_lists;
+INSERT INTO mcv_lists (a, b)
+   (SELECT array_agg(gs::numeric) AS a, array_agg(gs::numeric) AS b
+       FROM generate_series(1,1000) gs
+   );
+ANALYZE mcv_lists;
+
+DROP TABLE mcv_lists;

Which gives me the following regression.diffs:

*** /Users/mark/master/postgresql/src/test/regress/expected/stats_ext.out   2017-11-25 08:06:37.000000000 -0800
--- /Users/mark/master/postgresql/src/test/regress/results/stats_ext.out    2017-11-25 08:10:18.000000000 -0800
***************
*** 721,724 ****
           Index Cond: ((a IS NULL) AND (b IS NULL))
  (5 rows)
 
! RESET random_page_cost;
--- 721,741 ----
           Index Cond: ((a IS NULL) AND (b IS NULL))
  (5 rows)
 
! DROP TABLE mcv_lists;
! CREATE TABLE mcv_lists (
!     a NUMERIC[],
!   b NUMERIC[]
! );
! CREATE STATISTICS mcv_lists_stats (mcv) ON a, b FROM mcv_lists;
! INSERT INTO mcv_lists (a, b)
!   (SELECT array_agg(gs::numeric) AS a, array_agg(gs::numeric) AS b
!       FROM generate_series(1,1000) gs
!   );
! ANALYZE mcv_lists;
! INSERT INTO mcv_lists (a, b)
!   (SELECT array_agg(gs::numeric) AS a, array_agg(gs::numeric) AS b
!       FROM generate_series(1,1000) gs
!   );
! ANALYZE mcv_lists;
! ERROR:  operator 4294934272 is not a valid ordering operator
! DROP TABLE mcv_lists;

======================================================================


Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4
In reply to this post by Tomas Vondra-4

> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>
> Hi,
>
> Attached is an updated version of the patch, adopting the psql describe
> changes introduced by 471d55859c11b.
>
> regards
>
> --
> Tomas Vondra                  http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>

Hello Tomas,

In 0002-multivariate-histograms.patch, src/include/nodes/relation.h,
struct StatisticExtInfo, you change:

-       char            kind;                   /* statistic kind of this entry */
+       int                     kinds;                  /* statistic kinds of this entry */

to have 'kinds' apparently be a bitmask, based on reading how you use
this in the code.  The #defines just below the struct give the four bits
to be used,

#define STATS_EXT_INFO_NDISTINCT            1
#define STATS_EXT_INFO_DEPENDENCIES         2
#define STATS_EXT_INFO_MCV                  4
#define STATS_EXT_INFO_HISTOGRAM            8

except that nothing in the file indicates that this is so.  Perhaps a comment
could be added here mentioning that 'kinds' is a bitmask, and that these
#defines are related?

mark
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
In reply to this post by Mark Dilger-4
Hi,

On 11/25/2017 05:15 PM, Mark Dilger wrote:

>
>> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>>
>> Hi,
>>
>> Attached is an updated version of the patch, adopting the psql describe
>> changes introduced by 471d55859c11b.
>>
>> regards
>>
>> --
>> Tomas Vondra                  http://www.2ndQuadrant.com
>> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>
>
> Thanks, Tomas, again for your work on this feature.
>
> Applying just the 0001-multivariate-MCV-lists.patch to the current master, and
> then extending the stats_ext.sql test as follows, I am able to trigger an error,
> "ERROR:  operator 4294934272 is not a valid ordering operator".
>
Ah, that's a silly bug ...

The code assumes that VacAttrStats->extra_data is always StdAnalyzeData,
and attempts to extract the ltopr from that. But for arrays that's of
course not true (array_typanalyze uses ArrayAnalyzeExtraData instead).

The reason why this only fails after the second INSERT is that we need
at least two occurrences of a value before considering it eligible for
MCV list. So after the first INSERT we don't even call the serialize.

Attached is a fix that should resolve this in MCV lists by looking up
the operator using lookup_type_cache() when serializing the MCV.

FWIW histograms have the same issue, but on more places (not just in
serialize, but also when building the histogram).

I'll send a properly updated patch series shortly, with tests checking
correct behavior with arrays.

Thanks for the report.

regards

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

0001-MCV-fix.patch (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4
In reply to this post by Tomas Vondra-4

> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>
> Hi,
>
> Attached is an updated version of the patch, adopting the psql describe
> changes introduced by 471d55859c11b.
>
> regards
>
> --
> Tomas Vondra                  http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>

Hello Tomas,

After applying both your patches, I get a warning:

histogram.c:1284:10: warning: taking the absolute value of unsigned type 'uint32' (aka 'unsigned int') has no effect [-Wabsolute-value]
        delta = fabs(data->numrows);
                ^
histogram.c:1284:10: note: remove the call to 'fabs' since unsigned values cannot be negative
        delta = fabs(data->numrows);
                ^~~~
1 warning generated.


Looking closer at this section, there is some odd integer vs. floating point arithmetic happening
that is not necessarily wrong, but might be needlessly inefficient:

    delta = fabs(data->numrows);
    split_value = values[0].value;

    for (i = 1; i < data->numrows; i++)
    {
        if (values[i].value != values[i - 1].value)
        {
            /* are we closer to splitting the bucket in half? */
            if (fabs(i - data->numrows / 2.0) < delta)
            {
                /* let's assume we'll use this value for the split */
                split_value = values[i].value;
                delta = fabs(i - data->numrows / 2.0);
                nrows = i;
            }
        }
    }

I'm not sure the compiler will be able to optimize out the recomputation of data->numrows / 2.0
each time through the loop, since the compiler might not be able to prove to itself that data->numrows
does not get changed.  Perhaps you should compute it just once prior to entering the outer loop,
store it in a variable of integer type, round 'delta' off and store in an integer, and do integer comparisons
within the loop?  Just a thought....


mark
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4
In reply to this post by Tomas Vondra-4

> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>
> Hi,
>
> Attached is an updated version of the patch, adopting the psql describe
> changes introduced by 471d55859c11b.
>
> regards
>
> --
> Tomas Vondra                  http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>

In src/backend/statistics/mcv.c, you have a few typos:

+ * there bo be a lot of duplicate values. But perhaps that's not true and we

+       /* Now it's safe to access the dimention info. */

+        * Nowe we know the total expected MCV size, including all the pieces

+                       /* pased by reference, but fixed length (name, tid, ...) */


In src/include/statistics/statistics.h, there is some extraneous whitespace that needs
removing.


mark
Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4
In reply to this post by Tomas Vondra-4

> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>
> Hi,
>
> Attached is an updated version of the patch, adopting the psql describe
> changes introduced by 471d55859c11b.

Hi Tomas,

In src/backend/statistics/dependencies.c, you have introduced a comment:

+       /*
+        * build an array of SortItem(s) sorted using the multi-sort support
+        *
+        * XXX This relies on all stats entries pointing to the same tuple
+        * descriptor. Not sure if that might not be the case.
+        */

Would you mind explaining that a bit more for me?  I don't understand exactly what
you mean here, but it sounds like the sort of thing that needs to be clarified/fixed
before it can be committed.  Am I misunderstanding this?


In src/backend/statistics/mcv.c, you have comments:

+ * FIXME: Single-dimensional MCV is sorted by frequency (descending). We
+ * should do that too, because when walking through the list we want to
+ * check the most frequent items first.
+ *
+ * TODO: We're using Datum (8B), even for data types (e.g. int4 or float4).
+ * Maybe we could save some space here, but the bytea compression should
+ * handle it just fine.
+ *
+ * TODO: This probably should not use the ndistinct directly (as computed from
+ * the table, but rather estimate the number of distinct values in the
+ * table), no?

Do you intend these to be fixed/implemented prior to committing this patch?


Further down in function statext_mcv_build, you have two loops, the first allocating
memory and the second initializing the memory.  There is no clear reason why this
must be done in two loops.  I tried combining the two loops into one, and it worked
just fine, but did not look any cleaner to me.  Feel free to disregard this paragraph
if you like it better the way you currently have it organized.


Further down in statext_mcv_deserialize, you have some elogs which might need to be
ereports.  It is unclear to me whether you consider these deserialize error cases to be
"can't happen" type errors.  If so, you might add that fact to the comments rather than
changing the elogs to ereports.


mark


Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
In reply to this post by Mark Dilger-4
Hi,

On 11/25/2017 09:23 PM, Mark Dilger wrote:

>
>> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>>
>> Hi,
>>
>> Attached is an updated version of the patch, adopting the psql describe
>> changes introduced by 471d55859c11b.
>>
>> regards
>>
>> --
>> Tomas Vondra                  http://www.2ndQuadrant.com
>> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>> <0001-multivariate-MCV-lists.patch.gz><0002-multivariate-histograms.patch.gz>
>
> Hello Tomas,
>
> After applying both your patches, I get a warning:
>
> histogram.c:1284:10: warning: taking the absolute value of unsigned type 'uint32' (aka 'unsigned int') has no effect [-Wabsolute-value]
>         delta = fabs(data->numrows);
>                 ^
> histogram.c:1284:10: note: remove the call to 'fabs' since unsigned values cannot be negative
>         delta = fabs(data->numrows);
>                 ^~~~
> 1 warning generated.
>

Hmm, yeah. The fabs() call is unnecessary, and probably a remnant from
some previous version where the field was not uint32.

I wonder why you're getting the warning and I don't, though. What
compiler are you using?

>
> Looking closer at this section, there is some odd integer vs. floating point arithmetic happening
> that is not necessarily wrong, but might be needlessly inefficient:
>
>     delta = fabs(data->numrows);
>     split_value = values[0].value;
>
>     for (i = 1; i < data->numrows; i++)
>     {
>         if (values[i].value != values[i - 1].value)
>         {
>             /* are we closer to splitting the bucket in half? */
>             if (fabs(i - data->numrows / 2.0) < delta)
>             {
>                 /* let's assume we'll use this value for the split */
>                 split_value = values[i].value;
>                 delta = fabs(i - data->numrows / 2.0);
>                 nrows = i;
>             }
>         }
>     }
>
> I'm not sure the compiler will be able to optimize out the recomputation of data->numrows / 2.0
> each time through the loop, since the compiler might not be able to prove to itself that data->numrows
> does not get changed.  Perhaps you should compute it just once prior to entering the outer loop,
> store it in a variable of integer type, round 'delta' off and store in an integer, and do integer comparisons
> within the loop?  Just a thought....
>

Yeah, that's probably right. But I wonder if the loop is needed at all,
or whether we should start at i=(data->numrows/2.0) instead, and walk to
the closest change of value in both directions. That would probably save
more CPU than computing numrows/2.0 only once.

The other issue in that block of code seems to be that we compare the
values using simple inequality. That probably works for passbyval data
types, but we should use proper comparator (e.g. compare_datums_simple).

regards

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

Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
In reply to this post by Mark Dilger-4


On 11/25/2017 10:01 PM, Mark Dilger wrote:

>
>> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>>
>> Hi,
>>
>> Attached is an updated version of the patch, adopting the psql describe
>> changes introduced by 471d55859c11b.
>
> Hi Tomas,
>
> In src/backend/statistics/dependencies.c, you have introduced a comment:
>
> +       /*
> +        * build an array of SortItem(s) sorted using the multi-sort support
> +        *
> +        * XXX This relies on all stats entries pointing to the same tuple
> +        * descriptor. Not sure if that might not be the case.
> +        */
>
> Would you mind explaining that a bit more for me?  I don't understand exactly what
> you mean here, but it sounds like the sort of thing that needs to be clarified/fixed
> before it can be committed.  Am I misunderstanding this?
>

The call right after that comment is

    items = build_sorted_items(numrows, rows, stats[0]->tupDesc,
                               mss, k, attnums_dep);

That method processes an array of tuples, and the structure is defined
by "tuple descriptor" (essentially a list of attribute info - data type,
length, ...). We get that from stats[0] and assume all the entries point
to the same tuple descriptor. That's generally safe assumption, I think,
because all the stats entries relate to columns from the same table.

>
> In src/backend/statistics/mcv.c, you have comments:
>
> + * FIXME: Single-dimensional MCV is sorted by frequency (descending). We
> + * should do that too, because when walking through the list we want to
> + * check the most frequent items first.
> + *
> + * TODO: We're using Datum (8B), even for data types (e.g. int4 or float4).
> + * Maybe we could save some space here, but the bytea compression should
> + * handle it just fine.
> + *
> + * TODO: This probably should not use the ndistinct directly (as computed from
> + * the table, but rather estimate the number of distinct values in the
> + * table), no?
>
> Do you intend these to be fixed/implemented prior to committing this patch?
>

Actually, the first FIXME is obsolete, as build_distinct_groups returns
the groups sorted by frequency. I'll remove that.

I think the rest is more a subject for discussion, so I'd need to hear
some feedback.

>
> Further down in function statext_mcv_build, you have two loops, the first allocating
> memory and the second initializing the memory.  There is no clear reason why this
> must be done in two loops.  I tried combining the two loops into one, and it worked
> just fine, but did not look any cleaner to me.  Feel free to disregard this paragraph
> if you like it better the way you currently have it organized.
>

I did it this way because of readability. I don't think this is a major
efficiency issue, as the maximum number of items is fairly limited, and
it happens only once at the end of the MCV list build (and the sorts and
comparisons are likely much more CPU expensive).

>
> Further down in statext_mcv_deserialize, you have some elogs which might need to be
> ereports.  It is unclear to me whether you consider these deserialize error cases to be
> "can't happen" type errors.  If so, you might add that fact to the comments rather than
> changing the elogs to ereports.
>

I might be missing something, but why would ereport be more appropriate
than elog? Ultimately, there's not much difference between elog(ERROR)
and ereport(ERROR) - both will cause a failure.

regards

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

Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Mark Dilger-4

> On Nov 25, 2017, at 3:33 PM, Tomas Vondra <[hidden email]> wrote:
>
>
>
> On 11/25/2017 10:01 PM, Mark Dilger wrote:
>>
>>> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>>>
>>> Hi,
>>>
>>> Attached is an updated version of the patch, adopting the psql describe
>>> changes introduced by 471d55859c11b.
>>
>> Hi Tomas,
>>
>> In src/backend/statistics/dependencies.c, you have introduced a comment:
>>
>> +       /*
>> +        * build an array of SortItem(s) sorted using the multi-sort support
>> +        *
>> +        * XXX This relies on all stats entries pointing to the same tuple
>> +        * descriptor. Not sure if that might not be the case.
>> +        */
>>
>> Would you mind explaining that a bit more for me?  I don't understand exactly what
>> you mean here, but it sounds like the sort of thing that needs to be clarified/fixed
>> before it can be committed.  Am I misunderstanding this?
>>
>
> The call right after that comment is
>
>    items = build_sorted_items(numrows, rows, stats[0]->tupDesc,
>                               mss, k, attnums_dep);
>
> That method processes an array of tuples, and the structure is defined
> by "tuple descriptor" (essentially a list of attribute info - data type,
> length, ...). We get that from stats[0] and assume all the entries point
> to the same tuple descriptor. That's generally safe assumption, I think,
> because all the stats entries relate to columns from the same table.

Right, I got that, and tried mocking up some code to test that in an Assert.
I did not pursue that far enough to reach any conclusion, however.  You
seem to be indicating in the comment some uncertainty about whether the
assumption is safe.  Do we need to dig into that further?

>>
>> In src/backend/statistics/mcv.c, you have comments:
>>
>> + * FIXME: Single-dimensional MCV is sorted by frequency (descending). We
>> + * should do that too, because when walking through the list we want to
>> + * check the most frequent items first.
>> + *
>> + * TODO: We're using Datum (8B), even for data types (e.g. int4 or float4).
>> + * Maybe we could save some space here, but the bytea compression should
>> + * handle it just fine.
>> + *
>> + * TODO: This probably should not use the ndistinct directly (as computed from
>> + * the table, but rather estimate the number of distinct values in the
>> + * table), no?
>>
>> Do you intend these to be fixed/implemented prior to committing this patch?
>>
>
> Actually, the first FIXME is obsolete, as build_distinct_groups returns
> the groups sorted by frequency. I'll remove that.

Ok, good.  That's the one I understood least.

> I think the rest is more a subject for discussion, so I'd need to hear
> some feedback.

In terms of storage efficiency, you are using float8 for the frequency, which is consistent
with what other stats work uses, but may be overkill.  A float4 seems sufficient to me.
The extra four bytes for a float8 may be pretty small compared to the size of the arrays
being stored, so I'm not sure it matters.  Also, this might have been discussed before,
and I am not asking for a reversal of decisions the members of this mailing list may
already have reached.

As for using arrays of something smaller than Datum, you'd need some logic to specify
what the size is in each instance, and that probably complicates the code rather a lot.
Maybe someone else has a technique for doing that cleanly?

>>
>> Further down in function statext_mcv_build, you have two loops, the first allocating
>> memory and the second initializing the memory.  There is no clear reason why this
>> must be done in two loops.  I tried combining the two loops into one, and it worked
>> just fine, but did not look any cleaner to me.  Feel free to disregard this paragraph
>> if you like it better the way you currently have it organized.
>>
>
> I did it this way because of readability. I don't think this is a major
> efficiency issue, as the maximum number of items is fairly limited, and
> it happens only once at the end of the MCV list build (and the sorts and
> comparisons are likely much more CPU expensive).

I defer to your judgement here.  It seems fine the way you did it.

>> Further down in statext_mcv_deserialize, you have some elogs which might need to be
>> ereports.  It is unclear to me whether you consider these deserialize error cases to be
>> "can't happen" type errors.  If so, you might add that fact to the comments rather than
>> changing the elogs to ereports.
>>
>
> I might be missing something, but why would ereport be more appropriate
> than elog? Ultimately, there's not much difference between elog(ERROR)
> and ereport(ERROR) - both will cause a failure.

I understand project policy to allow elog for error conditions that will be reported
in "can't happen" type situations, similar to how an Assert would be used.  For
conditions that can happen through (mis)use by the user, ereport is appropriate.
Not knowing whether you thought these elogs were reporting conditions that a
user could cause, I did not know if you should change them to ereports, or if you
should just add a brief comment along the lines of /* should not be possible */.

I may misunderstand project policy.  If so, I'd gratefully accept correction on this
matter.


mark


Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4


On 11/26/2017 02:17 AM, Mark Dilger wrote:

>
>> On Nov 25, 2017, at 3:33 PM, Tomas Vondra <[hidden email]> wrote:
>>
>>
>>
>> On 11/25/2017 10:01 PM, Mark Dilger wrote:
>>>
>>>> On Nov 18, 2017, at 12:28 PM, Tomas Vondra <[hidden email]> wrote:
>>>>
>>>> Hi,
>>>>
>>>> Attached is an updated version of the patch, adopting the psql describe
>>>> changes introduced by 471d55859c11b.
>>>
>>> Hi Tomas,
>>>
>>> In src/backend/statistics/dependencies.c, you have introduced a comment:
>>>
>>> +       /*
>>> +        * build an array of SortItem(s) sorted using the multi-sort support
>>> +        *
>>> +        * XXX This relies on all stats entries pointing to the same tuple
>>> +        * descriptor. Not sure if that might not be the case.
>>> +        */
>>>
>>> Would you mind explaining that a bit more for me?  I don't understand exactly what
>>> you mean here, but it sounds like the sort of thing that needs to be clarified/fixed
>>> before it can be committed.  Am I misunderstanding this?
>>>
>>
>> The call right after that comment is
>>
>>    items = build_sorted_items(numrows, rows, stats[0]->tupDesc,
>>                               mss, k, attnums_dep);
>>
>> That method processes an array of tuples, and the structure is defined
>> by "tuple descriptor" (essentially a list of attribute info - data type,
>> length, ...). We get that from stats[0] and assume all the entries point
>> to the same tuple descriptor. That's generally safe assumption, I think,
>> because all the stats entries relate to columns from the same table.
>
> Right, I got that, and tried mocking up some code to test that in an Assert.
> I did not pursue that far enough to reach any conclusion, however.  You
> seem to be indicating in the comment some uncertainty about whether the
> assumption is safe.  Do we need to dig into that further?
>

I don't think it's worth the effort, really. I don't think we can really
get mismatching tuple descriptors here - that could only happen with
columns coming from different tables, or something similarly obscure.

>>>
>>> In src/backend/statistics/mcv.c, you have comments:
>>>
>>> + * FIXME: Single-dimensional MCV is sorted by frequency (descending). We
>>> + * should do that too, because when walking through the list we want to
>>> + * check the most frequent items first.
>>> + *
>>> + * TODO: We're using Datum (8B), even for data types (e.g. int4 or float4).
>>> + * Maybe we could save some space here, but the bytea compression should
>>> + * handle it just fine.
>>> + *
>>> + * TODO: This probably should not use the ndistinct directly (as computed from
>>> + * the table, but rather estimate the number of distinct values in the
>>> + * table), no?
>>>
>>> Do you intend these to be fixed/implemented prior to committing this patch?
>>>
>>
>> Actually, the first FIXME is obsolete, as build_distinct_groups returns
>> the groups sorted by frequency. I'll remove that.
>
> Ok, good.  That's the one I understood least.
>
>> I think the rest is more a subject for discussion, so I'd need to hear
>> some feedback.
>
> In terms of storage efficiency, you are using float8 for the frequency, which is consistent
> with what other stats work uses, but may be overkill.  A float4 seems sufficient to me.
> The extra four bytes for a float8 may be pretty small compared to the size of the arrays
> being stored, so I'm not sure it matters.  Also, this might have been discussed before,
> and I am not asking for a reversal of decisions the members of this mailing list may
> already have reached.
>
> As for using arrays of something smaller than Datum, you'd need some logic to specify
> what the size is in each instance, and that probably complicates the code rather a lot.
> Maybe someone else has a technique for doing that cleanly?
>

Note that this is not about storage efficiency. The comment is before
statext_mcv_build, so it's actually related to in-memory representation.
If you look into statext_mcv_serialize, it does use typlen to only copy
the number of bytes needed for each column.

>>>
>>> Further down in function statext_mcv_build, you have two loops, the first allocating
>>> memory and the second initializing the memory.  There is no clear reason why this
>>> must be done in two loops.  I tried combining the two loops into one, and it worked
>>> just fine, but did not look any cleaner to me.  Feel free to disregard this paragraph
>>> if you like it better the way you currently have it organized.
>>>
>>
>> I did it this way because of readability. I don't think this is a major
>> efficiency issue, as the maximum number of items is fairly limited, and
>> it happens only once at the end of the MCV list build (and the sorts and
>> comparisons are likely much more CPU expensive).
>
> I defer to your judgement here.  It seems fine the way you did it.
>
>>> Further down in statext_mcv_deserialize, you have some elogs which might need to be
>>> ereports.  It is unclear to me whether you consider these deserialize error cases to be
>>> "can't happen" type errors.  If so, you might add that fact to the comments rather than
>>> changing the elogs to ereports.
>>>
>>
>> I might be missing something, but why would ereport be more appropriate
>> than elog? Ultimately, there's not much difference between elog(ERROR)
>> and ereport(ERROR) - both will cause a failure.
>
> I understand project policy to allow elog for error conditions that will be reported
> in "can't happen" type situations, similar to how an Assert would be used.  For
> conditions that can happen through (mis)use by the user, ereport is appropriate.
> Not knowing whether you thought these elogs were reporting conditions that a
> user could cause, I did not know if you should change them to ereports, or if you
> should just add a brief comment along the lines of /* should not be possible */.
>
> I may misunderstand project policy.  If so, I'd gratefully accept correction on this
> matter.
>

I don't know - I always considered "elog" old interface, and "ereport"
is the new one. In any case, those are "should not happen" cases. It
would mean some sort of data corruption, or so.

regards

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

Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tom Lane-2
In reply to this post by Mark Dilger-4
Mark Dilger <[hidden email]> writes:
>> On Nov 25, 2017, at 3:33 PM, Tomas Vondra <[hidden email]> wrote:
>> I might be missing something, but why would ereport be more appropriate
>> than elog? Ultimately, there's not much difference between elog(ERROR)
>> and ereport(ERROR) - both will cause a failure.

The core technical differences are (1) an ereport message is exposed for
translation, normally, while an elog is not; and (2) with ereport you can
set the errcode, whereas with elog it's always going to be XX000
(ERRCODE_INTERNAL_ERROR).

> I understand project policy to allow elog for error conditions that will be reported
> in "can't happen" type situations, similar to how an Assert would be used.  For
> conditions that can happen through (mis)use by the user, ereport is appropriate.

The project policy about this is basically that elog should only be used
for things that are legitimately "internal errors", ie not user-facing.
If there's a deterministic way for a user to trigger the error, or if
it can reasonably be expected to occur during normal operation, it should
definitely have an ereport (and a non-default errcode).

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Álvaro Herrera
In reply to this post by Mark Dilger-4
Mark Dilger wrote:


> I understand project policy to allow elog for error conditions that will be reported
> in "can't happen" type situations, similar to how an Assert would be used.  For
> conditions that can happen through (mis)use by the user, ereport is appropriate.
> Not knowing whether you thought these elogs were reporting conditions that a
> user could cause, I did not know if you should change them to ereports, or if you
> should just add a brief comment along the lines of /* should not be possible */.

Two things dictate that policy:

1. messages are translated by default for ereport but not for elog.
Both things can be overridden, but we tend not to do it unless there's
no choice.

2. you can assign SQLSTATE only with ereport.

--
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Reply | Threaded
Open this post in threaded view
|

Re: PATCH: multivariate histograms and MCV lists

Tomas Vondra-4
In reply to this post by Tomas Vondra-4
Hi,

Attached is an updated version of the patch series, fixing the issues
reported by Mark Dilger:

1) Fix fabs() issue in histogram.c.

2) Do not rely on extra_data being StdAnalyzeData, and instead lookup
the LT operator explicitly. This also adds a simple regression tests to
make sure ANALYZE on arrays works fine, but perhaps we should invent
some simple queries too.

3) I've removed / clarified some of the comments mentioned by Mark.

4) I haven't changed how the statistics kinds are defined in relation.h,
but I agree there should be a comment explaining how STATS_EXT_INFO_*
relate to StatisticExtInfo.kinds.

5) The most significant change happened histograms. There used to be two
structures for histograms:

  - MVHistogram - expanded (no deduplication etc.), result of histogram
    build and never used for estimation

  - MVSerializedHistogram - deduplicated to save space, produced from
    MVHistogram before storing in pg_statistic_ext and never used for
    estimation

So there wasn't really any reason to expose the "non-serialized" version
outside histogram.c. It was just confusing and unnecessary, so I've
moved MVHistogram to histogram.c (and renamed it to MVHistogramBuild),
and renamed MVSerializedHistogram. And same for the MVBucket stuff.

So now we only deal with MVHistogram everywhere, except in histogram.c.

6) I've also made MVHistogram to include a varlena header directly (and
be packed as a bytea), which allows us to store it without having to
call any serialization functions).

I guess if we should do (5) and (6) for the MCV lists too, it seems more
convenient than the current approach. And perhaps even for the
statistics added to 9.6 (it does not change the storage format).


regards

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

0001-multivariate-MCV-lists.patch.gz (43K) Download Attachment
0002-multivariate-histograms.patch.gz (82K) Download Attachment
1234 ... 6