Re: UniqueKey v2

Antonin Houska <ah@cybertec.at> writes:

>> Could you make the reason clearer for adding 'List *opfamily_lists;'
>> into UniqueKey?  You said "This is needed to create ECs in the parent
>> query if the upper relation represents a subquery." but I didn't get the
>> it. Since we need to maintain the UniqueKey in the many places, I'd like
>> to keep it as simple as possbile. Of course, anything essentical should
>> be added for sure. 
>
> If unique keys are generated for a subquery output, they also need to be
> created for the corresponding relation in the upper query ("sub" in the
> following example):

OK.
>
> select * from tab1 left join (select * from tab2) sub;
>
> However, to create an unique key for "sub", you need an EC for each expression
> of the key.

OK.
> And to create an EC, you in turn need the list of operator
> families.

I'm thinking if we need to "create" any EC. Can you find out a user case
where the outer EC is missed and the UniqueKey is still interesting? I
don't have an example now.  

convert_subquery_pathkeys has a similar sistuation and has the following
codes:

                outer_ec =
                    get_eclass_for_sort_expr(root,
                                             (Expr *) outer_var,
                                             sub_eclass->ec_opfamilies,
                                             sub_member->em_datatype,
                                             sub_eclass->ec_collation,
                                             0,
                                             rel->relids,
                                             NULL,
                                             false);

                /*
                 * If we don't find a matching EC, sub-pathkey isn't
                 * interesting to the outer query
                 */
                if (outer_ec)
                    best_pathkey =
                        make_canonical_pathkey(root,
                                               outer_ec,
                                               sub_pathkey->pk_opfamily,
                                               sub_pathkey->pk_strategy,
                                               sub_pathkey->pk_nulls_first);
            }

> Even if the parent query already had ECs for the columns of "sub" which are
> contained in the unique key, you need to make sure that those ECs are
> "compatible" with the ECs of the subquery which generated the unique key. That
> is, if an EC of the subquery considers certain input values equal, the EC of
> the parent query must also be able to determine if they are equal or not.
>
>> > * RelOptInfo.notnullattrs
>> >
>> >   My understanding is that this field contains the set attributes whose
>> >   uniqueness is guaranteed by the unique key. They are acceptable because they
>> >   are either 1) not allowed to be NULL due to NOT NULL constraint or 2) NULL
>> >   value makes the containing row filtered out, so the row cannot break
>> >   uniqueness of the output. Am I right?
>> >
>> >   If so, I suggest to change the field name to something less generic, maybe
>> >   'uniquekey_attrs' or 'uniquekey_candidate_attrs', and adding a comment that
>> >   more checks are needed before particular attribute can actually be used in
>> >   UniqueKey.
>> 
>> I don't think so, UniqueKey is just one of the places to use this
>> not-null property, see 3af704098 for the another user case of it. 
>> 
>> (Because of 3af704098, we should leverage notnullattnums somehow in this
>> patch, which will be included in the next version as well).
>
> In your patch you modify 'notnullattrs' in add_base_clause_to_rel(), but that
> does not happen to 'notnullattnums' in the current master branch. Thus I think
> that 'notnullattrs' is specific to the unique keys feature, so the field name
> should be less generic.

OK.

>> >
>> > * uniquekey_useful_for_merging()
>> >
>> >   How does uniqueness relate to merge join? In README.uniquekey you seem to
>> >   point out that a single row is always sorted, but I don't think this
>> >   function is related to that fact. (Instead, I'd expect that pathkeys are
>> >   added to all paths for a single-row relation, but I'm not sure you do that
>> >   in the current version of the patch.)
>> 
>> The merging is for "mergejoinable join clauses", see function
>> eclass_useful_for_merging. Usually I think it as operator "t1.a = t2.a";
>
> My question is: why is the uniqueness important specifically to merge join? I
> understand that join evaluation can be more efficient if we know that one
> input relation is unique (i.e. we only scan that relation until we find the
> first match), but this is not specific to merge join.

So the answer is the "merging" in uniquekey_useful_for_merging() has
nothing with merge join. 

>> > * is_uniquekey_useful_afterjoin()
>> >
>> >   Now that my patch (0004) allows propagation of the unique keys from a
>> >   subquery to the upper query, I was wondering if the UniqueKey structure
>> >   needs the 'use_for_distinct field' I mean we should now propagate the unique
>> >   keys to the parent query whether the subquery has DISTINCT clause or not. I
>> >   noticed that the field is checked by is_uniquekey_useful_afterjoin(), so I
>> >   changed the function to always returned true. However nothing changed in the
>> >   output of regression tests (installcheck). Do you insist that the
>> >   'use_for_distinct' field is needed?
>
> I miss your answer to this comment.

After we considers the uniquekey from subquery, 'use_for_distinct' field
is not needed.

>> >   ** What does the 'multi' word in the function name mean?
>> 
>> multi means multiple, I thought we use this short name in the many
>> places, for ex bt_multi_page_stats after a quick search. 
>
> Why not simply uniquekey_contains_nulls() ?

> Actually I wouldn't say that an instance of UniqueKey contains any value (NULL
> or NOT NULL) because it describes the whole relation rather than particular
> row. I consider UniqueKey to be a set of expressions. How about
> uniquekey_expression_nullable() ?

uniquekey_expression_nullable() is a better name, I will use it in the
next version.

IIUC, we have reached to the agreement based on your latest response for
the most of the questions. Please point me if I missed anything.  

>> >   Of course one problem is that the number of combinations can grow
>> >   exponentially as new relations are joined.
>> 
>> Yes, that's why "rule 1" needed and "How to reduce the overhead" in
>> UniqueKey.README is introduced. 
>
> What if we are interested in unique keys of a subquery, but the subquery has
> no DISTINCT clause?

I agree we should remove the prerequisite of "use_for_distinct". 

-- 
Best Regards
Andy Fan