Re: Index Skip Scan

From: Dilip Kumar <dilipbalaut(at)gmail(dot)com>
To: Dmitry Dolgov <9erthalion6(at)gmail(dot)com>
Cc: Floris Van Nee <florisvannee(at)optiver(dot)com>, David Rowley <dgrowleyml(at)gmail(dot)com>, Kyotaro Horiguchi <horikyota(dot)ntt(at)gmail(dot)com>, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>, Peter Geoghegan <pg(at)bowt(dot)ie>, Jesper Pedersen <jesper(dot)pedersen(at)redhat(dot)com>, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>, Thomas Munro <thomas(dot)munro(at)gmail(dot)com>, James Coleman <jtc331(at)gmail(dot)com>, Rafia Sabih <rafia(dot)pghackers(at)gmail(dot)com>, Jeff Janes <jeff(dot)janes(at)gmail(dot)com>, "bhushan(dot)uparkar(at)gmail(dot)com" <bhushan(dot)uparkar(at)gmail(dot)com>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>
Subject: Re: Index Skip Scan
Date: 2020-04-11 09:47:25
Message-ID: CAFiTN-sRRGZ_6za6qhN+e98wCfcLrn4bE35RqxycteKbDutorA@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Wed, Apr 8, 2020 at 1:10 AM Dmitry Dolgov <9erthalion6(at)gmail(dot)com> wrote:
>
> > On Mon, Apr 06, 2020 at 06:31:08PM +0000, Floris Van Nee wrote:
> >
> > > Hm, I wasn't aware about this one, thanks for bringing this up. Btw, Floris, I
> > > would appreciate if in the future you can make it more visible that changes you
> > > suggest contain some fixes. E.g. it wasn't clear for me from your previous email
> > > that that's the case, and it doesn't make sense to pull into different direction
> > > when we're trying to achieve the same goal :)
> >
> > I wasn't aware that this particular case could be triggered before I saw Dilip's email, otherwise I'd have mentioned it here of course. It's just that because my patch handles filter conditions in general, it works for this case too.
>
> Oh, then fortunately I've got a wrong impression, sorry and thanks for
> clarification :)
>
> > > > > In the patch I posted a week ago these cases are all handled
> > > > > correctly, as it introduces this extra logic in the Executor.
> > > >
> > > > Okay, So I think we can merge those fixes in Dmitry's patch set.
> > >
> > > I'll definitely take a look at suggested changes in filtering part.
> >
> > It may be possible to just merge the filtering part into your patch, but I'm not entirely sure. Basically you have to pull the information about skipping one level up, out of the node, into the generic IndexNext code.
>
> I was actually thinking more about just preventing skip scan in this
> situation, which is if I'm not mistaken could be solved by inspecting
> qual conditions to figure out if they're covered in the index -
> something like in attachments (this implementation is actually too
> restrictive in this sense and will not allow e.g. expressions, that's
> why I haven't bumped patch set version for it - soon I'll post an
> extended version).

Some more comments...

+ so->skipScanKey->nextkey = ScanDirectionIsForward(dir);
+ _bt_update_skip_scankeys(scan, indexRel);
+
.......
+ /*
+ * We haven't found scan key within the current page, so let's scan from
+ * the root. Use _bt_search and _bt_binsrch to get the buffer and offset
+ * number
+ */
+ so->skipScanKey->nextkey = ScanDirectionIsForward(dir);
+ stack = _bt_search(scan->indexRelation, so->skipScanKey,
+ &buf, BT_READ, scan->xs_snapshot);

Why do we need to set so->skipScanKey->nextkey =
ScanDirectionIsForward(dir); multiple times? I think it is fine to
just
set it once?

+static inline bool
+_bt_scankey_within_page(IndexScanDesc scan, BTScanInsert key,
+ Buffer buf, ScanDirection dir)
+{
+ OffsetNumber low, high;
+ Page page = BufferGetPage(buf);
+ BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+ low = P_FIRSTDATAKEY(opaque);
+ high = PageGetMaxOffsetNumber(page);
+
+ if (unlikely(high < low))
+ return false;
+
+ return (_bt_compare(scan->indexRelation, key, page, low) > 0 &&
+ _bt_compare(scan->indexRelation, key, page, high) < 1);
+}

I think the high key condition should be changed to
_bt_compare(scan->indexRelation, key, page, high) < 0 ? Because if
prefix qual is equal to the high key then also
there is no point in searching on the current page so we can directly skip.

+ /* Check if an index skip scan is possible. */
+ can_skip = enable_indexskipscan & index->amcanskip;
+
+ /*
+ * Skip scan is not supported when there are qual conditions, which are not
+ * covered by index. The reason for that is that those conditions are
+ * evaluated later, already after skipping was applied.
+ *
+ * TODO: This implementation is too restrictive, and doesn't allow e.g.
+ * index expressions. For that we need to examine index_clauses too.
+ */
+ if (root->parse->jointree != NULL)
+ {
+ ListCell *lc;
+
+ foreach(lc, (List *)root->parse->jointree->quals)
+ {
+ Node *expr, *qual = (Node *) lfirst(lc);
+ Var *var;

I think we can avoid checking for expression if can_skip is already false.

--
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Jürgen Purtz 2020-04-11 12:10:21 Re: Add A Glossary
Previous Message Pavel Stehule 2020-04-11 09:19:19 Re: proposal - psql - possibility to redirect only tabular output