Re: Index Skip Scan (new UniqueKeys)

Hi David:

Thanks for looking into this.

On Fri, Jul 31, 2020 at 11:07 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Mon, 13 Jul 2020 at 10:18, Floris Van Nee <florisvannee(at)optiver(dot)com>
> wrote:
> > One question about the unique keys - probably for Andy or David: I've
> looked in the archives to find arguments for/against using Expr nodes or
> EquivalenceClasses in the Unique Keys patch. However, I couldn't really
> find a clear answer about why the current patch uses Expr rather than
> EquivalenceClasses. At some point David mentioned "that probably Expr nodes
> were needed rather than EquivalenceClasses", but it's not really clear to
> me why. What were the thoughts behind this?
>
> I'm still not quite sure on this either way. I did think
> EquivalenceClasses were more suitable before I wrote the POC patch for
> unique keys. But after that, I had in mind that Exprs might be
> better. The reason I thought this was due to the fact that the
> DISTINCT clause list is a bunch of Exprs and if the UniqueKeys were
> EquivalenceClasses then checking to see if the DISTINCT can be skipped
> turned into something more complex that required looking through lists
> of ec_members rather than just checking if the uniquekey exprs were a
> subset of the DISTINCT clause.
>

> Thinking about it a bit harder, if we did use Exprs then it would mean
> it a case like the following wouldn't work for Andy's DISTINCT no-op
> stuff.
>
> CREATE TABLE xy (x int primary key, y int not null);
>
> SELECT DISTINCT y FROM xy WHERE x=y;
>
> whereas if we use EquivalenceClasses then we'll find that we have an
> EC with x,y in it and can skip the DISTINCT since we have a UniqueKey
> containing that EquivalenceClass.

> Also, looking at what Andy wrote to make a case like the following
> work in his populate_baserel_uniquekeys() function in the 0002 patch:
>
> CREATE TABLE ab (a int, b int, primary key(a,b));
> SELECT DISTINCT a FROM ab WHERE b = 1;
>
> it's a bit uninspiring. Really what we want here when checking if we
> can skip doing the DISTINCT is a UniqueKey set using
> EquivalenceClasses as we can just insist that any unmatched UniqueKey
> items have an ec_is_const == true. However, that means we have to loop
> through the ec_members of the EquivalenceClasses in the uniquekeys
> during the DISTINCT check. That's particularly bad when you consider
> that in a partitioned table case there might be an ec_member for each
> child partition and there could be 1000s of child partitions and
> following those ec_members chains is going to be too slow.
>
> My current thoughts are that we should be using EquivalenceClasses but
> we should first add some infrastructure to make them perform better.
> My current thoughts are that we do something like what I mentioned in
> [1] or something more like what Andres mentions in [2]. After that,
> we could either make EquivalenceClass.ec_members a hash table or
> binary search tree. Or even perhaps just have a single hash table/BST
> for all EquivalenceClasses that allows very fast lookups from {Expr}
> -> {EquivalenceClass}. I think an Expr can only belong in a single
> non-merged EquivalenceClass. So when we do merging of
> EquivalenceClasses we could just repoint that data structure to point
> to the new EquivalenceClass. We'd never point to ones that have
> ec_merged != NULL. This would also allow us to fix the poor
> performance in regards to get_eclass_for_sort_expr() for partitioned
> tables.
>
> So, it seems the patch dependency chain for skip scans just got a bit
> longer :-(
>
>
I admit that EquivalenceClasses has a better expressive power. There are
2 more
cases we can handle better with EquivalenceClasses. SELECT DISTINCT a, b,
c
FROM t WHERE a = b; Currently the UniqueKey is (a, b, c), but it is better
be (a, c)
and (b, c). The other case happens similarly in group by case.

After realizing this, I am still hesitant to do that, due to the
complexity. If we do that,
we may have to maintain a EquivalenceClasses in one more place or make the
existing
EquivalenceClasses List longer, for example: SELECT pk FROM t; The
current
infrastructure doesn't create any EquivalenceClasses for pk. So we have to
create
a new one in this case and reuse some existing ones in other cases.
Finally since the
EquivalenceClasses is not so straight to upper user, we have to depend on
the
infrastructure change to look up an EquivalenceClasses quickly from an
Expr.

I rethink more about the case you provide above, IIUC, there is such issue
for joinrel.
then we can just add a EC checking for populate_baserel_uniquekeys. As for
the
DISTINCT/GROUP BY case, we should build the UniqueKeys from
root->distinct_pathkeys
and root->group_pathkeys where the EquivalenceClasses are already there.

I am still not insisting on either Expr or EquivalenceClasses right now,
if we need to
change it to EquivalenceClasses, I'd see if we need to have more places to
take
care before doing that.

--
Best Regards
Andy Fan