Re: Multidimensional Histograms

On 8/1/2024 16:21, Alexander Cheshev wrote:
> Hi Andrei,
>
>> Maybe my wording needed to be more precise. I didn't implement
>> multidimensional histograms before, so I don't know how expensive they
>> are. I meant that for dependency statistics over about six columns, we
>> have a lot of combinations to compute.
>
> Equi-Depth Histogram in a 6 dimensional case requires 6 times more
> iterations. Postgres already uses Equi-Depth Histogram. Even if you
> increase the number of buckets from 100 to 1000 then there will be no
> overhead as the time complexity of Equi-Depth Histogram has no
> dependence on the number of buckets. So, no overhead at all!

Maybe. For three columns, we have 9 combinations (passes) for building
dependency statistics and 4 combinations for ndistincts; for six
columns, we have 186 and 57 combinations correspondingly.
Even remembering that dependency is just one number for one combination,
building the dependency statistics is still massive work. So, in the
multicolumn case, having something like a histogram may be more effective.

--
regards,
Andrei Lepikhov
Postgres Professional