PostgreSQL 소스 판독(66) - 쿼리 문장 #51(make one rel 함수 #16-merge join#1)

25137 단어
이 절은 동적 기획 알고리즘 실현(standard join search) 중의join 을 대체적으로 소개한다.search_one_level->make_join_rel->populate_joinrel_with_paths->add_paths_to_joinrel 함수 중sortinner_and_outer 함수, 이 함수는mergejoin 접근 경로를 구성하려고 시도합니다.merge join의 알고리즘 구현 위조 코드는 다음과 같다: READ 데이터set_1 SORT BY JOIN KEY TO temp_ds1 READ data_set_2 SORT BY JOIN KEY TO temp_ds2 READ ds1_row FROM temp_ds1 READ ds2_row FROM temp_ds2 WHILE NOT eof ON temp_ds1,temp_ds2 LOOP IF ( temp_ds1.key = temp_ds2.key ) OUTPUT JOIN ds1_row,ds2_row ELSIF ( temp_ds1.key <= temp_ds2.key ) READ ds1_row FROM temp_ds1 ELSIF ( temp_ds1.key => temp_ds2.key ) READ ds2_row FROM temp_ds2 END LOOP
1. 데이터 구조
Cost 관련 주의: 실제 사용하는 매개 변수 값은 시스템 설정 파일을 통해 정의됩니다. 이곳의 상수 정의가 아닙니다.
 typedef double Cost; /* execution cost (in page-access units) */

 /* defaults for costsize.c's Cost parameters */
 /* NB: cost-estimation code should use the variables, not these constants! */
 /*   :             ,          ! */
 /* If you change these, update backend/utils/misc/postgresql.sample.conf */
 #define DEFAULT_SEQ_PAGE_COST  1.0       //    page   
 #define DEFAULT_RANDOM_PAGE_COST  4.0      //    page   
 #define DEFAULT_CPU_TUPLE_COST  0.01     //       CPU  
 #define DEFAULT_CPU_INDEX_TUPLE_COST 0.005   //         CPU  
 #define DEFAULT_CPU_OPERATOR_COST  0.0025    //          CPU  
 #define DEFAULT_PARALLEL_TUPLE_COST 0.1    //    ,   worker          worker   
 #define DEFAULT_PARALLEL_SETUP_COST  1000.0  //           
 
 #define DEFAULT_EFFECTIVE_CACHE_SIZE  524288    /*      , measured in pages */

 double      seq_page_cost = DEFAULT_SEQ_PAGE_COST;
 double      random_page_cost = DEFAULT_RANDOM_PAGE_COST;
 double      cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST;
 double      cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST;
 double      cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST;
 double      parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST;
 double      parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST;
 
 int         effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE;
 Cost        disable_cost = 1.0e10;//1  10 0,           ,           
 
 int         max_parallel_workers_per_gather = 2;//  gather   worker 

2. 원본 코드 해석
sort_inner_and_outer 함수는mergejoin 접근 경로를 구성하려고 시도합니다.구조 과정 중의 원가 추산 실현 함수 initialcost_mergejoin과finalcost_mergejoin은 다음 절에서 소개합니다.

//------------------------------------------------ sort_inner_and_outer

/*
 * sort_inner_and_outer
 *    Create mergejoin join paths by explicitly sorting both the outer and
 *    inner join relations on each available merge ordering.
 *        outer inner ,  mergejoin    .
 *
 * 'joinrel' is the join relation
 * joinrel-       relation
 * 'outerrel' is the outer join relation
 * outerrel-     outer relation(    ,   )
 * 'innerrel' is the inner join relation
 * innerrel-     inner relation(    )
 * 'jointype' is the type of join to do
 * jointype-    
 * 'extra' contains additional input values
 * extra-       
 */
static void
sort_inner_and_outer(PlannerInfo *root,
                     RelOptInfo *joinrel,
                     RelOptInfo *outerrel,
                     RelOptInfo *innerrel,
                     JoinType jointype,
                     JoinPathExtraData *extra)
{
    JoinType    save_jointype = jointype;
    Path       *outer_path;
    Path       *inner_path;
    Path       *cheapest_partial_outer = NULL;
    Path       *cheapest_safe_inner = NULL;
    List       *all_pathkeys;
    ListCell   *l;

    /*
     * We only consider the cheapest-total-cost input paths, since we are
     * assuming here that a sort is required.  We will consider
     * cheapest-startup-cost input paths later, and only if they don't need a
     * sort.
     *             ,           。
     *               ,               。
     *
     * This function intentionally does not consider parameterized input
     * paths, except when the cheapest-total is parameterized.  If we did so,
     * we'd have a combinatorial explosion of mergejoin paths of dubious
     * value.  This interacts with decisions elsewhere that also discriminate
     * against mergejoins with parameterized inputs; see comments in
     * src/backend/optimizer/README.
     *                ,             。
     *             ,mergejoin           ,      。
     *                 ,       "  "        mergejoin;
     *    src/backend/optimizer/README    。
     */
    outer_path = outerrel->cheapest_total_path;
    inner_path = innerrel->cheapest_total_path;

    /*
     * If either cheapest-total path is parameterized by the other rel, we
     * can't use a mergejoin.  (There's no use looking for alternative input
     * paths, since these should already be the least-parameterized available
     * paths.)
     *                         ,          。
     * (             ,                    。)
     */
    if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
        PATH_PARAM_BY_REL(inner_path, outerrel))
        return;

    /*
     * If unique-ification is requested, do it and then handle as a plain
     * inner join.
     *         ,             JOIN_INNER    
     */
    if (jointype == JOIN_UNIQUE_OUTER)
    {
        outer_path = (Path *) create_unique_path(root, outerrel,
                                                 outer_path, extra->sjinfo);
        Assert(outer_path);
        jointype = JOIN_INNER;
    }
    else if (jointype == JOIN_UNIQUE_INNER)
    {
        inner_path = (Path *) create_unique_path(root, innerrel,
                                                 inner_path, extra->sjinfo);
        Assert(inner_path);
        jointype = JOIN_INNER;
    }

    /*
     * If the joinrel is parallel-safe, we may be able to consider a partial
     * merge join.  However, we can't handle JOIN_UNIQUE_OUTER, because the
     * outer path will be partial, and therefore we won't be able to properly
     * guarantee uniqueness.  Similarly, we can't handle JOIN_FULL and
     * JOIN_RIGHT, because they can produce false null extended rows.  Also,
     * the resulting path must not be parameterized.
     *           ,            。
     *   ,PG    JOIN_UNIQUE_OUTER,          ,            。
     *    ,PG    JOIN_FULL JOIN_RIGHT,            。
     *   ,           。
     */
    if (joinrel->consider_parallel &&
        save_jointype != JOIN_UNIQUE_OUTER &&
        save_jointype != JOIN_FULL &&
        save_jointype != JOIN_RIGHT &&
        outerrel->partial_pathlist != NIL &&
        bms_is_empty(joinrel->lateral_relids))
    {
        cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);

        if (inner_path->parallel_safe)
            cheapest_safe_inner = inner_path;
        else if (save_jointype != JOIN_UNIQUE_INNER)
            cheapest_safe_inner =
                get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
    }

    /*
     * Each possible ordering of the available mergejoin clauses will generate
     * a differently-sorted result path at essentially the same cost.  We have
     * no basis for choosing one over another at this level of joining, but
     * some sort orders may be more useful than others for higher-level
     * mergejoins, so it's worth considering multiple orderings.
     *    mergejoin                                。
     *         ,             ,          ,
     *               ,             。
     *
     * Actually, it's not quite true that every mergeclause ordering will
     * generate a different path order, because some of the clauses may be
     * partially redundant (refer to the same EquivalenceClasses).  Therefore,
     * what we do is convert the mergeclause list to a list of canonical
     * pathkeys, and then consider different orderings of the pathkeys.
     *    ,     mergeclause           ,              (      )。
     *   ,     mergeclause              ,            。
     *
     * Generating a path for *every* permutation of the pathkeys doesn't seem
     * like a winning strategy; the cost in planning time is too high. For
     * now, we generate one path for each pathkey, listing that pathkey first
     * and the rest in random order.  This should allow at least a one-clause
     * mergejoin without re-sorting against any other possible mergejoin
     * partner path.  But if we've not guessed the right ordering of secondary
     * keys, we may end up evaluating clauses as qpquals when they could have
     * been done as mergeclauses.  (In practice, it's rare that there's more
     * than two or three mergeclauses, so expending a huge amount of thought
     * on that is probably not worth it.)
     *                        ,           。
     *   ,     pathkey      ,      pathkey,              。
     *              mergejoin,            mergejoin        。
     *                ,      qpquals         ,          mergeclauses  。
     * (   ,           mergeclauses,                )。
     *
     * The pathkey order returned by select_outer_pathkeys_for_merge() has
     * some heuristics behind it (see that function), so be sure to try it
     * exactly as-is as well as making variants.
     *     select_outer_pathkeys_for_merge          pathkey
     *           (      ),           ,     。
     */
    all_pathkeys = select_outer_pathkeys_for_merge(root,
                                                   extra->mergeclause_list,
                                                   joinrel);

    foreach(l, all_pathkeys)//          
    {
        List       *front_pathkey = (List *) lfirst(l);
        List       *cur_mergeclauses;
        List       *outerkeys;
        List       *innerkeys;
        List       *merge_pathkeys;

        /* Make a pathkey list with this guy first */
        if (l != list_head(all_pathkeys))
            outerkeys = lcons(front_pathkey,
                              list_delete_ptr(list_copy(all_pathkeys),
                                              front_pathkey));
        else
            outerkeys = all_pathkeys;   /* no work at first one... */

        /* Sort the mergeclauses into the corresponding ordering */
        cur_mergeclauses =
            find_mergeclauses_for_outer_pathkeys(root,
                                                 outerkeys,
                                                 extra->mergeclause_list);

        /* Should have used them all... */
        Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));

        /* Build sort pathkeys for the inner side */
        innerkeys = make_inner_pathkeys_for_merge(root,
                                                  cur_mergeclauses,
                                                  outerkeys);

        /* Build pathkeys representing output sort order */
        merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
                                             outerkeys);

        /*
         * And now we can make the path.
         *
         * Note: it's possible that the cheapest paths will already be sorted
         * properly.  try_mergejoin_path will detect that case and suppress an
         * explicit sort step, so we needn't do so here.
         *   :               。
         *      try_mergejoin_path                ,           。
         */
        try_mergejoin_path(root,
                           joinrel,
                           outer_path,
                           inner_path,
                           merge_pathkeys,
                           cur_mergeclauses,
                           outerkeys,
                           innerkeys,
                           jointype,
                           extra,
                           false);

        /*
         * If we have partial outer and parallel safe inner path then try
         * partial mergejoin path.
         *     
         */
        if (cheapest_partial_outer && cheapest_safe_inner)
            try_partial_mergejoin_path(root,
                                       joinrel,
                                       cheapest_partial_outer,
                                       cheapest_safe_inner,
                                       merge_pathkeys,
                                       cur_mergeclauses,
                                       outerkeys,
                                       innerkeys,
                                       jointype,
                                       extra);
    }
}


//----------------------------------- try_mergejoin_path
/*
 * try_mergejoin_path
 *    Consider a merge join path; if it appears useful, push it into
 *    the joinrel's pathlist via add_path().
 *      merge join path,   ,       add_path    joinrel pathlist   
 */
static void
try_mergejoin_path(PlannerInfo *root,
                   RelOptInfo *joinrel,
                   Path *outer_path,
                   Path *inner_path,
                   List *pathkeys,
                   List *mergeclauses,
                   List *outersortkeys,
                   List *innersortkeys,
                   JoinType jointype,
                   JoinPathExtraData *extra,
                   bool is_partial)
{
    Relids      required_outer;
    JoinCostWorkspace workspace;

    if (is_partial)
    {
        try_partial_mergejoin_path(root,
                                   joinrel,
                                   outer_path,
                                   inner_path,
                                   pathkeys,
                                   mergeclauses,
                                   outersortkeys,
                                   innersortkeys,
                                   jointype,
                                   extra);//    
        return;
    }

    /*
     * Check to see if proposed path is still parameterized, and reject if the
     * parameterization wouldn't be sensible.
     *               ,        ,   。
     */
    required_outer = calc_non_nestloop_required_outer(outer_path,
                                                      inner_path);
    if (required_outer &&
        !bms_overlap(required_outer, extra->param_source_rels))
    {
        /* Waste no memory when we reject a path here */
        bms_free(required_outer);
        return;
    }

    /*
     * If the given paths are already well enough ordered, we can skip doing
     * an explicit sort.
     *             ,       .
     */
    if (outersortkeys &&
        pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
        outersortkeys = NIL;
    if (innersortkeys &&
        pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
        innersortkeys = NIL;

    /*
     * See comments in try_nestloop_path().
     */
    initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
                           outer_path, inner_path,
                           outersortkeys, innersortkeys,
                           extra);//   mergejoin

    if (add_path_precheck(joinrel,
                          workspace.startup_cost, workspace.total_cost,
                          pathkeys, required_outer))//      
    {
        add_path(joinrel, (Path *)
                 create_mergejoin_path(root,
                                       joinrel,
                                       jointype,
                                       &workspace,
                                       extra,
                                       outer_path,
                                       inner_path,
                                       extra->restrictlist,
                                       pathkeys,
                                       required_outer,
                                       mergeclauses,
                                       outersortkeys,
                                       innersortkeys));//       
    }
    else
    {
        /* Waste no memory when we reject a path here */
        bms_free(required_outer);
    }
}


//----------------------- create_mergejoin_path
 
 /*
  * create_mergejoin_path
  *    Creates a pathnode corresponding to a mergejoin join between
  *    two relations
  *      merge join    
  *
  * 'joinrel' is the join relation
  * joinrel-       relation
  * 'jointype' is the type of join required
  * jointype-    
  * 'workspace' is the result from initial_cost_mergejoin
  * workspace-    initial_cost_mergejoin     
  * 'extra' contains various information about the join
  * extra-       
  * 'outer_path' is the outer path
  * outer_path-outer relation    
  * 'inner_path' is the inner path
  * inner_path-inner relation    
  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
  * restrict_clauses-      
  * 'pathkeys' are the path keys of the new join path
  * pathkeys-   
  * 'required_outer' is the set of required outer rels
  * required_outer-   outer rels,     relids
  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
  *      (this should be a subset of the restrict_clauses list)
  * mergeclauses-        
  * 'outersortkeys' are the sort varkeys for the outer relation
  * outersortkeys-outer relation    
  * 'innersortkeys' are the sort varkeys for the inner relation
  * innersortkeys-inner relation    
  */
 MergePath *
 create_mergejoin_path(PlannerInfo *root,
                       RelOptInfo *joinrel,
                       JoinType jointype,
                       JoinCostWorkspace *workspace,
                       JoinPathExtraData *extra,
                       Path *outer_path,
                       Path *inner_path,
                       List *restrict_clauses,
                       List *pathkeys,
                       Relids required_outer,
                       List *mergeclauses,
                       List *outersortkeys,
                       List *innersortkeys)
 {
     MergePath  *pathnode = makeNode(MergePath);
 
     pathnode->jpath.path.pathtype = T_MergeJoin;
     pathnode->jpath.path.parent = joinrel;
     pathnode->jpath.path.pathtarget = joinrel->reltarget;
     pathnode->jpath.path.param_info =
         get_joinrel_parampathinfo(root,
                                   joinrel,
                                   outer_path,
                                   inner_path,
                                   extra->sjinfo,
                                   required_outer,
                                   &restrict_clauses);
     pathnode->jpath.path.parallel_aware = false;
     pathnode->jpath.path.parallel_safe = joinrel->consider_parallel &&
         outer_path->parallel_safe && inner_path->parallel_safe;
     /* This is a foolish way to estimate parallel_workers, but for now... */
     pathnode->jpath.path.parallel_workers = outer_path->parallel_workers;
     pathnode->jpath.path.pathkeys = pathkeys;
     pathnode->jpath.jointype = jointype;
     pathnode->jpath.inner_unique = extra->inner_unique;
     pathnode->jpath.outerjoinpath = outer_path;
     pathnode->jpath.innerjoinpath = inner_path;
     pathnode->jpath.joinrestrictinfo = restrict_clauses;
     pathnode->path_mergeclauses = mergeclauses;
     pathnode->outersortkeys = outersortkeys;
     pathnode->innersortkeys = innersortkeys;
     /* pathnode->skip_mark_restore will be set by final_cost_mergejoin */
     /* pathnode->materialize_inner will be set by final_cost_mergejoin */
 
     final_cost_mergejoin(root, pathnode, workspace, extra);//    
 
     return pathnode;
 }

3. 추적 분석
테스트 스크립트는 다음과 같습니다
select a.*,b.grbh,b.je 
from t_dwxx a,
    lateral (select t1.dwbh,t1.grbh,t2.je 
     from t_grxx t1 
          inner join t_jfxx t2 on t1.dwbh = a.dwbh and t1.grbh = t2.grbh) b
order by b.dwbh;


gdb 시작, 인터럽트 설정
(gdb) b sort_inner_and_outer
Breakpoint 1 at 0x7af63a: file joinpath.c, line 888.
(gdb) c
Continuing.

Breakpoint 1, sort_inner_and_outer (root=0x1a4a278, joinrel=0x1aa7180, outerrel=0x1a55700, innerrel=0x1a56c30, 
    jointype=JOIN_INNER, extra=0x7ffca933f880) at joinpath.c:888
888     JoinType    save_jointype = jointype;
(gdb) 

새로 생성된joinrel은 1번과 3번 RTE의 연결이며, 유형은 JOININNER
(gdb) p *joinrel->relids->words
$1 = 10
(gdb) p jointype
$2 = JOIN_INNER

정렬 키 가져오기, PathKey의 등가 클래스 EC, 구성원 tgrxx.dwbh 및 tdwxx.dwbh
...
(gdb) 
993     all_pathkeys = select_outer_pathkeys_for_merge(root,
(gdb) n
997     foreach(l, all_pathkeys)
(gdb) p *all_pathkeys
$3 = {type = T_List, length = 1, head = 0x1a69490, tail = 0x1a69490}
(gdb) p *(PathKey *)all_pathkeys->head->data.ptr_value
$5 = {type = T_PathKey, pk_eclass = 0x1a60e08, pk_opfamily = 1994, pk_strategy = 1, pk_nulls_first = false}
...
(gdb) set $rt=(RelabelType *)((EquivalenceMember *)$ec->ec_members->head->data.ptr_value)->em_expr
(gdb) p *$rt->arg
$14 = {type = T_Var}
(gdb) p *(Var *)$rt->arg
$15 = {xpr = {type = T_Var}, varno = 3, varattno = 1, vartype = 1043, vartypmod = 14, varcollid = 100, varlevelsup = 0, 
  varnoold = 3, varoattno = 1, location = 208}
(gdb) set $rt2=(RelabelType *)((EquivalenceMember *)$ec->ec_members->head->next->data.ptr_value)->em_expr
(gdb) p *(Var *)$rt2->arg
$16 = {xpr = {type = T_Var}, varno = 1, varattno = 2, vartype = 1043, vartypmod = 24, varcollid = 100, varlevelsup = 0, 
  varnoold = 1, varoattno = 2, location = 218}

시작allpathkeys
(gdb) n
999         List       *front_pathkey = (List *) lfirst(l);

연결 조건 서브문장 가져오기, tdwxx.dwbh=t_grxx.dwbh
(gdb) p *cur_mergeclauses
$17 = {type = T_List, length = 1, head = 0x1a694f0, tail = 0x1a694f0}

outer와 inner relation의 정렬 키 만들기
(gdb) p *(PathKey *)innerkeys->head->data.ptr_value
$22 = {type = T_PathKey, pk_eclass = 0x1a60e08, pk_opfamily = 1994, pk_strategy = 1, pk_nulls_first = false}
(gdb) p *(PathKey *)merge_pathkeys->head->data.ptr_value
$25 = {type = T_PathKey, pk_eclass = 0x1a60e08, pk_opfamily = 1994, pk_strategy = 1, pk_nulls_first = false}

merge join 시도, 함수try 진입mergejoin_path
(gdb) 
1038            try_mergejoin_path(root,
(gdb) step
try_mergejoin_path (root=0x1a4dcc0, joinrel=0x1a68e20, outer_path=0x1a62288, inner_path=0x1a62320, pathkeys=0x1a694b8, 
    mergeclauses=0x1a69518, outersortkeys=0x1a694b8, innersortkeys=0x1a69578, jointype=JOIN_INNER, extra=0x7ffca933f880, 
    is_partial=false) at joinpath.c:572
572     if (is_partial)


초기 mergejoin 비용
...
(gdb) 
615     initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
(gdb) p workspace
$26 = {startup_cost = 10861.483356195882, total_cost = 11134.203356195881, run_cost = 24.997499999999999, 
  inner_run_cost = 247.72250000000003, inner_rescan_run_cost = 1.3627136827435593e-316, outer_rows = 9999, 
  inner_rows = 100000, outer_skip_rows = 0, inner_skip_rows = 911, numbuckets = 27665584, numbatches = 0, 
  inner_rows_total = 1.3681950446447804e-316}

구조mergejoin
...
(gdb) n
625                  create_mergejoin_path(root,
(gdb) 
624         add_path(joinrel, (Path *)
(gdb) 
644 }
(gdb) p *joinrel->pathlist
$28 = {type = T_List, length = 1, head = 0x1a6a180, tail = 0x1a6a180}
(gdb) p *(Node *)joinrel->pathlist->head->data.ptr_value
$29 = {type = T_MergePath}
(gdb) p *(MergePath *)joinrel->pathlist->head->data.ptr_value
$30 = {jpath = {path = {type = T_MergePath, pathtype = T_MergeJoin, parent = 0x1a68e20, pathtarget = 0x1a69058, 
      param_info = 0x0, parallel_aware = false, parallel_safe = true, parallel_workers = 0, rows = 100000, 
      startup_cost = 10863.760856195882, total_cost = 12409.200856195883, pathkeys = 0x1a694b8}, jointype = JOIN_INNER, 
    inner_unique = false, outerjoinpath = 0x1a62288, innerjoinpath = 0x1a62320, joinrestrictinfo = 0x1a692f8}, 
  path_mergeclauses = 0x1a69518, outersortkeys = 0x1a694b8, innersortkeys = 0x1a69578, skip_mark_restore = false, 
  materialize_inner = false}


호출 완료
(gdb) n
sort_inner_and_outer (root=0x1a4dcc0, joinrel=0x1a68e20, outerrel=0x1a4d700, innerrel=0x1a4d918, jointype=JOIN_INNER, 
    extra=0x7ffca933f880) at joinpath.c:1054
1054            if (cheapest_partial_outer && cheapest_safe_inner)
(gdb) 
997     foreach(l, all_pathkeys)
(gdb) 
1066    }
(gdb) n
add_paths_to_joinrel (root=0x1a4dcc0, joinrel=0x1a68e20, outerrel=0x1a4d700, innerrel=0x1a4d918, jointype=JOIN_INNER, 
    sjinfo=0x7ffca933f970, restrictlist=0x1a692f8) at joinpath.c:279
279     if (mergejoin_allowed)
(gdb) 
280         match_unsorted_outer(root, joinrel, outerrel, innerrel,
...

DONE!
4. 참고 자료
allpaths.c cost.h costsize.c PG Document:Query Planning

좋은 웹페이지 즐겨찾기