Re: Minmax indexes

From: Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
To: Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
Cc: Pg Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Minmax indexes
Date: 2013-09-25 20:16:52
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

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

> 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.


> 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
PostgreSQL Development, 24x7 Support, Training & Services

Attachment Content-Type Size
minmax-5a-incr.patch text/x-diff 3.6 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2013-09-25 20:23:32 Re: Minmax indexes
Previous Message David Rowley 2013-09-25 19:50:12 Re: FW: REVIEW: Allow formatting in log_line_prefix