qlc.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 1,743 行 · 第 1/5 页

prep_qlc(QFun, CodeF, Qdata0, QOpt, Opt) ->
    #qlc_opt{unique = Unique, cache = Cache, join = Join} = Opt,
    Optz = #optz{unique = Unique, cache = Cache, 
                 join_option = Join, opt = Opt},
    {Qdata, SortInfo} = qlc_sort_info(Qdata0, QOpt),
    QLC = #qlc{lcf = QFun, codef = CodeF, qdata = Qdata, 
               init_value = not_a_list, optz = Optz},
    #prepared{qh = QLC, sort_info = SortInfo,
              is_unique_objects = Unique, 
              is_cached = Cache =/= false}.

%% 'sorted', 'sorted_info', and 'sorted_info2' are used to avoid
%% sorting on a key when there is no need to sort on the key. 'sorted'
%% is set by qlc:sort() only; its purpose is to assure that if columns
%% 1 to i are constant, then column i+1 is key-sorted (always true if
%% the tuples are sorted). Note: the implementation is (too?) simple.
%% For instance, each column is annotated with 'ascending' or
%% 'descending' (not yet). More exact would be, as examples, 'always
%% ascending' and 'ascending if all preceding columns are constant'.
%%
%% The 'size' of the template is not used (size_of_qualifier(QOpt, 0)).

qlc_sort_info(Qdata, undefined) -> % single_v1, R10B
    F = fun(?qual_data(QNum, GoI, SI, 
                       {gen, #prepared{sort_info = SI}=Prep})) ->
                NPrepLE = Prep#prepared{sort_info2 = SI},
                ?qual_data(QNum, GoI, SI, {gen, NPrepLE});
           (Qd) -> Qd
        end,
    {lists:map(F, Qdata), []};
qlc_sort_info(Qdata0, QOpt) ->
    F = fun(?qual_data(_QNum, _GoI, _SI, fil)=Qd, Info) -> 
                {Qd, Info};
           (?qual_data(_QNum, _GoI, _SI, {gen, #join{}})=Qd, Info) ->
                {Qd, Info};
           (?qual_data(QNum, GoI, SI, {gen, PrepLE0}), Info) -> 
                PrepLE = sort_info(PrepLE0, QNum, QOpt),
                Qd = ?qual_data(QNum, GoI, SI, {gen, PrepLE}),
                I = [{{Column,Order}, [{traverse,QNum,C}]} ||
                        {{C,Order},What} <- PrepLE#prepared.sort_info2,
                        What =:= [], % Something else later...
                        Column <- equal_template_columns(QOpt, {QNum,C})],
                {Qd, [I | Info]}
        end,
    {Qdata, SortInfoL} = lists:mapfoldl(F, [], Qdata0),
    SortInfo0 = [{{Pos,Ord}, [template]} || 
                    Pos <- constant_columns(QOpt, 0), 
                    Ord <- orders(yes)]
           ++ lists:append(SortInfoL),
    SortInfo = family_union(SortInfo0),
    {Qdata, SortInfo}.

sort_info(#prepared{sort_info = SI, sorted = S} = Prep, QNum, QOpt) ->
    SI1 = [{{C,Ord},[]} || 
              S =/= no, 
              is_integer(Sz = size_of_qualifier(QOpt, QNum)), 
              Sz > 0, % the size of the pattern
              (NConstCols = size_of_constant_prefix(QOpt, QNum)) < Sz, 
              C <- [NConstCols+1],
              Ord <- orders(S)]
       ++ [{{Pos,Ord},[]} || Pos <- constant_columns(QOpt, QNum),
                             Ord <- orders(yes)]
       ++ [{PosOrd,[]} || {PosOrd,_} <- SI],
    SI2 = lists:usort(SI1),
    Prep#prepared{sort_info2 = SI2}. 

%orders(descending=O) ->
%    [O];
orders(ascending=O) ->
    [O];
orders(yes) ->
    [ascending
%   ,descending
    ].

sort_unique(true, #qlc_sort{opts = SortOptions, keypos = sort}=Sort) ->
    Sort#qlc_sort{unique = false, 
                  opts = lists:keydelete(unique, 
                                         1, 
                                         lists:delete(unique, SortOptions))};
sort_unique(_, Sort) ->
    Sort.

sort_tmpdir(S, #qlc_opt{tmpdir = ""}) ->
    S;
sort_tmpdir(S, Opt) ->
    S#qlc_sort{tmpdir = Opt#qlc_opt.tmpdir}.

short_list(L) ->
    %% length(L) < 2: all elements are known be equal
    #prepared{qh = #qlc_list{l = L}, sorted = yes, is_unique_objects = true, 
              is_cached = true}.
    
find_const_positions(#qlc_table{info_fun = IF, lookup_fun = LU_fun}, 
                     PosFun, #qlc_opt{max_lookup = Max, lookup = Lookup}) 
           when is_function(LU_fun), is_function(PosFun), is_function(IF),
                Lookup =/= false ->
    case call(IF, keypos, undefined, [])  of
        undefined ->
            Indices = call(IF, indices, undefined, []),
            find_const_position_idx(Indices, PosFun, Max, []);
        KeyPos ->
            case pos_vals(KeyPos, PosFun(KeyPos), Max) of
                false ->
                    find_const_position_idx(IF(indices), PosFun, Max, []);
                PosValuesSkip ->
                    PosValuesSkip
            end
    end;
find_const_positions(_, _PosFun, _Opt0) ->
    {false, {some,[]}}.

find_const_position_idx([I | Is], PosFun, Max, L0) ->
    case pos_vals(I, PosFun(I), Max) of
        false ->
            find_const_position_idx(Is, PosFun, Max, L0);
        {{_Pos, Values}, _SkipFils}=PosValuesFils ->
            L = [{length(Values), PosValuesFils} | L0],
            find_const_position_idx(Is, PosFun, Max, L)
    end;
find_const_position_idx(_, _PosFun, _Max, []) ->
    {false, {some,[]}};
find_const_position_idx(_, _PosFun, _Max, L) ->
    [{_,PVF} | _] = lists:sort(L),
    PVF.

pos_vals(Pos, {usort_needed, Values, SkipFils}, Max) ->
    pos_vals_max(Pos, lists:usort(Values), SkipFils, Max);
pos_vals(Pos, {values, Values, SkipFils}, Max) ->
    pos_vals_max(Pos, Values, SkipFils, Max);
pos_vals(Pos, {Tag, Values}, Max) ->
    %% R10B
    pos_vals(Pos, {Tag, Values, {some,[]}}, Max);
pos_vals(_Pos, _, _Max) ->
    false.

%% length(Values) >= 1
pos_vals_max(Pos, Values, Skip, Max) when Max =:= -1; Max >= length(Values) ->
    {{Pos, Values}, Skip};
pos_vals_max(_Pos, _Value, _Skip, _Max) ->
    false.

skip_lookup_filters(Prep, []) ->
    Prep;
skip_lookup_filters(#prepared{qh = #qlc{qdata = Qdata0}=QLC}=Prep, SkipFs) ->
    Qdata = [case lists:member(QNum, SkipFs) of
                 true ->
                     ?qual_data(QNum, GoI, ?SKIP, fil);
                 false ->
                     Qd
             end || ?qual_data(QNum, GoI, _, _)=Qd <- Qdata0],
    Prep#prepared{qh = QLC#qlc{qdata = Qdata}}.

prep_join(Prep, QOpt, Opt) ->
    case join_opt(QOpt) of
        undefined ->
            check_join_option(Opt),
            Prep;
        EqualMatch ->
            {Ix, M} = case EqualMatch of
                          {Equal, Match} ->
                              {Ix0, _} = pjoin(Match, Prep, QOpt, Opt),
                              {_, M0} = pjoin(Equal, Prep, QOpt, Opt),
                              {Ix0, M0};
                          _ ->
                              pjoin(EqualMatch, Prep, QOpt, Opt)
                      end,
            SI = family_union(Prep#prepared.sort_info ++ M),
            Prep#prepared{join = {Ix, M}, sort_info = SI}
    end.

%% The parse transform ensures that only two tables are involved.
pjoin(QCsL, #prepared{qh = #qlc{qdata = QData}}, QOpt, 
      #qlc_opt{join = JoinOpt}) ->
    LuJoin = (JoinOpt =:= any) or (JoinOpt =:= lookup),
    MJoin = (JoinOpt =:= any) or (JoinOpt =:= merge),
    lists:foldl(fun(QCs, {Ix0, M0}) -> 
                        {Ix,M} = pref_join(QCs, QData, QOpt, LuJoin, MJoin),
                        {Ix0++Ix, M0++M}
                end, {[],[]}, QCsL).

pref_join([{Q1,Cs1},{Q2,Cs2}], QData, QOpt, LuJoin, MJoin) ->
    {Is1, Sort1} = join_qual_data(QData, Q1),
    {Is2, Sort2} = join_qual_data(QData, Q2),
    Lu1 = [pref_lookup(Q1, C1, Q2, C2, QOpt) ||
              LuJoin, C2 <- Is2, lists:member(C2, Cs2), C1 <- Cs1],
    Lu2 = [pref_lookup(Q2, C2, Q1, C1, QOpt) ||
              LuJoin, C1 <- Is1, lists:member(C1, Cs1), C2 <- Cs2],
    Merge = lists:append([pref_merge(Q1, C1, Q2, C2, Sort1, Sort2, QOpt) ||
                             MJoin, C1 <- Cs1, C2 <- Cs2]),
    {family(Lu1 ++ Lu2), family_union(Merge)}.

pref_lookup(Q1, C1, Q2, C2, QOpt) ->
    {{Q1,C1,Q2,C2},{lookup,eq_template_columns(QOpt, {Q1,C1})}}.

pref_merge(Q1, C1, Q2, C2, Sort1, Sort2, QOpt) ->
    Col1 = {Q1,C1},
    Col2 = {Q2,C2},
    DoSort = [QC || {{_QNum,Col}=QC,SortL} <- [{Col1,Sort1}, {Col2,Sort2}],
                    lists:keysearch({Col, ascending}, 1, SortL) =:= false],
    J = [{{Q1,C1,Q2,C2}, {merge,DoSort}}],
    %% true = (QOpt(template))(Col1, '==') =:= (QOpt(template))(Col2, '==')
    [{{Column, ascending}, J} || 
        Column <- equal_template_columns(QOpt, Col1)] ++ [{other, J}].

join_qual_data(QData, QNum) ->
    case lists:keysearch(QNum, 1, QData) of
        {value, ?qual_data(QNum, _, _, {gen, PrepLE})} ->
            #prepared{sort_info2 = SortInfo} = PrepLE,
            {join_indices(PrepLE), SortInfo}
    end.

join_indices(#prepared{qh = #qlc_table{info_fun = IF, 
                                       ms = no_match_spec,
                                       lu_vals = undefined}}) ->
    KpL = case call(IF, keypos, undefined, []) of
              undefined -> [];
              Kp -> [Kp]
          end,
    case call(IF, indices, undefined, []) of
        undefined -> KpL;
        Is0 -> KpL ++ Is0
    end;
join_indices(_Prep) ->
    [].

table_sort_info(#qlc_table{info_fun = IF}) ->
    case call(IF, is_sorted_key, undefined, []) of
        undefined -> 
            {[], no};
        false -> 
            {[], no};
        true -> 
            case call(IF, keypos, undefined, []) of
                undefined -> % strange
                    {[], no};
                KeyPos ->
                    {[{{KeyPos,ascending},[]}], no}
            end
    end.

sort_sort_info(#qlc_sort{keypos = sort, order = Ord0}) ->
    {[], sort_order(Ord0)};
sort_sort_info(#qlc_sort{keypos = {keysort,Kp0}, order = Ord0}) ->
    Kp = case Kp0 of
             [Pos | _] -> Pos;
             _ -> Kp0
         end,
    {[{{Kp,sort_order(Ord0)},[]}], no}.

sort_order(F) when is_function(F) ->
    no;
sort_order(Order) ->
    Order.

check_join_option(#qlc_opt{join = any}) ->
    ok;
check_join_option(#qlc_opt{join = Join}) ->
    erlang:error(no_join_to_carry_out, [{join,Join}]).

check_lookup_option(#qlc_opt{lookup = true}, false) ->
    erlang:error(no_lookup_to_carry_out, [{lookup,true}]);
check_lookup_option(_QOpt, _LuV) ->
    ok.

equal_template_columns(QOpt, QNumColumn) ->
    (QOpt(template))(QNumColumn, '==').

eq_template_columns(QOpt, QNumColumn) ->
    (QOpt(template))(QNumColumn, '=:=').

size_of_constant_prefix(QOpt, QNum) ->
    (QOpt(n_leading_constant_columns))(QNum).

constants(undefined, _QNum) ->
    no_column_fun;
constants(QOpt, QNum) ->
    (QOpt(constants))(QNum).

join_opt(undefined=U) ->
    U;
join_opt(QOpt) ->
    QOpt(join).

match_specs(undefined=U, _QNum) ->
    U;
match_specs(QOpt, QNum) ->
    (QOpt(match_specs))(QNum).

constant_columns(QOpt, QNum) ->
    (QOpt(constant_columns))(QNum).

size_of_qualifier(QOpt, QNum) ->
    (QOpt(size))(QNum).

%% Two optimizations are carried out:
%% 1. The first generator is never cached if the QLC expression itself
%% is cached. Since the answers do not need to be cached, the top-most
%% QLC expression is never cached either. Simple QLCs not holding any
%% options are removed. Simple QLCs are coalesced when possible.
%% 2. Merge join and lookup join is done if possible.

opt_le(#prepared{qh = #simple_qlc{le = LE0, optz = Optz0}=QLC}=Prep0, 
       GenNum) ->
    case LE0 of
        #prepared{qh = #simple_qlc{p = LE_Pvar, le = LE2, optz = Optz2}} ->
            %% Coalesce two simple QLC expressions.
            Cachez = case Optz2#optz.cache of
                         false -> Optz0#optz.cache;
                         Cache2 -> Cache2
                     end,
            Optz = Optz0#optz{cache = Cachez,
                              unique = Optz0#optz.unique or Optz2#optz.unique},
            PVar = if 
                       LE_Pvar =:= ?SIMPLE_QVAR -> QLC#simple_qlc.p;
                       true -> LE_Pvar
                   end,
            Prep = Prep0#prepared{qh = QLC#simple_qlc{p = PVar, le = LE2,
                                                      optz = Optz}},
            opt_le(Prep, GenNum);
        _ ->
            Optz1 = no_cache_of_first_generator(Optz0, GenNum),
            case {opt_le(LE0, 1), Optz1} of
                {LE, #optz{unique = false, cache = false}} ->
                    LE;
                {LE, _} ->
                    Prep0#prepared{qh = QLC#simple_qlc{le = LE, optz = Optz1}}
            end
    end;
opt_le(#prepared{qh = #qlc{qdata = Qdata0, optz = Optz0}=QLC}=Prep, GenNum) ->
    #optz{join_option = JoinOption, opt = Opt} = Optz0,
    JoinOption = Optz0#optz.join_option,
    {Join, DoSort} = 
        opt_join(Prep#prepared.join, JoinOption, Qdata0, Opt),
    F = fun(?qual_data(QNum, GoI, SI, {gen, #prepared{}=PrepLE}), GenNum1) ->
                NewPrepLE = maybe_sort(PrepLE, QNum, DoSort, Opt),
                {?qual_data(QNum, GoI, SI, {gen, opt_le(NewPrepLE, GenNum1)}),
                 GenNum1 + 1};
           (Qd, GenNum1) ->
                {Qd, GenNum1}
        end,
    {Qdata, _} = lists:mapfoldl(F, 1, Qdata0),
    Optz1 = no_cache_of_first_generator(Optz0, GenNum),
    Optz = Optz1#optz{fast_join = Join},
    Prep#prepared{qh = QLC#qlc{qdata = Qdata, optz = Optz}};
opt_le(#prepared{qh = #qlc_append{hl = HL}}=Prep, GenNum) ->
    Hs = [opt_le(