MIME-Version: 1.0
References: <CAN_hQmsYDhPMK4bSJHPw3RGnpKqPbx2Uk_7HRV+Dz9F5H7dj1A@mail.gmail.com>
 <6e92450c-8136-11d4-8f6e-501c693af5c8@enterprisedb.com> <e665a0c8-4a5c-4345-2234-4487138a0d6f@enterprisedb.com>
 <CAN_hQmvOzA0CRjjDzyoOh_LZwHeQQNnZTK=whF4sKh7DRWnQjQ@mail.gmail.com>
 <d091b383-8589-4970-83f4-93169a525df4@enterprisedb.com> <CAN_hQmsNMK-8R2ier9prLXvJpTQ3bdke5D0KhP+QSY07giobeA@mail.gmail.com>
 <61d1e6b0-914e-4aa3-8a32-ff2cf9e91100@enterprisedb.com>
In-Reply-To: <61d1e6b0-914e-4aa3-8a32-ff2cf9e91100@enterprisedb.com>
From: Alexander Cheshev <alex.cheshev@gmail.com>
Date: Mon, 8 Jan 2024 00:49:11 +0100
Message-ID: <CAN_hQmv5ZK_TDsOkRU6Zy5Wn0GjqUkDNAQaNEor5Fs+T1raeVw@mail.gmail.com>
Subject: Re: Multidimensional Histograms
To: Tomas Vondra <tomas.vondra@enterprisedb.com>
Cc: pgsql-hackers@postgresql.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://www.postgresql.org/message-id/CAN_hQmv5ZK_TDsOkRU6Zy5Wn0GjqUkDNAQaNEor5Fs%2BT1raeVw%40mail.gmail.com>
Precedence: bulk

Hi Tomas,

> See section 3.2 in this paper (the "view PDF" does not work for me, but
> the "source PDF" does download a postscript):

I believe that you are referring to a dynamic programming approach. It
is a 1-dimensional case! To find an optimal solution in the
M-dimensional case is an NP-hard problem.

Regards,
Alexander Cheshev

On Mon, 8 Jan 2024 at 00:29, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:
>
>
>
> On 1/7/24 23:53, Alexander Cheshev wrote:
> > Hi Tomas,
> >
> >> The thing I was proposing is that it should be possible to build
> >> histograms with bins adapted to density in the given region. With
> >> smaller buckets in areas with high density. So that queries intersect
> >> with fewer buckets in low-density parts of the histogram.
> >
> > This is how Equi-Depth Histogram works. Postgres has maller buckets in
> > areas with high density:
> >
> > values[(i * (nvals - 1)) / (num_hist - 1)]
> >
> True, but the boundaries are somewhat random. Also, I was referring to
> the multi-dimensional case, it wasn't clear to me if the proposal is to
> do the same thing.
>
> >> I don't recall the details of the MHIST-2 scheme, but it's true
> >> calculating "perfect" V-optimal histogram would be quadratic O(N^2*B).
> >
> > In M-dimensional space "perfect" V-Optimal Histogram is an NP-hard
> > problem. In other words it is not possible to build it in polynomial
> > time. How did you come up with the estimate?!
> >
> See section 3.2 in this paper (the "view PDF" does not work for me, but
> the "source PDF" does download a postscript):
>
> https://citeseerx.ist.psu.edu/doc_view/pid/35e29cbc2bfe6662653bdae1fb89c091e2ece560
>
> >> But that's exactly why greedy/approximate algorithms exist. Yes, it's
> >> not going to produce the optimal V-optimal histogram, but so what?
> >
> > Greedy/approximate algorithm has time complexity O(M*N*B), where M
> > equals the number of dimensions. MHIST-2 is a greedy/approximate
> > algorithm.
> >
> >> And how does this compare to the approximate/greedy algorithms, both in
> >> terms of construction time and accuracy?
> >
> > Time complexity of Equi-Depth Histogram has no dependence on B.
> >
> Really? I'd expect that to build B buckets, the algorithm repeat some
> O(M*N) action B-times, roughly. I mean, it needs to pick a dimension by
> which to split, then do some calculation on the N tuples, etc.
>
> Maybe I'm imagining that wrong, though. It's been ages since I looked ad
> big-O complexity and/or the histograms. I'd have to play with those
> algorithms for a bit again.
>
>
> regards
>
> --
> Tomas Vondra
> EnterpriseDB: http://www.enterprisedb.com
> The Enterprise PostgreSQL Company