public inbox for [email protected]  

help / color / mirror / Atom feed

From: Andrei Lepikhov <[email protected]>
To: Alexander Cheshev <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: [email protected]
Cc: Teodor Sigaev <[email protected]>
Subject: Re: Multidimensional Histograms
Date: Wed, 10 Jan 2024 22:49:48 +0700
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAN_hQms_KKKGqyhUopk6t=cDgti5p3UWx9ruKXHsTERoXRs2-w@mail.gmail.com>
References: <CAN_hQmsYDhPMK4bSJHPw3RGnpKqPbx2Uk_7HRV+Dz9F5H7dj1A@mail.gmail.com>
	<[email protected]>
	<[email protected]>
	<CAN_hQmvOzA0CRjjDzyoOh_LZwHeQQNnZTK=whF4sKh7DRWnQjQ@mail.gmail.com>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<CAN_hQms_KKKGqyhUopk6t=cDgti5p3UWx9ruKXHsTERoXRs2-w@mail.gmail.com>

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

view thread (17+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected], [email protected]
  Subject: Re: Multidimensional Histograms
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox