/*
 * add_paths_to_joinrel
 *      Given a join relation and two component rels from which it can be made,
 *      consider all possible paths that use the two component rels as outer
 *      and inner rel respectively.  Add these paths to the join rel's pathlist
 *      if they survive comparison with other paths (and remove any existing
 *      paths that are dominated by these paths).
 *
 * Modifies the pathlist field of the joinrel node to contain the best
 * paths found so far.
 *
 * jointype is not necessarily the same as sjinfo->jointype; it might be
 * "flipped around" if we are considering joining the rels in the opposite
 * direction from what's indicated in sjinfo.
 *
 * Also, this routine and others in this module accept the special JoinTypes
 * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
 * unique-ify the outer or inner relation and then apply a regular inner
 * join.  These values are not allowed to propagate outside this module,
 * however.  Path cost estimation code may need to recognize that it's
 * dealing with such a case --- the combination of nominal jointype INNER
 * with sjinfo->jointype == JOIN_SEMI indicates that.
 */
void
add_paths_to_joinrel(PlannerInfo *root,
                     RelOptInfo *joinrel,
                     RelOptInfo *outerrel,
                     RelOptInfo *innerrel,
                     JoinType jointype,
                     SpecialJoinInfo *sjinfo,
                     List *restrictlist)
{
    List       *mergeclause_list = NIL;
    bool        mergejoin_allowed = true;
    SemiAntiJoinFactors semifactors;
    Relids        param_source_rels = NULL;
    ListCell   *lc;

    ///fprintf(stderr,"In add_paths_to_joinrel......\n");

    /*
     * Find potential mergejoin clauses.  We can skip this if we are not
     * interested in doing a mergejoin.  However, mergejoin may be our only
     * way of implementing a full outer join, so override enable_mergejoin if
     * it's a full join.
     */
    if (enable_mergejoin || jointype == JOIN_FULL)
    {

        fprintf(stderr,"----------------add_paths_to_joinrel---1\n");

        mergeclause_list = select_mergejoin_clauses(root,
                                                    joinrel,
                                                    outerrel,
                                                    innerrel,
                                                    restrictlist,
                                                    jointype,
                                                    &mergejoin_allowed);
    }

    /*
     * If it's SEMI or ANTI join, compute correction factors for cost
     * estimation.    These will be the same for all paths.
     */
    if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
    {

        fprintf(stderr,"----------------add_paths_to_joinrel---2\n");

        compute_semi_anti_join_factors(root, outerrel, innerrel,
                                       jointype, sjinfo, restrictlist,
                                       &semifactors);
    }

    /*
     * Decide whether it's sensible to generate parameterized paths for this
     * joinrel, and if so, which relations such paths should require.  There
     * is no need to create a parameterized result path unless there is a join
     * order restriction that prevents joining one of our input rels directly
     * to the parameter source rel instead of joining to the other input rel.
     * This restriction reduces the number of parameterized paths we have to
     * deal with at higher join levels, without compromising the quality of
     * the resulting plan.    We express the restriction as a Relids set that
     * must overlap the parameterization of any proposed join path.
     */
    foreach(lc, root->join_info_list)
    {

        fprintf(stderr,"----------------add_paths_to_joinrel---3\n");

        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);

        /*
         * SJ is relevant to this join if we have some part of its RHS
         * (possibly not all of it), and haven't yet joined to its LHS.  (This
         * test is pretty simplistic, but should be sufficient considering the
         * join has already been proven legal.)  If the SJ is relevant, it
         * presents constraints for joining to anything not in its RHS.
         */
        if (bms_overlap(joinrel->relids, sjinfo->min_righthand) &&
            !bms_overlap(joinrel->relids, sjinfo->min_lefthand))
        {

            fprintf(stderr,"----------------add_paths_to_joinrel---4\n");

            param_source_rels = bms_join(param_source_rels,
                                         bms_difference(root->all_baserels,
                                                     sjinfo->min_righthand));
        }

        /* full joins constrain both sides symmetrically */
        if (sjinfo->jointype == JOIN_FULL &&
            bms_overlap(joinrel->relids, sjinfo->min_lefthand) &&
            !bms_overlap(joinrel->relids, sjinfo->min_righthand))
        {

            fprintf(stderr,"----------------add_paths_to_joinrel---5\n");

            param_source_rels = bms_join(param_source_rels,
                                         bms_difference(root->all_baserels,
                                                      sjinfo->min_lefthand));
        }
    }

    /*
     * 1. Consider mergejoin paths where both relations must be explicitly
     * sorted.    Skip this if we can't mergejoin.
     */
    if (mergejoin_allowed)
    {
        fprintf(stderr,"----------------add_paths_to_joinrel---6\n");

        sort_inner_and_outer(root, joinrel, outerrel, innerrel,
                             restrictlist, mergeclause_list, jointype,
                             sjinfo, param_source_rels);
    }

    /*
     * 2. Consider paths where the outer relation need not be explicitly
     * sorted. This includes both nestloops and mergejoins where the outer
     * path is already ordered.  Again, skip this if we can't mergejoin.
     * (That's okay because we know that nestloop can't handle right/full
     * joins at all, so it wouldn't work in the prohibited cases either.)
     */
    if (mergejoin_allowed)
    {

        fprintf(stderr,"----------------add_paths_to_joinrel---7\n");

        match_unsorted_outer(root, joinrel, outerrel, innerrel,
                             restrictlist, mergeclause_list, jointype,
                             sjinfo, &semifactors, param_source_rels);
    }

#ifdef NOT_USED

    /*
     * 3. Consider paths where the inner relation need not be explicitly
     * sorted.    This includes mergejoins only (nestloops were already built in
     * match_unsorted_outer).
     *
     * Diked out as redundant 2/13/2000 -- tgl.  There isn't any really
     * significant difference between the inner and outer side of a mergejoin,
     * so match_unsorted_inner creates no paths that aren't equivalent to
     * those made by match_unsorted_outer when add_paths_to_joinrel() is
     * invoked with the two rels given in the other order.
     */
    if (mergejoin_allowed)
    {

        fprintf(stderr,"----------------add_paths_to_joinrel---8\n");

        match_unsorted_inner(root, joinrel, outerrel, innerrel,
                             restrictlist, mergeclause_list, jointype,
                             sjinfo, &semifactors, param_source_rels);
    }
#endif

    /*
     * 4. Consider paths where both outer and inner relations must be hashed
     * before being joined.  As above, disregard enable_hashjoin for full
     * joins, because there may be no other alternative.
     */
    if (enable_hashjoin || jointype == JOIN_FULL)
    {
        fprintf(stderr,"----------------add_paths_to_joinrel---9\n");

        hash_inner_and_outer(root, joinrel, outerrel, innerrel,
                             restrictlist, jointype,
                             sjinfo, &semifactors, param_source_rels);
    }
}

postgres=# select * from sales s inner join customers c on c.cust_id = s.cust_id;
 cust_id |   item   | cust_id | cust_name 
---------+----------+---------+-----------
       2 | camera   |       2 | John Doe
       3 | computer |       3 | Jane Doe
       3 | monitor  |       3 | Jane Doe
(3 rows)

postgres=#