Thread: Keep notnullattrs in RelOptInfo (Was part of UniqueKey patch series)

Can this information be part of PathTarget structure and hence part of
RelOptInfo::reltarget, so that it can be extended to join, group and
other kinds of RelOptInfo in future? In fact, it might be easy to do
that in this patch itself.

On Wed, Feb 10, 2021 at 8:57 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
>
> On Wed, Feb 10, 2021 at 11:18 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>>
>> Hi:
>>
>> This patch is the first patch in UniqueKey patch series[1], since I need to revise
>> that series many times but the first one would be not that often, so I'd like to
>> submit this one for review first so that I don't need to maintain it again and again.
>>
>> v1-0001-Introduce-notnullattrs-field-in-RelOptInfo-to-ind.patch
>>
>> Introduce notnullattrs field in RelOptInfo to indicate which attr are not null
>> in current query. The not null is judged by checking pg_attribute and query's
>> restrictinfo. The info is only maintained at Base RelOptInfo and Partition's
>> RelOptInfo level so far.
>>
>>
>> Any thoughts?
>>
>> [1] https://www.postgresql.org/message-id/CAKU4AWr1BmbQB4F7j22G%2BNS4dNuem6dKaUf%2B1BK8me61uBgqqg%40mail.gmail.com
>> --
>> Best Regards
>> Andy Fan (https://www.aliyun.com/)
>
>
> Add the missed patch..
>
> --
> Best Regards
> Andy Fan (https://www.aliyun.com/)



-- 
Best Wishes,
Ashutosh Bapat

Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> writes:
> Can this information be part of PathTarget structure and hence part of
> RelOptInfo::reltarget, so that it can be extended to join, group and
> other kinds of RelOptInfo in future?

Why would that be better than keeping it in RelOptInfo?

            regards, tom lane

On Wed, 10 Feb 2021 at 16:18, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> v1-0001-Introduce-notnullattrs-field-in-RelOptInfo-to-ind.patch
>
> Introduce notnullattrs field in RelOptInfo to indicate which attr are not null
> in current query. The not null is judged by checking pg_attribute and query's
> restrictinfo. The info is only maintained at Base RelOptInfo and Partition's
> RelOptInfo level so far.
>
>
> Any thoughts?

I'm not that happy with what exactly the definition is of
RelOptInfo.notnullattrs.

The comment for the field says:
+ /* Not null attrs, start from -FirstLowInvalidHeapAttributeNumber */

So you could expect someone to assume that these are a Bitmapset of
attnums for all columns in the relation marked as NOT NULL.  However,
that's not true since you use find_nonnullable_vars() to chase down
quals that filter out NULL values and you mark those too.

The reason I don't really like this is that it really depends where
you want to use RelOptInfo.notnullattrs.  If someone wants to use it
to optimise something before the base quals are evaluated then they
might be unhappy that they found some NULLs.

I think you either need to explain in detail what the field means or
separate out the two meanings somehow.

David

On Thu, Feb 11, 2021 at 8:22 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> writes:
> > Can this information be part of PathTarget structure and hence part of
> > RelOptInfo::reltarget, so that it can be extended to join, group and
> > other kinds of RelOptInfo in future?
>
> Why would that be better than keeping it in RelOptInfo?
>
>                         regards, tom lane

We have all the expressions relevant to a given relation (simple,
join, group whatever) in Pathtarget. We could remember notnullness of
attributes of a simple relation in RelOptInfo. But IMO non/nullness of
the TLEs of a relation is more useful that attributes and thus
associate those in the PathTarget which is used to produce TLEs. That
way we could use this infra in more general ways.

-- 
Best Wishes,
Ashutosh Bapat

Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> writes:
> On Thu, Feb 11, 2021 at 8:22 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> writes:
>>> Can this information be part of PathTarget structure and hence part of
>>> RelOptInfo::reltarget, so that it can be extended to join, group and
>>> other kinds of RelOptInfo in future?

>> Why would that be better than keeping it in RelOptInfo?

> We have all the expressions relevant to a given relation (simple,
> join, group whatever) in Pathtarget. We could remember notnullness of
> attributes of a simple relation in RelOptInfo. But IMO non/nullness of
> the TLEs of a relation is more useful that attributes and thus
> associate those in the PathTarget which is used to produce TLEs. That
> way we could use this infra in more general ways.

That argument seems nearly vacuous to me, because for pretty much any
expression that isn't a base-relation Var, the answer will have to be
"don't know".  Meanwhile, there are clear costs to keeping such info
in PathTarget, namely having to copy it around.  Another issue with
keeping it in PathTarget is that I'm not convinced it'll be readily
available where you need it: most places that would be interested in
making such proofs are only looking at expression trees.

Now there is one angle that *might* become easier if the info were in
PathTarget, namely that it could be simpler and more reliable to mark
nullable output columns of an outer join as being nullable (even if
they came from not-null base columns).  However, as I've muttered
about elsewhere, I'd prefer to deal with that can of worms by altering
the representation of the Vars themselves.  Again, if you're looking
at a WHERE clause, it's not real clear how you would find a relevant
PathTarget.

            regards, tom lane

On Fri, 12 Feb 2021 at 15:18, Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
> On Fri, Feb 12, 2021 at 9:02 AM David Rowley <dgrowleyml@gmail.com> wrote:
>> The reason I don't really like this is that it really depends where
>> you want to use RelOptInfo.notnullattrs.  If someone wants to use it
>> to optimise something before the base quals are evaluated then they
>> might be unhappy that they found some NULLs.
>>
>
> Do you mean the notnullattrs is not set correctly before the base quals are
> evaluated?  I think we have lots of data structures which are set just after some
> stage.  but notnullattrs is special because it is set at more than 1 stage.  However
> I'm doubtful it is unacceptable, Some fields ever change their meaning at different
> stages like Var->varno.  If a user has a misunderstanding on it, it probably will find it
> at the testing stage.

You're maybe focusing too much on your use case for notnullattrs. It
only cares about NULLs in the result for each query level.

.... thinks of an example...

OK, let's say I decided that COUNT(*) is faster than COUNT(id) so
decided that I might like to write a patch which rewrite the query to
use COUNT(*) when it was certain that "id" could not contain NULLs.

The query is:

SELECT p.partid, p.partdesc,COUNT(s.saleid) FROM part p LEFT OUTER
JOIN sales s ON p.partid = s.partid GROUP BY p.partid;

sale.saleid is marked as NOT NULL in pg_attribute.  As the writer of
the patch, I checked the comment for notnullattrs and it says "Not
null attrs, start from -FirstLowInvalidHeapAttributeNumber", so I
should be ok to assume since sales.saleid is marked in notnullattrs
that I can rewrite the query?!

The documentation about the RelOptInfo.notnullattrs needs to be clear
what exactly it means. I'm not saying your representation of how to
record NOT NULL in incorrect. I'm saying that you need to be clear
what exactly is being recorded in that field.

If you want it to mean "attribute marked here cannot output NULL
values at this query level", then you should say something along those
lines.

However, having said that, because this is a Bitmapset of
pg_attribute.attnums, it's only possible to record Vars from base
relations.  It does not seem like you have any means to record
attributes that are normally NULLable, but cannot produce NULL values
due to a strict join qual.

e.g: SELECT t.nullable FROM t INNER JOIN j ON t.nullable = j.something;

I'd expect the RelOptInfo for t not to contain a bit for the
"nullable" column, but there's no way to record the fact that the join
RelOptInfo for {t,j} cannot produce a NULL for that column. It might
be quite useful to know that for the UniqueKeys patch.

I know there's another discussion here between Ashutosh and Tom about
PathTarget's and Vars.   I had the Var idea too once myself [1] but it
was quickly shot down.  Tom's reasoning there in [1] seems legit.  I
guess we'd need some sort of planner version of Var and never confuse
it with the Parse version of Var.  That sounds like quite a big
project which would have quite a lot of code churn. I'm not sure how
acceptable it would be to have Var represent both these things.  It
gets complex when you do equal(var1, var2) and expect that to return
true when everything matches apart from the notnull field. We
currently have this issue with the "location" field and we even have a
special macro which just ignores those in equalfuncs.c.  I imagine not
many people would like to expand that to other fields.

It would be good to agree on the correct representation for Vars that
cannot produce NULLs so that we don't shut the door on classes of
optimisation that require something other than what you need for your
case.

David

[1] https://www.postgresql.org/message-id/flat/14678.1401639369%40sss.pgh.pa.us#d726d397f86755b64bb09d0c487f975f

On Sun, 4 Jul 2021 at 02:08, Andy Fan <zhihui.fan1213@gmail.com> wrote:
>  I'd start to work on UniqueKey again, it would be great that we can target it
>  to PG 15. The attached patch is just for the notnull_attrs. Since we can't say
>  a column is nullable or not without saying in which resultset, so I think attaching
> it to RelOptInfo is unavoidable. Here is how my patch works.

I'd also like to see this work progress for PG15.  My current thoughts
are that Tom as mentioned another way to track nullability inside Var.
It would be a fairly big task to do that.

Tom, I'm wondering if you might get a chance to draw up a design for
what you've got in mind with this?  I assume adding a new field in
Var, but I'm drawing a few blanks on how things might work for equal()
when one Var has the field set and another does not.

David

David Rowley <dgrowleyml@gmail.com> writes:
> Tom, I'm wondering if you might get a chance to draw up a design for
> what you've got in mind with this?  I assume adding a new field in
> Var, but I'm drawing a few blanks on how things might work for equal()
> when one Var has the field set and another does not.

As I said before, it hasn't progressed much past the handwaving stage,
but it does seem like it's time to get it done.  I doubt I'll have any
cycles for it during the commitfest, but maybe I can devote a block of
time during August.

            regards, tom lane

On Wed, 7 Jul 2021 at 13:04, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> Looking forward to watching this change closely, thank you both David and Tom!
> But I still don't understand what the faults my way have , do you mind telling the
> details?

The problem is that we don't need 6 different ways to determine if a
Var can be NULL or not.  You're proposing to add a method using
Bitmapsets and Tom has some proposing ideas around tracking
nullability in Vars.  We don't need both.

It seems to me that having it in Var allows us to have a much finer
gradient about where exactly a Var can be NULL.

For example: SELECT nullablecol FROM tab WHERE nullablecol = <value>;

If the equality operator is strict then the nullablecol can be NULL in
the WHERE clause but not in the SELECT list. Tom's idea should allow
us to determine both of those things but your idea cannot tell them
apart, so, in theory at least, Tom's idea seems better to me.

David

On Tue, Jul 6, 2021 at 5:34 PM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Sun, 4 Jul 2021 at 02:08, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> >  I'd start to work on UniqueKey again, it would be great that we can target it
> >  to PG 15. The attached patch is just for the notnull_attrs. Since we can't say
> >  a column is nullable or not without saying in which resultset, So I think attaching
> > it to RelOptInfo is unavoidable. Here is how my patch works.
>
> I'd also like to see this work progress for PG15.


Thank you David!

I am re-designing/implementing the UniqueKey, but it is better to have
a design review as soon as possible. This writing is for that. To make the
review easier, I also uploaded my in-completed patch (Correct, runable
with testcase).

Main changes are:
1. Use EC instead of expr, to cover more UniqueKey case.
2. Redesign the UniqueKey as below:

@@ -246,6 +246,7 @@ struct PlannerInfo
* subquery outputs */

List   *eq_classes; /* list of active EquivalenceClasses */
+ List   *unique_exprs; /* List of unique expr */

  bool ec_merging_done; /* set true once ECs are canonical */

+typedef struct UniqueKey
+{
+ NodeTag type;
+ Bitmapset *unique_expr_indexes;
+ bool multi_nulls;
+} UniqueKey;
+

PlannerInfo.unique_exprs is a List of unique exprs.  Unique Exprs is a set of
EquivalenceClass. for example:

CREATE TABLE T1(A INT NOT NULL, B INT NOT NULL, C INT,  pk INT primary key);
CREATE UNIQUE INDEX ON t1(a, b);

SELECT DISTINCT * FROM T1 WHERE a = c;

Then we would have PlannerInfo.unique_exprs as below
[
[EC(a, c), EC(b)],
[EC(pk)]
]

RelOptInfo(t1) would have 2 UniqueKeys.
UniqueKey1 {unique_expr_indexes=bms{0}, multinull=false]
UniqueKey2 {unique_expr_indexes=bms{1}, multinull=false]

The design will benefit many table joins cases. For example, 10 tables
join. Each table has a primary key (a, b).  Then we would have a UniqueKey like
this.

JoinRel{1,2,3,4} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b}
JoinRel{1,2,3,4, 5} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b t5.a t5.b}

This would be memory consuming and building such UniqueKey is CPU consuming as
well. With the new design, we can store it as

PlannerInfo.unique_exprs =
[
[t1.a, t1.b], -- EC is ignored in document.
[t2.a, t2.b],
[t3.a, t3.b],
[t4.a, t4.b],
[t5.a, t5.b],
[t6.a, t6.b],
[t7.a, t7.b],
[t8.a, t8.b],
[t9.a, t9.b],
[t10.a, t10.b],
]

JoinRel{1,2,3,4} -  Bitmapset{0,1,2,3} -- one bitmapword.
JoinRel{1,2,3,4,5} -  Bitmapset{0,1,2,3,4} -- one bitmapword.

3. Define a new SingleRow node and use it in joinrel as well.

+typedef struct SingleRow
+{
+ NodeTag type;
+ Index relid;
+} SingleRow;

SELECT * FROM t1, t2 WHERE t2.pk = 1;

PlannerInfo.unique_exprs
[
[t1.a, t1.b],
SingleRow{relid=2}
]

JoinRel{t1} - Bitmapset{0}
JoinRel{t2} - Bitmapset{1}
JoinRelt{1, 2} Bitmapset{0, 1} -- SingleRow will never be expanded to dedicated
exprs.

4. Cut the useless UniqueKey totally on the baserel stage based on
   root->distinct_pathkey.  If we want to use it anywhere else, I think this
   design is OK as well. for example: group by UniqueKey.

5. Implemented the relation_is_distinct_for(root, rel, distinct_pathkey)
   effectively.  Here I used distinct_pathkey rather than
   Query->distinctClause.

Since I implemented the EC in PlannerInfo.unique_exprs point to the
PathKey.pk_eqclass, so we can compare the address directly with '=', rather than
equal(a, b). (since qual would check the address as well, so even I use equal,
the performance is good as well). SingleRow is handled as well for this case.

You can check the more details in the attached patch.  Any feedback is welcome.

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

> 4. Cut the useless UniqueKey totally on the baserel stage based on
>    root->distinct_pathkey.  If we want to use it anywhere else, I think this
>    design is OK as well. for example: group by UniqueKey.
>

The intention of this is I want to cut off the useless UniqueKey ASAP. In the
previous patch, I say "if the unique_exprs not exists in root->distinct_paths,
then it is useless". However This looks only works for single rel. As for the
joinrel, we have to maintain the UniqueKey on mergeable join clause for the case
like below.

SELECT DISTINCT t1.pk FROM t1, t2 WHERE t1.a = t2.pk;
or
SELECT DISTINCT t1.pk FROM t1 left join t2 on t1.a = t2.pk;

In this case, t2.pk isn't shown in distinct_pathkey, but it is still useful at
the join stage and not useful after joining.

So how can we maintain the UniqueKey like t2.pk?
1). If t2.pk exists in root->eq_classes, keep it.
2). If t2.pk doesn't exist in RelOptInfo->reltarget after joining, discard it.

Step 1 is not so bad since we have RelOptInfo.eclass_indexes. However step 2
looks pretty boring since we have to check on every RelOptInfo and we may have
lots of RelOptInfo.

Any suggestions on this?

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

On Tue, Jul 13, 2021 at 5:55 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
> > 4. Cut the useless UniqueKey totally on the baserel stage based on
> >    root->distinct_pathkey.  If we want to use it anywhere else, I think this
> >    design is OK as well. for example: group by UniqueKey.
> >
>
> The intention of this is I want to cut off the useless UniqueKey ASAP. In the
> previous patch, I say "if the unique_exprs not exists in root->distinct_paths,
> then it is useless". However This looks only works for single rel. As for the
> joinrel, we have to maintain the UniqueKey on mergeable join clause for the case
> like below.
>
> SELECT DISTINCT t1.pk FROM t1, t2 WHERE t1.a = t2.pk;
> or
> SELECT DISTINCT t1.pk FROM t1 left join t2 on t1.a = t2.pk;
>
> In this case, t2.pk isn't shown in distinct_pathkey, but it is still useful at
> the join stage and not useful after joining.
>
> So how can we maintain the UniqueKey like t2.pk?
> 1). If t2.pk exists in root->eq_classes, keep it.
> 2). If t2.pk doesn't exist in RelOptInfo->reltarget after joining, discard it.
>
> Step 1 is not so bad since we have RelOptInfo.eclass_indexes. However step 2
> looks pretty boring since we have to check on every RelOptInfo and we may have
> lots of RelOptInfo.
>
> Any suggestions on this?
>

Just a function like truncate_useless_pathkey would be OK. For that we need
to handle uniquekey_useful_for_merging and uniquekey_useful_for_distinct.

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

Hi:

I have finished the parts for baserel, joinrel, subquery, distinctrel. I think
the hardest ones have been verified.  Here is the design overview.

1. Use EC instead of expr to cover more UniqueKey cases.
2. Redesign the UniqueKey as below:

@@ -246,6 +246,7 @@ struct PlannerInfo

List   *eq_classes; /* list of active EquivalenceClasses */
+ List   *unique_exprs; /* List of unique expr */

  bool ec_merging_done; /* set true once ECs are canonical */

+typedef struct UniqueKey
+{
+ NodeTag type;
+ Bitmapset *unique_expr_indexes;
+ bool multi_nulls;
+} UniqueKey;
+

PlannerInfo.unique_exprs is a List of unique exprs.  Unique Exprs is a set of
EquivalenceClass. for example:

CREATE TABLE T1(A INT NOT NULL, B INT NOT NULL, C INT,  pk INT primary key);
CREATE UNIQUE INDEX ON t1(a, b);

SELECT DISTINCT * FROM T1 WHERE a = c;

Then we would have PlannerInfo.unique_exprs as below
[
[EC(a, c), EC(b)],
[EC(pk)]
]

RelOptInfo(t1) would have 2 UniqueKeys.
UniqueKey1 {unique_expr_indexes=bms{0}, multinull=false]
UniqueKey2 {unique_expr_indexes=bms{1}, multinull=false]

The design will benefit many table joins cases. For instance a 10- tables join,
each table has a primary key (a, b).  Then we would have a UniqueKey like
this.

JoinRel{1,2,3,4} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b}
JoinRel{1,2,3,4,5} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b t5.a t5.b}

When more tables are joined, the list would be longer and longer, build the list
consumes both CPU cycles and memory.

With the method as above, we can store it as:

root->unique_exprs =  /* All the UniqueKey is stored once */
[
[t1.a, t1.b], -- EC is ignored in document.
[t2.a, t2.b],
[t3.a, t3.b],
[t4.a, t4.b],
[t5.a, t5.b],
[t6.a, t6.b],
[t7.a, t7.b],
[t8.a, t8.b],
[t9.a, t9.b],
[t10.a, t10.b],
]

JoinRel{1,2,3,4} -  Bitmapset{0,1,2,3} -- one bitmapword.
JoinRel{1,2,3,4,5} -  Bitmapset{0,1,2,3,4} -- one bitmapword.

The member in the bitmap is the index of root->unique_exprs rather than
root->eq_classes because we need to store the SingleRow case in
root->unqiue_exprs as well.

3. Define a new SingleRow node and use it in joinrel as well.

+typedef struct SingleRow
+{
+ NodeTag type;
+ Index relid;
+} SingleRow;

SELECT * FROM t1, t2 WHERE t2.pk = 1;

root->unique_exprs
[
[t1.a, t1.b],
SingleRow{relid=2}
]

JoinRel{t1} - Bitmapset{0}
JoinRel{t2} - Bitmapset{1}

JoinRelt{1, 2} Bitmapset{0, 1} -- SingleRow will never be expanded to dedicated
exprs.

4. Interesting UniqueKey to remove the Useless UniqueKey as soon as possible.

The overall idea is similar with PathKey, I distinguish the UniqueKey for
distinct purpose and useful_for_merging purpose.

SELECT DISTINCT pk FROM  t; -- OK, maintain it all the time, just like
root->query_pathkey.

SELECT DISTINCT t2.c FROM t1, t2 WHERE t1.d = t2.pk; -- T2's UniqueKey PK is
use before t1 join t2, but not useful after it.

Currently the known issue I didn't pass the "interesting UniqueKey" info to
subquery well [2], I'd like to talk more about this when we discuss about
UnqiueKey on subquery part.


5. relation_is_distinct_for

Now I design the function as

+ bool
+ relation_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List
  *distinct_pathkey)

It is "List *distinct_pathkey", rather than "List *exprs". The reason pathkey
has EC in it, and all the UniqueKey has EC as well. if so, the subset-like
checking is very effective.  As for the distinct/group as no-op case, we have
pathkey all the time. The only drawback of it is some clauses are not-sortable,
in this case, the root->distinct_pathkey and root->group_pathkey is not
set. However it should be rare by practice, so I ignore this part for
now. After all, I can have a relation_is_disticnt_for version for Exprs. I just
not implemented it so far.

6. EC overhead in UnqiueKey & UNION case.

Until now I didn't create any new EC for the UniqueKey case, I just used the
existing ones. However I can't handle the case like

SELECT a, b FROM t1
UNION
SELECT x, y FROM t2;

In this case, there is no EC created with existing code. and I don't want to
create them for the UniqueKey case as well.  so my plan is just not to handle
the case for UNION.

Since we need some big effort from the reviewer, I split the patch into many
smaller chunks.

Patch 1 / Patch 2:  I just split some code which UniqueKey uses but not very
interrelated. Splitting them out to reduce the core patch size.
Patch 3:  still the notnull stuff.  This one doesn't play a big role overall,
even if the design is changed at last, we can just modify some small stuff. IMO,
I don't think it is a blocker issue to move on.
Patch 4:  Support the UniqueKey for baserel.
Patch 5: Support the UniqueKey for joinrel.
Patch 6: Support the UniqueKey for some upper relation, like distinctrel,
groupby rel.

I'd suggest moving on like this:
1. Have an overall review to see if any outstanding issues the patch has.
2. If not, we can review and commit patch 1 & patch 2 to reduce the patch size.
3. Decide which method to take for not null stuff. IMO Tom's method
would be a bit
   complex and the benefit is not very clear to me[1].  So the choices
   include: a). move on UniqueKey stuff until Tom's method is ready. b). Move
   on the UniqueKey with my notnull way, and changes to Tom's method when
   necessary. I prefer method b).
4. Review & Commit the UniqueKey for BaseRel part.
5. Review & Commit the UniqueKey for JoinRel part.
6. Review & Commit the UniqueKey for SubQuery part *without* the Interesting
   UniqueKey well handled.
7. Review & Commit the UniqueKey for SubQuery part *with* the Interesting
   UniqueKey well handled.
8. Discuss about the UniqueKey on partitioned rel case and develop/review/commit
   it.
9. Apply UniqueKey stuff on more user cases rather than DISTINCT.

What do you think about this?

[1] https://www.postgresql.org/message-id/CAApHDvo5b2pYX%2BdbPy%2BysGBSarezRSfXthX32TZNFm0wPdfKGQ%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAKU4AWo6-%3D9mg3UQ5UJhGCMw6wyTPyPGgV5oh6dFvwEN%3D%2Bhb_w%40mail.gmail.com


Thanks

Hi Zhihong,

On Mon, Aug 16, 2021 at 12:35 AM Zhihong Yu <zyu@yugabyte.com> wrote:
>
>
>
> On Sun, Aug 15, 2021 at 7:33 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>>
>> Hi:
>>
>> I have finished the parts for baserel, joinrel, subquery, distinctrel. I think
>> the hardest ones have been verified.  Here is the design overview.
>>
>> 1. Use EC instead of expr to cover more UniqueKey cases.
>> 2. Redesign the UniqueKey as below:
>>
>> @@ -246,6 +246,7 @@ struct PlannerInfo
>>
>> List   *eq_classes; /* list of active EquivalenceClasses */
>> + List   *unique_exprs; /* List of unique expr */
>>
>>   bool ec_merging_done; /* set true once ECs are canonical */
>>
>> +typedef struct UniqueKey
>> +{
>> + NodeTag type;
>> + Bitmapset *unique_expr_indexes;
>> + bool multi_nulls;
>> +} UniqueKey;
>> +
>>
>> PlannerInfo.unique_exprs is a List of unique exprs.  Unique Exprs is a set of
>> EquivalenceClass. for example:
>>
>> CREATE TABLE T1(A INT NOT NULL, B INT NOT NULL, C INT,  pk INT primary key);
>> CREATE UNIQUE INDEX ON t1(a, b);
>>
>> SELECT DISTINCT * FROM T1 WHERE a = c;
>>
>> Then we would have PlannerInfo.unique_exprs as below
>> [
>> [EC(a, c), EC(b)],
>> [EC(pk)]
>> ]
>>
>> RelOptInfo(t1) would have 2 UniqueKeys.
>> UniqueKey1 {unique_expr_indexes=bms{0}, multinull=false]
>> UniqueKey2 {unique_expr_indexes=bms{1}, multinull=false]
>>
>> The design will benefit many table joins cases. For instance a 10- tables join,
>> each table has a primary key (a, b).  Then we would have a UniqueKey like
>> this.
>>
>> JoinRel{1,2,3,4} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b}
>> JoinRel{1,2,3,4,5} -  {t1.a, t1.b, t2.a, t2.b, t3.a, t3.b t4.a t4.b t5.a t5.b}
>>
>> When more tables are joined, the list would be longer and longer, build the list
>> consumes both CPU cycles and memory.
>>
>> With the method as above, we can store it as:
>>
>> root->unique_exprs =  /* All the UniqueKey is stored once */
>> [
>> [t1.a, t1.b], -- EC is ignored in document.
>> [t2.a, t2.b],
>> [t3.a, t3.b],
>> [t4.a, t4.b],
>> [t5.a, t5.b],
>> [t6.a, t6.b],
>> [t7.a, t7.b],
>> [t8.a, t8.b],
>> [t9.a, t9.b],
>> [t10.a, t10.b],
>> ]
>>
>> JoinRel{1,2,3,4} -  Bitmapset{0,1,2,3} -- one bitmapword.
>> JoinRel{1,2,3,4,5} -  Bitmapset{0,1,2,3,4} -- one bitmapword.
>>
>> The member in the bitmap is the index of root->unique_exprs rather than
>> root->eq_classes because we need to store the SingleRow case in
>> root->unqiue_exprs as well.
>>
>> 3. Define a new SingleRow node and use it in joinrel as well.
>>
>> +typedef struct SingleRow
>> +{
>> + NodeTag type;
>> + Index relid;
>> +} SingleRow;
>>
>> SELECT * FROM t1, t2 WHERE t2.pk = 1;
>>
>> root->unique_exprs
>> [
>> [t1.a, t1.b],
>> SingleRow{relid=2}
>> ]
>>
>> JoinRel{t1} - Bitmapset{0}
>> JoinRel{t2} - Bitmapset{1}
>>
>> JoinRelt{1, 2} Bitmapset{0, 1} -- SingleRow will never be expanded to dedicated
>> exprs.
>>
>> 4. Interesting UniqueKey to remove the Useless UniqueKey as soon as possible.
>>
>> The overall idea is similar with PathKey, I distinguish the UniqueKey for
>> distinct purpose and useful_for_merging purpose.
>>
>> SELECT DISTINCT pk FROM  t; -- OK, maintain it all the time, just like
>> root->query_pathkey.
>>
>> SELECT DISTINCT t2.c FROM t1, t2 WHERE t1.d = t2.pk; -- T2's UniqueKey PK is
>> use before t1 join t2, but not useful after it.
>>
>> Currently the known issue I didn't pass the "interesting UniqueKey" info to
>> subquery well [2], I'd like to talk more about this when we discuss about
>> UnqiueKey on subquery part.
>>
>>
>> 5. relation_is_distinct_for
>>
>> Now I design the function as
>>
>> + bool
>> + relation_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List
>>   *distinct_pathkey)
>>
>> It is "List *distinct_pathkey", rather than "List *exprs". The reason pathkey
>> has EC in it, and all the UniqueKey has EC as well. if so, the subset-like
>> checking is very effective.  As for the distinct/group as no-op case, we have
>> pathkey all the time. The only drawback of it is some clauses are not-sortable,
>> in this case, the root->distinct_pathkey and root->group_pathkey is not
>> set. However it should be rare by practice, so I ignore this part for
>> now. After all, I can have a relation_is_disticnt_for version for Exprs. I just
>> not implemented it so far.
>>
>> 6. EC overhead in UnqiueKey & UNION case.
>>
>> Until now I didn't create any new EC for the UniqueKey case, I just used the
>> existing ones. However I can't handle the case like
>>
>> SELECT a, b FROM t1
>> UNION
>> SELECT x, y FROM t2;
>>
>> In this case, there is no EC created with existing code. and I don't want to
>> create them for the UniqueKey case as well.  so my plan is just not to handle
>> the case for UNION.
>>
>> Since we need some big effort from the reviewer, I split the patch into many
>> smaller chunks.
>>
>> Patch 1 / Patch 2:  I just split some code which UniqueKey uses but not very
>> interrelated. Splitting them out to reduce the core patch size.
>> Patch 3:  still the notnull stuff.  This one doesn't play a big role overall,
>> even if the design is changed at last, we can just modify some small stuff. IMO,
>> I don't think it is a blocker issue to move on.
>> Patch 4:  Support the UniqueKey for baserel.
>> Patch 5: Support the UniqueKey for joinrel.
>> Patch 6: Support the UniqueKey for some upper relation, like distinctrel,
>> groupby rel.
>>
>> I'd suggest moving on like this:
>> 1. Have an overall review to see if any outstanding issues the patch has.
>> 2. If not, we can review and commit patch 1 & patch 2 to reduce the patch size.
>> 3. Decide which method to take for not null stuff. IMO Tom's method
>> would be a bit
>>    complex and the benefit is not very clear to me[1].  So the choices
>>    include: a). move on UniqueKey stuff until Tom's method is ready. b). Move
>>    on the UniqueKey with my notnull way, and changes to Tom's method when
>>    necessary. I prefer method b).
>> 4. Review & Commit the UniqueKey for BaseRel part.
>> 5. Review & Commit the UniqueKey for JoinRel part.
>> 6. Review & Commit the UniqueKey for SubQuery part *without* the Interesting
>>    UniqueKey well handled.
>> 7. Review & Commit the UniqueKey for SubQuery part *with* the Interesting
>>    UniqueKey well handled.
>> 8. Discuss about the UniqueKey on partitioned rel case and develop/review/commit
>>    it.
>> 9. Apply UniqueKey stuff on more user cases rather than DISTINCT.
>>
>> What do you think about this?
>>
>> [1] https://www.postgresql.org/message-id/CAApHDvo5b2pYX%2BdbPy%2BysGBSarezRSfXthX32TZNFm0wPdfKGQ%40mail.gmail.com
>> [2]
https://www.postgresql.org/message-id/CAKU4AWo6-%3D9mg3UQ5UJhGCMw6wyTPyPGgV5oh6dFvwEN%3D%2Bhb_w%40mail.gmail.com
>>
>>
>> Thanks
>
> Hi,
> For v3-0005-Support-UniqueKey-on-JoinRel.patch :
>
> +static void populate_joinrel_composited_uniquekey(PlannerInfo *root,
>
> populate_joinrel_composited_uniquekey -> populate_joinrel_composite_uniquekey (without the trailing d for composite)
>
> For populate_joinrel_uniquekeys():
>
> +       foreach(lc, outerrel->uniquekeys)
> +       {
> ...
> +           return;
>
> Should the remaining unique keys be considered ?
>
> For populate_joinrel_uniquekey_for_rel():
>
> +       else if (bms_equal(r->right_relids, rel->relids) && r->left_ec != NULL)
> +       {
> +           other_ecs = lappend(other_ecs, r->right_ec);
> +           other_relids = bms_add_members(other_relids, r->left_relids);
>
> It seems the append to other_ecs is the same as the one for the `bms_equal(r->left_relids, rel->relids) &&
r->right_ec!= NULL` case. Is this correct ?
 
>

Correct, both of them are bugs, I will fix them in the next version,
including the "tailing d".
Thanks for your review!

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

Hi:

patch v4 fixed the 2 bugs Zhihong reported.

Any feedback is welcome.

On Tue, Jul 6, 2021 at 9:14 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Rowley <dgrowleyml@gmail.com> writes:
> > Tom, I'm wondering if you might get a chance to draw up a design for
> > what you've got in mind with this?  I assume adding a new field in
> > Var, but I'm drawing a few blanks on how things might work for equal()
> > when one Var has the field set and another does not.
>
> As I said before, it hasn't progressed much past the handwaving stage,
> but it does seem like it's time to get it done.  I doubt I'll have any
> cycles for it during the commitfest, but maybe I can devote a block of
> time during August.
>
>                         regards, tom lane

Hi Tom:  do you get a chance to work on this? Looks like we have to fix
this one before we can move on to the uniquekey stuff.

-- 
Best Regards
Andy Fan

Unknown why people have so little interest in this, AFAICS, there are more great
usages of UniqueKey rather than the 'marking-distinct-as-noop'. The most
exciting usage for me is it is helpful for JoinRel's pathkey.

Take an example of this:

SELECT .. FROM t1 JOIN t2 ON t1.any_column = t2.uniquekey;
SELECT .. FROM t1 LEFT JOIN t2 ON t1.any_column = t2.uniquekey;

Suppose before the join, t1 has a pathkey X,  t2 has PathKey y. Then
(t1.X, t2.Y) is
ordered as well for JoinRel(t1, t2).  Then the pathkey of JoinRel(t1,
t2)  has a lot
of usage again.  Currently after the joining, only the outer join's
pathkey is maintained.

As for the extra planning cost of this, it looks like our current
infrastructure can support it
well since we know all the information when we generate the pathkey
for the Join Path.

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

> On Wed, Jul 07, 2021 at 01:20:24PM +1200, David Rowley wrote:
> On Wed, 7 Jul 2021 at 13:04, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> > Looking forward to watching this change closely, thank you both David and Tom!
> > But I still don't understand what the faults my way have , do you mind telling the
> > details?
>
> The problem is that we don't need 6 different ways to determine if a
> Var can be NULL or not.  You're proposing to add a method using
> Bitmapsets and Tom has some proposing ideas around tracking
> nullability in Vars.  We don't need both.
>
> It seems to me that having it in Var allows us to have a much finer
> gradient about where exactly a Var can be NULL.
>
> For example: SELECT nullablecol FROM tab WHERE nullablecol = <value>;
>
> If the equality operator is strict then the nullablecol can be NULL in
> the WHERE clause but not in the SELECT list. Tom's idea should allow
> us to determine both of those things but your idea cannot tell them
> apart, so, in theory at least, Tom's idea seems better to me.

Hi,

This patch still occupies some place in my head, so I would like to ask few
questions to see where it's going:

* From the last emails in this thread I gather that the main obstacle from the
  design side of things is functionality around figuring out if a Var could be
  NULL or not, and everyone is waiting for a counterproposal about how to do
  that better. Is that correct?

* Is this thread only about notnullattrs field in RelOptInfo, or about the
  UniqueKeys patch series after all? The title indicates the first one, but the
  last posted patch series included everything as far as I can see.

* Putting my archaeologist's hat on, I've tried to find out what this
  alternative proposal was about. The result findings are scattered through the
  archives -- which proves that it's a hard topic indeed -- and participants of
  this thread are probably more aware about them than I am. The most detailed
  handwaving I found in the thread [1], with an idea to introduce NullableVar
  wrapper created by parser, is that it? It makes more clear why such approach
  could be more beneficial than a new field in RelOptInfo. And if the thread is
  only about the notnullattrs, I guess it would be indeed enough to object.

* Now, how essential is notnullattrs functionality for the UniqueKeys patch
  series? From what I understand, it's being used to set multi_nulls field of
  every UniqueKey to indicate whether this key could produce NULL or not (which
  means no guaranties about uniqueness could be provided). Is there a way to
  limit the scope of the patch series and introduce UniqueKeys without require
  multi_nulls at all, or (again, in some limited situations) fetch necessary
  information somehow on the fly e.g. only from catcache without introducing
  any new infrastructure?

[1]: https://www.postgresql.org/message-id/25142.1580847861%40sss.pgh.pa.us

Hi Dmitry:

On Wed, Nov 17, 2021 at 11:20 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
>
> > On Wed, Jul 07, 2021 at 01:20:24PM +1200, David Rowley wrote:
> > On Wed, 7 Jul 2021 at 13:04, Andy Fan <zhihui.fan1213@gmail.com> wrote:
> > > Looking forward to watching this change closely, thank you both David and Tom!
> > > But I still don't understand what the faults my way have , do you mind telling the
> > > details?
> >
> > The problem is that we don't need 6 different ways to determine if a
> > Var can be NULL or not.  You're proposing to add a method using
> > Bitmapsets and Tom has some proposing ideas around tracking
> > nullability in Vars.  We don't need both.
> >
> > It seems to me that having it in Var allows us to have a much finer
> > gradient about where exactly a Var can be NULL.
> >
> > For example: SELECT nullablecol FROM tab WHERE nullablecol = <value>;
> >
> > If the equality operator is strict then the nullablecol can be NULL in
> > the WHERE clause but not in the SELECT list. Tom's idea should allow
> > us to determine both of those things but your idea cannot tell them
> > apart, so, in theory at least, Tom's idea seems better to me.
>
> Hi,
>
> This patch still occupies some place in my head, so I would like to ask few
> questions to see where it's going:

Thanks for that!

> * From the last emails in this thread I gather that the main obstacle from the
>   design side of things is functionality around figuring out if a Var could be
>   NULL or not, and everyone is waiting for a counterproposal about how to do
>   that better. Is that correct?

That is correct.

> * Is this thread only about notnullattrs field in RelOptInfo, or about the
>   UniqueKeys patch series after all? The title indicates the first one, but the
>   last posted patch series included everything as far as I can see.

This thread is talking about the path series after all. Not null maintenance
is the first step of the UniqueKey patch.  If the not null issue can't
be addressed,
the overall UniqueKey patch would be hopeless.

> * Putting my archaeologist's hat on, I've tried to find out what this
>   alternative proposal was about. The result findings are scattered through the
>   archives -- which proves that it's a hard topic indeed -- and participants of
>   this thread are probably more aware about them than I am. The most detailed
>   handwaving I found in the thread [1], with an idea to introduce NullableVar
>   wrapper created by parser, is that it? It makes more clear why such approach
>   could be more beneficial than a new field in RelOptInfo. And if the thread is
>   only about the notnullattrs, I guess it would be indeed enough to object.
>
> * Now, how essential is notnullattrs functionality for the UniqueKeys patch
>   series? From what I understand, it's being used to set multi_nulls field of
>   every UniqueKey to indicate whether this key could produce NULL or not (which
>   means no guaranties about uniqueness could be provided). Is there a way to
>   limit the scope of the patch series and introduce UniqueKeys without require
>   multi_nulls at all, or (again, in some limited situations) fetch necessary
>   information somehow on the fly e.g. only from catcache without introducing
>   any new infrastructure?
>

_I_ think there is no way to bypass that.  I guess Tom has a bigger plan on
Var (not only for notnull), but no time to invest in them so far.  If
that is the case,
personally I think we can go ahead with my method first and continue the review
process.


-- 
Best Regards
Andy Fan

On Mon, 22 Nov 2021 at 02:14, Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
> _I_ think there is no way to bypass that.  I guess Tom has a bigger plan on
> Var (not only for notnull), but no time to invest in them so far.  If
> that is the case,
> personally I think we can go ahead with my method first and continue the review
> process.

This discussion has gone on for two years now and meandered into
different directions. There have been a number of interesting
proposals and patches in that time but it's not clear now what patch
is even under consideration and what questions remain for it. And I
think this message from last November is the last comment on it so I
wonder if it's reached a bit of an impasse.

I think I would suggest starting a fresh thread with a patch distilled
from the previous discussions. Then once that's settled repeat with
additional patches, keeping the discussion focused just on the current
change.

Personally I think these kinds of optimizations are important because
they're what allow people to use SQL without micro-optimizing each
query.

-- 
greg