Re: BRIN indexes - TRAP: BadArgument

Alvaro Herrera wrote:

Heikki Linnakangas wrote:

If you add a new datatype, and define b-tree operators for it, what
is required to create a minmax opclass for it? Would it be possible
to generalize the functions in brin_minmax.c so that they can be
reused for any datatype (with b-tree operators) without writing any
new C code? I think we're almost there; the only thing that differs
between each data type is the opcinfo function. Let's pass the type
OID as argument to the opcinfo function. You could then have just a
single minmax_opcinfo function, instead of the macro to generate a
separate function for each built-in datatype.

Yeah, that's how I had that initially. I changed it to what it's now as
part of a plan to enable building cross-type opclasses, so you could
have "WHERE int8col=42" without requiring a cast of the constant to type
int8. This might have been a thinko, because AFAICS it's possible to
build them with a constant opcinfo as well (I changed several other
things to support this, as described in a previous email.) I will look
into this later.

I found out that we don't really throw errors in such cases anymore; we
insert casts instead. Maybe there's a performance argument that it
might be better to use existing cross-type operators than casting, but
justifying this work just turned a lot harder. Here's a patch that
reverts opcinfo into a generic function that receives the type OID.

I will look into adding some testing mechanism for the union support
proc; with that I will just consider the patch ready for commit and will
push.

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Sep 23, 2014 at 3:04 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Alvaro Herrera wrote:

Heikki Linnakangas wrote:

If you add a new datatype, and define b-tree operators for it, what
is required to create a minmax opclass for it? Would it be possible
to generalize the functions in brin_minmax.c so that they can be
reused for any datatype (with b-tree operators) without writing any
new C code? I think we're almost there; the only thing that differs
between each data type is the opcinfo function. Let's pass the type
OID as argument to the opcinfo function. You could then have just a
single minmax_opcinfo function, instead of the macro to generate a
separate function for each built-in datatype.

Yeah, that's how I had that initially. I changed it to what it's now as
part of a plan to enable building cross-type opclasses, so you could
have "WHERE int8col=42" without requiring a cast of the constant to type
int8. This might have been a thinko, because AFAICS it's possible to
build them with a constant opcinfo as well (I changed several other
things to support this, as described in a previous email.) I will look
into this later.

I found out that we don't really throw errors in such cases anymore; we
insert casts instead. Maybe there's a performance argument that it
might be better to use existing cross-type operators than casting, but
justifying this work just turned a lot harder. Here's a patch that
reverts opcinfo into a generic function that receives the type OID.

I will look into adding some testing mechanism for the union support
proc; with that I will just consider the patch ready for commit and will
push.

With all respect, I think this is a bad idea. I know you've put a lot
of energy into this patch and I'm confident it's made a lot of
progress. But as with Stephen's patch, the final form deserves a
thorough round of looking over by someone else before it goes in.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Sep 24, 2014 at 8:23 AM, Robert Haas <robertmhaas@gmail.com> wrote:

On Tue, Sep 23, 2014 at 3:04 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Alvaro Herrera wrote:
I will look into adding some testing mechanism for the union support
proc; with that I will just consider the patch ready for commit and will
push.

With all respect, I think this is a bad idea. I know you've put a lot
of energy into this patch and I'm confident it's made a lot of
progress. But as with Stephen's patch, the final form deserves a
thorough round of looking over by someone else before it goes in.

Would this person be it an extra committer or an simple reviewer? It
would give more insurance if such huge patches (couple of thousands of
lines) get an extra +1 from another committer, proving that the code
has been reviewed by people well-experienced with backend code. Now as
this would put more pressure in the hands of committers, an extra
external pair of eyes, be it non-committer but let's say a seasoned
reviewer would be fine IMO.
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas wrote:

With all respect, I think this is a bad idea. I know you've put a lot
of energy into this patch and I'm confident it's made a lot of
progress. But as with Stephen's patch, the final form deserves a
thorough round of looking over by someone else before it goes in.

As you can see in the thread, Heikki's put a lot of review effort into
it (including important code contributions); I don't feel I'm rushing it
at this point. If you or somebody else want to give it a look, I have
no problem waiting a bit longer. I don't want to delay indefinitely,
though, because I think it's better shipped early in the release cycle
than later, to allow for further refinements and easier testing by other
interested parties.

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 23, 2014 at 7:35 PM, Michael Paquier
<michael.paquier@gmail.com> wrote:

Would this person be it an extra committer or an simple reviewer? It
would give more insurance if such huge patches (couple of thousands of
lines) get an extra +1 from another committer, proving that the code
has been reviewed by people well-experienced with backend code. Now as
this would put more pressure in the hands of committers, an extra
external pair of eyes, be it non-committer but let's say a seasoned
reviewer would be fine IMO.

If you're volunteering, I certainly wouldn't say "no". The more the
merrier. Same with anyone else. Since Heikki looked at it before, I
also think it would be appropriate to give him a bit of time to see if
he feels satisfied with it now - nobody on this project has more
experience with indexing than he does, but he may not have the time,
and even if he does, someone else might spot something he misses.

Alvaro's quite right to point out that there is no sense in waiting a
long time for a review that isn't coming. That just backs everything
up against the end of the release cycle to no benefit. But if there's
review available from experienced people within the community, taking
advantage of that now might find things that could be much harder to
fix later. That's a win for everybody. And it's not like we're
pressed up against the end of the cycle, nor is it as if this feature
has been through endless rounds of review already. It's certainly had
some, and it's gotten better as a result. But it's also changed a lot
in the process.

And much of the review to date has been high-level design review, like
"how should the opclasses look?" and "what should we call this thing
anyway?". Going through it for logic errors, documentation
shortcomings, silly thinkos, etc. has not been done too much, I think,
and definitely not on the latest version. So, some of that might not
be out of place.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 23, 2014 at 9:23 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Robert Haas wrote:

With all respect, I think this is a bad idea. I know you've put a lot
of energy into this patch and I'm confident it's made a lot of
progress. But as with Stephen's patch, the final form deserves a
thorough round of looking over by someone else before it goes in.

As you can see in the thread, Heikki's put a lot of review effort into
it (including important code contributions); I don't feel I'm rushing it
at this point.

Yeah, I was really glad Heikki looked at it. That seemed good.

If you or somebody else want to give it a look, I have
no problem waiting a bit longer. I don't want to delay indefinitely,
though, because I think it's better shipped early in the release cycle
than later, to allow for further refinements and easier testing by other
interested parties.

I agree with that. I'd like to look at it, and I will if I get time,
but as I said elsewhere, I also think it's appropriate to give a
little time around the final version of any big, complex patch just
because people may have thoughts, and they may not have time to
deliver those thoughts the minute the patch hits the list.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas wrote:

On Tue, Sep 23, 2014 at 9:23 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

If you or somebody else want to give it a look, I have
no problem waiting a bit longer. I don't want to delay indefinitely,
though, because I think it's better shipped early in the release cycle
than later, to allow for further refinements and easier testing by other
interested parties.

I agree with that. I'd like to look at it, and I will if I get time,
but as I said elsewhere, I also think it's appropriate to give a
little time around the final version of any big, complex patch just
because people may have thoughts, and they may not have time to
deliver those thoughts the minute the patch hits the list.

Fair enough -- I'll keep it open for the time being.

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 09/23/2014 10:04 PM, Alvaro Herrera wrote:

+  <para>
+   The <acronym>BRIN</acronym> implementation in <productname>PostgreSQL</productname>
+   is primarily maintained by &Aacute;lvaro Herrera.
+  </para>

We don't usually have such verbiage in the docs. The GIN and GiST pages
do, but I think those are a historic exceptions, not something we want
to do going forward.

+   <variablelist>
+    <varlistentry>
+     <term><function>BrinOpcInfo *opcInfo(void)</></term>
+     <listitem>
+      <para>
+       Returns internal information about the indexed columns' summary data.
+      </para>
+     </listitem>
+    </varlistentry>

I think you should explain what that internal information is. The
minmax-19a.patch adds the type OID argument to this; remember to update
the docs.

In SP-GiST, the similar function is called "config". It might be good to
use the same name here, for consistency across indexams (although I
actually like the "opcInfo" name better than "config")

The docs for the other support functions need to be updated, now that
you changed the arguments from DeformedBrTuple to BrinValues.

+ <!-- this needs improvement ... -->
+   To implement these methods in a generic ways, normally the opclass
+   defines its own internal support functions.  For instance, minmax
+   opclasses add the support functions for the four inequality operators
+   for the datatype.
+   Additionally, the operator class must supply appropriate
+   operator entries,
+   to enable the optimizer to use the index when those operators are
+   used in queries.

The above needs improvement ;-)

+    BRIN indexes (a shorthand for Block Range indexes)
+    store summaries about the values stored in consecutive table physical block ranges.

"consecutive table physical block ranges" is quite a mouthful.

+    For datatypes that have a linear sort order, the indexed data
+    corresponds to the minimum and maximum values of the
+    values in the column for each block range,
+    which support indexed queries using these operators:
+
+    <simplelist>
+     <member><literal>&lt;</literal></member>
+     <member><literal>&lt;=</literal></member>
+     <member><literal>=</literal></member>
+     <member><literal>&gt;=</literal></member>
+     <member><literal>&gt;</literal></member>
+    </simplelist>

That's the built-in minmax indexing strategy, yes, but you could have
others, even for datatypes with a linear sort order.

+ To find out the index tuple for a particular page range, we have an internal

s/find out/find/

+ new heap tuple contains null values but the index tuple indicate there are no

s/indicate/indicates/

+ Open questions
+ --------------
+
+ * Same-size page ranges?
+   Current related literature seems to consider that each "index entry" in a
+   BRIN index must cover the same number of pages.  There doesn't seem to be a

What is the related literature? Is there an academic paper or something
that should be cited as a reference for BRIN?

+  * TODO
+  *		* ScalarArrayOpExpr (amsearcharray -> SK_SEARCHARRAY)
+  *		* add support for unlogged indexes
+  *		* ditto expressional indexes

We don't have unlogged indexes in general, so no need to list that here.
What would be needed to implement ScalarArrayOpExprs?

I didn't realize that expression indexes are still not supported. And I
see that partial indexes are not supported either. Why not? I wouldn't
expect BRIN to need to care about those things in particular; the
expressions for an expressional or partial index are handled in the
executor, no?

+ /*
+  * A tuple in the heap is being inserted.  To keep a brin index up to date,
+  * we need to obtain the relevant index tuple, compare its stored values with
+  * those of the new tuple; if the tuple values are consistent with the summary
+  * tuple, there's nothing to do; otherwise we need to update the index.

s/compare/and compare/. Perhaps replace one of the semicolons with a
full stop.

+  * If the range is not currently summarized (i.e. the revmap returns InvalidTid
+  * for it), there's nothing to do either.
+  */
+ Datum
+ brininsert(PG_FUNCTION_ARGS)

There is no InvalidTid, as a constant or a #define. Perhaps replace with
"invalid item pointer".

+ 	/*
+ 	 * XXX We need to know the size of the table so that we know how long to
+ 	 * iterate on the revmap.  There's room for improvement here, in that we
+ 	 * could have the revmap tell us when to stop iterating.
+ 	 */

The revmap doesn't know how large the table is. Remember that you have
to return all blocks that are not in the revmap, so you can't just stop
when you reach the end of the revmap. I think the current design is fine.

I have to stop now to do some other stuff. Overall, this is in pretty
good shape. In addition to little cleanup of things I listed above, and
similar stuff elsewhere that I didn't read through right now, there are
a few medium-sized items I'd still like to see addressed before you
commit this:

* expressional/partial index support
* the difficulty of testing the union support function that we discussed
earlier
* clarify the memory context stuff of support functions that we also
discussed earlier

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, September 23, 2014 21:04, Alvaro Herrera wrote:

Alvaro Herrera wrote:

[minmax-19.patch]
[minmax-19a.patch]

Although admittedly it is not directly likely for us to need it, and although I see that there is a BRIN Extensibility
chapter added (good!), I am still a bit surprised by the absence of a built-in BRIN operator class for bigint, as the BRIN
index type is specifically useful for huge tables (where after all huge values are more likely to occur).

Will a brin int8 be added operator class for 9.5? (I know, quite some time left...)

(btw, so far the patch proves quite stable under my abusive testing...)

thanks,

Erik Rijkers

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Heikki Linnakangas wrote:

On 09/23/2014 10:04 PM, Alvaro Herrera wrote:

+  <para>
+   The <acronym>BRIN</acronym> implementation in <productname>PostgreSQL</productname>
+   is primarily maintained by &Aacute;lvaro Herrera.
+  </para>

We don't usually have such verbiage in the docs. The GIN and GiST
pages do, but I think those are a historic exceptions, not something
we want to do going forward.

Removed.

+   <variablelist>
+    <varlistentry>
+     <term><function>BrinOpcInfo *opcInfo(void)</></term>
+     <listitem>
+      <para>
+       Returns internal information about the indexed columns' summary data.
+      </para>
+     </listitem>
+    </varlistentry>

I think you should explain what that internal information is. The
minmax-19a.patch adds the type OID argument to this; remember to
update the docs.

Updated.

In SP-GiST, the similar function is called "config". It might be
good to use the same name here, for consistency across indexams
(although I actually like the "opcInfo" name better than "config")

Well, I'm not sure that there's any value in being consistent if the new
name is better than the old one. Most likely, a person trying to
implement an spgist opclass wouldn't try to do a brin opclass at the
same time, so it's not like there's a lot of value in being consistent
there, anyway.

The docs for the other support functions need to be updated, now
that you changed the arguments from DeformedBrTuple to BrinValues.

Updated.

+ <!-- this needs improvement ... -->
+   To implement these methods in a generic ways, normally the opclass
+   defines its own internal support functions.  For instance, minmax
+   opclasses add the support functions for the four inequality operators
+   for the datatype.
+   Additionally, the operator class must supply appropriate
+   operator entries,
+   to enable the optimizer to use the index when those operators are
+   used in queries.

The above needs improvement ;-)

I rechecked and while I tweaked it here and there, I wasn't able to add
much more to it.

+    BRIN indexes (a shorthand for Block Range indexes)
+    store summaries about the values stored in consecutive table physical block ranges.

"consecutive table physical block ranges" is quite a mouthful.

I reworded this introduction. I hope it makes more sense now.

+    For datatypes that have a linear sort order, the indexed data
+    corresponds to the minimum and maximum values of the
+    values in the column for each block range,
+    which support indexed queries using these operators:
+
+    <simplelist>
+     <member><literal>&lt;</literal></member>
+     <member><literal>&lt;=</literal></member>
+     <member><literal>=</literal></member>
+     <member><literal>&gt;=</literal></member>
+     <member><literal>&gt;</literal></member>
+    </simplelist>

That's the built-in minmax indexing strategy, yes, but you could
have others, even for datatypes with a linear sort order.

I "fixed" this by removing this list. It's not possible to be
comprehensive here, I think, and anyway I don't think there's much
point.

+ To find out the index tuple for a particular page range, we have an internal

s/find out/find/

+ new heap tuple contains null values but the index tuple indicate there are no

s/indicate/indicates/

Both fixed.

+ Open questions
+ --------------
+
+ * Same-size page ranges?
+   Current related literature seems to consider that each "index entry" in a
+   BRIN index must cover the same number of pages.  There doesn't seem to be a

What is the related literature? Is there an academic paper or
something that should be cited as a reference for BRIN?

I the original "minmax-proposal" file, I had these four URLs:

: Other database systems already have similar features. Some examples:
:
: * Oracle Exadata calls this "storage indexes"
: http://richardfoote.wordpress.com/category/storage-indexes/
:
: * Netezza has "zone maps"
: http://nztips.com/2010/11/netezza-integer-join-keys/
:
: * Infobright has this automatically within their "data packs" according to a
: May 3rd, 2009 blog post
: http://www.infobright.org/index.php/organizing_data_and_more_about_rough_data_contest/
:
: * MonetDB also uses this technique, according to a published paper
: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.2662
: "Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS"

I gave them all a quick look and none of them touches the approach in
detail; in fact other than the Oracle Exadata one, they are all talking
about something else and mention the "minmax" stuff only in passing. I
don't think any of them is worth citing.

+  * TODO
+  *		* ScalarArrayOpExpr (amsearcharray -> SK_SEARCHARRAY)
+  *		* add support for unlogged indexes
+  *		* ditto expressional indexes

We don't have unlogged indexes in general, so no need to list that
here. What would be needed to implement ScalarArrayOpExprs?

Well, it requires a different way to handle ScanKeys. Anyway the
queries that it is supposed to serve can already be served in some other
ways for AMs that don't have amsearcharray, so I don't think it's a huge
loss if we don't implement it. We can add that later.

I didn't realize that expression indexes are still not supported.
And I see that partial indexes are not supported either. Why not? I
wouldn't expect BRIN to need to care about those things in
particular; the expressions for an expressional or partial index are
handled in the executor, no?

Yeah; those restrictions were leftovers from back when I didn't really
know how they were supposed to be implemented. I took out the
restrictions and there wasn't anything else required to support both
these features.

+ /*
+  * A tuple in the heap is being inserted.  To keep a brin index up to date,
+  * we need to obtain the relevant index tuple, compare its stored values with
+  * those of the new tuple; if the tuple values are consistent with the summary
+  * tuple, there's nothing to do; otherwise we need to update the index.

s/compare/and compare/. Perhaps replace one of the semicolons with a
full stop.

Fixed.

+  * If the range is not currently summarized (i.e. the revmap returns InvalidTid
+  * for it), there's nothing to do either.
+  */
+ Datum
+ brininsert(PG_FUNCTION_ARGS)

There is no InvalidTid, as a constant or a #define. Perhaps replace
with "invalid item pointer".

Fixed -- actually it doesn't return invalid TID anymore, only NULL.

+ 	/*
+ 	 * XXX We need to know the size of the table so that we know how long to
+ 	 * iterate on the revmap.  There's room for improvement here, in that we
+ 	 * could have the revmap tell us when to stop iterating.
+ 	 */

The revmap doesn't know how large the table is. Remember that you
have to return all blocks that are not in the revmap, so you can't
just stop when you reach the end of the revmap. I think the current
design is fine.

Yeah, I was leaning towards the same conclusion myself. I have removed
the comment. (We could think about having brininsert update the
metapage so that the index keeps track of what's the last heap page,
which could help us support this, but I'm not sure there's much point.
Anyway we can tweak this later.)

I have to stop now to do some other stuff. Overall, this is in
pretty good shape. In addition to little cleanup of things I listed
above, and similar stuff elsewhere that I didn't read through right
now, there are a few medium-sized items I'd still like to see
addressed before you commit this:

* expressional/partial index support
* the difficulty of testing the union support function that we
discussed earlier

I added an USE_ASSERTION-only block in brininsert that runs the union
support proc and compares the output with the one from regular addValue.
I haven't tested this too much yet.

* clarify the memory context stuff of support functions that we also
discussed earlier

I re-checked this stuff. Turns out that the support functions don't
palloc/pfree memory too much, except to update the stuff stored in
BrinValues, by using datumCopy(). This memory is only freed when we
need to update a previous Datum. There's no way for the brin.c code to
know when the Datum is going to be released by the support proc, and
thus no way for a temp context to be used.

The memory context experiments I alluded to earlier are related to
pallocs done in brininsert / bringetbitmap themselves, not in the
opclass-provided support procs. All in all, I don't think there's much
room for improvement, other than perhaps doing so in brininsert/
bringetbitmap. Don't really care too much about this either way.

Once again, many thanks for the review. Here's a new version. I have
added operator classes for int8, text, and actually everything that btree
supports except:
bool
record
oidvector
anyarray
tsvector
tsquery
jsonb
range

since I'm not sure that it makes sense to have opclasses for any of
these -- at least not regular minmax opclasses. There are some
interesting possibilities, for example for range types, whereby we store
in the index tuple the union of all the range in the block range.

(I had an opclass for anyenum too, but on further thought I removed it
because it is going to be pointless in nearly all cases.)

contrib/pageinspect/Makefile | 2 +-
contrib/pageinspect/brinfuncs.c | 410 +++++++++++
contrib/pageinspect/pageinspect--1.2.sql | 37 +
contrib/pg_xlogdump/rmgrdesc.c | 1 +
doc/src/sgml/brin.sgml | 498 +++++++++++++
doc/src/sgml/filelist.sgml | 1 +
doc/src/sgml/indices.sgml | 36 +-
doc/src/sgml/postgres.sgml | 1 +
src/backend/access/Makefile | 2 +-
src/backend/access/brin/Makefile | 18 +
src/backend/access/brin/README | 179 +++++
src/backend/access/brin/brin.c | 1116 ++++++++++++++++++++++++++++++
src/backend/access/brin/brin_minmax.c | 320 +++++++++
src/backend/access/brin/brin_pageops.c | 712 +++++++++++++++++++
src/backend/access/brin/brin_revmap.c | 473 +++++++++++++
src/backend/access/brin/brin_tuple.c | 553 +++++++++++++++
src/backend/access/brin/brin_xlog.c | 319 +++++++++
src/backend/access/common/reloptions.c | 7 +
src/backend/access/heap/heapam.c | 22 +-
src/backend/access/rmgrdesc/Makefile | 3 +-
src/backend/access/rmgrdesc/brindesc.c | 112 +++
src/backend/access/transam/rmgr.c | 1 +
src/backend/catalog/index.c | 24 +
src/backend/replication/logical/decode.c | 1 +
src/backend/storage/page/bufpage.c | 179 ++++-
src/backend/utils/adt/selfuncs.c | 74 +-
src/include/access/brin.h | 52 ++
src/include/access/brin_internal.h | 87 +++
src/include/access/brin_page.h | 70 ++
src/include/access/brin_pageops.h | 36 +
src/include/access/brin_revmap.h | 39 ++
src/include/access/brin_tuple.h | 97 +++
src/include/access/brin_xlog.h | 107 +++
src/include/access/heapam.h | 2 +
src/include/access/reloptions.h | 3 +-
src/include/access/relscan.h | 4 +-
src/include/access/rmgrlist.h | 1 +
src/include/catalog/index.h | 8 +
src/include/catalog/pg_am.h | 2 +
src/include/catalog/pg_amop.h | 164 +++++
src/include/catalog/pg_amproc.h | 245 +++++++
src/include/catalog/pg_opclass.h | 32 +
src/include/catalog/pg_opfamily.h | 28 +
src/include/catalog/pg_proc.h | 38 +
src/include/storage/bufpage.h | 2 +
src/include/utils/selfuncs.h | 1 +
src/test/regress/expected/opr_sanity.out | 14 +-
src/test/regress/sql/opr_sanity.sql | 7 +-
48 files changed, 6122 insertions(+), 18 deletions(-)

(I keep naming the patch file "minmax", but nothing in the code is
actually called that way anymore, except the opclasses).

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 10/07/2014 01:33 AM, Alvaro Herrera wrote:

Heikki Linnakangas wrote:

On 09/23/2014 10:04 PM, Alvaro Herrera wrote:

+ Open questions
+ --------------
+
+ * Same-size page ranges?
+   Current related literature seems to consider that each "index entry" in a
+   BRIN index must cover the same number of pages.  There doesn't seem to be a

What is the related literature? Is there an academic paper or
something that should be cited as a reference for BRIN?

I the original "minmax-proposal" file, I had these four URLs:

: Other database systems already have similar features. Some examples:
:
: * Oracle Exadata calls this "storage indexes"
: http://richardfoote.wordpress.com/category/storage-indexes/
:
: * Netezza has "zone maps"
: http://nztips.com/2010/11/netezza-integer-join-keys/
:
: * Infobright has this automatically within their "data packs" according to a
: May 3rd, 2009 blog post
: http://www.infobright.org/index.php/organizing_data_and_more_about_rough_data_contest/
:
: * MonetDB also uses this technique, according to a published paper
: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.2662
: "Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS"

I gave them all a quick look and none of them touches the approach in
detail; in fact other than the Oracle Exadata one, they are all talking
about something else and mention the "minmax" stuff only in passing. I
don't think any of them is worth citing.

I think the "current related literature" phrase should be removed, if
there isn't in fact any literature on this. If there's any literature
worth referencing, should add a proper citation.

I added an USE_ASSERTION-only block in brininsert that runs the union
support proc and compares the output with the one from regular addValue.
I haven't tested this too much yet.

Ok, that's better than nothing. I wonder if it's too strict, though. It
uses brin_tuple_equal(), which does a memcmp() on the tuples. That will
trip for any non-meaningful differences, like the scale in a numeric.

* clarify the memory context stuff of support functions that we also
discussed earlier

I re-checked this stuff. Turns out that the support functions don't
palloc/pfree memory too much, except to update the stuff stored in
BrinValues, by using datumCopy(). This memory is only freed when we
need to update a previous Datum. There's no way for the brin.c code to
know when the Datum is going to be released by the support proc, and
thus no way for a temp context to be used.

The memory context experiments I alluded to earlier are related to
pallocs done in brininsert / bringetbitmap themselves, not in the
opclass-provided support procs.

At the very least, it needs to be documented.

All in all, I don't think there's much
room for improvement, other than perhaps doing so in brininsert/
bringetbitmap. Don't really care too much about this either way.

Doing it in brininsert/bringetbitmap seems like the right approach.
GiST, GIN, and SP-GiST all use a temporary memory context like that.

It would be wise to reserve some more support procedure numbers, for
future expansion. Currently, support procs 1-4 are used by BRIN itself,
and higher numbers can be used by the opclass. minmax opclasses uses 5-8
for the <, <=, >= and > operators. If we ever want to add a new,
optional, support function to BRIN, we're out of luck. Let's document
that e.g. support procs < 10 are reserved for BRIN.

The redo routines should be updated to follow the new
XLogReadBufferForRedo idiom (commit
f8f4227976a2cdb8ac7c611e49da03aa9e65e0d2).

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Once again, many thanks for the review. Here's a new version. I have
added operator classes for int8, text, and actually everything that btree
supports except:
bool
record
oidvector
anyarray
tsvector
tsquery
jsonb
range

since I'm not sure that it makes sense to have opclasses for any of
these -- at least not regular minmax opclasses. There are some
interesting possibilities, for example for range types, whereby we store
in the index tuple the union of all the range in the block range.

I thought we can do better than minmax for the inet data type,
and ended up with a generalized opclass supporting both inet and range
types. Patch based on minmax-v20 attached. It works well except
a few small problems. I will improve the patch and add into
a commitfest after BRIN framework is committed.

To support more operators I needed to change amstrategies and
amsupport on the catalog. It would be nice if amsupport can be set
to 0 like amstrategies.

Inet data types accept IP version 4 and version 6. It is not possible
to represent union of addresses from different versions with a valid
inet type. So, I made the union function return NULL in this case.
Then, I tried to store if returned value is NULL or not, in
column->values[] as boolean, but it failed on the pfree() inside
brin_dtuple_initilize(). It doesn't seem right to free the values
based on attr->attbyval.

I think the same opclass can be used for geometric types. I can
rename it to inclusion_ops instead of range_ops. The GiST opclasses
for the geometric types use bounding boxes. It wouldn't be possible
to use a different data type in a generic oplass. Maybe STORAGE
parameter can be used for that purpose.

(I had an opclass for anyenum too, but on further thought I removed it
because it is going to be pointless in nearly all cases.)

It can be useful in some circumstances. We wouldn't lose anything
by supporting more types. I think we should even add an operator
class for boolean.

Heikki Linnakangas wrote:

On 10/07/2014 01:33 AM, Alvaro Herrera wrote:

I added an USE_ASSERTION-only block in brininsert that runs the union
support proc and compares the output with the one from regular addValue.
I haven't tested this too much yet.

Ok, that's better than nothing. I wonder if it's too strict, though. It uses
brin_tuple_equal(), which does a memcmp() on the tuples. That will trip for
any non-meaningful differences, like the scale in a numeric.

True. I'm not real sure how to do better, though. For types that have
a btree opclass it's easy, because we can just use the btree equality
function to compare the values. But most interesting cases would not
have btree opclasses; those are covered by the minmax family of
opclasses.

It would be wise to reserve some more support procedure numbers, for future
expansion. Currently, support procs 1-4 are used by BRIN itself, and higher
numbers can be used by the opclass. minmax opclasses uses 5-8 for the <, <=,

= and > operators. If we ever want to add a new, optional, support function

to BRIN, we're out of luck. Let's document that e.g. support procs < 10 are
reserved for BRIN.

Sure. I hope we never need to add a seventh optional support function ...

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

+   <acronym>BRIN</acronym> indexes can satisfy queries via the bitmap
+   scanning facility, and will return all tuples in all pages within

"The bitmap scanning facility?" Does this mean a bitmap index scan?
Or something novel to BRIN? I think this could be clearer.

+   This enables them to work as very fast sequential scan helpers to avoid
+   scanning blocks that are known not to contain matching tuples.

Hmm, but they don't actually do anything about sequential scans per
se, right? I'd say something like: "Because a BRIN index is very
small, scanning the index adds little overhead compared to a
sequential scan, but may avoid scanning large parts of the table that
are known not to contain matching tuples."

+ depend on the operator class selected for the data type.

The operator class is selected for the index, not the data type.

+   The size of the block range is determined at index creation time with
+   the <literal>pages_per_range</> storage parameter.
+   The smaller the number, the larger the index becomes (because of the need to
+   store more index entries), but at the same time the summary data stored can
+   be more precise and more data blocks can be skipped during an index scan.

I would insert a sentence something like this: "The number of index
entries will be equal to the size of the relation in pages divided by
the selected value for pages_per_range. Therefore, the smaller the
number...." At least, I would insert that if it's actually true. My
point is that I think the effect of pages_per_range could be made more
clear.

+   The core <productname>PostgreSQL</productname> distribution includes
+   includes the <acronym>BRIN</acronym> operator classes shown in
+   <xref linkend="gin-builtin-opclasses-table">.

Shouldn't that say brin, not gin?

+ requiring the access method implementer only to implement the semantics

The naming of the reverse range map seems a little weird. It seems
like most operations go through it, so it feels more like the forward
direction. Maybe I'm misunderstanding. (I doubt it's worth renaming
it at this point either way, but I thought I'd mention it.)

+ errmsg("unlogged BRIN indexes are not supported")));

Why not? Shouldn't be particularly hard, I wouldn't think.

I'm pretty sure you need to create a pageinspect--1.3.sql, not just
update the 1.2 file. Because that's in 9.4, and this won't be.

I'm pretty excited about this feature. I think it's going to be very
good for PostgreSQL.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas wrote:

[lots]

I have fixed all these items in the attached, thanks -- most
user-visible change was the pageinspect 1.3 thingy. pg_upgrade from 1.2
works fine now. I also fixed some things Heikki noted, mainly avoid
retail pfree where possible, and renumber the support procs to leave
room for future expansion of the framework. XLog replay code is updated
too.

Also, I made the summarization step callable directly from SQL without
having to invoke VACUUM.

So here's v21. I also attach a partial diff from v20, just in case
anyone wants to give it a look.

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Nov 3, 2014 at 2:18 PM, Alvaro Herrera <alvherre@2ndquadrant.com>
wrote:

Robert Haas wrote:

[lots]

I have fixed all these items in the attached, thanks -- most
user-visible change was the pageinspect 1.3 thingy. pg_upgrade from 1.2
works fine now. I also fixed some things Heikki noted, mainly avoid
retail pfree where possible, and renumber the support procs to leave
room for future expansion of the framework. XLog replay code is updated
too.

Also, I made the summarization step callable directly from SQL without
having to invoke VACUUM.

So here's v21. I also attach a partial diff from v20, just in case
anyone wants to give it a look.

I get a couple compiler warnings with this:

brin.c: In function 'brininsert':
brin.c:97: warning: 'tupcxt' may be used uninitialized in this function
brin.c:98: warning: 'oldcxt' may be used uninitialized in this function

Also, I think it is missing a cat version bump. It let me start the
patched server against an unpatched initdb run, but once started it didn't
find the index method.

What would it take to make CLUSTER work on a brin index? Now I just added
a btree index on the same column, clustered on that, then dropped that
index.

Thanks,

Jeff

Jeff Janes wrote:

On Mon, Nov 3, 2014 at 2:18 PM, Alvaro Herrera <alvherre@2ndquadrant.com>
wrote:

I get a couple compiler warnings with this:

brin.c: In function 'brininsert':
brin.c:97: warning: 'tupcxt' may be used uninitialized in this function
brin.c:98: warning: 'oldcxt' may be used uninitialized in this function

Ah, that's easily fixed. My compiler (gcc 4.9 from Debian Jessie
nowadays) doesn't complain, but I can see that it's not entirely
trivial.

Also, I think it is missing a cat version bump. It let me start the
patched server against an unpatched initdb run, but once started it didn't
find the index method.

Sure, that's expected (by me at least). I'm too lazy to maintain
catversion bumps in the patch before pushing, since that generates
constant conflicts as I rebase.

What would it take to make CLUSTER work on a brin index? Now I just added
a btree index on the same column, clustered on that, then dropped that
index.

Interesting question. What's the most efficient way to pack a table to
minimize the intervals covered by each index entry? One thing that
makes this project a bit easier, I think, is that CLUSTER has already
been generalized so that it supports either an indexscan or a
seqscan+sort. If anyone wants to work on this, be my guest; I'm
certainly not going to add it to the initial commit.

--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 3 November 2014 22:18, Alvaro Herrera <alvherre@2ndquadrant.com> wrote:

So here's v21. I also attach a partial diff from v20, just in case
anyone wants to give it a look.

Looks really good.

I'd like to reword this sentence in the readme, since one of the main
use cases would be tables without btrees
   It's unlikely that BRIN would be the only
+ indexes in a table, though, because primary keys can be btrees only, and so
+ we don't implement this optimization.

I don't see a regression test. Create, use, VACUUM, just so we know it
hasn't regressed after commit.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Nov 3, 2014 at 2:18 PM, Alvaro Herrera <alvherre@2ndquadrant.com>
wrote:

So here's v21. I also attach a partial diff from v20, just in case
anyone wants to give it a look.

This needs a bump to 1.3, or the extension won't install:

contrib/pageinspect/pageinspect.control

During crash recovery, I am getting a segfault:

#0 0x000000000067ee35 in LWLockRelease (lock=0x0) at lwlock.c:1161
#1 0x0000000000664f4a in UnlockReleaseBuffer (buffer=0) at bufmgr.c:2888
#2 0x0000000000465a88 in brin_xlog_revmap_extend (lsn=<value optimized
out>, record=<value optimized out>) at brin_xlog.c:261
#3 brin_redo (lsn=<value optimized out>, record=<value optimized out>) at
brin_xlog.c:284
#4 0x00000000004ce505 in StartupXLOG () at xlog.c:6795

I failed to preserve the data directory, I'll try to repeat this later this
week if needed.

Cheers,

Jeff