Date: Sun, 10 May 2020 19:49:35 +0200
From: Dmitry Dolgov <9erthalion6@gmail.com>
To: Dilip Kumar <dilipbalaut@gmail.com>
Cc: Floris Van Nee <florisvannee@optiver.com>,
	David Rowley <dgrowleyml@gmail.com>,
	Kyotaro Horiguchi <horikyota.ntt@gmail.com>,
	Tomas Vondra <tomas.vondra@2ndquadrant.com>,
	Peter Geoghegan <pg@bowt.ie>,
	Jesper Pedersen <jesper.pedersen@redhat.com>,
	Alvaro Herrera <alvherre@2ndquadrant.com>,
	Thomas Munro <thomas.munro@gmail.com>,
	James Coleman <jtc331@gmail.com>,
	Rafia Sabih <rafia.pghackers@gmail.com>,
	Jeff Janes <jeff.janes@gmail.com>,
	"bhushan.uparkar@gmail.com" <bhushan.uparkar@gmail.com>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>,
	Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Message-ID: <20200510174935.teqyazdw6jj6vh47@localhost>
References: <20200325085100.5fixaiteuoln4f45@localhost>
 <CAFiTN-sgsxS7cXi0sd9UWmbSwjPc6+78rGa4SFfAxGfs5zj7Aw@mail.gmail.com>
 <20200405161029.fpqqll7xbgfqy5na@localhost>
 <CAFiTN-sRnYp7MkctzYakyjWRPQQHFzEAwKV8vwf+sUgA+8JtQw@mail.gmail.com>
 <80ef5f0744f542b18e508fb589a6425a@opammb0562.comp.optiver.com>
 <CAFiTN-tp8S3BTwYXT33tnY=53fNCsS4ZZUjbEFtcJym1acoLeA@mail.gmail.com>
 <20200406163941.rh3okji2rhbnptyt@localhost>
 <8abe43ac82714c2f9044fb8bac0ebfd0@opammb0562.comp.optiver.com>
 <20200407194220.edf4nbi7l4cpxk4v@localhost>
 <CAFiTN-sRRGZ_6za6qhN+e98wCfcLrn4bE35RqxycteKbDutorA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: 
 <CAFiTN-sRRGZ_6za6qhN+e98wCfcLrn4bE35RqxycteKbDutorA@mail.gmail.com>
Precedence: bulk

> On Sat, Apr 11, 2020 at 03:17:25PM +0530, Dilip Kumar wrote:
>
> Some more comments...

Thanks for reviewing. Since this patch took much longer than I expected,
it's useful to have someone to look at it with a "fresh eyes".

> + 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?

I believe it was necessary for previous implementations, but in the
current version we can avoid this, you're right.

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

From nbtree/README and comments to functions like _bt_split I've got an
impression that the high key could be equal to the last item on the leaf
page, so there is a point in searching. Is that incorrect?

> + /* 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.

Yes, that makes sense. I'll include your suggestions into the next
rebased version I'm preparing.