From: Tomas Vondra <tomas.vondra@enterprisedb.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: WIP: BRIN multi-range indexes
Date: Wed, 20 Jan 2021 01:07:00 +0100
Message-ID: <c970fcb3-b483-1578-b33f-d61ebc56a948@enterprisedb.com> (raw)
In-Reply-To: <CAFBsxsEOX8JztU3-DWu95rVdfzcOdxn_9LyyJqGxBRS+agcuXQ@mail.gmail.com>
References: <c1138ead-7668-f0e1-0638-c3be3237e812@2ndquadrant.com>
<20201001222127.GA24173@alvherre.pgsql>
<160434032777.4948.12542847889193566385.pgcf@coridan.postgresql.org>
<20201102232545.zw4xir577gq55ogj@development>
<88b3831d-8afa-4135-a420-27b12bf9fae4@enterprisedb.com>
<CAFBsxsFwLTg3qfs6RcoQouGDh54GUZLr7+BEXfo86qYPuNaZjA@mail.gmail.com>
<1fdcbd2a-ff0f-fb81-d227-22279d5cbcb7@enterprisedb.com>
<CAFBsxsF0spTU=NMBNER4KwJ5NLmkoU7ModUg7g8HAqZ9k+7OgA@mail.gmail.com>
<061b24c0-87eb-51a7-17d6-e1ba8c59fd23@enterprisedb.com>
<CAFBsxsE05b=iYEFm9Aw--vodne80DSqbzYfUYLy0FYQWOJRmTw@mail.gmail.com>
<8a40b7e4-357e-b0c2-e8b7-72001993fc32@enterprisedb.com>
<CAFBsxsEOX8JztU3-DWu95rVdfzcOdxn_9LyyJqGxBRS+agcuXQ@mail.gmail.com>
On 1/19/21 9:44 PM, John Naylor wrote:
> On Tue, Jan 12, 2021 at 1:42 PM Tomas Vondra
> <tomas.vondra@enterprisedb.com <mailto:tomas.vondra@enterprisedb.com>>
> wrote:
> > I suspect it'd due to minmax having to decide which "ranges" to merge,
> > which requires repeated sorting, etc. I certainly don't dare to claim
> > the current algorithm is perfect. I wouldn't have expected such big
> > difference, though - so definitely worth investigating.
>
> It seems that monotonically increasing (or decreasing) values in a table
> are a worst case scenario for multi-minmax indexes, or basically, unique
> values within a range. I'm guessing it's because it requires many passes
> to fit all the values into a limited number of ranges. I tried using
> smaller pages_per_range numbers, 32 and 8, and that didn't help.
>
> Now, with a different data distribution, using only 10 values that
> repeat over and over, the results are muchs more sympathetic to multi-minmax:
>
> insert into iot (num, create_dt)
> select random(), '2020-01-01 0:00'::timestamptz + (x % 10 || '
> seconds')::interval
> from generate_series(1,5*365*24*60*60) x;
>
> create index cd_single on iot using brin(create_dt);
> 27.2s
>
> create index cd_multi on iot using brin(create_dt
> timestamptz_minmax_multi_ops);
> 30.4s
>
> create index cd_bt on iot using btree(create_dt);
> 61.8s
>
> Circling back to the monotonic case, I tried running a simple perf
> record on a backend creating a multi-minmax index on a timestamptz
> column and these were the highest non-kernel calls:
> + 21.98% 21.91% postgres postgres [.]
> FunctionCall2Coll
> + 9.31% 9.29% postgres postgres [.]
> compare_combine_ranges
> + 8.60% 8.58% postgres postgres [.] qsort_arg
> + 5.68% 5.66% postgres postgres [.]
> brin_minmax_multi_add_value
> + 5.63% 5.60% postgres postgres [.] timestamp_lt
> + 4.73% 4.71% postgres postgres [.]
> reduce_combine_ranges
> + 3.80% 0.00% postgres [unknown] [.]
> 0x0320016800040000
> + 3.51% 3.50% postgres postgres [.] timestamp_eq
>
> There's no one place that's pathological enough to explain the 4x
> slowness over traditional BRIN and nearly 3x slowness over btree when
> using a large number of unique values per range, so making progress here
> would have to involve a more holistic approach.
>
Yeah. This very much seems like the primary problem is in how we build
the ranges incrementally - with monotonic sequences, we end up having to
merge the ranges over and over again. I don't know what was the
structure of the table, but I guess it was kinda narrow (very few
columns), which exacerbates the problem further, because the number of
rows per range will be way higher than in real-world.
I do think the solution to this might be to allow more values during
batch index creation, and only "compress" to the requested number at the
very end (when serializing to on-disk format).
There are a couple additional comments about possibly replacing
sequential scan with a binary search, that could help a bit too.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
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: pgsql-hackers@postgresql.org
Cc: tomas.vondra@enterprisedb.com, john.naylor@enterprisedb.com, pgsql-hackers@lists.postgresql.org
Subject: Re: WIP: BRIN multi-range indexes
In-Reply-To: <c970fcb3-b483-1578-b33f-d61ebc56a948@enterprisedb.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox