Subject: Re: Merging statistics from children instead of re-sampling everything

From: Andrey Lepikhov <[email-masked]>
Date: Thu, 10 Feb 2022 16:50:31 +0500

On 21/1/2022 01:25, Tomas Vondra wrote:
> But I don't have a very good idea what to do about statistics that we
> can't really merge. For some types of statistics it's rather tricky to
> reasonably merge the results - ndistinct is a simple example, although
> we could work around that by building and merging hyperloglog counters.
I think, as a first step on this way we can reduce a number of pulled 
tuples. We don't really needed to pull all tuples from a remote server. 
To construct a reservoir, we can pull only a tuple sample. Reservoir 
method needs only a few arguments to return a sample like you read 
tuples locally. Also, to get such parts of samples asynchronously, we 
can get size of each partition on a preliminary step of analysis.
In my opinion, even this solution can reduce heaviness of a problem 
drastically.

-- 
regards,
Andrey Lepikhov
Postgres Professional

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 10 Feb 2022 23:37:26 +0100

> In my opinion, even this solution can reduce heaviness of a problem

Oh, wow! I haven't realized we're fetching all the rows from foreign
(postgres_fdw) partitions. For local partitions we already do that,
because that uses the usual acquire function, with a reservoir
proportional to partition size. I have assumed we use tablesample to
fetch just a small fraction of rows from FDW partitions, and I agree
doing that would be a pretty huge benefit.

I actually tried hacking that together - there's a couple problems with
that (e.g. determining what fraction to sample using bernoulli/system),
but in principle it seems quite doable. Some minor changes to the FDW
API may be necessary, not sure.

Not sure about the async execution - that seems way more complicated,
and the sampling reduces the total cost, async just parallelizes it.

That being said, this thread was not really about foreign partitions,
but about re-analyzing inheritance trees in general. And sampling
foreign partitions doesn't really solve that - we'll still do the
sampling over and over.

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: "Andrey V. Lepikhov" <[email-masked]>
Date: Fri, 11 Feb 2022 09:29:38 +0500

> foreign partitions doesn't really solve that - we'll still do the
IMO, to solve the problem we should do two things:
1. Avoid repeatable partition scans in the case inheritance tree.
2. Avoid to re-analyze everything in the case of active changes in small 
subset of partitions.

For (1) i can imagine a solution like multiplexing: on the stage of 
defining which relations to scan, group them and prepare parameters of 
scanning to make multiple samples in one shot.
It looks like we need a separate logic for analysis of partitioned 
tables - we should form and cache samples on each partition before an 
analysis.
It requires a prototype to understand complexity of such solution and 
can be done separately from (2).

Task (2) is more difficult to solve. Here we can store samples from each 
partition in values[] field of pg_statistic or in specific table which 
stores a 'most probable values' snapshot of each table.
Most difficult problem here, as you mentioned, is ndistinct value. Is it 
possible to store not exactly calculated value of ndistinct, but an 
'expected value', based on analysis of samples and histograms on 
partitions? Such value can solve also a problem of estimation of a SETOP 
result grouping (joining of them, etc), where we have statistics only on 
sources of the union.

-- 
regards,
Andrey Lepikhov
Postgres Professional

---

From: Tomas Vondra <[email-masked]>
Date: Fri, 11 Feb 2022 16:12:16 +0100

> can be done separately from (2).

I'm not sure I understand what you mean by multiplexing. The term 
usually means "sending multiple signals at once" but I'm not sure how 
that applies to this issue. Can you elaborate?

I assume you mean something like collecting a sample for a partition 
once, and then keeping and reusing the sample for future ANALYZE runs, 
until invalidated in some sense.

Yeah, I agree that'd be useful - and not just for partitions, actually. 
I've been pondering something like that for regular tables, because the 
sample might be used for estimation of clauses directly.

But it requires storing the sample somewhere, and I haven't found a good 
and simple way to do that. We could serialize that into bytea, or we 
could create a new fork, or something, but what should that do with 
oversized attributes (how would TOAST work for a fork) and/or large 
samples (which might not fit into 1GB bytea)?

> stores a 'most probable values' snapshot of each table.

I think storing samples in pg_statistic is problematic, because values[] 
is subject to 1GB limit etc. Not an issue for small MCV list of a single 
attribute, certainly an issue for larger samples. Even if the data fit, 
the size of pg_statistic would explode.

> result grouping (joining of them, etc), where we have statistics only on 

I think ndistinct is problem only when merging final estimates. But if 
we're able to calculate and store some intermediate results, we can 
easily use HLL and merge that.

regards

---

From: "Andrey V. Lepikhov" <[email-masked]>
Date: Mon, 14 Feb 2022 15:22:30 +0500

On 2/11/22 20:12, Tomas Vondra wrote:
>> 2. Avoid to re-analyze everything in the case of active changes in 
>> small subset of partitions.
>>

I suppose to make a set of samples in one scan: one sample for plane 
table, another - for a parent and so on, according to the inheritance 
tree. And cache these samples in memory. We can calculate all parameters 
of reservoir method to do it.

> sample might be used for estimation of clauses directly.
You mean, to use them in difficult cases, such of estimation of grouping 
over APPEND ?
> samples (which might not fit into 1GB bytea)? 
This feature looks like meta-info over a database. It can be stored in 
separate relation. It is not obvious that we need to use it for each 
relation, for example, with large samples. I think, it can be controlled 
by a table parameter.

-- 
regards,
Andrey Lepikhov
Postgres Professional