pgsql: BRIN minmax-multi indexes

BRIN minmax-multi indexes

Adds BRIN opclasses similar to the existing minmax, except that instead
of summarizing the page range into a single [min,max] range, the summary
consists of multiple ranges and/or points, allowing gaps. This allows
more efficient handling of data with poor correlation to physical
location within the table and/or outlier values, for which the regular
minmax opclassed tend to work poorly.

It's possible to specify the number of values kept for each page range,
either as a single point or an interval boundary.

CREATE TABLE t (a int);
CREATE INDEX ON t
USING brin (a int4_minmax_multi_ops(values_per_range=16));

When building the summary, the values are combined into intervals with
the goal to minimize the "covering" (sum of interval lengths), using a
support procedure computing distance between two values.

Bump catversion, due to various catalog changes.

Author: Tomas Vondra <tomas(dot)vondra(at)postgresql(dot)org>
Reviewed-by: Alvaro Herrera <alvherre(at)alvh(dot)no-ip(dot)org>
Reviewed-by: Alexander Korotkov <aekorotkov(at)gmail(dot)com>
Reviewed-by: Sokolov Yura <y(dot)sokolov(at)postgrespro(dot)ru>
Reviewed-by: John Naylor <john(dot)naylor(at)enterprisedb(dot)com>
Discussion: https://postgr.es/m/c1138ead-7668-f0e1-0638-c3be3237e812@2ndquadrant.com
Discussion: https://postgr.es/m/5d78b774-7e9c-c94e-12cf-fef51cc89b1a%402ndquadrant.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/ab596105b55f1d7fbd5a66b66f65227d210b047d

Modified Files
--------------
doc/src/sgml/brin.sgml | 280 ++-
src/backend/access/brin/Makefile | 1 +
src/backend/access/brin/brin_minmax_multi.c | 3036 +++++++++++++++++++++++++++
src/backend/access/brin/brin_tuple.c | 17 +
src/include/access/brin_tuple.h | 8 +
src/include/access/transam.h | 10 +-
src/include/catalog/catversion.h | 2 +-
src/include/catalog/pg_amop.dat | 544 +++++
src/include/catalog/pg_amproc.dat | 362 ++++
src/include/catalog/pg_opclass.dat | 57 +
src/include/catalog/pg_opfamily.dat | 28 +
src/include/catalog/pg_proc.dat | 85 +
src/include/catalog/pg_type.dat | 6 +
src/test/regress/expected/brin_multi.out | 450 ++++
src/test/regress/expected/psql.out | 13 +-
src/test/regress/expected/type_sanity.out | 7 +-
src/test/regress/parallel_schedule | 2 +-
src/test/regress/serial_schedule | 1 +
src/test/regress/sql/brin_multi.sql | 403 ++++
19 files changed, 5286 insertions(+), 26 deletions(-)