On 1/19/21 9:44 PM, John Naylor wrote:
On Tue, Jan 12, 2021 at 1:42 PM Tomas Vondra
<tomas.von...@enterprisedb.com <mailto:tomas.von...@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
