Re: Minmax indexes

Hi,

Here's a reviewable version of what I've dubbed Minmax indexes. Some
people said they would like to use some other name for this feature, but
I have yet to hear usable ideas, so for now I will keep calling them
this way. I'm open to proposals, but if you pick something that cannot
be abbreviated "mm" I might have you prepare a rebased version which
renames the files and structs.

The implementation here has been simplified from what I originally
proposed at 20130614222805(dot)GZ5491(at)eldon(dot)alvh(dot)no-ip(dot)org -- in particular,
I noticed that there's no need to involve aggregate functions at all; we
can just use inequality operators. So the pg_amproc entries are gone;
only the pg_amop entries are necessary.

I've somewhat punted on the question of doing resummarization separately
from vacuuming. Right now, resummarization (as well as other necessary
index cleanup) takes place in amvacuumcleanup. This is not optimal; I
have stated elsewhere that I'd like to create separate maintenance
actions that can be carried out by autovacuum. That would be useful
both for Minmax indexes and GIN indexes (pending insertion list); maybe
others. That's not part of this patch, however.

The design of this stuff is in the file "minmax-proposal" at the top of
the tree. That file is up to date, though it still contains some open
questions that were present in the original proposal. (I have not fixed
some bogosities pointed out by Noah, for instance. I will do that
shortly.) In a final version, that file would be applied as
src/backend/access/minmax/README, most likely.

One area on which I needed to modify core code is IndexBuildHeapScan. I
needed a version that was able to scan only a certain range of pages,
not the entire table, so I introduced a new IndexBuildHeapRangeScan, and
added a quick "heap_scansetlimits" function. I haven't tested that this
works outside of the HeapRangeScan thingy, so it's probably completely
bogus; I'm open to suggestions if people think this should be
implemented differently. In any case, keeping that implementation
together with vanilla IndexBuildHeapScan makes a lot of sense.

One thing still to tackle is when to mark ranges as unsummarized. Right
now, any new tuple on a page range would cause a new index entry to be
created and a new revmap update. This would cause huge index bloat if,
say, a page is emptied and vacuumed and filled with new tuples with
increasing values outside the original range; each new tuple would
create a new index tuple. I have two ideas about this (1. mark range as
unsummarized if 3rd time we touch the same page range; 2. vacuum the
affected index page if it's full, so we can maintain the index always up
to date without causing unduly bloat), but I haven't implemented
anything yet.

The "amcostestimate" routine is completely bogus; right now it returns
constant 0, meaning the index is always chosen if it exists.

There are opclasses for int4, numeric and text. The latter doesn't work
at all, because collation info is not passed down at all. I will have
to figure that out (even if I find unlikely that minmax indexes have any
usefulness on top of text columns). I admit that numeric hasn't been
tested, and it's quite likely that they won't work; mainly because of
lack of some datumCopy() calls, about which the code contains some
/* XXX */ lines. I think this should be relatively straightforward.
Ideally, the final version of this patch would contain opclasses for all
supported datatypes (i.e. the same that have got btree opclasses).

I have messed up the opclass information, as evidenced by failures in
opr_sanity regression test. I will research that later.

There's working contrib/pageinspect support; pg_xlogdump (and wal_debug)
seems to work sanely too.
This patch compiles cleanly under -Werror.

The research leading to these results has received funding from the
European Union's Seventh Framework Programme (FP7/2007-2013) under
grant agreement n° 318633

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

On Sat, 2013-09-14 at 21:14 -0300, Alvaro Herrera wrote:
> Here's a reviewable version of what I've dubbed Minmax indexes.

Please fix duplicate OID 3177.

On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:

> Hi,
>
> Here's a reviewable version of what I've dubbed Minmax indexes. Some
> people said they would like to use some other name for this feature, but
> I have yet to hear usable ideas, so for now I will keep calling them
> this way. I'm open to proposals, but if you pick something that cannot
> be abbreviated "mm" I might have you prepare a rebased version which
> renames the files and structs.
>
> The implementation here has been simplified from what I originally
> proposed at 20130614222805(dot)GZ5491(at)eldon(dot)alvh(dot)no-ip(dot)org -- in particular,
> I noticed that there's no need to involve aggregate functions at all; we
> can just use inequality operators. So the pg_amproc entries are gone;
> only the pg_amop entries are necessary.
>
> I've somewhat punted on the question of doing resummarization separately
> from vacuuming. Right now, resummarization (as well as other necessary
> index cleanup) takes place in amvacuumcleanup. This is not optimal; I
> have stated elsewhere that I'd like to create separate maintenance
> actions that can be carried out by autovacuum. That would be useful
> both for Minmax indexes and GIN indexes (pending insertion list); maybe
> others. That's not part of this patch, however.
>
> The design of this stuff is in the file "minmax-proposal" at the top of
> the tree. That file is up to date, though it still contains some open
> questions that were present in the original proposal. (I have not fixed
> some bogosities pointed out by Noah, for instance. I will do that
> shortly.) In a final version, that file would be applied as
> src/backend/access/minmax/README, most likely.
>
> One area on which I needed to modify core code is IndexBuildHeapScan. I
> needed a version that was able to scan only a certain range of pages,
> not the entire table, so I introduced a new IndexBuildHeapRangeScan, and
> added a quick "heap_scansetlimits" function. I haven't tested that this
> works outside of the HeapRangeScan thingy, so it's probably completely
> bogus; I'm open to suggestions if people think this should be
> implemented differently. In any case, keeping that implementation
> together with vanilla IndexBuildHeapScan makes a lot of sense.
>
> One thing still to tackle is when to mark ranges as unsummarized. Right
> now, any new tuple on a page range would cause a new index entry to be
> created and a new revmap update. This would cause huge index bloat if,
> say, a page is emptied and vacuumed and filled with new tuples with
> increasing values outside the original range; each new tuple would
> create a new index tuple. I have two ideas about this (1. mark range as
> unsummarized if 3rd time we touch the same page range; 2. vacuum the
> affected index page if it's full, so we can maintain the index always up
> to date without causing unduly bloat), but I haven't implemented
> anything yet.
>
> The "amcostestimate" routine is completely bogus; right now it returns
> constant 0, meaning the index is always chosen if it exists.
>
> There are opclasses for int4, numeric and text. The latter doesn't work
> at all, because collation info is not passed down at all. I will have
> to figure that out (even if I find unlikely that minmax indexes have any
> usefulness on top of text columns). I admit that numeric hasn't been
> tested, and it's quite likely that they won't work; mainly because of
> lack of some datumCopy() calls, about which the code contains some
> /* XXX */ lines. I think this should be relatively straightforward.
> Ideally, the final version of this patch would contain opclasses for all
> supported datatypes (i.e. the same that have got btree opclasses).
>
> I have messed up the opclass information, as evidenced by failures in
> opr_sanity regression test. I will research that later.
>
>
> There's working contrib/pageinspect support; pg_xlogdump (and wal_debug)
> seems to work sanely too.
> This patch compiles cleanly under -Werror.
>
> The research leading to these results has received funding from the
> European Union's Seventh Framework Programme (FP7/2007-2013) under
> grant agreement n° 318633

Thanks for the patch, but I seem to have immediately hit a snag:

pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
PANIC: invalid xlog record length 0

--
Thom

On 15.09.2013 03:14, Alvaro Herrera wrote:
> + Partial indexes are not supported; since an index is concerned with minimum and
> + maximum values of the involved columns across all the pages in the table, it
> + doesn't make sense to exclude values. Another way to see "partial" indexes
> + here would be those that only considered some pages in the table instead of all
> + of them; but this would be difficult to implement and manage and, most likely,
> + pointless.

Something like this seems completely sensible to me:

create index i_accounts on accounts using minmax (ts) where valid = true;

The situation where that would be useful is if 'valid' accounts are
fairly well clustered, but invalid ones are scattered all over the
table. The minimum and maximum stoed in the index would only concern
valid accounts.

- Heikki

> On 16 September 2013 at 11:03 Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>
> wrote:

>
> Something like this seems completely sensible to me:
>
> create index i_accounts on accounts using minmax (ts) where valid = true;
>
> The situation where that would be useful is if 'valid' accounts are
> fairly well clustered, but invalid ones are scattered all over the
> table. The minimum and maximum stoed in the index would only concern
> valid accounts.

Here's one that occurs to me:

CREATE INDEX i_billing_id_mm ON billing(id) WHERE paid_in_full IS NOT TRUE;

Note that this would be a frequently moving target and over years of billing,
the subset would be quite small compared to the full system (imagine, say, 50k
rows out of 20M).

Best Wises,
Chris Travers
>
> - Heikki
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
Best Wishes,
Chris Travers
http://www.2ndquadrant.com
PostgreSQL Services, Training, and Support

On 2013-09-16 11:19:19 +0100, Chris Travers wrote:
>
>
> > On 16 September 2013 at 11:03 Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>
> > wrote:
>
> >
> > Something like this seems completely sensible to me:
> >
> > create index i_accounts on accounts using minmax (ts) where valid = true;
> >
> > The situation where that would be useful is if 'valid' accounts are
> > fairly well clustered, but invalid ones are scattered all over the
> > table. The minimum and maximum stoed in the index would only concern
> > valid accounts.

Yes, I wondered the same myself.

> Here's one that occurs to me:
>
> CREATE INDEX i_billing_id_mm ON billing(id) WHERE paid_in_full IS NOT TRUE;
>
> Note that this would be a frequently moving target and over years of billing,
> the subset would be quite small compared to the full system (imagine, say, 50k
> rows out of 20M).

In that case you'd just use a normal btree index, no?

Greetings,

Andres Freund

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

On Mon, Sep 16, 2013 at 3:47 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>>
>> Hi,
>>
>> Here's a reviewable version of what I've dubbed Minmax indexes.
>>
> Thanks for the patch, but I seem to have immediately hit a snag:
>
> pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
> PANIC: invalid xlog record length 0
>

fwiw, this seems to be triggered by ANALYZE.
At least i can trigger it by executing ANALYZE on the table (attached
is a stacktrace of a backend exhibiting the failure)

Another thing is this messages i got when compiling:
"""
mmxlog.c: In function ‘minmax_xlog_revmap_set’:
mmxlog.c:161:14: warning: unused variable ‘blkno’ [-Wunused-variable]
bufpage.c: In function ‘PageIndexDeleteNoCompact’:
bufpage.c:1066:18: warning: ‘lastused’ may be used uninitialized in
this function [-Wmaybe-uninitialized]
"""

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

On 17 September 2013 07:20, Jaime Casanova <jaime(at)2ndquadrant(dot)com> wrote:

> On Mon, Sep 16, 2013 at 3:47 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> > On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
> wrote:
> >>
> >> Hi,
> >>
> >> Here's a reviewable version of what I've dubbed Minmax indexes.
> >>
> > Thanks for the patch, but I seem to have immediately hit a snag:
> >
> > pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
> > PANIC: invalid xlog record length 0
> >
>
> fwiw, this seems to be triggered by ANALYZE.
> At least i can trigger it by executing ANALYZE on the table (attached
> is a stacktrace of a backend exhibiting the failure)
>
> Another thing is this messages i got when compiling:
> """
> mmxlog.c: In function ‘minmax_xlog_revmap_set’:
> mmxlog.c:161:14: warning: unused variable ‘blkno’ [-Wunused-variable]
> bufpage.c: In function ‘PageIndexDeleteNoCompact’:
> bufpage.c:1066:18: warning: ‘lastused’ may be used uninitialized in
> this function [-Wmaybe-uninitialized]
> """
>

I'm able to run ANALYSE manually without it dying:

pgbench=# analyse pgbench_accounts;
ANALYZE
pgbench=# analyse pgbench_accounts;
ANALYZE
pgbench=# create index minmaxtest on pgbench_accounts using minmax (aid);
PANIC: invalid xlog record length 0

--
Thom

On Tue, Sep 17, 2013 at 3:30 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> On 17 September 2013 07:20, Jaime Casanova <jaime(at)2ndquadrant(dot)com> wrote:
>>
>> On Mon, Sep 16, 2013 at 3:47 AM, Thom Brown <thom(at)linux(dot)com> wrote:
>> > On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
>> > wrote:
>> >>
>> >> Hi,
>> >>
>> >> Here's a reviewable version of what I've dubbed Minmax indexes.
>> >>
>> > Thanks for the patch, but I seem to have immediately hit a snag:
>> >
>> > pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax
>> > (aid);
>> > PANIC: invalid xlog record length 0
>> >
>>
>> fwiw, this seems to be triggered by ANALYZE.
>> At least i can trigger it by executing ANALYZE on the table (attached
>> is a stacktrace of a backend exhibiting the failure)
>>
>
> I'm able to run ANALYSE manually without it dying:
>

try inserting some data before the ANALYZE, that will force a
resumarization which is mentioned in the stack trace of the failure

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

On 17 September 2013 14:37, Jaime Casanova <jaime(at)2ndquadrant(dot)com> wrote:

> On Tue, Sep 17, 2013 at 3:30 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> > On 17 September 2013 07:20, Jaime Casanova <jaime(at)2ndquadrant(dot)com>
> wrote:
> >>
> >> On Mon, Sep 16, 2013 at 3:47 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> >> > On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
> >> > wrote:
> >> >>
> >> >> Hi,
> >> >>
> >> >> Here's a reviewable version of what I've dubbed Minmax indexes.
> >> >>
> >> > Thanks for the patch, but I seem to have immediately hit a snag:
> >> >
> >> > pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax
> >> > (aid);
> >> > PANIC: invalid xlog record length 0
> >> >
> >>
> >> fwiw, this seems to be triggered by ANALYZE.
> >> At least i can trigger it by executing ANALYZE on the table (attached
> >> is a stacktrace of a backend exhibiting the failure)
> >>
> >
> > I'm able to run ANALYSE manually without it dying:
> >
>
> try inserting some data before the ANALYZE, that will force a
> resumarization which is mentioned in the stack trace of the failure
>

I've tried inserting 1 row then ANALYSE and 10,000 rows then ANALYSE, and
in both cases there's no error. But then trying to create the index again
results in my original error.

--
Thom

On Tue, Sep 17, 2013 at 8:43 AM, Thom Brown <thom(at)linux(dot)com> wrote:
> On 17 September 2013 14:37, Jaime Casanova <jaime(at)2ndquadrant(dot)com> wrote:
>>
>> On Tue, Sep 17, 2013 at 3:30 AM, Thom Brown <thom(at)linux(dot)com> wrote:
>> > On 17 September 2013 07:20, Jaime Casanova <jaime(at)2ndquadrant(dot)com>
>> > wrote:
>> >>
>> >> On Mon, Sep 16, 2013 at 3:47 AM, Thom Brown <thom(at)linux(dot)com> wrote:
>> >> > On 15 September 2013 01:14, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
>> >> > wrote:
>> >> >>
>> >> >> Hi,
>> >> >>
>> >> >> Here's a reviewable version of what I've dubbed Minmax indexes.
>> >> >>
>> >> > Thanks for the patch, but I seem to have immediately hit a snag:
>> >> >
>> >> > pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax
>> >> > (aid);
>> >> > PANIC: invalid xlog record length 0
>> >> >
>> >>
>> >> fwiw, this seems to be triggered by ANALYZE.
>> >> At least i can trigger it by executing ANALYZE on the table (attached
>> >> is a stacktrace of a backend exhibiting the failure)
>> >>
>> >
>> > I'm able to run ANALYSE manually without it dying:
>> >
>>
>> try inserting some data before the ANALYZE, that will force a
>> resumarization which is mentioned in the stack trace of the failure
>
>
> I've tried inserting 1 row then ANALYSE and 10,000 rows then ANALYSE, and in
> both cases there's no error. But then trying to create the index again
> results in my original error.
>

Ok

So, please confirm if this is the pattern you are following:

CREATE TABLE t1(i int);
INSERT INTO t1 SELECT generate_series(1, 10000);
CREATE INDEX idx1 ON t1 USING minmax (i);

if that, then the attached stack trace (index_failure_thom.txt) should
correspond to the failure you are looking.

My test was slightly different:

CREATE TABLE t1(i int);
CREATE INDEX idx1 ON t1 USING minmax (i);
INSERT INTO t1 SELECT generate_series(1, 10000);
ANALYZE t1;

and the failure happened in a different time, in resumarization
(attached index_failure_jcm.txt)

but in the end, both failures seems to happen for the same reason: a
record of length 0... at XLogInsert time

#4 XLogInsert at xlog.c:966
#5 mmSetHeapBlockItemptr at mmrevmap.c:169
#6 mm_doinsert at minmax.c:1410

actually, if you create a temp table both tests works fine

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

Thom Brown wrote:

Thanks for testing.

> Thanks for the patch, but I seem to have immediately hit a snag:
>
> pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
> PANIC: invalid xlog record length 0

Silly mistake I had already made in another patch. Here's an
incremental patch which fixes this bug. Apply this on top of previous
minmax-1.patch.

I also renumbered the duplicate OID pointed out by Peter, and fixed the
two compiler warnings reported by Jaime.

Note you'll need to re-initdb in order to get the right catalog entries.

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

On 17 September 2013 22:03, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:

> Thom Brown wrote:
>
> Thanks for testing.
>
> > Thanks for the patch, but I seem to have immediately hit a snag:
> >
> > pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
> > PANIC: invalid xlog record length 0
>
> Silly mistake I had already made in another patch. Here's an
> incremental patch which fixes this bug. Apply this on top of previous
> minmax-1.patch.
>

Thanks.

Hit another issue with exactly the same procedure:

pgbench=# create index minmaxtest on pgbench_accounts using minmax (aid);
ERROR: lock 176475 is not held

--
Thom

On Tue, September 17, 2013 23:03, Alvaro Herrera wrote:

> [minmax-1.patch. + minmax-2-incr.patch. (and initdb)]

The patches apply and compile OK.

I've not yet really tested; I just wanted to mention that make check gives the following differences:

*** /home/aardvark/pg_stuff/pg_sandbox/pgsql.minmax/src/test/regress/expected/opr_sanity.out 2013-09-17 23:18:31.427356703
+0200
--- /home/aardvark/pg_stuff/pg_sandbox/pgsql.minmax/src/test/regress/results/opr_sanity.out 2013-09-17 23:20:48.208150824
+0200
***************
*** 1076,1081 ****
--- 1076,1086 ----
2742 | 2 | @@@
2742 | 3 | <@
2742 | 4 | =
+ 3847 | 1 | <
+ 3847 | 2 | <=
+ 3847 | 3 | =
+ 3847 | 4 | >=
+ 3847 | 5 | >
4000 | 1 | <<
4000 | 1 | ~<~
4000 | 2 | &<
***************
*** 1098,1104 ****
4000 | 15 | >
4000 | 16 | @>
4000 | 18 | =
! (62 rows)

-- Check that all opclass search operators have selectivity estimators.
-- This is not absolutely required, but it seems a reasonable thing
--- 1103,1109 ----
4000 | 15 | >
4000 | 16 | @>
4000 | 18 | =
! (67 rows)

-- Check that all opclass search operators have selectivity estimators.
-- This is not absolutely required, but it seems a reasonable thing
***************
*** 1272,1280 ****
WHERE am.amname <> 'btree' AND am.amname <> 'gist' AND am.amname <> 'gin'
GROUP BY amname, amsupport, opcname, amprocfamily
HAVING count(*) != amsupport OR amprocfamily IS NULL;
! amname | opcname | count
! --------+---------+-------
! (0 rows)

SELECT amname, opcname, count(*)
FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
--- 1277,1288 ----
WHERE am.amname <> 'btree' AND am.amname <> 'gist' AND am.amname <> 'gin'
GROUP BY amname, amsupport, opcname, amprocfamily
HAVING count(*) != amsupport OR amprocfamily IS NULL;
! amname | opcname | count
! --------+-------------+-------
! minmax | int4_ops | 1
! minmax | text_ops | 1
! minmax | numeric_ops | 1
! (3 rows)

SELECT amname, opcname, count(*)
FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid

======================================================================

Erik Rijkers

Thom Brown wrote:

> Hit another issue with exactly the same procedure:
>
> pgbench=# create index minmaxtest on pgbench_accounts using minmax (aid);
> ERROR: lock 176475 is not held

That's what I get for restructuring the way buffers are acquired to use
the FSM, and then neglecting to test creation on decently-sized indexes.
Fix attached.

I just realized that xlog replay is also broken.

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

Erik Rijkers wrote:
> On Tue, September 17, 2013 23:03, Alvaro Herrera wrote:
>
> > [minmax-1.patch. + minmax-2-incr.patch. (and initdb)]
>
>
> The patches apply and compile OK.
>
> I've not yet really tested; I just wanted to mention that make check gives the following differences:

Oops, I forgot to update the expected file. I had to comment on this
when submitting minmax-2-incr.patch and forgot. First, those extra five
operators are supposed to be there; expected file needs an update. As
for this:

> --- 1277,1288 ----
> WHERE am.amname <> 'btree' AND am.amname <> 'gist' AND am.amname <> 'gin'
> GROUP BY amname, amsupport, opcname, amprocfamily
> HAVING count(*) != amsupport OR amprocfamily IS NULL;
> ! amname | opcname | count
> ! --------+-------------+-------
> ! minmax | int4_ops | 1
> ! minmax | text_ops | 1
> ! minmax | numeric_ops | 1
> ! (3 rows)

I think the problem is that the query is wrong. This is the complete query:

SELECT amname, opcname, count(*)
FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
amproclefttype = amprocrighttype AND amproclefttype = opcintype
WHERE am.amname <> 'btree' AND am.amname <> 'gist' AND am.amname <> 'gin'
GROUP BY amname, amsupport, opcname, amprocfamily
HAVING count(*) != amsupport OR amprocfamily IS NULL;

I should be, instead, this:

SELECT amname, opcname, count(*)
FROM pg_am am JOIN pg_opclass op ON opcmethod = am.oid
LEFT JOIN pg_amproc p ON amprocfamily = opcfamily AND
amproclefttype = amprocrighttype AND amproclefttype = opcintype
WHERE am.amname <> 'btree' AND am.amname <> 'gist' AND am.amname <> 'gin'
GROUP BY amname, amsupport, opcname, amprocfamily
HAVING count(*) != amsupport AND (amprocfamily IS NOT NULL);

This query is supposed to check that there are no opclasses with
mismatching number of support procedures; but if the left join returns a
null-extended row for pg_amproc, that means there is no support proc,
yet count(*) will return 1. So count(*) will not match amsupport, and
the row is supposed to be excluded by the amprocfamily IS NULL clause in
HAVING.

Both queries return empty in HEAD, but only the second one correctly
returns empty with the patch applied.

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

On Tue, Sep 17, 2013 at 4:03 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Thom Brown wrote:
>
> Thanks for testing.
>
>> Thanks for the patch, but I seem to have immediately hit a snag:
>>
>> pgbench=# CREATE INDEX minmaxtest ON pgbench_accounts USING minmax (aid);
>> PANIC: invalid xlog record length 0
>
> Silly mistake I had already made in another patch. Here's an
> incremental patch which fixes this bug. Apply this on top of previous
> minmax-1.patch.
>
> I also renumbered the duplicate OID pointed out by Peter, and fixed the
> two compiler warnings reported by Jaime.
>
> Note you'll need to re-initdb in order to get the right catalog entries.
>

Hi,

Found another problem with the this steps:

create table t1 (i int);
create index idx_t1_i on t1 using minmax(i);
insert into t1 select generate_series(1, 2000000);
ERROR: could not read block 1 in file "base/12645/16397_vm": read
only 0 of 8192 bytes
STATEMENT: insert into t1 select generate_series(1, 2000000);
ERROR: could not read block 1 in file "base/12645/16397_vm": read
only 0 of 8192 bytes

After that, i keep receiving these messages (when autovacuum tries to
vacuum this table):

ERROR: could not truncate file "base/12645/16397_vm" to 2 blocks:
it's only 1 blocks now
CONTEXT: automatic vacuum of table "postgres.public.t1"
ERROR: could not truncate file "base/12645/16397_vm" to 2 blocks:
it's only 1 blocks now
CONTEXT: automatic vacuum of table "postgres.public.t1"

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

Jaime Casanova wrote:

> Found another problem with the this steps:
>
> create table t1 (i int);
> create index idx_t1_i on t1 using minmax(i);
> insert into t1 select generate_series(1, 2000000);
> ERROR: could not read block 1 in file "base/12645/16397_vm": read
> only 0 of 8192 bytes

Thanks. This was a trivial off-by-one bug; fixed in the attached patch.
While studying it, I noticed that I was also failing to notice extension
of the fork by another process. I have tried to fix that also in the
current patch, but I'm afraid that a fully robust solution for this will
involve having a cached fork size in the index's relcache entry -- just
like we have smgr_vm_nblocks. In fact, since the revmap fork is
currently reusing the VM forknum, I might even be able to use the same
variable to keep track of the fork size. But I don't really like this
bit of reusing the VM forknum for revmap, so I've refrained from
extending that assumption into further code for the time being.

There was also a bug that we would try to initialize a revmap page twice
during recovery, if two backends thought they needed to extend it; that
would cause the data written by the first extender to be lost.

This patch applies on top of the two previous incremental patches. I
will send a full patch later, including all those fixes and the fix for
the opr_sanity regression test.

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

On Wed, September 25, 2013 00:14, Alvaro Herrera wrote:
> [minmax-4-incr.patch]

After a --data-checksums initdb (successful), the following error came up:

after the statement: create index t_minmax_idx on t using minmax (r);

WARNING: page verification failed, calculated checksum 25951 but expected 0
ERROR: invalid page in block 1 of relation base/21324/26267_vm

it happens reliably. every time I run the program.

Below is the whole program that I used.

Thanks,

Erik Rijkers

#!/bin/sh

t=t

if [[ 1 -eq 1 ]]; then

echo "
drop table if exists $t ;
create table $t
as
select i, cast( random() * 10^9 as integer ) as r
from generate_series(1, 1000000) as f(i) ;
analyze $t;
table $t limit 5;
select count(*) from $t;
explain analyze select min(r), max(r) from $t;
select min(r), max(r) from $t;

create index ${t}_minmax_idx on $t using minmax (r);
analyze $t;

explain analyze select min(r), max(r) from $t;
select min(r), max(r) from $t;

" | psql

fi

On Sun, Sep 15, 2013 at 5:44 AM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Hi,
>
> Here's a reviewable version of what I've dubbed Minmax indexes. Some
> people said they would like to use some other name for this feature, but
> I have yet to hear usable ideas, so for now I will keep calling them
> this way. I'm open to proposals, but if you pick something that cannot
> be abbreviated "mm" I might have you prepare a rebased version which
> renames the files and structs.
>
> The implementation here has been simplified from what I originally
> proposed at 20130614222805(dot)GZ5491(at)eldon(dot)alvh(dot)no-ip(dot)org -- in particular,
> I noticed that there's no need to involve aggregate functions at all; we
> can just use inequality operators. So the pg_amproc entries are gone;
> only the pg_amop entries are necessary.
>
> I've somewhat punted on the question of doing resummarization separately
> from vacuuming. Right now, resummarization (as well as other necessary
> index cleanup) takes place in amvacuumcleanup. This is not optimal; I
> have stated elsewhere that I'd like to create separate maintenance
> actions that can be carried out by autovacuum. That would be useful
> both for Minmax indexes and GIN indexes (pending insertion list); maybe
> others. That's not part of this patch, however.
>
> The design of this stuff is in the file "minmax-proposal" at the top of
> the tree. That file is up to date, though it still contains some open
> questions that were present in the original proposal. (I have not fixed
> some bogosities pointed out by Noah, for instance. I will do that
> shortly.) In a final version, that file would be applied as
> src/backend/access/minmax/README, most likely.
>
> One area on which I needed to modify core code is IndexBuildHeapScan. I
> needed a version that was able to scan only a certain range of pages,
> not the entire table, so I introduced a new IndexBuildHeapRangeScan, and
> added a quick "heap_scansetlimits" function. I haven't tested that this
> works outside of the HeapRangeScan thingy, so it's probably completely
> bogus; I'm open to suggestions if people think this should be
> implemented differently. In any case, keeping that implementation
> together with vanilla IndexBuildHeapScan makes a lot of sense.
>
> One thing still to tackle is when to mark ranges as unsummarized. Right
> now, any new tuple on a page range would cause a new index entry to be
> created and a new revmap update. This would cause huge index bloat if,
> say, a page is emptied and vacuumed and filled with new tuples with
> increasing values outside the original range; each new tuple would
> create a new index tuple. I have two ideas about this (1. mark range as
> unsummarized if 3rd time we touch the same page range;

Why only at 3rd time?
Doesn't it need to be precise, like if someone inserts a row having
value greater than max value of corresponding index tuple,
then that index tuple's corresponding max value needs to be updated
and I think its updated with the help of validity map.

For example:
considering we need to store below info for each index tuple:
In each index tuple (corresponding to one page range), we store:
- first block this tuple applies to
- last block this tuple applies to
- for each indexed column:
* min() value across all tuples in the range
* max() value across all tuples in the range

Assume first and last block for index tuple is same (assume block
no. 'x') and min value is 5 and max is 10.
Now user insert/update value in block 'x' such that max value of
index col. is 11, if we don't update corresponding
index tuple or at least invalidate it, won't it lead to wrong results?

> 2. vacuum the
> affected index page if it's full, so we can maintain the index always up
> to date without causing unduly bloat), but I haven't implemented
> anything yet.
>
> The "amcostestimate" routine is completely bogus; right now it returns
> constant 0, meaning the index is always chosen if it exists.

I think for first version, you might want to keep things simple, but
there should be some way for optimizer to select this index.
So rather than choose if it is present, we can make optimizer choose
when some-one says set enable_minmax index to true.

How about keeping this up-to-date during foreground operations.
Vacuum/Maintainer task maintaining things usually have problems of
bloat and
then we need optimize/workaround issues.
Lot of people have raised this or similar point previously and what
I read you are of opinion that it seems to be slow.
I really don't think that it can be so slow that adding so much
handling to get it up-to-date by some maintainer task is useful.
Currently there are
systems like Oracle where index clean-up is mainly done during
foreground operation, so this alone cannot be reason for slowness.

Comparing the logic with IOS is also not completely right as for
IOS, we need to know each tuple's visibility, which is not the case
here.

Now it can so happen that min and max values are sometimes not right
because later the operation is rolled back, but I think such cases
will
be less and we can find some way to handle such cases may be
maintainer task only, but the handling will be quite simpler.

On Windows, patch gives below compilation errors:
src\backend\access\minmax\mmtuple.c(96): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(96): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(96): error C2133: 'values' : unknown size
src\backend\access\minmax\mmtuple.c(97): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(97): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(97): error C2133: 'nulls' : unknown size
src\backend\access\minmax\mmtuple.c(102): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(102): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(102): error C2133:
'phony_nullbitmap' : unknown size
src\backend\access\minmax\mmtuple.c(110): warning C4034: sizeof returns 0
src\backend\access\minmax\mmtuple.c(246): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(246): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(246): error C2133: 'values' : unknown size
src\backend\access\minmax\mmtuple.c(247): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(247): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(247): error C2133: 'allnulls' :
unknown size
src\backend\access\minmax\mmtuple.c(248): error C2057: expected
constant expression
src\backend\access\minmax\mmtuple.c(248): error C2466: cannot
allocate an array of constant size 0
src\backend\access\minmax\mmtuple.c(248): error C2133: 'hasnulls' :
unknown size

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Amit Kapila escribió:
> On Sun, Sep 15, 2013 at 5:44 AM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:

> > One thing still to tackle is when to mark ranges as unsummarized. Right
> > now, any new tuple on a page range would cause a new index entry to be
> > created and a new revmap update. This would cause huge index bloat if,
> > say, a page is emptied and vacuumed and filled with new tuples with
> > increasing values outside the original range; each new tuple would
> > create a new index tuple. I have two ideas about this (1. mark range as
> > unsummarized if 3rd time we touch the same page range;
>
> Why only at 3rd time?
> Doesn't it need to be precise, like if someone inserts a row having
> value greater than max value of corresponding index tuple,
> then that index tuple's corresponding max value needs to be updated
> and I think its updated with the help of validity map.

Of course. Note I no longer have the concept of a validity map; I have
switched things to use a "reverse range map", or revmap for short. The
revmap is responsible for mapping each page number to an individual
index TID. If the TID stored in the revmap is InvalidTid, that means
the range is not summarized. Summarized ranges are always considered as
"match query quals", and thus all tuples in them are returned in the
bitmap for heap recheck.

The way it works currently, is that any tuple insert (that's outside the
bounds of the current index tuple) causes a new index tuple to be
created, and the revmap is updated to point to the new index tuple. The
old index tuple is orphaned and will be deleted at next vacuum. This
works fine. However the problem is excess orphaned tuples; I don't want
a long series of updates to create many orphaned dead tuples. Instead I
would like the system to, at some point, stop creating new index tuples
and instead set the revmap to InvalidTid. That would stop the index
bloat.

> For example:
> considering we need to store below info for each index tuple:
> In each index tuple (corresponding to one page range), we store:
> - first block this tuple applies to
> - last block this tuple applies to
> - for each indexed column:
> * min() value across all tuples in the range
> * max() value across all tuples in the range
>
> Assume first and last block for index tuple is same (assume block
> no. 'x') and min value is 5 and max is 10.
> Now user insert/update value in block 'x' such that max value of
> index col. is 11, if we don't update corresponding
> index tuple or at least invalidate it, won't it lead to wrong results?

Sure, that would result in wrong results. Fortunately that's not how I
am suggesting to do it.

I note you're reading an old version of the design. I realize now that
this is my mistake because instead of posting the new design in the
cover letter for the patch, I only put it in the "minmax-proposal" file.
Please give that file a read to see how the design differs from the
design I originally posted in the old thread.

> > The "amcostestimate" routine is completely bogus; right now it returns
> > constant 0, meaning the index is always chosen if it exists.
>
> I think for first version, you might want to keep things simple, but
> there should be some way for optimizer to select this index.
> So rather than choose if it is present, we can make optimizer choose
> when some-one says set enable_minmax index to true.

Well, enable_bitmapscan already disables minmax indexes, just like it
disables other indexes.

> How about keeping this up-to-date during foreground operations.
> Vacuum/Maintainer task maintaining things usually have problems of
> bloat and
> then we need optimize/workaround issues.
> Lot of people have raised this or similar point previously and what
> I read you are of opinion that it seems to be slow.

Well, the current code does keep the index up to date -- I did choose to
implement what people suggested :-)

> Now it can so happen that min and max values are sometimes not right
> because later the operation is rolled back, but I think such cases
> will
> be less and we can find some way to handle such cases may be
> maintainer task only, but the handling will be quite simpler.

Agreed.

> On Windows, patch gives below compilation errors:
> src\backend\access\minmax\mmtuple.c(96): error C2057: expected
> constant expression

I have fixed all these compile errors (fix attached). Thanks for
reporting them. I'll post a new version shortly.

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

Erik Rijkers wrote:

> After a --data-checksums initdb (successful), the following error came up:
>
> after the statement: create index t_minmax_idx on t using minmax (r);
>
> WARNING: page verification failed, calculated checksum 25951 but expected 0
> ERROR: invalid page in block 1 of relation base/21324/26267_vm
>
> it happens reliably. every time I run the program.

Thanks for the report. That's fixed with the attached.

> Below is the whole program that I used.

Hmm, this test program shows that you're trying to use the index to
optimize min() and max() queries, but that's not what these indexes do.
You will need to use operators > >= = <= < (or BETWEEN, which is the
same thing) to see your index in action.

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

Here's an updated version of this patch, with fixes to all the bugs
reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
Amit Kapila for the reports.

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

On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:

> [minmax-5.patch]

I have the impression it's not quite working correctly.

The attached program returns different results for different values of enable_bitmapscan (consistently).

( Btw, I had to make the max_locks_per_transaction higher for even not-so-large tables -- is that expected? For a 100M row
table, max_locks_per_transaction=1024 was not enough; I set it to 2048. Might be worth some documentation, eventually. )

From eyeballing the results it looks like the minmax result (i.e. the result set with enable_bitmapscan = 1) yields only
the last part because the only 'last' rows seem to be present (see the values in column i in table tmm in the attached
program).

Thanks,

Erikjan Rijkers

On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
> On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
>
>> [minmax-5.patch]
>
> I have the impression it's not quite working correctly.
>
> The attached program returns different results for different values of enable_bitmapscan (consistently).
>
> ( Btw, I had to make the max_locks_per_transaction higher for even not-so-large tables -- is that expected? For a 100M row
> table, max_locks_per_transaction=1024 was not enough; I set it to 2048. Might be worth some documentation, eventually. )
>
> From eyeballing the results it looks like the minmax result (i.e. the result set with enable_bitmapscan = 1) yields only
> the last part because the only 'last' rows seem to be present (see the values in column i in table tmm in the attached
> program).

Looking back at that, I realize I should have added a bit more detail on that test.sh program and its output (attached on
previous mail).

test.sh creates a table tmm and a minmax index on that table:

testdb=# \d tmm
Table "public.tmm"
Column | Type | Modifiers
--------+---------+-----------
i | integer |
r | integer |
Indexes:
"tmm_minmax_idx" minmax (r)

The following shows the problem: the same search with minax index on versus off gives different result sets:

testdb=# set enable_bitmapscan=0; select count(*) from tmm where r between symmetric 19494484 and 145288238;
SET
Time: 0.473 ms
count
-------
1261
(1 row)

Time: 7.764 ms
testdb=# set enable_bitmapscan=1; select count(*) from tmm where r between symmetric 19494484 and 145288238;
SET
Time: 0.471 ms
count
-------
3
(1 row)

Time: 1.014 ms

testdb=# set enable_bitmapscan =1; select * from tmm where r between symmetric 19494484 and 145288238;
SET
Time: 0.615 ms
i | r
------+-----------
9945 | 45405603
9951 | 102552485
9966 | 63763962
(3 rows)

Time: 0.984 ms

testdb=# set enable_bitmapscan=0; select * from ( select * from tmm where r between symmetric 19494484 and 145288238 order
by i desc limit 10) f order by i ;
SET
Time: 0.470 ms
i | r
------+-----------
9852 | 114996906
9858 | 69907169
9875 | 43341583
9894 | 127862657
9895 | 44740033
9911 | 51797553
9916 | 58538774
9945 | 45405603
9951 | 102552485
9966 | 63763962
(10 rows)

Time: 8.704 ms
testdb=#

If enable_bitmapscan=1 (i.e. using the minmax index), then only some values are retrieved (in this case 3 rows). It turns
out those are always the last N rows of the full resultset (i.e. with enable_bitmapscan=0).

Erikjan Rijkers

On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Here's an updated version of this patch, with fixes to all the bugs
> reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> Amit Kapila for the reports.

I'm not very happy with the use of a separate relation fork for
storing this data. Using an existing fork number rather than creating
a new one avoids some of them (like, the fact that we loop over all
known fork numbers in various places, and adding another one will add
latency in all of those places, particularly when there is a system
call in the loop) but not all of them (like, what happens if the index
is unlogged? we have provisions to reset the main fork but any others
are just removed; is that OK?), and it also creates some new ones
(like, files having misleading names).

More generally, I fear we really opened a bag of worms with this
relation fork stuff. Every time I turn around I run into a problem
that could be solved by adding another relation fork. I'm not
terribly sure that it was a good idea to go that way to begin with,
because we've got customers who are unhappy about 3 files/heap due to
inode consumption and slow directory lookups. I think we would have
been smarter to devise a strategy for storing the fsm and vm pages
within the main fork in some fashion, and I tend to think that's the
right solution here as well. Of course, it may be hopeless to put the
worms back in the can at this point, and surely these indexes will be
lightly used compared to heaps, so it's not incrementally exacerbating
the problems all that much. But I still feel uneasy about widening
use of that mechanism.

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

Robert Haas escribió:
> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:
> > Here's an updated version of this patch, with fixes to all the bugs
> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> > Amit Kapila for the reports.
>
> I'm not very happy with the use of a separate relation fork for
> storing this data.

I understand this opinion, as I considered it myself while developing
it. Also, GIN already does things this way. Perhaps I should just bite
the bullet and do this.

> Using an existing fork number rather than creating
> a new one avoids some of them (like, the fact that we loop over all
> known fork numbers in various places, and adding another one will add
> latency in all of those places, particularly when there is a system
> call in the loop) but not all of them (like, what happens if the index
> is unlogged? we have provisions to reset the main fork but any others
> are just removed; is that OK?), and it also creates some new ones
> (like, files having misleading names).

All good points.

Index scans will normally access the revmap in sequential fashion; it
would be enough to chain revmap pages, keeping a single block number in
the metapage pointing to the first one, and subsequent ones are accessed
from a "next" block number in each page. However, heap insertion might
need to access a random revmap page, and this would be too slow. I
think it would be enough to keep an array of block numbers in the
index's metapage; the metapage would be share locked on every scan and
insert, but that's not a big deal because exclusive lock would only be
needed on the metapage to extend the revmap, which would be a very
infrequent operation.

As this will require some rework to this code, I think it's fair to mark
this as returned with feedback for the time being. I will return with
an updated version soon, fixing the relation fork issue as well as the
locking and visibility bugs reported by Erik.

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

Erik Rijkers wrote:

> I have the impression it's not quite working correctly.
>
> The attached program returns different results for different values of enable_bitmapscan (consistently).

Clearly there's some bug somewhere. I'll investigate it more.

> ( Btw, I had to make the max_locks_per_transaction higher for even not-so-large tables -- is that expected? For a 100M row
> table, max_locks_per_transaction=1024 was not enough; I set it to 2048. Might be worth some documentation, eventually. )

Not documentation -- that would also be a bug which needs to be fixed.

Thanks for testing.

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

On 9/26/13 12:00 PM, Robert Haas wrote:
> More generally, I fear we really opened a bag of worms with this
> relation fork stuff. Every time I turn around I run into a problem
> that could be solved by adding another relation fork. I'm not
> terribly sure that it was a good idea to go that way to begin with,
> because we've got customers who are unhappy about 3 files/heap due to
> inode consumption and slow directory lookups. I think we would have
> been smarter to devise a strategy for storing the fsm and vm pages
> within the main fork in some fashion, and I tend to think that's the
> right solution here as well. Of course, it may be hopeless to put the
> worms back in the can at this point, and surely these indexes will be
> lightly used compared to heaps, so it's not incrementally exacerbating
> the problems all that much. But I still feel uneasy about widening
> use of that mechanism.

Why would we add additional code complexity when forks do the trick? That seems like a step backwards, not forward.

If the only complaint about forks is directory traversal why wouldn't we go with the well established practice of using multiple directories instead of glomming everything into one place?
--
Jim C. Nasby, Data Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net

On Thu, Sep 26, 2013 at 2:58 PM, Jim Nasby <jim(at)nasby(dot)net> wrote:
> Why would we add additional code complexity when forks do the trick? That
> seems like a step backwards, not forward.

Well, they sorta do the trick, but see e.g. commit
ece01aae479227d9836294b287d872c5a6146a11. I doubt that's the only
code that's poorly-optimized for multiple forks; IOW, every time
someone adds a new fork, there's a system-wide cost to that, even if
that fork is only used in a tiny percentage of the relations that
exist in the system.

It's tempting to think that we can use the fork mechanism every time
we have multiple logical "streams" of blocks within a relation and
don't want to figure out a way to multiplex them onto the same
physical file. However, the reality is that the fork mechanism isn't
up to the job. I certainly don't want to imply that we shouldn't have
gone in that direction - both the fsm and the vm are huge steps
forward, and we wouldn't have gotten them in 8.4 without that
mechanism. But they haven't been entirely without their own pain,
too, and that pain is going to grow the more we push in the direction
of relying on forks.

> If the only complaint about forks is directory traversal why wouldn't we go
> with the well established practice of using multiple directories instead of
> glomming everything into one place?

That's not the only complaint about forks - but I support what you're
proposing there anyhow, because it will be helpful to users with lots
of relations regardless of what we do or do not decide to do about
forks.

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

On Thu, Sep 26, 2013 at 1:46 AM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Amit Kapila escribió:
>> On Sun, Sep 15, 2013 at 5:44 AM, Alvaro Herrera
>> <alvherre(at)2ndquadrant(dot)com> wrote:
>

>
>> On Windows, patch gives below compilation errors:
>> src\backend\access\minmax\mmtuple.c(96): error C2057: expected
>> constant expression
>
> I have fixed all these compile errors (fix attached). Thanks for
> reporting them. I'll post a new version shortly.

Thanks for fixing it. In last few days I had spent some time
reading about minmax or equivalent indexes in other databases (Netezza
and Oracle) and going through some parts of your proposal. Its a bit
bigger patch and needs much more time, but I would like to share my
findings/thoughts I had developed till now.

Firstly about interface and use case, as far as I could understand
other databases provide this index automatically rather than having a
separate Create Index command which may be because such an index can
be mainly useful when the data is ordered or if it's distributed in
such a way that it's quite useful for repeatedly executing queries.
You have proposed it as a command which means user needs to take care
of it which I find is okay for first version, later may be we can also
have some optimisations so that it can get created automatically.
For the page range, If I read correctly, currently you have used hash
define, do you want to expose it to user in some way like GUC or
maintain it internally and assign the right value based on performance
of different queries?

Operations on this index seems to be very fast, like Oracle has this
as an in-memory structure and I read in Netezza that write operations
doesn't carry any significant overhead for zone maps as compare to
other indexes, so shouldn't we consider it to be without WAL logged?
OTOH I think because these structures get automatically created in
those databases, so it might be okay but if we provide it as a
command, then user might be bothered if he didn't find it
automatically on server restart.

Few Questions and observations:
1.
+ When a new heap tuple is inserted in a summarized page range, it is
possible to
+ compare the existing index tuple with the new heap tuple. If the
heap tuple is
+ outside the minimum/maximum boundaries given by the index tuple for
any indexed
+ column (or if the new heap tuple contains null values but the index tuple
+ indicate there are no nulls), it is necessary to create a new index tuple with
+ the new values. To do this, a new index tuple is inserted, and the
reverse range
+ map is updated to point to it. The old index tuple is left in
place, for later
+ garbage collection.

Is there a reason why we can't directly update the value rather then
new insert in index, as I understand for other indexes like btree
we do this because we might need to rollback, but here even if after
updating the min or max value, rollback happens, it will not cause
any harm (tuple loss).

2.
+ If the reverse range map points to an invalid TID, the corresponding
page range
+ is not summarized.

3.
It might be better if you can mention when range map will point to an
invalid TID, it's not explained in your proposal, but you have used it
in you proposal to explain some other things.

4.
Range reverse map is a good terminology, but isn't Range translation
map better. I don't mind either way, it's just a thought came to my
mind while understanding concept of Range Reverse map.

5.
/*
* As above, except that instead of scanning the complete heap, only the given
* range is scanned. Scan to end-of-rel can be signalled by passing
* InvalidBlockNumber as end block number.
*/
double
IndexBuildHeapRangeScan(Relation heapRelation,
Relation indexRelation,
IndexInfo *indexInfo,
bool allow_sync,
BlockNumber start_blockno,
BlockNumber numblocks,
IndexBuildCallback callback,
void *callback_state)

In comments you have used end block number, which parameter does it
refer to? I could see only start_blockno and numb locks?

6.
currently you are passing 0 as start block and InvalidBlockNumber as
number of blocks, what's the logic for it?
return IndexBuildHeapRangeScan(heapRelation, indexRelation,
indexInfo, allow_sync,
0, InvalidBlockNumber,
callback, callback_state);

7.
In mmbuildCallback, it only add's tuple to minmax index, if it
satisfies page range, else this can lead to waste of big scan incase
page range is large (1280 pages as you mentiones in one of your
mails). Why can't we include it end of scan?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Sep 27, 2013 at 11:49 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Thu, Sep 26, 2013 at 1:46 AM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:
>> Amit Kapila escribió:
>>> On Sun, Sep 15, 2013 at 5:44 AM, Alvaro Herrera
>>> <alvherre(at)2ndquadrant(dot)com> wrote:
>>
>
>>
>>> On Windows, patch gives below compilation errors:
>>> src\backend\access\minmax\mmtuple.c(96): error C2057: expected
>>> constant expression
>>
>> I have fixed all these compile errors (fix attached). Thanks for
>> reporting them. I'll post a new version shortly.
>
> Thanks for fixing it. In last few days I had spent some time
> reading about minmax or equivalent indexes in other databases (Netezza
> and Oracle) and going through some parts of your proposal. Its a bit
> bigger patch and needs much more time, but I would like to share my
> findings/thoughts I had developed till now.
>
> Firstly about interface and use case, as far as I could understand
> other databases provide this index automatically rather than having a
> separate Create Index command which may be because such an index can
> be mainly useful when the data is ordered or if it's distributed in
> such a way that it's quite useful for repeatedly executing queries.
> You have proposed it as a command which means user needs to take care
> of it which I find is okay for first version, later may be we can also
> have some optimisations so that it can get created automatically.
> For the page range, If I read correctly, currently you have used hash
> define, do you want to expose it to user in some way like GUC or
> maintain it internally and assign the right value based on performance
> of different queries?
>
> Operations on this index seems to be very fast, like Oracle has this
> as an in-memory structure and I read in Netezza that write operations
> doesn't carry any significant overhead for zone maps as compare to
> other indexes, so shouldn't we consider it to be without WAL logged?
> OTOH I think because these structures get automatically created in
> those databases, so it might be okay but if we provide it as a
> command, then user might be bothered if he didn't find it
> automatically on server restart.
>
> Few Questions and observations:
> 1.
> + When a new heap tuple is inserted in a summarized page range, it is
> possible to
> + compare the existing index tuple with the new heap tuple. If the
> heap tuple is
> + outside the minimum/maximum boundaries given by the index tuple for
> any indexed
> + column (or if the new heap tuple contains null values but the index tuple
> + indicate there are no nulls), it is necessary to create a new index tuple with
> + the new values. To do this, a new index tuple is inserted, and the
> reverse range
> + map is updated to point to it. The old index tuple is left in
> place, for later
> + garbage collection.
>
>
> Is there a reason why we can't directly update the value rather then
> new insert in index, as I understand for other indexes like btree
> we do this because we might need to rollback, but here even if after
> updating the min or max value, rollback happens, it will not cause
> any harm (tuple loss).
>
> 2.
> + If the reverse range map points to an invalid TID, the corresponding
> page range
> + is not summarized.
>
> 3.
> It might be better if you can mention when range map will point to an
> invalid TID, it's not explained in your proposal, but you have used it
> in you proposal to explain some other things.
>
> 4.
> Range reverse map is a good terminology, but isn't Range translation
> map better. I don't mind either way, it's just a thought came to my
> mind while understanding concept of Range Reverse map.
>
> 5.
> /*
> * As above, except that instead of scanning the complete heap, only the given
> * range is scanned. Scan to end-of-rel can be signalled by passing
> * InvalidBlockNumber as end block number.
> */
> double
> IndexBuildHeapRangeScan(Relation heapRelation,
> Relation indexRelation,
> IndexInfo *indexInfo,
> bool allow_sync,
> BlockNumber start_blockno,
> BlockNumber numblocks,
> IndexBuildCallback callback,
> void *callback_state)
>
> In comments you have used end block number, which parameter does it
> refer to? I could see only start_blockno and numb locks?
>
> 6.
> currently you are passing 0 as start block and InvalidBlockNumber as
> number of blocks, what's the logic for it?
> return IndexBuildHeapRangeScan(heapRelation, indexRelation,
> indexInfo, allow_sync,
> 0, InvalidBlockNumber,
> callback, callback_state);

I got it, I think here it means scan all the pages.

> 7.
> In mmbuildCallback, it only add's tuple to minmax index, if it
> satisfies page range, else this can lead to waste of big scan incase
> page range is large (1280 pages as you mentiones in one of your
> mails). Why can't we include it end of scan?
>
>
> With Regards,
> Amit Kapila.
> EnterpriseDB: http://www.enterprisedb.com

On 9/26/13 2:46 PM, Robert Haas wrote:
> On Thu, Sep 26, 2013 at 2:58 PM, Jim Nasby <jim(at)nasby(dot)net> wrote:
>> Why would we add additional code complexity when forks do the trick? That
>> seems like a step backwards, not forward.
>
> Well, they sorta do the trick, but see e.g. commit
> ece01aae479227d9836294b287d872c5a6146a11. I doubt that's the only
> code that's poorly-optimized for multiple forks; IOW, every time
> someone adds a new fork, there's a system-wide cost to that, even if
> that fork is only used in a tiny percentage of the relations that
> exist in the system.

Yeah, we obviously kept things simpler when adding forks in order to get the feature out the door. There's improvements that need to be made. But IMHO that's not reason to automatically avoid forks; we need to consider the cost of improving them vs what we gain by using them.

Of course there's always some added cost so we shouldn't just blindly use them all over the place without considering the fork cost either...

> It's tempting to think that we can use the fork mechanism every time
> we have multiple logical "streams" of blocks within a relation and
> don't want to figure out a way to multiplex them onto the same
> physical file. However, the reality is that the fork mechanism isn't
> up to the job. I certainly don't want to imply that we shouldn't have
> gone in that direction - both the fsm and the vm are huge steps
> forward, and we wouldn't have gotten them in 8.4 without that
> mechanism. But they haven't been entirely without their own pain,
> too, and that pain is going to grow the more we push in the direction
> of relying on forks.

Agreed.

Honestly, I think we actually need more obfuscation between what happens on the filesystem and the rest of postgres... we're starting to look at areas where that would help. For example, the recent idea of being able to truncate individual relation files and not being limited to only truncating the end of the relation. My concern in that case is that 1GB is a pretty arbitrary size that we happened to pick, so if we're going to go for more efficiency in storage we probably shouldn't just blindly stick with 1G (though of course initial implementation might do that to reduce complexity, but we better still consider where we're headed).

>> If the only complaint about forks is directory traversal why wouldn't we go
>> with the well established practice of using multiple directories instead of
>> glomming everything into one place?
>
> That's not the only complaint about forks - but I support what you're
> proposing there anyhow, because it will be helpful to users with lots
> of relations regardless of what we do or do not decide to do about
> forks.
>

--
Jim C. Nasby, Data Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net

On Fri, Sep 27, 2013 at 7:22 PM, Jim Nasby <jim(at)nasby(dot)net> wrote:
>
> Yeah, we obviously kept things simpler when adding forks in order to get the feature out the door. There's improvements that need to be made. But IMHO that's not reason to automatically avoid forks; we need to consider the cost of improving them vs what we gain by using them.

We think this gives short change to the decision to introduce forks.
If you go back to the discussion at the time it was a topic of debate
and the argument which won the day is that interleaving different
streams of data in one storage system is exactly what the file system
is designed to do and we would just be reinventing the wheel if we
tried to do it ourselves. I think that makes a lot of sense for things
like the fsm or vm which grow indefinitely and are maintained by a
different piece of code from the main heap.

The tradeoff might be somewhat different for the pieces of a data
structure like a bitmap index or gin index where the code responsible
for maintaining it is all the same.

> Honestly, I think we actually need more obfuscation between what happens on the filesystem and the rest of postgres... we're starting to look at areas where that would help. For example, the recent idea of being able to truncate individual relation files and not being limited to only truncating the end of the relation. My concern in that case is that 1GB is a pretty arbitrary size that we happened to pick, so if we're going to go for more efficiency in storage we probably shouldn't just blindly stick with 1G (though of course initial implementation might do that to reduce complexity, but we better still consider where we're headed).

The ultimate goal here would be to get the filesystem to issue a TRIM
call so an SSD storage system can reuse the underlying blocks.
Truncating 1GB files might be a convenient way to do it, especially if
we have some new kind of vacuum full that can pack tuples within each
1GB file.

But there may be easier ways to achieve the same thing. If we can
notify the filesystem that we're not using some of the blocks in the
middle of the file we might be able to just leave things where they
are and have holes in the files. Or we might be better off not
depending on truncate and just look for ways to mark entire 1GB files
as "deprecated" and move tuples out of them until we can just remove
that whole file.

--
greg

On 9/27/13 1:43 PM, Greg Stark wrote:
>> Honestly, I think we actually need more obfuscation between what happens on the filesystem and the rest of postgres... we're starting to look at areas where that would help. For example, the recent idea of being able to truncate individual relation files and not being limited to only truncating the end of the relation. My concern in that case is that 1GB is a pretty arbitrary size that we happened to pick, so if we're going to go for more efficiency in storage we probably shouldn't just blindly stick with 1G (though of course initial implementation might do that to reduce complexity, but we better still consider where we're headed).
> The ultimate goal here would be to get the filesystem to issue a TRIM
> call so an SSD storage system can reuse the underlying blocks.
> Truncating 1GB files might be a convenient way to do it, especially if
> we have some new kind of vacuum full that can pack tuples within each
> 1GB file.
>
> But there may be easier ways to achieve the same thing. If we can
> notify the filesystem that we're not using some of the blocks in the
> middle of the file we might be able to just leave things where they
> are and have holes in the files. Or we might be better off not
> depending on truncate and just look for ways to mark entire 1GB files
> as "deprecated" and move tuples out of them until we can just remove
> that whole file.

Yeah, there's a ton of different things we might do. And dealing with free space is just one example... things like the VM give us the ability to detect areas of the heap that have gone "dormant"; imagine if we could seamlessly move that data to it's own storage, possibly compressing it at the same time. (Yes, I realize there's partitioning and tablespaces and compressing filesystems, but those are a lot more work and will never be as efficient as what the database itself can do).

Anyway, I think we're all on the same page. We should stop hijacking Alvaro's thread... ;)
--
Jim C. Nasby, Data Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net

On 27.09.2013 21:43, Greg Stark wrote:
> On Fri, Sep 27, 2013 at 7:22 PM, Jim Nasby<jim(at)nasby(dot)net> wrote:
>>
>> Yeah, we obviously kept things simpler when adding forks in order to get the feature out the door. There's improvements that need to be made. But IMHO that's not reason to automatically avoid forks; we need to consider the cost of improving them vs what we gain by using them.
>
> We think this gives short change to the decision to introduce forks.
> If you go back to the discussion at the time it was a topic of debate
> and the argument which won the day is that interleaving different
> streams of data in one storage system is exactly what the file system
> is designed to do and we would just be reinventing the wheel if we
> tried to do it ourselves. I think that makes a lot of sense for things
> like the fsm or vm which grow indefinitely and are maintained by a
> different piece of code from the main heap.
>
> The tradeoff might be somewhat different for the pieces of a data
> structure like a bitmap index or gin index where the code responsible
> for maintaining it is all the same.

There are quite a dfew cases where we have several "streams" of data,
all related to a single relation. We've solved them all in slightly
different ways:

1. TOAST. A separate heap relation with accompanying b-tree index is
created.

2. GIN. GIN contains a b-tree, and data pages (and somer other kinds of
pages too IIRC). It would be natural to use the regular B-tree code for
the B-tree, but instead it contains a completely separate
implementation. All the different kinds of streams are stored in the
main fork.

3. Free space map. Stored as a separate fork.

4. Visibility map. Stored as a separate fork.

And upcoming:

5. Minmax indexes, with the linearly-addressed range reverse map and
variable lenghth index tuples.

6. Bitmap indexes. Like in GIN, there's a B-tree and the data pages
containing the bitmaps.

A nice property of the VM and FSM forks currently is that they are just
auxiliary information to speed things up. You can safely remove them
(when the server is shut down), and the system will recreate them on
next vacuum. It's not carved in stone that it has to be that way for all
extra forks, but it is today and I like it.

I feel we need a new kind of a relation fork, something more
heavy-weight than the current forks, but not as heavy-weight as the way
TOAST does it. It would be nice if GIN and bitmap indexes could use the
regular nbtree code. Or any other index type - imagine a bitmap index
using a SP-GiST index instead of a B-tree! You could create a bitmap
index for 2d points, and use it to speed up operations like overlap for
example.

The nbtree code expects the data to be in the main fork and uses the FSM
fork too. Maybe it could be abstracted, so that the regular b-tree could
be used as part of another index type. Same with other indexams.

Perhaps relation forks need to be made more flexible, allowing access
methods to define what forks exists. IOW, let's not avoid using relation
forks, let's make them better instead.

- Heikki

What would it take to abstract the minmax indexes to allow maintaing a
bounding box for points, instead of a plain min/max? Or for ranges. In
other words, why is this restricted to b-tree operators?

- Heikki

On Mon, Sep 30, 2013 at 02:17:39PM +0300, Heikki Linnakangas wrote:
> What would it take to abstract the minmax indexes to allow maintaing
> a bounding box for points, instead of a plain min/max? Or for
> ranges. In other words, why is this restricted to b-tree operators?

If I had to guess, I'd guess, "first cut."

I take it this also occurred to you and that you believe that this
approach makes the more general case or at least further out than it
would need to be. Am I close?

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

David Fetter wrote:
> On Mon, Sep 30, 2013 at 02:17:39PM +0300, Heikki Linnakangas wrote:
> > What would it take to abstract the minmax indexes to allow maintaing
> > a bounding box for points, instead of a plain min/max? Or for
> > ranges. In other words, why is this restricted to b-tree operators?
>
> If I had to guess, I'd guess, "first cut."

Yeah, there were a few other simplifications in the design too, though I
admit allowing for multidimensional dataypes hadn't occured to me
(though I will guess Simon did think about it and just didn't tell me to
avoid me going overboard with stuff that would make the first version
take forever).

I think we'd better add version numbers and stuff to the metapage to
allow for extensions and proper upgradability.

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

On 30.09.2013 19:49, Alvaro Herrera wrote:
> David Fetter wrote:
>> On Mon, Sep 30, 2013 at 02:17:39PM +0300, Heikki Linnakangas wrote:
>>> What would it take to abstract the minmax indexes to allow maintaing
>>> a bounding box for points, instead of a plain min/max? Or for
>>> ranges. In other words, why is this restricted to b-tree operators?
>>
>> If I had to guess, I'd guess, "first cut."
>
> Yeah, there were a few other simplifications in the design too, though I
> admit allowing for multidimensional dataypes hadn't occured to me

You can almost create a bounding box opclass in the current
implementation, by mapping < operator to "contains" and > to "not
contains". But there's no support for creating a new, larger, bounding
box on insert. It will just replace the max with the new value if it's
"greater than", when it should create a whole new value to store in the
index that covers both the old and the new values. (or less than? I'm
not sure which way those operators would work..)

When you think of the general case, it's weird that the current
implementation requires storing both the min and the max. For a bounding
box, you store the bounding box that covers all heap tuples in the
range. If that corresponds to "max", what does "min" mean?

In fact, even with regular b-tree operators, over integers for example,
you don't necessarily want to store both min and max. If you only ever
perform queries like "WHERE col > ?", there's no need to track the min
value. So to make this really general, you should be able to create an
index on only the minimum or maximum. Or if you want both, you can store
them as separate index columns. Something like:

CREATE INDEX minindex ON table (col ASC); -- For min
CREATE INDEX minindex ON table (col DESC); -- For max
CREATE INDEX minindex ON table (col ASC, col DESC); -- For both

That said, in practice most people probably want to store both min and
max. Maybe it's a bit too finicky if we require people to write "col
ASC, col DESC" to get that. Some kind of a shorthand probably makes sense.

> (though I will guess Simon did think about it and just didn't tell me to
> avoid me going overboard with stuff that would make the first version
> take forever).

Heh, and I ruined that great plan :-).

- Heikki

On Mon, Sep 30, 2013 at 1:20 PM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> You can almost create a bounding box opclass in the current implementation,
> by mapping < operator to "contains" and > to "not contains". But there's no
> support for creating a new, larger, bounding box on insert. It will just
> replace the max with the new value if it's "greater than", when it should
> create a whole new value to store in the index that covers both the old and
> the new values. (or less than? I'm not sure which way those operators would
> work..)

This sounds an awful lot like GiST's "union" operation. Actually,
following the GiST model of having "union" and "consistent" operations
might be a smart way to go. Then the exact index semantics could be
decided by the opclass. This might not even be that much extra code;
the existing consistent and union functions for GiST are pretty short.
That way, it'd be easy to add new opclasses with somewhat different
behavior; the common thread would be that every opclass of this new AM
works by summarizing a physical page range into a single indexed
value. You might call the AM something like "summary" or "sparse" and
then have "minmax_ops" for your first opclass.

> In fact, even with regular b-tree operators, over integers for example, you
> don't necessarily want to store both min and max. If you only ever perform
> queries like "WHERE col > ?", there's no need to track the min value. So to
> make this really general, you should be able to create an index on only the
> minimum or maximum. Or if you want both, you can store them as separate
> index columns. Something like:
>
> CREATE INDEX minindex ON table (col ASC); -- For min
> CREATE INDEX minindex ON table (col DESC); -- For max
> CREATE INDEX minindex ON table (col ASC, col DESC); -- For both

This doesn't seem very general, since you're relying on the fact that
ASC and DESC map to < and >. It's not clear what you'd write here if
you wanted to optimize #$ and @!. But something based on opclasses
will work, since each opclass can support an arbitrary set of
operators.

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

Erik Rijkers wrote:
> On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
> > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
> >
> >> [minmax-5.patch]
> >
> > I have the impression it's not quite working correctly.

Here's a version 7 of the patch, which fixes these bugs and adds
opclasses for a bunch more types (timestamp, timestamptz, date, time,
timetz), courtesy of Martín Marqués. It's also been rebased to apply
cleanly on top of today's master branch.

I have also added a selectivity function, but I'm not positive that it's
very useful yet.

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

Robert Haas escribió:
> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:
> > Here's an updated version of this patch, with fixes to all the bugs
> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> > Amit Kapila for the reports.
>
> I'm not very happy with the use of a separate relation fork for
> storing this data.

I have been playing with having the revmap in the main fork of the index
rather than a separate one. On the surface many things stay just what
they are; I only had to add a layer beneath the revmap that maps its
logical block numbers to physical block numbers. The problem with this
is that it needs more disk access, because revmap block numbers cannot be
hardcoded.

After doing some quick math, what I ended up with was to keep an array
of BlockNumbers in the metapage. Each element in this array points to
array pages; each array page is, in turn, filled with more BlockNumbers,
which this time correspond to the logical revmap pages we used to have
in the revmap fork. (I initially feared that this design would not
allow me to address enough revmap pages for the largest of tables; but
fortunately this is sufficient unless you configure very small pages,
say BLCKSZ 2kB, use small page ranges, and use small datatypes, say
"char". I have no problem with saying that that scenario is not
supported if you want to have minmax indexes on 32 TB tables. I mean,
who uses BLCKSZ smaller than 8kB anyway?).

The advantage of this design is that in order to find any particular
logical revmap page, you always have to do a constant number of page
accesses. You read the metapage, then read the array page, then read
the revmap page; done. Another idea I considered was chaining revmap
pages (so each would have a pointer-to-next), or chaining array pages;
but this would have meant that to locate an individual page to the end
of the revmap, you might need to do many accesses. Not good.

As an optimization for relatively small indexes, we hardcode the page
number for the first revmap page: it's always the page right after the
metapage (so BlockNumber 1). A revmap page can store, with the default
page size, about 1350 item pointers; so with an index built for page
ranges of 1000 pages per range, you can point to enough index entries
for a ~10 GB table without having the need to examine the first array
page. This seems pretty acceptable; people with larger tables can
likely spare one extra page accessed every now and then.
(For comparison, each regular minmax page can store about 500 index
tuples, if it's built for a single 4-byte column; this means that the 10
GB table requires a 5-page index.)

This is not complete yet; although I have a proof-of-concept working, I
still need to write XLog support code and update the pageinspect code to
match.

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

Alvaro Herrera escribió:

> I have been playing with having the revmap in the main fork of the index
> rather than a separate one.
...
> This is not complete yet; although I have a proof-of-concept working, I
> still need to write XLog support code and update the pageinspect code to
> match.

Just to be clear: the v7 published elsewhere in this thread does not
contain this revmap-in-main-fork code.

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

On Fri, November 8, 2013 21:11, Alvaro Herrera wrote:
>
> Here's a version 7 of the patch, which fixes these bugs and adds
> opclasses for a bunch more types (timestamp, timestamptz, date, time,
> timetz), courtesy of Martín Marqués. It's also been rebased to apply
> cleanly on top of today's master branch.
>
> I have also added a selectivity function, but I'm not positive that it's
> very useful yet.
>
> [minmax-7.patch]

The earlier errors are indeed fixed; now, I've been trying with the attached test case but I'm unable to find a query that
improves with minmax index use. (it gets used sometimes but speedup is negligable).

That probably means I'm doing something wrong; could you (or anyone) give some hints about use-case would be expected?

(Or is it just the unfinished selectivity function?)

Thanks,

Erikjan Rijkers

On Mon, November 11, 2013 09:53, Erik Rijkers wrote:
> On Fri, November 8, 2013 21:11, Alvaro Herrera wrote:
>>
>> Here's a version 7 of the patch, which fixes these bugs and adds
>> opclasses for a bunch more types (timestamp, timestamptz, date, time,
>> timetz), courtesy of Martín Marqués. It's also been rebased to apply
>> cleanly on top of today's master branch.
>>
>> I have also added a selectivity function, but I'm not positive that it's
>> very useful yet.
>>
>> [minmax-7.patch]
>
> The earlier errors are indeed fixed; now, I've been trying with the attached test case but I'm unable to find a query that
> improves with minmax index use. (it gets used sometimes but speedup is negligable).
>

Another issue (I think):

Attached is a program (and output as a .txt file) that gives the following (repeatable) error:

$ ./casanova_test.sh
\timing on
drop table if exists t1;
Time: 333.159 ms
create table t1 (i int);
Time: 155.827 ms
create index t1_i_idx on t1 using minmax(i);
Time: 204.031 ms
insert into t1 select generate_series(1, 25000000);
Time: 126312.302 ms
analyze t1;
ERROR: could not truncate file base/21324/26339_vm to 41 blocks: it's only 1 blocks now
Time: 472.504 ms
[...]

Thanks,

Erik Rijkers

On Mon, Nov 11, 2013 at 12:53 AM, Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> On Fri, November 8, 2013 21:11, Alvaro Herrera wrote:
> >
> > Here's a version 7 of the patch, which fixes these bugs and adds
> > opclasses for a bunch more types (timestamp, timestamptz, date, time,
> > timetz), courtesy of Martín Marqués. It's also been rebased to apply
> > cleanly on top of today's master branch.
> >
> > I have also added a selectivity function, but I'm not positive that it's
> > very useful yet.
> >
> > [minmax-7.patch]
>
> The earlier errors are indeed fixed; now, I've been trying with the
> attached test case but I'm unable to find a query that
> improves with minmax index use. (it gets used sometimes but speedup is
> negligable).
>

Your data set seems to be completely random. I believe that minmax indices
would only be expected to be useful when the data is clustered. Perhaps
you could try it on a table where it is populated something like
i+random()/10*max_i.

Cheers,

Jeff

On Mon, November 11, 2013 09:53, Erik Rijkers wrote:
> On Fri, November 8, 2013 21:11, Alvaro Herrera wrote:
>>
>> Here's a version 7 of the patch, which fixes these bugs and adds
>>
>> [minmax-7.patch]
[...]
> some hints about use-case would be expected?
>

I've been messing with minmax indexes some more so here are some results of that.

Perhaps someone finds these timings useful.

Centos 5.7, 32 GB memory, 2 quadcores.

'--prefix=/var/data1/pg_stuff/pg_installations/pgsql.minmax' '--with-pgport=6444' '--enable-depend' '--enable-cassert'
'--enable-debug' '--with-perl' '--with-openssl' '--with-libxml' '--enable-dtrace'

Detail is in the attached files; the below is a grep through these.

-- rowcount (size_string): 10_000
368,640 | size table
245,760 | size btree index
16,384 | size minmax index
Total runtime: 0.167 ms <-- btree (4x) ( last 2x disabled index-only )
Total runtime: 0.046 ms
Total runtime: 0.046 ms
Total runtime: 0.049 ms
Total runtime: 0.102 ms <-- minmax (4x)
Total runtime: 0.047 ms
Total runtime: 0.047 ms
Total runtime: 0.047 ms
Total runtime: 1.066 ms <-- seqscan

-- rowcount (size_string): 100_000
3,629,056 | size table
2,260,992 | size btree index
16,384 | size minmax index
Total runtime: 0.090 ms <-- btree (4x) ( last 2x disabled index-only )
Total runtime: 0.046 ms
Total runtime: 0.426 ms
Total runtime: 0.287 ms
Total runtime: 0.391 ms <-- minmax (4x)
Total runtime: 0.285 ms
Total runtime: 0.285 ms
Total runtime: 0.291 ms
Total runtime: 14.065 ms <-- seqscan

-- rowcount (size_string): 1_000_000
36,249,600 | size table
22,487,040 | size btree index
57,344 | size minmax index
Total runtime: 0.077 ms <-- btree (4x) ( last 2x disabled index-only )
Total runtime: 0.048 ms
Total runtime: 0.044 ms
Total runtime: 0.038 ms
Total runtime: 2.284 ms <-- minmax (4x)
Total runtime: 1.812 ms
Total runtime: 1.813 ms
Total runtime: 1.809 ms
Total runtime: 142.958 ms <-- seqscan

-- rowcount (size_string): 100_000_000
3,624,779,776 | size table
2,246,197,248 | size btree index
4,456,448 | size minmax index
Total runtime: 0.091 ms <-- btree (4x) ( last 2x disabled index-only )
Total runtime: 0.047 ms
Total runtime: 0.046 ms
Total runtime: 0.038 ms
Total runtime: 181.874 ms <-- minmax (4x)
Total runtime: 175.084 ms
Total runtime: 175.104 ms
Total runtime: 174.349 ms
Total runtime: 14833.994 ms <-- seqscan

-- rowcount (size_string): 1_000_000_000
36,247,789,568 | size table
22,461,628,416 | size btree index
44,433,408 | size minmax index
Total runtime: 14.735 ms <-- btree (4x) ( last 2x disabled index-only )
Total runtime: 0.046 ms
Total runtime: 0.044 ms
Total runtime: 0.041 ms
Total runtime: 1790.591 ms <-- minmax (4x)
Total runtime: 1750.129 ms
Total runtime: 1747.987 ms
Total runtime: 1748.476 ms
Total runtime: 169770.455 ms <-- seqscan

The messy "program" is attached too (although it still has Jaime's name, the mess is mine).

hth,

Erik Rijkers

PS.
The bug I reported earlier is (of course) still there; but I noticed that it only occurs on larger table sizes (e.g. +1M
rows).

On 2013-11-15 17:11:46 +0100, Erik Rijkers wrote:
> I've been messing with minmax indexes some more so here are some results of that.
>
> Perhaps someone finds these timings useful.
>
>
> Centos 5.7, 32 GB memory, 2 quadcores.
>
> '--prefix=/var/data1/pg_stuff/pg_installations/pgsql.minmax' '--with-pgport=6444' '--enable-depend' '--enable-cassert'
> '--enable-debug' '--with-perl' '--with-openssl' '--with-libxml' '--enable-dtrace'

Just some general advice: doing timings with --enale-cassert isn't that
meaningful - it often can distort results significantly.

Greetings,

Andres Freund

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

Erik Rijkers <er(at)xs4all(dot)nl> wrote:

> Perhaps someone finds these timings useful.

> '--enable-cassert'

Assertions can really distort the timings, and not always equally
for all code paths.  Any chance of re-running those tests without
that?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, November 15, 2013 17:33, Kevin Grittner wrote:
> Erik Rijkers <er(at)xs4all(dot)nl> wrote:
>
>> Perhaps someone finds these timings useful.
>
>> '--enable-cassert'
>
> Assertions can really distort the timings, and not always equally
> for all code paths.  Any chance of re-running those tests without
> that?
>

Fair enough. It seems it doesn't make all that much difference for this case, here are the results:

'--prefix=/var/data1/pg_stuff/pg_installations/pgsql.minmax' '--with-pgport=6444' '--enable-depend' '--with-perl'
'--with-openssl' '--with-libxml'

-- rowcount (size_string): 10_000
368640 | size table | 360 kB
245760 | size btree index | 240 kB
16384 | size minmax index | 16 kB
Total runtime: 0.121 ms
Total runtime: 0.041 ms
Total runtime: 0.039 ms
Total runtime: 0.040 ms
Total runtime: 0.043 ms
Total runtime: 0.041 ms
Total runtime: 0.040 ms
Total runtime: 0.040 ms
Total runtime: 0.948 ms

-- rowcount (size_string): 100_000
3629056 | size table | 3544 kB
2260992 | size btree index | 2208 kB
16384 | size minmax index | 16 kB
Total runtime: 0.082 ms
Total runtime: 0.039 ms
Total runtime: 0.396 ms
Total runtime: 0.252 ms
Total runtime: 0.339 ms
Total runtime: 0.245 ms
Total runtime: 0.240 ms
Total runtime: 0.241 ms
Total runtime: 13.268 ms

-- rowcount (size_string): 1_000_000
36249600 | size table | 35 MB
22487040 | size btree index | 21 MB
57344 | size minmax index | 56 kB
Total runtime: 0.096 ms
Total runtime: 0.039 ms
Total runtime: 0.039 ms
Total runtime: 0.034 ms
Total runtime: 1.975 ms
Total runtime: 1.527 ms
Total runtime: 1.523 ms
Total runtime: 1.519 ms
Total runtime: 145.125 ms

-- rowcount (size_string): 100_000_000
3624779776 | size table | 3457 MB
2246197248 | size btree index | 2142 MB
4456448 | size minmax index | 4352 kB
Total runtime: 0.074 ms
Total runtime: 0.039 ms
Total runtime: 0.040 ms
Total runtime: 0.033 ms
Total runtime: 150.450 ms
Total runtime: 147.039 ms
Total runtime: 145.410 ms
Total runtime: 145.142 ms
Total runtime: 15068.171 ms

-- rowcount (size_string): 1_000_000_000
36247789568 | size table | 34 GB
22461628416 | size btree index | 21 GB
44433408 | size minmax index | 42 MB
Total runtime: 15.454 ms <-- 4x btree
Total runtime: 0.040 ms
Total runtime: 0.040 ms
Total runtime: 0.034 ms
Total runtime: 1502.353 ms <-- 4x minmax
Total runtime: 1482.322 ms
Total runtime: 1489.522 ms
Total runtime: 1481.424 ms
Total runtime: 162213.392 ms <-- seqscan

I'd say minmax indexes give spectacular gains for very small indexsize.

Erik Rijkers

On Fri, Nov 8, 2013 at 12:11 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>wrote:

> Erik Rijkers wrote:
> > On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
> > > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
> > >
> > >> [minmax-5.patch]
> > >
> > > I have the impression it's not quite working correctly.
>
> Here's a version 7 of the patch, which fixes these bugs and adds
> opclasses for a bunch more types (timestamp, timestamptz, date, time,
> timetz), courtesy of Martín Marqués. It's also been rebased to apply
> cleanly on top of today's master branch.
>
> I have also added a selectivity function, but I'm not positive that it's
> very useful yet.
>

I tested it with attached script, but broke out of the "for" loop after 5
iterations (when it had 300,000,005 rows inserted)

Then I did an analyze, and got an error message below:

jjanes=# analyze;
ERROR: could not truncate file "base/16384/16388_vm" to 488 blocks: it's
only 82 blocks now

16388 is the index's relfilenode.

Here is the backtrace upon entry to the truncate that is going to fail:

#0 mdtruncate (reln=0x23c91b0, forknum=VISIBILITYMAP_FORKNUM, nblocks=488)
at md.c:858
#1 0x000000000048eb4a in mmRevmapTruncate (rmAccess=0x26ad878,
heapNumBlocks=1327434) at mmrevmap.c:360
#2 0x000000000048d37a in mmvacuumcleanup (fcinfo=<value optimized out>) at
minmax.c:1264
#3 0x000000000072dcef in FunctionCall2Coll (flinfo=<value optimized out>,
collation=<value optimized out>, arg1=<value optimized out>,
arg2=<value optimized out>) at fmgr.c:1323
#4 0x000000000048c1e5 in index_vacuum_cleanup (info=<value optimized out>,
stats=0x0) at indexam.c:715
#5 0x000000000052a7ce in do_analyze_rel (onerel=0x7f59798589e8,
vacstmt=0x23b0bd8, acquirefunc=0x5298d0 <acquire_sample_rows>,
relpages=1327434,
inh=0 '\000', elevel=13) at analyze.c:634
#6 0x000000000052b320 in analyze_rel (relid=<value optimized out>,
vacstmt=0x23b0bd8, bstrategy=<value optimized out>) at analyze.c:267
#7 0x000000000057cba7 in vacuum (vacstmt=0x23b0bd8, relid=<value optimized
out>, do_toast=1 '\001', bstrategy=<value optimized out>,
for_wraparound=0 '\000', isTopLevel=<value optimized out>) at
vacuum.c:249
#8 0x0000000000663177 in standard_ProcessUtility (parsetree=0x23b0bd8,
queryString=<value optimized out>, context=<value optimized out>,
params=0x0,
dest=<value optimized out>, completionTag=<value optimized out>) at
utility.c:682
#9 0x00007f598290b791 in pgss_ProcessUtility (parsetree=0x23b0bd8,
queryString=0x23b0220 "analyze \n;", context=PROCESS_UTILITY_TOPLEVEL,
params=0x0,
dest=0x23b0f18, completionTag=0x7fffd3442f30 "") at
pg_stat_statements.c:825
#10 0x000000000065fcf7 in PortalRunUtility (portal=0x24195e0,
utilityStmt=0x23b0bd8, isTopLevel=1 '\001', dest=0x23b0f18,
completionTag=0x7fffd3442f30 "")
at pquery.c:1187
#11 0x0000000000660c6d in PortalRunMulti (portal=0x24195e0, isTopLevel=1
'\001', dest=0x23b0f18, altdest=0x23b0f18, completionTag=0x7fffd3442f30 "")
at pquery.c:1318
#12 0x0000000000661323 in PortalRun (portal=0x24195e0,
count=9223372036854775807, isTopLevel=1 '\001', dest=0x23b0f18,
altdest=0x23b0f18,
completionTag=0x7fffd3442f30 "") at pquery.c:816
#13 0x000000000065dbb4 in exec_simple_query (query_string=0x23b0220
"analyze \n;") at postgres.c:1048
#14 0x000000000065f259 in PostgresMain (argc=<value optimized out>,
argv=<value optimized out>, dbname=0x2347be8 "jjanes", username=<value
optimized out>)
at postgres.c:3992
#15 0x000000000061b7d0 in BackendRun (argc=<value optimized out>,
argv=<value optimized out>) at postmaster.c:4085
#16 BackendStartup (argc=<value optimized out>, argv=<value optimized out>)
at postmaster.c:3774
#17 ServerLoop (argc=<value optimized out>, argv=<value optimized out>) at
postmaster.c:1585
#18 PostmasterMain (argc=<value optimized out>, argv=<value optimized out>)
at postmaster.c:1240
#19 0x00000000005b5e90 in main (argc=3, argv=0x2346cd0) at main.c:196

Cheers,

Jeff

On 8 November 2013 20:11, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> Erik Rijkers wrote:
>> On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
>> > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
>> >
>> >> [minmax-5.patch]
>> >
>> > I have the impression it's not quite working correctly.
>
> Here's a version 7 of the patch, which fixes these bugs and adds
> opclasses for a bunch more types (timestamp, timestamptz, date, time,
> timetz), courtesy of Martín Marqués. It's also been rebased to apply
> cleanly on top of today's master branch.
>
> I have also added a selectivity function, but I'm not positive that it's
> very useful yet.

This patch doesn't appear to have been submitted to any Commitfest.
Is this still a feature undergoing research then?

--
Thom

Thom Brown wrote:
> On 8 November 2013 20:11, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> > Erik Rijkers wrote:
> >> On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
> >> > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
> >> >
> >> >> [minmax-5.patch]
> >> >
> >> > I have the impression it's not quite working correctly.
> >
> > Here's a version 7 of the patch, which fixes these bugs and adds
> > opclasses for a bunch more types (timestamp, timestamptz, date, time,
> > timetz), courtesy of Martín Marqués. It's also been rebased to apply
> > cleanly on top of today's master branch.
> >
> > I have also added a selectivity function, but I'm not positive that it's
> > very useful yet.
>
> This patch doesn't appear to have been submitted to any Commitfest.
> Is this still a feature undergoing research then?

It's still a planned feature, but I didn't have time to continue work
for 2014-01.

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

On 24 January 2014 17:53, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> Thom Brown wrote:
>> On 8 November 2013 20:11, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>> > Erik Rijkers wrote:
>> >> On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
>> >> > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
>> >> >
>> >> >> [minmax-5.patch]
>> >> >
>> >> > I have the impression it's not quite working correctly.
>> >
>> > Here's a version 7 of the patch, which fixes these bugs and adds
>> > opclasses for a bunch more types (timestamp, timestamptz, date, time,
>> > timetz), courtesy of Martín Marqués. It's also been rebased to apply
>> > cleanly on top of today's master branch.
>> >
>> > I have also added a selectivity function, but I'm not positive that it's
>> > very useful yet.
>>
>> This patch doesn't appear to have been submitted to any Commitfest.
>> Is this still a feature undergoing research then?
>
> It's still a planned feature, but I didn't have time to continue work
> for 2014-01.

Alles klar.

Thanks

--
Thom

On Fri, Jan 24, 2014 at 2:54 PM, Thom Brown <thom(at)linux(dot)com> wrote:
> On 24 January 2014 17:53, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>> Thom Brown wrote:
>>> On 8 November 2013 20:11, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>>> > Erik Rijkers wrote:
>>> >> On Thu, September 26, 2013 00:34, Erik Rijkers wrote:
>>> >> > On Wed, September 25, 2013 22:34, Alvaro Herrera wrote:
>>> >> >
>>> >> >> [minmax-5.patch]
>>> >> >
>>> >> > I have the impression it's not quite working correctly.
>>> >
>>> > Here's a version 7 of the patch, which fixes these bugs and adds
>>> > opclasses for a bunch more types (timestamp, timestamptz, date, time,
>>> > timetz), courtesy of Martín Marqués. It's also been rebased to apply
>>> > cleanly on top of today's master branch.
>>> >
>>> > I have also added a selectivity function, but I'm not positive that it's
>>> > very useful yet.
>>>
>>> This patch doesn't appear to have been submitted to any Commitfest.
>>> Is this still a feature undergoing research then?
>>
>> It's still a planned feature, but I didn't have time to continue work
>> for 2014-01.

What's the status?

I believe I have more than a use for minmax indexes, and wouldn't mind
lending a hand if it's within my grasp.

On Fri, Jan 24, 2014 at 12:58 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
>
> What's the status?
>
> I believe I have more than a use for minmax indexes, and wouldn't mind
> lending a hand if it's within my grasp.

I'm also interested in looking at this. Mostly because I have ideas
for other "summary" functions that would be interesting and could use
the same infrastructure otherwise.

--
greg

Robert Haas wrote:
> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:
> > Here's an updated version of this patch, with fixes to all the bugs
> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> > Amit Kapila for the reports.
>
> I'm not very happy with the use of a separate relation fork for
> storing this data.

Here's a new version of this patch. Now the revmap is not stored in a
separate fork, but together with all the regular data, as explained
elsewhere in the thread.

I added a few pageinspect functions that let one explore the data in the
index. With this you can start by reading the metapage, and from there
obtain the block numbers for the revmap array pages; and explore revmap
array pages to read regular revmap pages, which contain the TIDs to
index entries. All these pageinspect functions don't currently have any
documentation, but it's as easy as

with idxname as (select 'ti'::text as idxname)
select *
from idxname,
generate_series(0, pg_relation_size(idxname) / 8192 - 1) i,
minmax_page_type(get_raw_page(idxname, i::int));

select * -- data in metapage
from
minmax_metapage_info(get_raw_page('ti', 0));

select * -- data in revmap array pages
from minmax_revmap_array_data(get_raw_page('ti', 6));

select logblk, unnest(pages) -- data in regular revmap pages
from minmax_revmap_data(get_raw_page('ti', 15));

select * -- data in regular index pages
from minmax_page_items(get_raw_page('ti', 2), 'ti'::regclass);

Note that in this last case you need to give it the OID of the index as
the second parameter, so that it can construct a tupledesc for decoding
the min/max data.

I have followed the suggestion by Amit to overwrite the index tuple when
a new heap tuple is inserted, instead of creating a separate index
tuple. This saves a lot of index bloat. This required a new entry
point in bufpage.c, PageOverwriteItemData(). bufpage.c also has a new
function PageIndexDeleteNoCompact which is similar in spirit to
PageIndexMultiDelete except that item pointers do not change. This is
necessary because the revmap stores item pointers, and such reference
would break if we were to renumber items in index pages.

I have also added a reloption for the size of each page range, so you
can do
create index ti on t using minmax (a) with (pages_per_range = 2);
The default is 128 pages per range, and I have an arbitrary maximum of
131072 (default size of a 1GB segment). There doesn't seem to be much
point in having larger page ranges; intuitively I think page ranges
should be more or less the size of kernel readahead, but I haven't
tested this.

I didn't want to rebase past 0ef0b6784 in a hurry. I only know this
applies cleanly on top of fe7337f2dc, so please use that if you want to
play with it. I will post a rebased version shortly.

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

On Sat, Jun 14, 2014 at 10:34 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Robert Haas wrote:
>> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
>> <alvherre(at)2ndquadrant(dot)com> wrote:
>> > Here's an updated version of this patch, with fixes to all the bugs
>> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
>> > Amit Kapila for the reports.
>>
>> I'm not very happy with the use of a separate relation fork for
>> storing this data.
>
> Here's a new version of this patch. Now the revmap is not stored in a
> separate fork, but together with all the regular data, as explained
> elsewhere in the thread.

Cool.

Have you thought more about this comment from Heikki?

http://www.postgresql.org/message-id/52495DD3.9010809@vmware.com

I'm concerned that we could end up with one index type of this general
nature for min/max type operations, and then another very similar
index type for geometric operators or text-search operators or what
have you. Considering the overhead in adding and maintaining an index
AM, I think we should try to be sure that we've done a reasonably
solid job making each one as general as we reasonably can.

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

On 2014-06-17 10:26:11 -0400, Robert Haas wrote:
> On Sat, Jun 14, 2014 at 10:34 PM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:
> > Robert Haas wrote:
> >> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
> >> <alvherre(at)2ndquadrant(dot)com> wrote:
> >> > Here's an updated version of this patch, with fixes to all the bugs
> >> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> >> > Amit Kapila for the reports.
> >>
> >> I'm not very happy with the use of a separate relation fork for
> >> storing this data.
> >
> > Here's a new version of this patch. Now the revmap is not stored in a
> > separate fork, but together with all the regular data, as explained
> > elsewhere in the thread.
>
> Cool.
>
> Have you thought more about this comment from Heikki?
>
> http://www.postgresql.org/message-id/52495DD3.9010809@vmware.com

Is there actually a significant usecase behind that wish or just a
general demand for being generic? To me it seems fairly unlikely you'd
end up with something useful by doing a minmax index over bounding
boxes.

Greetings,

Andres Freund

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

On Tue, Jun 17, 2014 at 3:31 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Is there actually a significant usecase behind that wish or just a
> general demand for being generic? To me it seems fairly unlikely you'd
> end up with something useful by doing a minmax index over bounding
> boxes.

Isn't min/max just a 2d bounding box? If you do a bulk data load of
something like the census data then sure, every page will have data
points for some geometrically clustered set of data.

I had in mind to do a small bloom filter per block. In general any
kind of predicate like bounding box should work.

--
greg

On Tue, Jun 17, 2014 at 10:31 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2014-06-17 10:26:11 -0400, Robert Haas wrote:
>> On Sat, Jun 14, 2014 at 10:34 PM, Alvaro Herrera
>> <alvherre(at)2ndquadrant(dot)com> wrote:
>> > Robert Haas wrote:
>> >> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
>> >> <alvherre(at)2ndquadrant(dot)com> wrote:
>> >> > Here's an updated version of this patch, with fixes to all the bugs
>> >> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
>> >> > Amit Kapila for the reports.
>> >>
>> >> I'm not very happy with the use of a separate relation fork for
>> >> storing this data.
>> >
>> > Here's a new version of this patch. Now the revmap is not stored in a
>> > separate fork, but together with all the regular data, as explained
>> > elsewhere in the thread.
>>
>> Cool.
>>
>> Have you thought more about this comment from Heikki?
>>
>> http://www.postgresql.org/message-id/52495DD3.9010809@vmware.com
>
> Is there actually a significant usecase behind that wish or just a
> general demand for being generic? To me it seems fairly unlikely you'd
> end up with something useful by doing a minmax index over bounding
> boxes.

Well, I'm not the guy who does things with geometric data, but I don't
want to ignore the significant percentage of our users who are. As
you must surely know, the GIST implementations for geometric data
types store bounding boxes on internal pages, and that seems to be
useful to people. What is your reason for thinking that it would be
any less useful in this context?

I do also think that a general demand for being generic ought to carry
some weight. We have gone to great lengths to make sure that our
indexing can handle more than just < and >, where a lot of other
products have not bothered. I think we have gotten a lot of mileage
out of that decision and feel that we shouldn't casually back away
from it. Obviously, we do already have some special-case
optimizations and will likely have more in the future, and there are
can certainly be valid reasons for taking that approach. But it needs
to be justified in some way; we shouldn't accept a less-generic
approach blindly, without questioning whether it's possible to do
better.

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

On 2014-06-17 11:48:10 -0400, Robert Haas wrote:
> On Tue, Jun 17, 2014 at 10:31 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > On 2014-06-17 10:26:11 -0400, Robert Haas wrote:
> >> On Sat, Jun 14, 2014 at 10:34 PM, Alvaro Herrera
> >> <alvherre(at)2ndquadrant(dot)com> wrote:
> >> > Robert Haas wrote:
> >> >> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
> >> >> <alvherre(at)2ndquadrant(dot)com> wrote:
> >> >> > Here's an updated version of this patch, with fixes to all the bugs
> >> >> > reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
> >> >> > Amit Kapila for the reports.
> >> >>
> >> >> I'm not very happy with the use of a separate relation fork for
> >> >> storing this data.
> >> >
> >> > Here's a new version of this patch. Now the revmap is not stored in a
> >> > separate fork, but together with all the regular data, as explained
> >> > elsewhere in the thread.
> >>
> >> Cool.
> >>
> >> Have you thought more about this comment from Heikki?
> >>
> >> http://www.postgresql.org/message-id/52495DD3.9010809@vmware.com
> >
> > Is there actually a significant usecase behind that wish or just a
> > general demand for being generic? To me it seems fairly unlikely you'd
> > end up with something useful by doing a minmax index over bounding
> > boxes.
>
> Well, I'm not the guy who does things with geometric data, but I don't
> want to ignore the significant percentage of our users who are. As
> you must surely know, the GIST implementations for geometric data
> types store bounding boxes on internal pages, and that seems to be
> useful to people. What is your reason for thinking that it would be
> any less useful in this context?

For me minmax indexes are helpful because they allow to generate *small*
'coarse' indexes over large volumes of data. From my pov that's possible
possible because they don't contain item pointers for every contained
row.
That'ill imo work well if there are consecutive rows in the table that
can be summarized into one min/max range. That's quite likely to happen
for common applications of number of scalar datatypes. But the
likelihood of placing sufficiently many rows with very similar bounding
boxes close together seems much less relevant in practice. And I think
that's generally likely for operations which can't be well represented
as btree opclasses - the substructure that implies inside a Datum will
make correlation between consecutive rows less likely.

Maybe I've a major intuition failure here though...

> I do also think that a general demand for being generic ought to carry
> some weight.

Agreed. It's always a balance act. But it's not like this doesn't use a
datatype abstraction concept...

> We have gone to great lengths to make sure that our
> indexing can handle more than just < and >, where a lot of other
> products have not bothered. I think we have gotten a lot of mileage
> out of that decision and feel that we shouldn't casually back away
> from it.

I don't see this as a case of backing away from that though?

> we shouldn't accept a less-generic
> approach blindly, without questioning whether it's possible to do
> better.

But the aim shouldn't be to add genericity that's not going to be used,
but to add it where it's somewhat likely to help...

Greetings,

Andres Freund

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

On Tue, Jun 17, 2014 at 12:04 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> Well, I'm not the guy who does things with geometric data, but I don't
>> want to ignore the significant percentage of our users who are. As
>> you must surely know, the GIST implementations for geometric data
>> types store bounding boxes on internal pages, and that seems to be
>> useful to people. What is your reason for thinking that it would be
>> any less useful in this context?
>
> For me minmax indexes are helpful because they allow to generate *small*
> 'coarse' indexes over large volumes of data. From my pov that's possible
> possible because they don't contain item pointers for every contained
> row.
> That'ill imo work well if there are consecutive rows in the table that
> can be summarized into one min/max range. That's quite likely to happen
> for common applications of number of scalar datatypes. But the
> likelihood of placing sufficiently many rows with very similar bounding
> boxes close together seems much less relevant in practice. And I think
> that's generally likely for operations which can't be well represented
> as btree opclasses - the substructure that implies inside a Datum will
> make correlation between consecutive rows less likely.

Well, I don't know: suppose you're loading geospatial data showing the
location of every building in some country. It might easily be the
case that the data is or can be loaded in an order that provides
pretty good spatial locality, leading to tight bounding boxes over
physically consecutive data ranges.

But I'm not trying to say that we absolutely have to support that kind
of thing; what I am trying to say is that there should be a README or
a mailing list post or some such that says: "We thought about how
generic to make this. We considered A, B, and C. We rejected C as
too narrow, and A because if we made it that general it would have
greatly enlarged the disk footprint for the following reasons.
Therefore we selected B." Basically, I think Heikki asked a good
question - which was "could we abstract this more?" - and I can't
recall seeing a clear answer explaining why we could or couldn't and
what the trade-offs would be.

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

On 2014-06-17 12:14:00 -0400, Robert Haas wrote:
> On Tue, Jun 17, 2014 at 12:04 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> >> Well, I'm not the guy who does things with geometric data, but I don't
> >> want to ignore the significant percentage of our users who are. As
> >> you must surely know, the GIST implementations for geometric data
> >> types store bounding boxes on internal pages, and that seems to be
> >> useful to people. What is your reason for thinking that it would be
> >> any less useful in this context?
> >
> > For me minmax indexes are helpful because they allow to generate *small*
> > 'coarse' indexes over large volumes of data. From my pov that's possible
> > possible because they don't contain item pointers for every contained
> > row.
> > That'ill imo work well if there are consecutive rows in the table that
> > can be summarized into one min/max range. That's quite likely to happen
> > for common applications of number of scalar datatypes. But the
> > likelihood of placing sufficiently many rows with very similar bounding
> > boxes close together seems much less relevant in practice. And I think
> > that's generally likely for operations which can't be well represented
> > as btree opclasses - the substructure that implies inside a Datum will
> > make correlation between consecutive rows less likely.
>
> Well, I don't know: suppose you're loading geospatial data showing the
> location of every building in some country. It might easily be the
> case that the data is or can be loaded in an order that provides
> pretty good spatial locality, leading to tight bounding boxes over
> physically consecutive data ranges.

Well, it might be doable to correlate them along one axis, but along
both? That's more complicated... And even alongside one axis you
already get into problems if your geometries are irregularly sized.
Asingle large polygon will completely destroy indexability for anything
stored physically close by because suddently the minmax range will be
huge... So you'll need to cleverly sort for that as well.

I think hierarchical datastructures are so much better suited for this,
that there's little point trying to fit them into minmax. I can very
well imagine that there's benefit in a gist support for only storing one
pointer per block instead of one pointer per item or such. But it seems
like separate feature.

> But I'm not trying to say that we absolutely have to support that kind
> of thing; what I am trying to say is that there should be a README or
> a mailing list post or some such that says: "We thought about how
> generic to make this. We considered A, B, and C. We rejected C as
> too narrow, and A because if we made it that general it would have
> greatly enlarged the disk footprint for the following reasons.
> Therefore we selected B."

Isn't 'simpler implementation' a valid reason that's already been
discussed onlist? Obviously simpler implementation doesn't trump
everything, but it's one valid reason...
Note that I have zap to do with the design of this feature. I work for
the same company as Alvaro, but that's pretty much it...

> Basically, I think Heikki asked a good
> question - which was "could we abstract this more?" - and I can't
> recall seeing a clear answer explaining why we could or couldn't and
> what the trade-offs would be.

'could we abstract more' imo is a pretty bad design guideline. It's 'is
there benefit in abstracting more'. Otherwise you end up with way to
complicated systems.

Greetings,

Andres Freund

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

On Tue, Jun 17, 2014 at 1:04 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> For me minmax indexes are helpful because they allow to generate *small*
> 'coarse' indexes over large volumes of data. From my pov that's possible
> possible because they don't contain item pointers for every contained
> row.

But minmax is just a specific form of bloom filter.

This could certainly be generalized to a bloom filter index with some
set of bloom&hashing operators (minmax being just one).

On 06/17/2014 09:14 AM, Robert Haas wrote:
> Well, I don't know: suppose you're loading geospatial data showing the
> location of every building in some country. It might easily be the
> case that the data is or can be loaded in an order that provides
> pretty good spatial locality, leading to tight bounding boxes over
> physically consecutive data ranges.

I admin a production application which has exactly this. However, that
application doesn't have big enough data to benefit from minmax indexes;
it uses the basic spatial indexes.

So, my $0.02: bounding box minmax falls under the heading of "would be
nice to have, but not if it delays the feature".

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Tue, Jun 17, 2014 at 11:16 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Well, it might be doable to correlate them along one axis, but along
> both? That's more complicated... And even alongside one axis you
> already get into problems if your geometries are irregularly sized.
> Asingle large polygon will completely destroy indexability for anything
> stored physically close by because suddently the minmax range will be
> huge... So you'll need to cleverly sort for that as well.

I think there's a misunderstanding here, possibly mine. My
understanding is that a min/max index will always be exactly the same
size for a given size table. It stores the minimum and maximum value
of the key for each page. Then you can do a bitmap scan by comparing
the search key with each page's minimum and maximum to see if that
page needs to be included in the scan. The failure mode is not that
the index is large but that a page that has an outlier will be
included in every scan as a false positive incurring an extra iop.

I don't think it's implausible at all that Geometric data would work
well. If you load Geometric data it's very common to load data by
geographic area so that all objects in San Francisco in one part of
the data load, probably even by zip code or census block.

What operations would an opclass for min/max need? I think it would be
pretty similar to the operators that GiST needs (thankfully minus the
baroque page split function):

An aggregate to generate a min/max "bounding box" from several values
A function which takes an "bounding box" and a new value and returns
the new "bounding box"
A function which tests if a value is in a "bounding box"
A function which tests if a "bounding box" overlaps a "bounding box"

The nice thing is this would let us add things like range @> (contains
element) to the plain integer min/max case.

--
greg

On 06/17/2014 09:16 PM, Andres Freund wrote:
> On 2014-06-17 12:14:00 -0400, Robert Haas wrote:
>> On Tue, Jun 17, 2014 at 12:04 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>>>> Well, I'm not the guy who does things with geometric data, but I don't
>>>> want to ignore the significant percentage of our users who are. As
>>>> you must surely know, the GIST implementations for geometric data
>>>> types store bounding boxes on internal pages, and that seems to be
>>>> useful to people. What is your reason for thinking that it would be
>>>> any less useful in this context?
>>>
>>> For me minmax indexes are helpful because they allow to generate *small*
>>> 'coarse' indexes over large volumes of data. From my pov that's possible
>>> possible because they don't contain item pointers for every contained
>>> row.
>>> That'ill imo work well if there are consecutive rows in the table that
>>> can be summarized into one min/max range. That's quite likely to happen
>>> for common applications of number of scalar datatypes. But the
>>> likelihood of placing sufficiently many rows with very similar bounding
>>> boxes close together seems much less relevant in practice. And I think
>>> that's generally likely for operations which can't be well represented
>>> as btree opclasses - the substructure that implies inside a Datum will
>>> make correlation between consecutive rows less likely.
>>
>> Well, I don't know: suppose you're loading geospatial data showing the
>> location of every building in some country. It might easily be the
>> case that the data is or can be loaded in an order that provides
>> pretty good spatial locality, leading to tight bounding boxes over
>> physically consecutive data ranges.
>
> Well, it might be doable to correlate them along one axis, but along
> both? That's more complicated... And even alongside one axis you
> already get into problems if your geometries are irregularly sized.

Sure, there are cases where it would be useless. But it's easy to
imagine scenarios where it would work well, where points are loaded in
clusters and points that are close to each other also end up physically
close to each other.

> Asingle large polygon will completely destroy indexability for anything
> stored physically close by because suddently the minmax range will be
> huge... So you'll need to cleverly sort for that as well.

That's an inherent risk with minmax indexes: insert a few rows to the
"wrong" locations in the heap, and the selectivity of the index degrades
rapidly.

The main problem with using it for geometric types is that you can't
easily CLUSTER the table to make the minmax index effective again. But
there are ways around that.

>> But I'm not trying to say that we absolutely have to support that kind
>> of thing; what I am trying to say is that there should be a README or
>> a mailing list post or some such that says: "We thought about how
>> generic to make this. We considered A, B, and C. We rejected C as
>> too narrow, and A because if we made it that general it would have
>> greatly enlarged the disk footprint for the following reasons.
>> Therefore we selected B."
>
> Isn't 'simpler implementation' a valid reason that's already been
> discussed onlist? Obviously simpler implementation doesn't trump
> everything, but it's one valid reason...
> Note that I have zap to do with the design of this feature. I work for
> the same company as Alvaro, but that's pretty much it...

Without some analysis (e.g implementing it and comparing), I don't buy
that it makes the implementation simpler to restrict it in this way.
Maybe it does, but often it's actually simpler to solve the general case.

- Heikki

On 2014-06-18 12:18:26 +0300, Heikki Linnakangas wrote:
> On 06/17/2014 09:16 PM, Andres Freund wrote:
> >Well, it might be doable to correlate them along one axis, but along
> >both? That's more complicated... And even alongside one axis you
> >already get into problems if your geometries are irregularly sized.
>
> Sure, there are cases where it would be useless. But it's easy to imagine
> scenarios where it would work well, where points are loaded in clusters and
> points that are close to each other also end up physically close to each
> other.

> >Asingle large polygon will completely destroy indexability for anything
> >stored physically close by because suddently the minmax range will be
> >huge... So you'll need to cleverly sort for that as well.
>
> That's an inherent risk with minmax indexes: insert a few rows to the
> "wrong" locations in the heap, and the selectivity of the index degrades
> rapidly.

Sure. But it's fairly normal to have natural clusteredness in many
columns (surrogate keys, dateseries type of data). Even if you insert
geometric types in a geographic clusters you'll have worse results
because some bounding boxes will be big and such.

And:
> The main problem with using it for geometric types is that you can't easily
> CLUSTER the table to make the minmax index effective again. But there are
> ways around that.

Which are? Sure you can try stuff like recreating the table, sorting
rows with boundary boxes area above threshold first, and then go on to
sort by the lop left corner of the bounding box. But that'll be neither
builtin, nor convenient, nor perfect. In contrast to a normal CLUSTER
for types with a btree opclass which will yield the perfect order.

> >Isn't 'simpler implementation' a valid reason that's already been
> >discussed onlist? Obviously simpler implementation doesn't trump
> >everything, but it's one valid reason...
> >Note that I have zap to do with the design of this feature. I work for
> >the same company as Alvaro, but that's pretty much it...
>
> Without some analysis (e.g implementing it and comparing), I don't buy that
> it makes the implementation simpler to restrict it in this way. Maybe it
> does, but often it's actually simpler to solve the general case.

So to implement a feature one now has to implement the most generic
variant as a prototype first? Really?

Greetings,

Andres Freund

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

On 2014-06-17 16:48:07 -0700, Greg Stark wrote:
> On Tue, Jun 17, 2014 at 11:16 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > Well, it might be doable to correlate them along one axis, but along
> > both? That's more complicated... And even alongside one axis you
> > already get into problems if your geometries are irregularly sized.
> > Asingle large polygon will completely destroy indexability for anything
> > stored physically close by because suddently the minmax range will be
> > huge... So you'll need to cleverly sort for that as well.
>
> I think there's a misunderstanding here, possibly mine. My
> understanding is that a min/max index will always be exactly the same
> size for a given size table. It stores the minimum and maximum value
> of the key for each page. Then you can do a bitmap scan by comparing
> the search key with each page's minimum and maximum to see if that
> page needs to be included in the scan. The failure mode is not that
> the index is large but that a page that has an outlier will be
> included in every scan as a false positive incurring an extra iop.

I just rechecked, and no, it doesn't, by default, store a range for each
page. It's MINMAX_DEFAULT_PAGES_PER_RANGE=128 pages by
default... Haven't checked what's the lowest it can be se tto.

Greetings,

Andres Freund

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

On 06/18/2014 01:46 PM, Andres Freund wrote:
> On 2014-06-18 12:18:26 +0300, Heikki Linnakangas wrote:
>> The main problem with using it for geometric types is that you can't easily
>> CLUSTER the table to make the minmax index effective again. But there are
>> ways around that.
>
> Which are? Sure you can try stuff like recreating the table, sorting
> rows with boundary boxes area above threshold first, and then go on to
> sort by the lop left corner of the bounding box.

Right, something like that. Or cluster using some other column that
correlates with the geometry, like a zip code.

> But that'll be neither
> builtin, nor convenient, nor perfect. In contrast to a normal CLUSTER
> for types with a btree opclass which will yield the perfect order.

Sure.

BTW, CLUSTERing by a geometric type would be useful anyway, even without
minmax indexes.

>>> Isn't 'simpler implementation' a valid reason that's already been
>>> discussed onlist? Obviously simpler implementation doesn't trump
>>> everything, but it's one valid reason...
>>> Note that I have zap to do with the design of this feature. I work for
>>> the same company as Alvaro, but that's pretty much it...
>>
>> Without some analysis (e.g implementing it and comparing), I don't buy that
>> it makes the implementation simpler to restrict it in this way. Maybe it
>> does, but often it's actually simpler to solve the general case.
>
> So to implement a feature one now has to implement the most generic
> variant as a prototype first? Really?

Implementing something is a good way to demonstrate how it would look
like. But no, I don't insist on implementing every possible design
whenever a new feature is proposed.

I liked Greg's sketch of what the opclass support functions would be. It
doesn't seem significantly more complicated than what's in the patch now.

- Heikki

On Tue, Jun 17, 2014 at 2:16 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> But I'm not trying to say that we absolutely have to support that kind
>> of thing; what I am trying to say is that there should be a README or
>> a mailing list post or some such that says: "We thought about how
>> generic to make this. We considered A, B, and C. We rejected C as
>> too narrow, and A because if we made it that general it would have
>> greatly enlarged the disk footprint for the following reasons.
>> Therefore we selected B."
>
> Isn't 'simpler implementation' a valid reason that's already been
> discussed onlist? Obviously simpler implementation doesn't trump
> everything, but it's one valid reason...
> Note that I have zap to do with the design of this feature. I work for
> the same company as Alvaro, but that's pretty much it...

It really *hasn't* been discussed on-list. See these emails,
discussing the same ideas, from 8 months ago:

http://www.postgresql.org/message-id/5249B2D3.6030606@vmware.com
http://www.postgresql.org/message-id/CA+TgmoYSCbW-UC8LQV96sziGnXSuzAyQbfdQmK-FGu22HdKkaw@mail.gmail.com

Now, Alvaro did not respond to those emails, nor did anyone involved
in the development of the feature. There may be an argument that
implementing that would be too complicated, but Heikki said he didn't
think it would be, and nobody's made a concrete argument as to why
he's wrong (and Heikki knows a lot about indexing).

>> Basically, I think Heikki asked a good
>> question - which was "could we abstract this more?" - and I can't
>> recall seeing a clear answer explaining why we could or couldn't and
>> what the trade-offs would be.
>
> 'could we abstract more' imo is a pretty bad design guideline. It's 'is
> there benefit in abstracting more'. Otherwise you end up with way to
> complicated systems.

On the flip side, if you don't abstract enough, you end up being able
to cover only a small set of the relevant use cases, or else you end
up with a bunch of poorly-coordinated tools to cover slightly
different use cases.

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

On Wed, Jun 18, 2014 at 8:51 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
>
> I liked Greg's sketch of what the opclass support functions would be. It
> doesn't seem significantly more complicated than what's in the patch now.

Which was

On Tue, Jun 17, 2014 at 8:48 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> An aggregate to generate a min/max "bounding box" from several values
> A function which takes an "bounding box" and a new value and returns
> the new "bounding box"
> A function which tests if a value is in a "bounding box"
> A function which tests if a "bounding box" overlaps a "bounding box"

Which I'd generalize a bit further by renaming "bounding box" with
"compressed set", and allow it to be parameterized.

So, you have:

An aggregate to generate a "compressed set" from several values
A function which adds a new value to the "compressed set" and returns
the new "compressed set"
A function which tests if a value is in a "compressed set"
A function which tests if a "compressed set" overlaps another
"compressed set" of equal type

If you can define different compressed sets, you can use this to
generate both min/max indexes as well as bloom filter indexes. Whether
we'd want to have both is perhaps questionable, but having the ability
to is probably desirable.

One problem with such a generalized implementation would be, that I'm
not sure in-place modification of the "compressed set" on-disk can be
assumed to be safe on all cases. Surely, for strictly-enlarging sets
it would, but while min/max and bloom filters both fit the bill, it's
not clear that one can assume this for all structures.

Adding also a "in-place updateable" bit to the "type" would perhaps
inflate the complexity of the patch due to the need to provide both
code paths?

On 06/18/2014 12:46 PM, Andres Freund wrote:
>>> Isn't 'simpler implementation' a valid reason that's already been
>>> > >discussed onlist? Obviously simpler implementation doesn't trump
>>> > >everything, but it's one valid reason...
>>> > >Note that I have zap to do with the design of this feature. I work for
>>> > >the same company as Alvaro, but that's pretty much it...
>> >
>> > Without some analysis (e.g implementing it and comparing), I don't buy that
>> > it makes the implementation simpler to restrict it in this way. Maybe it
>> > does, but often it's actually simpler to solve the general case.
>
> So to implement a feature one now has to implement the most generic
> variant as a prototype first? Really?

Well, there is the inventor's paradox to consider.
--
Vik

On 06/18/2014 06:09 PM, Claudio Freire wrote:
> On Tue, Jun 17, 2014 at 8:48 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
>> An aggregate to generate a min/max "bounding box" from several values
>> A function which takes an "bounding box" and a new value and returns
>> the new "bounding box"
>> A function which tests if a value is in a "bounding box"
>> A function which tests if a "bounding box" overlaps a "bounding box"
>
> Which I'd generalize a bit further by renaming "bounding box" with
> "compressed set", and allow it to be parameterized.

What do you mean by parameterized?

> So, you have:
>
> An aggregate to generate a "compressed set" from several values
> A function which adds a new value to the "compressed set" and returns
> the new "compressed set"
> A function which tests if a value is in a "compressed set"
> A function which tests if a "compressed set" overlaps another
> "compressed set" of equal type

Yeah, something like that. I'm not sure I like the "compressed set" term
any more than bounding box, though. GiST seems to have avoided naming
the thing, and just talks about "index entries". But if we can come up
with a good name, that would be more clear.

> One problem with such a generalized implementation would be, that I'm
> not sure in-place modification of the "compressed set" on-disk can be
> assumed to be safe on all cases. Surely, for strictly-enlarging sets
> it would, but while min/max and bloom filters both fit the bill, it's
> not clear that one can assume this for all structures.

I don't understand what you mean. It's a fundamental property of minmax
indexes that you can always replace the "min" or "max" or "compressing
set" or "bounding box" or whatever with another datum that represents
all the keys that the old one did, plus some.

- Heikki

Vik Fearing <vik(dot)fearing(at)dalibo(dot)com> writes:
> On 06/18/2014 12:46 PM, Andres Freund wrote:
>> So to implement a feature one now has to implement the most generic
>> variant as a prototype first? Really?

> Well, there is the inventor's paradox to consider.

I have not seen anyone demanding a different implementation in this
thread. What *has* been asked for, and not supplied, is a concrete
defense of the particular level of generality that's been selected
in this implementation. It's not at all clear to the rest of us
whether it was the right choice, and that is something that ought
to be asked now not later.

regards, tom lane

On Wed, Jun 18, 2014 at 4:51 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Implementing something is a good way to demonstrate how it would look like.
> But no, I don't insist on implementing every possible design whenever a new
> feature is proposed.
>
> I liked Greg's sketch of what the opclass support functions would be. It
> doesn't seem significantly more complicated than what's in the patch now.

As a counter-point to my own point there will be nothing stopping us
in the future from generalizing things. Dealing with catalogs is
mostly book-keeping headaches and careful work. it's something that
might be well-suited for a GSOC or first patch from someone looking to
familiarize themselves with the system architecture. It's hard to
invent a whole new underlying infrastructure at the same time as
dealing with all that book-keeping and it's hard for someone
familiarizing themselves with the system to also have a great new
idea. Having tasks like this that are easy to explain and that mentor
understands well can be easier to manage than tasks where the newcomer
has some radical new idea.

--
greg

On Thu, Jun 19, 2014 at 10:06 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> On 06/18/2014 06:09 PM, Claudio Freire wrote:
>>
>> On Tue, Jun 17, 2014 at 8:48 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
>>>
>>> An aggregate to generate a min/max "bounding box" from several values
>>> A function which takes an "bounding box" and a new value and returns
>>> the new "bounding box"
>>> A function which tests if a value is in a "bounding box"
>>> A function which tests if a "bounding box" overlaps a "bounding box"
>>
>>
>> Which I'd generalize a bit further by renaming "bounding box" with
>> "compressed set", and allow it to be parameterized.
>
>
> What do you mean by parameterized?

Bloom filters can be paired with number of hashes, number of bit
positions, and hash function, so it's not a simple bloom filter index,
but a bloom filter index with N SHA-1-based hashes spread on a
K-length bitmap.

>> So, you have:
>>
>> An aggregate to generate a "compressed set" from several values
>> A function which adds a new value to the "compressed set" and returns
>> the new "compressed set"
>> A function which tests if a value is in a "compressed set"
>> A function which tests if a "compressed set" overlaps another
>> "compressed set" of equal type
>
>
> Yeah, something like that. I'm not sure I like the "compressed set" term any
> more than bounding box, though. GiST seems to have avoided naming the thing,
> and just talks about "index entries". But if we can come up with a good
> name, that would be more clear.

I don't want to use the term bloom filter since it's very specific of
a specific technique, but it's basically that - an approximate set
without false negatives. Ie: compressed set.

It's not a bounding box either when using bloom filters. So...

>> One problem with such a generalized implementation would be, that I'm
>> not sure in-place modification of the "compressed set" on-disk can be
>> assumed to be safe on all cases. Surely, for strictly-enlarging sets
>> it would, but while min/max and bloom filters both fit the bill, it's
>> not clear that one can assume this for all structures.
>
>
> I don't understand what you mean. It's a fundamental property of minmax
> indexes that you can always replace the "min" or "max" or "compressing set"
> or "bounding box" or whatever with another datum that represents all the
> keys that the old one did, plus some.

Yes, and bloom filters happen to fall on that category too.

Never mind what I said. I was thinking of other potential and
imaginary implementation that supports removal or updates, that might
need care with transaction lifetimes, but that's easily fixed by
letting vacuum or some lazy process do the deleting just as it happens
with other indexes anyway.

So, I guess the interface must include also the invariant that
compressed sets only grow, never shrink unless from a rebuild or a
vacuum operation.

I'm sorry if I missed something, but ISTM this is beginning to look a
lot like GiST. This was pointed out by Robert Haas last year.

On Wed, Jun 18, 2014 at 12:09:42PM -0300, Claudio Freire wrote:
> So, you have:
>
> An aggregate to generate a "compressed set" from several values

Which GiST does by calling 'compress' on each value, and the 'unions' the
results together.

> A function which adds a new value to the "compressed set" and returns
> the new "compressed set"

Again, 'compress' + 'union'

> A function which tests if a value is in a "compressed set"

Which GiST does using 'compress' +'consistant'

> A function which tests if a "compressed set" overlaps another
> "compressed set" of equal type

Which GiST calls 'consistant'

So I'm wondering why you can't just reuse the btree_gist functions we
already have in contrib. It seems to me that these MinMax indexes are
in fact a variation on GiST that indexes the pages of a table based
upon the 'union' of all the elements in a page. By reusing the GiST
operator class you get support for many datatypes for free.

> If you can define different compressed sets, you can use this to
> generate both min/max indexes as well as bloom filter indexes. Whether
> we'd want to have both is perhaps questionable, but having the ability
> to is probably desirable.

You could implement bloom filter in GiST too. It's been discussed
before but I can't find any implementation. Probably because the filter
needs to be parameterised and if you store the bloom filter for each
element it gets expensive very quickly. However, hooked into a minmax
structure which only indexes whole pages it could be quite efficient.

> One problem with such a generalized implementation would be, that I'm
> not sure in-place modification of the "compressed set" on-disk can be
> assumed to be safe on all cases. Surely, for strictly-enlarging sets
> it would, but while min/max and bloom filters both fit the bill, it's
> not clear that one can assume this for all structures.

I think GiST has already solved this problem.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> He who writes carelessly confesses thereby at the very outset that he does
> not attach much importance to his own thoughts.
-- Arthur Schopenhauer

Some comments, aside from the design wrt. bounding boxes etc. :

On 06/15/2014 05:34 AM, Alvaro Herrera wrote:
> Robert Haas wrote:
>> On Wed, Sep 25, 2013 at 4:34 PM, Alvaro Herrera
>> <alvherre(at)2ndquadrant(dot)com> wrote:
>>> Here's an updated version of this patch, with fixes to all the bugs
>>> reported so far. Thanks to Thom Brown, Jaime Casanova, Erik Rijkers and
>>> Amit Kapila for the reports.
>>
>> I'm not very happy with the use of a separate relation fork for
>> storing this data.
>
> Here's a new version of this patch. Now the revmap is not stored in a
> separate fork, but together with all the regular data, as explained
> elsewhere in the thread.

Thanks! Please update the README accordingly.

If I understand the code correctly, the revmap is a three-level deep
structure. The bottom level consists of "regular revmap pages", and each
regular revmap page is filled with ItemPointerDatas, which point to the
index tuples. The middle level consists of "array revmap pages", and
each array revmap page contains an array of BlockNumbers of the "regular
revmap" pages. The top level is an array of BlockNumbers of the array
revmap pages, and it is stored in the metapage.

With 8k block size, that's just enough to cover the full range of 2^32-1
blocks that you'll need if you set mm_pages_per_range=1. Each regular
revmap page can store about 8192/6 = 1365 item pointers, each array
revmap page can store about 8192/4 = 2048 block references, and the size
of the top array is 8192/4. That's just enough; to store the required
number of array pages in the top array, the array needs to be
(2^32/1365)/2048)=1536 elements large.

But with 4k or smaller blocks, it's not enough.

I wonder if it would be simpler to just always store the revmap pages in
the beginning of the index, before any other pages. Finding the revmap
page would then be just as easy as with a separate fork. When the
table/index is extended so that a new revmap page is needed, move the
existing page at that block out of the way. Locking needs some
consideration, but I think it would be feasible and simpler than you
have now.

> I have followed the suggestion by Amit to overwrite the index tuple when
> a new heap tuple is inserted, instead of creating a separate index
> tuple. This saves a lot of index bloat. This required a new entry
> point in bufpage.c, PageOverwriteItemData(). bufpage.c also has a new
> function PageIndexDeleteNoCompact which is similar in spirit to
> PageIndexMultiDelete except that item pointers do not change. This is
> necessary because the revmap stores item pointers, and such reference
> would break if we were to renumber items in index pages.

ISTM that when the old tuple cannot be updated in-place, the new index
tuple is inserted with mm_doinsert(), but the old tuple is never deleted.

- Heikki

--
- Heikki

Heikki Linnakangas wrote:
> Some comments, aside from the design wrt. bounding boxes etc. :

Thanks. I haven't commented on that sub-thread because I think it's
possible to come up with a reasonable design that solves the issue by
adding a couple of amprocs. I need to do some more thinking to ensure
it is really workable, and then I'll post my ideas.

> On 06/15/2014 05:34 AM, Alvaro Herrera wrote:
> >Robert Haas wrote:

> If I understand the code correctly, the revmap is a three-level deep
> structure. The bottom level consists of "regular revmap pages", and
> each regular revmap page is filled with ItemPointerDatas, which
> point to the index tuples. The middle level consists of "array
> revmap pages", and each array revmap page contains an array of
> BlockNumbers of the "regular revmap" pages. The top level is an
> array of BlockNumbers of the array revmap pages, and it is stored in
> the metapage.

Yep, that's correct. Essentially, we still have the revmap as a linear
space (containing TIDs); the other two levels on top of that are only
there to enable locating the physical page numbers for each revmap
logical page. I make one exception that the first logical revmap page
is always stored in page 1, to optimize the case of a smallish table
(~1360 page ranges; approximately 1.3 gigabytes of data at 128 pages per
range, or 170 megabytes at 16 pages per range.)

Each page has a page header (24 bytes) and special space (4 bytes), so
it has 8192-28=8164 bytes available for data, so 1360 item pointers.

> With 8k block size, that's just enough to cover the full range of
> 2^32-1 blocks that you'll need if you set mm_pages_per_range=1. Each
> regular revmap page can store about 8192/6 = 1365 item pointers,
> each array revmap page can store about 8192/4 = 2048 block
> references, and the size of the top array is 8192/4. That's just
> enough; to store the required number of array pages in the top
> array, the array needs to be (2^32/1365)/2048)=1536 elements large.
>
> But with 4k or smaller blocks, it's not enough.

Yeah. As I said elsewhere, actual useful values are likely to be close
to the read-ahead setting of the underlying disk; by default that'd be
16 pages (128kB), but I think it's common advice to increase the kernel
setting to improve performance. I don't think we don't need to prevent
minmax indexes with pages_per_range=1, but I don't think we need to
ensure that that setting works with the largest tables, either, because
it doesn't make any sense to set it up like that.

Also, while there are some recommendations to set up a system with
larger page sizes (32kB), I have never seen any recommendation to set it
lower. It wouldn't make sense to build a system that has very large
tables and use a smaller page size.

So in other words, yes, you're correct that the mechanism doesn't work
in some cases (small page size and index configured for highest level of
detail), but the conditions are such that I don't think it matters.

ISTM the thing to do here is to do the math at index creation time, and
if we find that we don't have enough space in the metapage for all array
revmap pointers we need, bail out and require the index to be created
with a larger pages_per_range setting.

> I wonder if it would be simpler to just always store the revmap
> pages in the beginning of the index, before any other pages. Finding
> the revmap page would then be just as easy as with a separate fork.
> When the table/index is extended so that a new revmap page is
> needed, move the existing page at that block out of the way. Locking
> needs some consideration, but I think it would be feasible and
> simpler than you have now.

Moving index items around is not easy, because you'd have to adjust the
revmap to rewrite the item pointers.

> >I have followed the suggestion by Amit to overwrite the index tuple when
> >a new heap tuple is inserted, instead of creating a separate index
> >tuple. This saves a lot of index bloat. This required a new entry
> >point in bufpage.c, PageOverwriteItemData(). bufpage.c also has a new
> >function PageIndexDeleteNoCompact which is similar in spirit to
> >PageIndexMultiDelete except that item pointers do not change. This is
> >necessary because the revmap stores item pointers, and such reference
> >would break if we were to renumber items in index pages.
>
> ISTM that when the old tuple cannot be updated in-place, the new
> index tuple is inserted with mm_doinsert(), but the old tuple is
> never deleted.

It's deleted by the next vacuum.

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

On 06/23/2014 08:07 PM, Alvaro Herrera wrote:
> Heikki Linnakangas wrote:
>> With 8k block size, that's just enough to cover the full range of
>> 2^32-1 blocks that you'll need if you set mm_pages_per_range=1. Each
>> regular revmap page can store about 8192/6 = 1365 item pointers,
>> each array revmap page can store about 8192/4 = 2048 block
>> references, and the size of the top array is 8192/4. That's just
>> enough; to store the required number of array pages in the top
>> array, the array needs to be (2^32/1365)/2048)=1536 elements large.
>>
>> But with 4k or smaller blocks, it's not enough.
>
> Yeah. As I said elsewhere, actual useful values are likely to be close
> to the read-ahead setting of the underlying disk; by default that'd be
> 16 pages (128kB), but I think it's common advice to increase the kernel
> setting to improve performance.

My gut feeling is that it might well be best to set pages_per_page=1.
Even if you do the same amount of I/O, thanks to kernel read-ahead, you
might still avoid processing a lot of tuples. But would need to see some
benchmarks to know..

> I don't think we don't need to prevent
> minmax indexes with pages_per_range=1, but I don't think we need to
> ensure that that setting works with the largest tables, either, because
> it doesn't make any sense to set it up like that.
>
> Also, while there are some recommendations to set up a system with
> larger page sizes (32kB), I have never seen any recommendation to set it
> lower. It wouldn't make sense to build a system that has very large
> tables and use a smaller page size.
>
> So in other words, yes, you're correct that the mechanism doesn't work
> in some cases (small page size and index configured for highest level of
> detail), but the conditions are such that I don't think it matters.
>
> ISTM the thing to do here is to do the math at index creation time, and
> if we find that we don't have enough space in the metapage for all array
> revmap pointers we need, bail out and require the index to be created
> with a larger pages_per_range setting.

Yeah, I agree that would be acceptable.

I feel that the below would nevertheless be simpler:

>> I wonder if it would be simpler to just always store the revmap
>> pages in the beginning of the index, before any other pages. Finding
>> the revmap page would then be just as easy as with a separate fork.
>> When the table/index is extended so that a new revmap page is
>> needed, move the existing page at that block out of the way. Locking
>> needs some consideration, but I think it would be feasible and
>> simpler than you have now.
>
> Moving index items around is not easy, because you'd have to adjust the
> revmap to rewrite the item pointers.

Hmm. Two alternative schemes come to mind:

1. Move each index tuple off the page individually, updating the revmap
while you do it, until the page is empty. Updating the revmap for a
single index tuple isn't difficult; you have to do it anyway when an
index tuple is replaced. (MMTuples don't contain a heap block number
ATM, but IMHO they should, see below)

2. Store the new block number of the page that you moved out of the way
in the revmap page, and leave the revmap pointers unchanged. The revmap
pointers can be updated later, lazily.

Both of those seem pretty straightforward.

>>> I have followed the suggestion by Amit to overwrite the index tuple when
>>> a new heap tuple is inserted, instead of creating a separate index
>>> tuple. This saves a lot of index bloat. This required a new entry
>>> point in bufpage.c, PageOverwriteItemData(). bufpage.c also has a new
>>> function PageIndexDeleteNoCompact which is similar in spirit to
>>> PageIndexMultiDelete except that item pointers do not change. This is
>>> necessary because the revmap stores item pointers, and such reference
>>> would break if we were to renumber items in index pages.
>>
>> ISTM that when the old tuple cannot be updated in-place, the new
>> index tuple is inserted with mm_doinsert(), but the old tuple is
>> never deleted.
>
> It's deleted by the next vacuum.

Ah I see. Vacuum reads the whole index, and builds an in-memory hash
table that contains an ItemPointerData for every tuple in the index.
Doesn't that require a lot of memory, for a large index? That might be
acceptable - you ought to have plenty of RAM if you're pushing around
multi-terabyte tables - but it would nevertheless be nice to not have a
hard requirement for something as essential as vacuum.

In addition to the hash table, remove_deletable_tuples() pallocs an
array to hold an ItemPointer for every index tuple about to be removed.
A single palloc is limited to 1GB, so that will fail outright if there
are more than ~179 million dead index tuples. You're unlikely to hit
that in practice, but if you do, you'll never be able to vacuum the
index. So that's not very nice.

Wouldn't it be simpler to remove the old tuple atomically with inserting
the new tuple and updating the revmap? Or at least mark the old tuple as
deletable, so that vacuum can just delete it, without building the large
hash table to determine that it's deletable.

As it is, remove_deletable_tuples looks racy:

1. Vacuum begins, and remove_deletable_tuples performs the first pass
over the regular, non-revmap index pages, building the hash table of all
items in the index.

2. Another process inserts a new row to the heap, which causes a new
minmax tuple to be inserted and the revmap to be updated to point to the
new tuple.

3. Vacuum proceeds to scan the revmap. It will find the updated revmap
entry that points to the new index tuple. The new index tuples is not
found in the hash table, so it throws an error: "reverse map references
nonexistant (sic) index tuple".

I think to fix that you can just ignore tuples that are not found in the
hash table. (Although as I said above I think it would be simpler to not
leave behind any dead index tuples in the first place and get rid of the
vacuum scans altogether)

Regarding locking, I think it would be good to mention explicitly the
order that the pages must be locked if you need to lock multiple pages
at the same time, to avoid deadlock. Based on the Locking
considerations-section in the README, I believe the order is that you
always lock the regular index page first, and then the revmap page.
There's no mention of the order of locking two regular or two revmap
pages, but I guess you never do that ATM.

I'm quite surprised by the use of LockTuple on the index tuples. I think
the main reason for needing that is the fact that MMTuple doesn't store
the heap (range) block number that the tuple points to: LockTuple is
required to ensure that the tuple doesn't go away while a scan is
following a pointer from the revmap to it. If the MMTuple contained the
BlockNumber, a scan could check that and go back to the revmap if it
doesn't match. Alternatively, you could keep the revmap page locked when
you follow a pointer to the regular index page.

The lack of a block number on index tuples also makes my idea of moving
tuples out of the way of extending the revmap much more difficult;
there's no way to find the revmap entry pointing to an index tuple,
short of scanning the whole revmap. And also on general robustness
grounds, and for debugging purposes, it would be nice to have the block
number there.

- Heikki

On Thu, Jun 19, 2014 at 12:32 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> On Wed, Jun 18, 2014 at 4:51 AM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>> Implementing something is a good way to demonstrate how it would look like.
>> But no, I don't insist on implementing every possible design whenever a new
>> feature is proposed.
>>
>> I liked Greg's sketch of what the opclass support functions would be. It
>> doesn't seem significantly more complicated than what's in the patch now.
>
> As a counter-point to my own point there will be nothing stopping us
> in the future from generalizing things. Dealing with catalogs is
> mostly book-keeping headaches and careful work. it's something that
> might be well-suited for a GSOC or first patch from someone looking to
> familiarize themselves with the system architecture. It's hard to
> invent a whole new underlying infrastructure at the same time as
> dealing with all that book-keeping and it's hard for someone
> familiarizing themselves with the system to also have a great new
> idea. Having tasks like this that are easy to explain and that mentor
> understands well can be easier to manage than tasks where the newcomer
> has some radical new idea.

Generalizing this in the future would be highly likely to change the
on-disk format for existing indexes, which would be a problem for
pg_upgrade. I think we will likely be stuck with whatever the initial
on-disk format looks like for a very long time, which is why I think
we need to try rather hard to get this right the first time.

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

Claudio Freire wrote:

> An aggregate to generate a "compressed set" from several values
> A function which adds a new value to the "compressed set" and returns
> the new "compressed set"
> A function which tests if a value is in a "compressed set"
> A function which tests if a "compressed set" overlaps another
> "compressed set" of equal type
>
> If you can define different compressed sets, you can use this to
> generate both min/max indexes as well as bloom filter indexes. Whether
> we'd want to have both is perhaps questionable, but having the ability
> to is probably desirable.

Here's a new version of this patch, which is more generic the original
versions, and similar to what you describe.

The way it works now, each opclass needs to have three support
procedures; I've called them getOpers, maybeUpdateValues, and compare.
(I realize these names are pretty bad, and will be changing them.)
getOpers is used to obtain information about what is stored for that
data type; it says how many datum values are stored for a column of that
type (two for sortable: min and max), and how many operators it needs
setup. Then, the generic code fills in a MinmaxDesc(riptor) and creates
an initial DeformedMMTuple (which is a rather ugly name for a minmax
tuple held in memory). The maybeUpdateValues amproc can then be called
when there's a new heap tuple, which updates the DeformedMMTuple to
account for the new tuple (in essence, it's a union of the original
values and the new tuple). This can be done repeatedly (when a new
index is being created) or only once (when a new heap tuple is inserted
into an existing index). There is no need for an "aggregate".

This DeformedMMTuple can easily be turned into the on-disk
representation; there is no hardcoded assumption on the number of index
values stored per heap column, so it is possible to build an opclass
that stores a bounding box column for a geometry heap column, for
instance.

Then we have the "compare" amproc. This is used during index scans;
after extracting an index tuple, it is turned into DeformedMMTuple, and
the "compare" amproc for each column is called with the values of scan
keys. (Now that I think about this, it seems pretty much what
"consistent" is for GiST opclasses). A true return value indicates that
the scan key matches the page range boundaries and thus all pages in the
range are added to the output TID bitmap.

Of course, you can have multicolumn indexes, and (as would be expected)
each column can have totally different opclasses; so for instance you
could have an integer column and a geometric column in the same index,
and it should work fine. In a query that constrained both columns, only
those page ranges that satisfied the scan keys for both columns would be
returned.

I think this level of abstraction is good --- AFAICS it is easy to
implement opclasses for datatypes not suitable for btree opclasses such
as geometric ones, etc. This answers the concerns of those who wanted
to see this support datatypes that don't have the concept of min/max at
all. I'm not sure about bloom filters, as I've forgotten how those
work. Of course, the implementation of min/max is there: that logic has
been abstracted out into what I've called "sortable opfamilies" for now
(name suggestions welcome) --- it can be used for any datatype with a
btree opclass.

I think design-wise it ended up making a lot of sense, because all the
opclass-specific assumptions about usage of "min" and "max" values and
comparisons using the less-than etc operators are contained in the
mmsortable.c file, and the basic minmax.c file only needs to know to
call the right opclass-specific procedures. The basic code might need
some tweaks to ensure that we're not assuming anything about the
datatypes of the stored values (as opposed to the datatypes of the
indexed columns), but this is a matter of tweaking the MinmaxDesc and
the getOpers amprocs; it wouldn't require changing the on-disk
representation, and thus is upgrade-compatible.

There's a bit of boilerplate code in the amproc routines which would be
nice to be able to remove (mainly involving null values), but I think to
do that we would need to split those three amprocs into maybe four or
five, which is not as nice, so I'm not real sure about doing it.

All this being said, I'm sticking to the name "Minmax indexes". There
was a poll in pgsql-advocacy
http://www.postgresql.org/message-id/53A0B4F8.8080803@agliodbs.com
about a new name, but there were no suggestions supported by more than
one person. If a brilliant new name comes up, I'm open to changing it.

Another thing I noticed is that version 8 of the patch blindly believed
the "pages_per_range" declared in catalogs. This meant that if somebody
did "alter index foo set pages_per_range=123" the index would
immediately break (i.e. return corrupted results when queried). I have
fixed this by storing the pages_per_range value used to construct the
index in the metapage. Now if you do the ALTER INDEX thing, the new
value is only used when the index is recreated by REINDEX.

There are still things to go over before this is committable,
particularly regarding vacuuming the index, but as far as index creation
and scanning it should be good to test. (Vacuuming should work just
fine most of the time also, but there are a few wrinkles pointed out by
Heikki.)

One thing I've disabled for now is the pageinspect code that displays
index items. I need to rewrite that.

Closing thought: thinking more about it, the bit about returning
function OIDs by getOpers when creating a MinmaxDesc seems unnecessary.
I think we could go by with just returning the number of values stored
in the column, and have the operators be part of an opaque struct that's
initialized and only touched by the opclass amprocs, not by the generic
code.

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

Heikki Linnakangas wrote:
> On 06/23/2014 08:07 PM, Alvaro Herrera wrote:

> I feel that the below would nevertheless be simpler:
>
> >>I wonder if it would be simpler to just always store the revmap
> >>pages in the beginning of the index, before any other pages. Finding
> >>the revmap page would then be just as easy as with a separate fork.
> >>When the table/index is extended so that a new revmap page is
> >>needed, move the existing page at that block out of the way. Locking
> >>needs some consideration, but I think it would be feasible and
> >>simpler than you have now.
> >
> >Moving index items around is not easy, because you'd have to adjust the
> >revmap to rewrite the item pointers.
>
> Hmm. Two alternative schemes come to mind:
>
> 1. Move each index tuple off the page individually, updating the
> revmap while you do it, until the page is empty. Updating the revmap
> for a single index tuple isn't difficult; you have to do it anyway
> when an index tuple is replaced. (MMTuples don't contain a heap
> block number ATM, but IMHO they should, see below)
>
> 2. Store the new block number of the page that you moved out of the
> way in the revmap page, and leave the revmap pointers unchanged. The
> revmap pointers can be updated later, lazily.
>
> Both of those seem pretty straightforward.

The trouble I have with moving blocks around to make space, is that it
would cause the index to have periodic hiccups to make room for the new
revmap pages. One nice property that these indexes are supposed to have
is that the effect into insertion times should be pretty minimal. That
would cease to be the case if we have to do your proposed block moves.

> >>ISTM that when the old tuple cannot be updated in-place, the new
> >>index tuple is inserted with mm_doinsert(), but the old tuple is
> >>never deleted.
> >
> >It's deleted by the next vacuum.
>
> Ah I see. Vacuum reads the whole index, and builds an in-memory hash
> table that contains an ItemPointerData for every tuple in the index.
> Doesn't that require a lot of memory, for a large index? That might
> be acceptable - you ought to have plenty of RAM if you're pushing
> around multi-terabyte tables - but it would nevertheless be nice to
> not have a hard requirement for something as essential as vacuum.

I guess if you're expecting that pages_per_range=1 is a common case,
yeah it might become an issue eventually. One idea I just had is to
have a bit for each index tuple, which is set whenever the revmap no
longer points to it. That way, vacuuming is much easier: just scan the
index and delete all tuples having that bit set. No need for this hash
table stuff. I am still concerned with adding more overhead whenever a
page range is modified, so that insertions in the table continue to be
fast. If we're going to dirty the index every time, it might not be so
fast anymore. But then maybe I'm worrying about nothing; I will have to
measure how slower it is.

> Wouldn't it be simpler to remove the old tuple atomically with
> inserting the new tuple and updating the revmap? Or at least mark
> the old tuple as deletable, so that vacuum can just delete it,
> without building the large hash table to determine that it's
> deletable.

Yes, it might be simpler, but it'd require dirtying more pages on
insertions (and holding more page-level locks, for longer. Not good for
concurrent access).

> I'm quite surprised by the use of LockTuple on the index tuples. I
> think the main reason for needing that is the fact that MMTuple
> doesn't store the heap (range) block number that the tuple points
> to: LockTuple is required to ensure that the tuple doesn't go away
> while a scan is following a pointer from the revmap to it. If the
> MMTuple contained the BlockNumber, a scan could check that and go
> back to the revmap if it doesn't match. Alternatively, you could
> keep the revmap page locked when you follow a pointer to the regular
> index page.

There's the intention that these accesses be kept as concurrent as
possible; this is why we don't want to block the whole page. Locking
individual TIDs is fine in this case (which is not in SELECT FOR UPDATE)
because we can only lock a single tuple in any one index scan, so
there's no unbounded growth of the lock table.

I prefer not to have BlockNumbers in index tuples, because that would
make them larger for not much gain. That data would mostly be
redundant, and would be necessary only for vacuuming.

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

On 07/09/2014 02:16 PM, Alvaro Herrera wrote:
> The way it works now, each opclass needs to have three support
> procedures; I've called them getOpers, maybeUpdateValues, and compare.
> (I realize these names are pretty bad, and will be changing them.)

I kind of like "maybeUpdateValues". Very ... NoSQL-ish. "Maybe update
the values, maybe not." ;-)

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Wed, Jul 9, 2014 at 2:16 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> All this being said, I'm sticking to the name "Minmax indexes". There
> was a poll in pgsql-advocacy
> http://www.postgresql.org/message-id/53A0B4F8.8080803@agliodbs.com
> about a new name, but there were no suggestions supported by more than
> one person. If a brilliant new name comes up, I'm open to changing it.

How about "summarizing indexes"? That seems reasonably descriptive.

--
Peter Geoghegan

Josh Berkus wrote:
> On 07/09/2014 02:16 PM, Alvaro Herrera wrote:
> > The way it works now, each opclass needs to have three support
> > procedures; I've called them getOpers, maybeUpdateValues, and compare.
> > (I realize these names are pretty bad, and will be changing them.)
>
> I kind of like "maybeUpdateValues". Very ... NoSQL-ish. "Maybe update
> the values, maybe not." ;-)

:-) Well, that's exactly what happens. If we insert a new tuple into
the table, and the existing summarizing tuple (to use Peter's term)
already covers it, then we don't need to update the index tuple at all.
What this name doesn't say is what values are to be maybe-updated.

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

On Wed, Jul 9, 2014 at 10:16 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> there is no hardcoded assumption on the number of index
> values stored per heap column, so it is possible to build an opclass
> that stores a bounding box column for a geometry heap column, for
> instance.

I think the more Postgresy thing to do is to store one datum per heap
column. It's up to the opclass to find or make a composite data type
that stores all the necessary state. So you could make a minmax_accum
data type like NumericAggState in numeric.c:numeric_accum() or the
array of floats in float8_accum. For a bounding box a 2d geometric
min/max index could use the "box" data type for example. The way
you've done it seems more convenient but there's something to be said
for using the same style for different areas. A single bounding box
accumulator function would probably suffice for both an aggregate and
index opclass for example.

But this sounds pretty great. I think it would let me do the bloom
filter index I had in mind fairly straightforwardly. The result would
be something very similar to a bitmap index. I'm not sure if there's a
generic term that includes bitmap indexes or other summary functions
like bounding boxes (which min/max is basically -- a 1D bounding box).

Thanks a lot for listening and being so open, I think what you
describe is a lot more flexible than what you had before and I can see
some pretty great things coming out of it (including min/max itself of
course).
--
greg

On Wed, Jul 9, 2014 at 6:16 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> Another thing I noticed is that version 8 of the patch blindly believed
> the "pages_per_range" declared in catalogs. This meant that if somebody
> did "alter index foo set pages_per_range=123" the index would
> immediately break (i.e. return corrupted results when queried). I have
> fixed this by storing the pages_per_range value used to construct the
> index in the metapage. Now if you do the ALTER INDEX thing, the new
> value is only used when the index is recreated by REINDEX.

This seems a lot like parameterizing. So I guess the only thing left
is to issue a NOTICE when said alter takes place (I don't see that on
the patch, but maybe it's there?)

Claudio Freire wrote:
> On Wed, Jul 9, 2014 at 6:16 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> > Another thing I noticed is that version 8 of the patch blindly believed
> > the "pages_per_range" declared in catalogs. This meant that if somebody
> > did "alter index foo set pages_per_range=123" the index would
> > immediately break (i.e. return corrupted results when queried). I have
> > fixed this by storing the pages_per_range value used to construct the
> > index in the metapage. Now if you do the ALTER INDEX thing, the new
> > value is only used when the index is recreated by REINDEX.
>
> This seems a lot like parameterizing.

I don't understand what that means -- care to elaborate?

> So I guess the only thing left is to issue a NOTICE when said alter
> takes place (I don't see that on the patch, but maybe it's there?)

That's not in the patch. I don't think we have an appropriate place to
emit such a notice.

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

On 07/10/2014 12:20 PM, Alvaro Herrera wrote:
>> So I guess the only thing left is to issue a NOTICE when said alter
>> > takes place (I don't see that on the patch, but maybe it's there?)
> That's not in the patch. I don't think we have an appropriate place to
> emit such a notice.

What do you mean by "don't have an appropriate place"?

The suggestion is that when a user does:

ALTER INDEX foo_minmax SET PAGES_PER_RANGE=100

they should get a NOTICE:

"NOTICE: changes to pages per range will not take effect until the index
is REINDEXed"

otherwise, we're going to get a lot of "I Altered the pages per range,
but performance didn't change" emails.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus wrote:
> On 07/10/2014 12:20 PM, Alvaro Herrera wrote:
> >> So I guess the only thing left is to issue a NOTICE when said alter
> >> > takes place (I don't see that on the patch, but maybe it's there?)
> > That's not in the patch. I don't think we have an appropriate place to
> > emit such a notice.
>
> What do you mean by "don't have an appropriate place"?

What I think should happen is that if the value is changed, the index
sholud be rebuilt right there. But there is no way to have this occur
from the generic tablecmds.c code. Maybe we should extend the AM
interface so that they are notified of changes and can take action.
Inserting AM-specific code into tablecmds.c seems pretty wrong to me --
existing stuff for WITH CHECK OPTION views notwithstanding.

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

On Thu, Jul 10, 2014 at 3:50 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> On 07/10/2014 12:20 PM, Alvaro Herrera wrote:
>>> So I guess the only thing left is to issue a NOTICE when said alter
>>> > takes place (I don't see that on the patch, but maybe it's there?)
>> That's not in the patch. I don't think we have an appropriate place to
>> emit such a notice.
>
> What do you mean by "don't have an appropriate place"?
>
> The suggestion is that when a user does:
>
> ALTER INDEX foo_minmax SET PAGES_PER_RANGE=100
>
> they should get a NOTICE:
>
> "NOTICE: changes to pages per range will not take effect until the index
> is REINDEXed"
>
> otherwise, we're going to get a lot of "I Altered the pages per range,
> but performance didn't change" emails.
>

How is this different from "ALTER TABLE foo SET (FILLFACTOR=80); " or
from "ALTER TABLE foo ALTER bar SET STORAGE EXTERNAL; " ?

we don't get a notice for these cases either

--
Jaime Casanova www.2ndQuadrant.com
Professional PostgreSQL: Soporte 24x7 y capacitación
Phone: +593 4 5107566 Cell: +593 987171157

On 07/10/2014 02:30 PM, Jaime Casanova wrote:
> How is this different from "ALTER TABLE foo SET (FILLFACTOR=80); " or
> from "ALTER TABLE foo ALTER bar SET STORAGE EXTERNAL; " ?
>
> we don't get a notice for these cases either

Good idea. We should also emit notices for those. Well, maybe not for
fillfactor.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Thu, Jul 10, 2014 at 2:30 PM, Jaime Casanova <jaime(at)2ndquadrant(dot)com>
wrote:

> On Thu, Jul 10, 2014 at 3:50 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> > On 07/10/2014 12:20 PM, Alvaro Herrera wrote:
> >>> So I guess the only thing left is to issue a NOTICE when said alter
> >>> > takes place (I don't see that on the patch, but maybe it's there?)
> >> That's not in the patch. I don't think we have an appropriate place to
> >> emit such a notice.
> >
> > What do you mean by "don't have an appropriate place"?
> >
> > The suggestion is that when a user does:
> >
> > ALTER INDEX foo_minmax SET PAGES_PER_RANGE=100
> >
> > they should get a NOTICE:
> >
> > "NOTICE: changes to pages per range will not take effect until the index
> > is REINDEXed"
> >
> > otherwise, we're going to get a lot of "I Altered the pages per range,
> > but performance didn't change" emails.
> >
>
> How is this different from "ALTER TABLE foo SET (FILLFACTOR=80); " or
> from "ALTER TABLE foo ALTER bar SET STORAGE EXTERNAL; " ?
>
> we don't get a notice for these cases either
>

I think those are different. They don't rewrite existing data in the
table, but they are applied to new (and updated) data. My understanding is
that changing PAGES_PER_RANGE will have no effect on future data until a
re-index is done, even if the entire table eventually turns over.

Cheers,

Jeff

On Thu, Jul 10, 2014 at 10:29 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
>
> What I think should happen is that if the value is changed, the index
> sholud be rebuilt right there.

I disagree. It would be a non-orthogonal interface if ALTER TABLE
sometimes causes the index to be rebuilt and sometimes just makes a
configuration change. I already see a lot of user confusion when some
ALTER TABLE commands rewrite the table and some are quick meta data
changes.

Especially in this case where the type of configuration being changed
is just an internal storage parameter and the user visible shape of
the index is unchanged it would be weird to rebuild the index.

IMHO the "right" thing to do is just to say this parameter is
read-only and have the AM throw an error when the user changes it. But
even that would require an AM callback for the AM to even know about
the change.

--
greg

On Thu, Jul 10, 2014 at 6:16 AM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Claudio Freire wrote:
>
>> An aggregate to generate a "compressed set" from several values
>> A function which adds a new value to the "compressed set" and returns
>> the new "compressed set"
>> A function which tests if a value is in a "compressed set"
>> A function which tests if a "compressed set" overlaps another
>> "compressed set" of equal type
>>
>> If you can define different compressed sets, you can use this to
>> generate both min/max indexes as well as bloom filter indexes. Whether
>> we'd want to have both is perhaps questionable, but having the ability
>> to is probably desirable.
>
> Here's a new version of this patch, which is more generic the original
> versions, and similar to what you describe.

I've not read the discussion so far at all, but I found the problem
when I played with this patch. Sorry if this has already been discussed.

=# create table test as select num from generate_series(1,10) num;
SELECT 10
=# create index testidx on test using minmax (num);
CREATE INDEX
=# alter table test alter column num type text;
ERROR: could not determine which collation to use for string comparison
HINT: Use the COLLATE clause to set the collation explicitly.

Regards,

--
Fujii Masao

On 9 July 2014 23:54, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Wed, Jul 9, 2014 at 2:16 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>> All this being said, I'm sticking to the name "Minmax indexes". There
>> was a poll in pgsql-advocacy
>> http://www.postgresql.org/message-id/53A0B4F8.8080803@agliodbs.com
>> about a new name, but there were no suggestions supported by more than
>> one person. If a brilliant new name comes up, I'm open to changing it.
>
> How about "summarizing indexes"? That seems reasonably descriptive.

-1 for another name change. That boat sailed some months back.

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

On 10 July 2014 00:13, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> Josh Berkus wrote:
>> On 07/09/2014 02:16 PM, Alvaro Herrera wrote:
>> > The way it works now, each opclass needs to have three support
>> > procedures; I've called them getOpers, maybeUpdateValues, and compare.
>> > (I realize these names are pretty bad, and will be changing them.)
>>
>> I kind of like "maybeUpdateValues". Very ... NoSQL-ish. "Maybe update
>> the values, maybe not." ;-)
>
> :-) Well, that's exactly what happens. If we insert a new tuple into
> the table, and the existing summarizing tuple (to use Peter's term)
> already covers it, then we don't need to update the index tuple at all.
> What this name doesn't say is what values are to be maybe-updated.

There are lots of functions that maybe-do-things, that's just modular
programming. Not sure we need to prefix things with maybe to explain
that, otherwise we'd have maybeXXX everywhere.

More descriptive name would be MaintainIndexBounds() or similar.

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

Fujii Masao wrote:
> On Thu, Jul 10, 2014 at 6:16 AM, Alvaro Herrera
> <alvherre(at)2ndquadrant(dot)com> wrote:

> > Here's a new version of this patch, which is more generic the original
> > versions, and similar to what you describe.
>
> I've not read the discussion so far at all, but I found the problem
> when I played with this patch. Sorry if this has already been discussed.
>
> =# create table test as select num from generate_series(1,10) num;
> SELECT 10
> =# create index testidx on test using minmax (num);
> CREATE INDEX
> =# alter table test alter column num type text;
> ERROR: could not determine which collation to use for string comparison
> HINT: Use the COLLATE clause to set the collation explicitly.

Ah, yes, I need to pass down collation OIDs to comparison functions.
That's marked as XXX in various places in the code. Sorry I forgot to
mention that.

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

On Thu, Jul 10, 2014 at 4:20 PM, Alvaro Herrera
<alvherre(at)2ndquadrant(dot)com> wrote:
> Claudio Freire wrote:
>> On Wed, Jul 9, 2014 at 6:16 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
>> > Another thing I noticed is that version 8 of the patch blindly believed
>> > the "pages_per_range" declared in catalogs. This meant that if somebody
>> > did "alter index foo set pages_per_range=123" the index would
>> > immediately break (i.e. return corrupted results when queried). I have
>> > fixed this by storing the pages_per_range value used to construct the
>> > index in the metapage. Now if you do the ALTER INDEX thing, the new
>> > value is only used when the index is recreated by REINDEX.
>>
>> This seems a lot like parameterizing.
>
> I don't understand what that means -- care to elaborate?

We've been talking about bloom filters, and how their shape differs
according to the parameters of the bloom filter (number of hashes,
hash type, etc).

But after seeing this case of pages_per_range, I noticed it's an
effective-enough mechanism. Like: