Date: Tue, 1 Dec 2020 21:21:19 +0100
From: Dmitry Dolgov <9erthalion6@gmail.com>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Peter Geoghegan <pg@bowt.ie>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>,
	Jesper Pedersen <jesper.pedersen@redhat.com>,
	David Rowley <dgrowleyml@gmail.com>,
	Floris Van Nee <florisvannee@optiver.com>,
	Kyotaro Horiguchi <horikyota.ntt@gmail.com>,
	Thomas Munro <thomas.munro@gmail.com>,
	Tomas Vondra <tomas.vondra@2ndquadrant.com>,
	Andy Fan <zhihui.fan1213@gmail.com>,
	Dilip Kumar <dilipbalaut@gmail.com>
Subject: Re: Index Skip Scan (new UniqueKeys)
Message-ID: <20201201202119.jcsr7z6cdiffuops@localhost>
References: <20200609102247.jdlatmfyeecg52fi@localhost>
 <CAH2-WznUY=0_yYek3ciNv4-ObotrWokAZbGnWjEsqxZ4oMWCGg@mail.gmail.com>
 <20200711161258.5modwkdeszhf55ux@localhost>
 <CAH2-Wzkyx9A28bb5yNiN+6iRDJpGS0sQdAhyWEAA_yjrsh98-Q@mail.gmail.com>
 <20200727102431.mjspwec4yhzeyny2@localhost>
 <20200815141240.wuyc6ijkmnywywtn@localhost>
 <CAH2-Wz=z8yXENbUWgP+3PhfS7HfB9bj01XuuSY8bj4jasQj_3A@mail.gmail.com>
 <20201006152039.xs2ul7il52sowhlu@localhost>
 <20201024164553.tel5uynf2dzyh4az@localhost>
 <598ff988-5ebb-f6f7-0c9d-82208dff3bbd@iki.fi>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <598ff988-5ebb-f6f7-0c9d-82208dff3bbd@iki.fi>
Precedence: bulk

> On Mon, Nov 30, 2020 at 04:42:20PM +0200, Heikki Linnakangas wrote:
>
> I had a quick look at this patch. I haven't been following this thread, so
> sorry if I'm repeating old arguments, but here we go:

Thanks!

> - I'm surprised you need a new index AM function (amskip) for this. Can't
> you just restart the scan with index_rescan()? The btree AM can check if the
> new keys are on the same page, and optimize the rescan accordingly, like
> amskip does. That would speed up e.g. nested loop scans too, where the keys
> just happen to be clustered.

An interesting point. At the moment I'm not sure whether it's possible
to implement skipping via index_rescan or not, need to take a look. But
checking if the new keys are on the same page would introduce some
overhead I guess, wouldn't it be too invasive to add it into already
existing btree AM?

> - Does this optimization apply to bitmap index scans?

No, from what I understand it doesn't.

> - This logic in build_index_paths() is not correct:
>
> > +		/*
> > +		 * 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;
> > +				bool found = false;
> > +
> > +				if (!is_opclause(qual))
> > +				{
> > +					not_empty_qual = true;
> > +					break;
> > +				}
> > +
> > +				expr = get_leftop(qual);
> > +
> > +				if (!IsA(expr, Var))
> > +				{
> > +					not_empty_qual = true;
> > +					break;
> > +				}
> > +
> > +				var = (Var *) expr;
> > +
> > +				for (int i = 0; i < index->ncolumns; i++)
> > +				{
> > +					if (index->indexkeys[i] == var->varattno)
> > +					{
> > +						found = true;
> > +						break;
> > +					}
> > +				}
> > +
> > +				if (!found)
> > +				{
> > +					not_empty_qual = true;
> > +					break;
> > +				}
> > +			}
> > +		}
>
> If you care whether the qual is evaluated by the index AM or not, you need
> to also check that the operator is indexable. Attached is a query that
> demonstrates that problem.
> ...
> Also, you should probably check that the index quals are in the operator
> family as that used for the DISTINCT.

Yes, good point, will change this in the next version.

> I'm actually a bit confused why we need this condition. The IndexScan
> executor node should call amskip() only after checking the additional quals,
> no?

This part I don't quite get, what exactly you mean by checking the
additional quals in the executor node? But at the end of the day this
condition was implemented exactly to address the described issue, which
was found later and added to the tests.