[m-dev.] diff: improve Aditi join optimization
Simon Taylor
stayl at cs.mu.OZ.AU
Tue Feb 22 13:56:24 AEDT 2000
Estimated hours taken: 80
Improve the handling of joins in the Aditi back end.
- generate hash and sort-merge joins for equijoins.
- use the semi-join bytecodes for joins which
return one of the input tuples.
- optimize `trivial' joins where the join condition does not
depend on one of the input tuples.
compiler/rl.m:
Store information about whether a join is a semi-join
or a trivial join.
Add `hash' to the list of alternatives for `join_type'.
Remove `semi' from the list of alternatives for `join_type' --
semi-join is a modified implementation of one of the other
join types.
Remove `cross' from the list of alternatives for `join_type' --
a cross-product is just a modified nested-loop join.
All subtracts are done as semi-subtracts (no projection is performed
on the output by the subtract instruction) -- rename the
constructors of type `subtract_type' to reflect this.
Add more predicates to manipulate join conditions.
Add field labels to the `rl_goal' type.
compiler/rl_sort.m:
Introduce sort-merge and hash joins.
compiler/rl_key.m:
Add `rl_key__is_equijoin', to work out whether a join
condition tests whether attributes of the input tuples
are equal.
compiler/rl_block_opt.m:
Fill in the semi-join and trivial join fields of join
instructions.
compiler/rl_out.pp:
Handle sort-merge, hash, semi and trivial joins.
Use record syntax for the rl_out_info access predicates.
compiler/rl_exprn.m:
Generate RL expressions for use in sort-merge and
hash joins.
compiler/rl_relops.m:
Remove code to handle semi-joins -- they are
introduced later.
compiler/rl_*.m:
Handle the extra fields of join instructions.
Index: rl.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl.m,v
retrieving revision 1.8
diff -u -u -r1.8 rl.m
--- rl.m 1999/08/25 06:34:01 1.8
+++ rl.m 2000/02/22 02:11:40
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -126,7 +126,9 @@
relation_id, % input 1
relation_id, % input 2
join_type,
- rl_goal % join condition
+ rl_goal, % join condition
+ maybe(semi_join_info),
+ maybe(trivial_join_info)
)
;
subtract( % output = input 1 - input 2
@@ -306,6 +308,12 @@
:- type join_type
---> nested_loop
; sort_merge(sort_spec, sort_spec)
+ ; hash(list(int), list(int))
+ % Hash join, used for joins where
+ % the condition tests equality of
+ % one or more attributes of the input
+ % relations.
+ % Attribute numbers start at 1.
; index(index_spec, key_range)
% The second relation is indexed.
% Each tuple in the first relation
@@ -314,19 +322,57 @@
% builds the lower and upper bounds
% on the key range from the input
% tuple from the first relation.
- ; cross
- ; semi % The output tuple is copied from the
- % first input tuple. An output projection
- % must be done as a separate operation.
.
+
+ % A semi-join does not do a projection on the output - it
+ % just returns one of the input tuples.
+:- type semi_join_info == tuple_num.
+
+ % For some joins the join condition does not depend on
+ % one of the input tuples. This commonly happens for joins
+ % with a zero-arity input relation at the start of a procedure.
+ %
+ % Output = join(Input1, Input2, Cond), where Cond does
+ % not depend on Input2, can be generated as:
+ %
+ % if (empty(Input2)) {
+ % Output = project(Input1, Cond)
+ % else {
+ % init(Output)
+ % }
+ %
+ % If the join is a semi-join with a deterministic
+ % condition, the project is not necessary.
+ %
+ % We don't just do this optimization in the intermediate RL
+ % because it introduces extra branching which can interfere
+ % with other optimizations (e.g. rl_block_opt.m, rl_stream.m).
+:- type trivial_join_info
+ ---> trivial_join_info(
+ tuple_num, % which tuple does the join depend on
+ maybe(project_type)
+ % the type of projection to use,
+ % if one is needed
+ ).
+
+ % All subtracts are done using the semi-subtract operator.
+ % There is no advantage in including any post projection
+ % in the operation because the projection cannot use any
+ % of the intermediate results of the test -- the projection
+ % is only done if the test fails for all negated tuples.
:- type subtract_type
- ---> nested_loop
- ; semi % The output tuple is copied from the
- % first input tuple. An output projection
- % must be done as a separate operation.
- ; sort_merge(sort_spec, sort_spec)
- ; index(index_spec, key_range)
+ ---> semi_nested_loop
+ ; semi_sort_merge(sort_spec, sort_spec)
+ % Hash join, used for joins where
+ % the condition tests equality of
+ % one or more attributes of the input
+ % relations.
+ % Attribute numbers start at 1.
+ ; semi_hash(list(int), list(int))
+ ; semi_index(index_spec, key_range)
+ % The negated (second) input relation
+ % is indexed.
.
:- type difference_type
@@ -372,18 +418,18 @@
% hlds_goal form.
:- type rl_goal
---> rl_goal(
- maybe(pred_proc_id),
+ pred_proc_id :: maybe(pred_proc_id),
% Predicate from which the expression was
% taken - used to avoid unnecessarily merging
% varsets. Should be `no' if the varset
% contains vars from multiple procs.
- prog_varset,
- map(prog_var, type),
- instmap, % instmap before goal
- rl_goal_inputs,
- rl_goal_outputs,
- list(hlds_goal),
- list(rl_var_bounds)
+ varset :: prog_varset,
+ vartypes :: map(prog_var, type),
+ instmap:: instmap, % instmap before goal
+ inputs :: rl_goal_inputs,
+ outputs :: rl_goal_outputs,
+ goal :: list(hlds_goal),
+ bounds :: list(rl_var_bounds)
).
:- type rl_goal_inputs
@@ -407,6 +453,11 @@
:- type rl_var_bounds == map(prog_var, pair(key_term)).
+:- type tuple_num
+ ---> one
+ ; two
+ .
+
%-----------------------------------------------------------------------------%
:- type label_id == int.
@@ -437,29 +488,53 @@
% Get a list of all attributes for a given schema.
:- pred rl__attr_list(list(T)::in, list(int)::out) is det.
+:- pred rl__is_semi_join(join_type::in, rl_goal::in,
+ maybe(semi_join_info)::out) is det.
+
+:- pred rl__is_trivial_join(module_info::in, join_type::in, rl_goal::in,
+ maybe(semi_join_info)::in, maybe(trivial_join_info)::out) is det.
+
% Succeed if the goal contain any of the variables corresponding
% to the attributes of the given input tuple.
:- pred rl__goal_is_independent_of_input(tuple_num::in,
- rl_goal::in, rl_goal::out) is semidet.
+ rl_goal::in) is semidet.
+
+ % Remove the specified input tuple from the goal, aborting
+ % if the goal is not independent of that input tuple.
+:- pred rl__remove_goal_input(tuple_num::in, rl_goal::in, rl_goal::out) is det.
+:- pred rl__swap_join_type_inputs(join_type::in, join_type::out) is det.
+
% Swap the inputs of a goal such as a join condition which
- % as two input relations.
+ % has two input relations.
:- pred rl__swap_goal_inputs(rl_goal::in, rl_goal::out) is det.
+
+ % Remove the output tuple from a goal, converting a join
+ % into a semi-join.
+:- pred rl__strip_goal_outputs(rl_goal::in, rl_goal::out) is det.
% Succeed if the goal produces an output tuple.
:- pred rl__goal_produces_tuple(rl_goal::in) is semidet.
-:- type tuple_num
- ---> one
- ; two
- .
+ % Succeed if a project/select with the given condition
+ % can be removed without changing the semantics of the
+ % program.
+:- pred rl__goal_can_be_removed(module_info::in,
+ list(hlds_goal)::in) is semidet.
+
+ % If the goal has an output tuple, check whether the
+ % output tuple is the same as one of the input tuples.
+ % If the operator is a join, the semi-join operator can be used.
+:- pred rl__goal_returns_input_tuple(rl_goal::in, tuple_num::out) is semidet.
+
+:- pred rl__swap_tuple_num(tuple_num::in, tuple_num::out) is det.
%-----------------------------------------------------------------------------%
% Find out the name of the RL procedure corresponding
% to the given Mercury procedure.
-:- pred rl__get_entry_proc_name(module_info, pred_proc_id, rl_proc_name).
-:- mode rl__get_entry_proc_name(in, in, out) is det.
+:- pred rl__get_entry_proc_name(module_info::in, pred_proc_id::in,
+ rl_proc_name::out) is det.
% Work out the name for a permanent relation.
:- pred rl__permanent_relation_name(module_info::in,
@@ -507,7 +582,7 @@
%-----------------------------------------------------------------------------%
:- implementation.
-:- import_module code_util, globals, llds_out, options, prog_out.
+:- import_module code_util, code_aux, globals, llds_out, options, prog_out.
:- import_module prog_util, type_util.
:- import_module bool, int, require, string.
@@ -525,7 +600,8 @@
%-----------------------------------------------------------------------------%
-rl__instr_relations(join(output_rel(Output, _), Input1, Input2, _, _) - _,
+rl__instr_relations(
+ join(output_rel(Output, _), Input1, Input2, _, _, _, _) - _,
[Input1, Input2], [Output]).
rl__instr_relations(subtract(output_rel(Output, _),
Input1, Input2, _, _) - _, [Input1, Input2], [Output]).
@@ -614,10 +690,113 @@
rl__attr_list_2(NextIndex, Types, Attrs).
%-----------------------------------------------------------------------------%
+
+rl__is_semi_join(JoinType, Exprn, SemiJoinInfo) :-
+ (
+ rl__goal_returns_input_tuple(Exprn, SemiTupleNum),
+
+ % XXX sort-merge semi-joins are
+ % not yet implemented in Aditi.
+ JoinType \= sort_merge(_, _),
+
+ %
+ % An indexed semi-join where the tuple from the
+ % indexed relation is returned is not
+ % strictly a semi-join. A semi-join is normally
+ % guaranteed to return each tuple only once, but
+ % the indexed tuples may match against multiple
+ % tuples in the non-indexed relation.
+ %
+ ( JoinType = index(_, _) => SemiTupleNum = one )
+ ->
+ SemiJoinInfo = yes(SemiTupleNum)
+ ;
+ SemiJoinInfo = no
+ ).
-rl__goal_is_independent_of_input(InputNo, RLGoal0, RLGoal) :-
- RLGoal0 = rl_goal(A, B, C, D, Inputs0, MaybeOutputs, Goals, H),
- rl__select_input_args(InputNo, Inputs0, Inputs, InputArgs),
+rl__is_trivial_join(ModuleInfo, JoinType, Cond,
+ SemiJoinInfo, TrivialJoinInfo) :-
+ (
+ join_type_to_project_type(JoinType, yes(ProjectType))
+ ->
+ ( rl__goal_is_independent_of_input(one, Cond) ->
+ rl__make_trivial_join_info(ModuleInfo, ProjectType,
+ Cond, two, SemiJoinInfo, TrivialJoinInfo)
+ ; rl__goal_is_independent_of_input(two, Cond) ->
+ rl__make_trivial_join_info(ModuleInfo, ProjectType,
+ Cond, one, SemiJoinInfo, TrivialJoinInfo)
+ ;
+ TrivialJoinInfo = no
+ )
+ ;
+ TrivialJoinInfo = no
+ ).
+
+:- pred rl__make_trivial_join_info(module_info::in, project_type::in,
+ rl_goal::in, tuple_num::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_info)::out) is det.
+
+rl__make_trivial_join_info(ModuleInfo, ProjectType,
+ Cond, TupleNum, SemiJoin, TrivialJoinInfo) :-
+ Goals = Cond ^ goal,
+
+ (
+ %
+ % A projection is not needed for semi-joins with
+ % deterministic conditions.
+ %
+ SemiJoin = yes(_),
+ rl__goal_can_be_removed(ModuleInfo, Goals)
+ ->
+ MaybeProjectType = no
+ ;
+ MaybeProjectType = yes(ProjectType)
+ ),
+
+ TrivialJoinInfo = yes(trivial_join_info(TupleNum, MaybeProjectType)).
+
+rl__goal_can_be_removed(ModuleInfo, Goals) :-
+ goal_list_determinism(Goals, Detism),
+ determinism_components(Detism, cannot_fail, MaxSoln),
+ MaxSoln \= at_most_zero,
+
+ module_info_globals(ModuleInfo, Globals),
+ globals__lookup_bool_option(Globals, fully_strict, FullyStrict),
+
+ (
+ FullyStrict = no
+ ;
+ all [Goal] (
+ list__member(Goal, Goals)
+ =>
+ code_aux__goal_cannot_loop(ModuleInfo, Goal)
+ )
+ ).
+
+:- pred join_type_to_project_type(join_type::in,
+ maybe(project_type)::out) is det.
+
+join_type_to_project_type(nested_loop, yes(filter)).
+join_type_to_project_type(index(IndexSpec, KeyRange),
+ yes(index(IndexSpec, KeyRange))).
+ %
+ % Introducing sort-merge and hash joins means that there is a
+ % connection between the arguments of the two input tuples, so
+ % the join cannot be turned into a projection.
+ %
+join_type_to_project_type(sort_merge(_, _), no).
+join_type_to_project_type(hash(_, _), no).
+
+rl__remove_goal_input(InputNo, RLGoal0, RLGoal) :-
+ require(rl__goal_is_independent_of_input(InputNo, RLGoal0),
+ "rl__remove_goal_input: not independent"),
+ rl__select_input_args(InputNo, RLGoal0 ^ inputs, Inputs, _),
+ RLGoal = RLGoal0 ^ inputs := Inputs.
+
+rl__goal_is_independent_of_input(InputNo, RLGoal) :-
+ rl__select_input_args(InputNo, RLGoal ^ inputs, _, InputArgs),
+ MaybeOutputs = RLGoal ^ outputs,
+ Goals = RLGoal ^ goal,
set__list_to_set(InputArgs, InputArgSet),
\+ (
MaybeOutputs = yes(Outputs),
@@ -631,8 +810,7 @@
goal_info_get_nonlocals(GoalInfo, NonLocals),
set__intersect(NonLocals, InputArgSet, Intersection),
\+ set__empty(Intersection)
- ),
- RLGoal = rl_goal(A, B, C, D, Inputs, MaybeOutputs, Goals, H).
+ ).
:- pred rl__select_input_args(tuple_num::in, rl_goal_inputs::in,
rl_goal_inputs::out, list(prog_var)::out) is det.
@@ -647,17 +825,44 @@
rl__select_input_args(two, two_inputs(Args1, Args),
one_input(Args1), Args).
+rl__swap_join_type_inputs(nested_loop, nested_loop).
+rl__swap_join_type_inputs(sort_merge(A, B), sort_merge(B, A)).
+rl__swap_join_type_inputs(hash(A, B), hash(B, A)).
+rl__swap_join_type_inputs(index(_, _), _) :-
+ error("rl__swap_join_type_inputs: can't swap inputs of index join").
+
rl__swap_goal_inputs(RLGoal0, RLGoal) :-
- RLGoal0 = rl_goal(A, B, C, D, Inputs0, F, G, H),
+ Inputs0 = RLGoal0 ^ inputs,
( Inputs0 = two_inputs(Inputs1, Inputs2) ->
- RLGoal = rl_goal(A, B, C, D, two_inputs(Inputs2, Inputs1),
- F, G, H)
+ RLGoal = RLGoal0 ^ inputs := two_inputs(Inputs2, Inputs1)
;
error("rl__swap_inputs: goal does not have two inputs to swap")
).
+rl__strip_goal_outputs(RLGoal0, RLGoal0 ^ outputs := no).
+
rl__goal_produces_tuple(RLGoal) :-
- RLGoal = rl_goal(_, _, _, _, _, yes(_), _, _).
+ RLGoal ^ outputs = yes(_).
+
+rl__goal_returns_input_tuple(RLGoal, TupleReturned) :-
+ Inputs = RLGoal ^ inputs,
+ yes(OutputVars) = RLGoal ^ outputs,
+ (
+ Inputs = two_inputs(InputVars1, InputVars2),
+ ( InputVars1 = OutputVars ->
+ TupleReturned = one
+ ; InputVars2 = OutputVars ->
+ TupleReturned = two
+ ;
+ fail
+ )
+ ;
+ Inputs = one_input(OutputVars),
+ TupleReturned = one
+ ).
+
+rl__swap_tuple_num(one, two).
+rl__swap_tuple_num(two, one).
%-----------------------------------------------------------------------------%
Index: rl_block_opt.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_block_opt.m,v
retrieving revision 1.4
diff -u -u -r1.4 rl_block_opt.m
--- rl_block_opt.m 1999/06/16 00:34:48 1.4
+++ rl_block_opt.m 2000/02/22 02:11:48
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -87,7 +87,8 @@
% Add an instruction to the DAG for the block.
:- pred rl_block_opt__build_dag(rl_instruction::in, dag::in, dag::out) is det.
-rl_block_opt__build_dag(join(Output, Input1, Input2, Type, Exprn) - _) -->
+rl_block_opt__build_dag(
+ join(Output, Input1, Input2, Type, Exprn, _, _) - _) -->
rl_block_opt__lookup_relation(Input1, Input1Node),
rl_block_opt__lookup_relation(Input2, Input2Node),
rl_block_opt__add_dag_node([Output], [Input1Node, Input2Node],
@@ -875,7 +876,7 @@
% generated tuple into the output if the input is non-empty
\+ (
OutputGoals = [OutputGoal],
- rl__goal_is_independent_of_input(one, OutputGoal, _)
+ rl__goal_is_independent_of_input(one, OutputGoal)
),
\+ (
list__member(OtherOutputProjn, OutputProjns0),
@@ -1340,11 +1341,22 @@
list(rl_instruction)::out, dag::in, dag::out) is det.
rl_block_opt__generate_instr(_, NodeOutputs, NodeRels,
- join(Input1Loc, Input2Loc, Type, Exprn),
- [join(Output, Input1, Input2, Type, Exprn) - ""]) -->
+ join(Input1Loc, Input2Loc, JoinType, Exprn), [JoinInstr]) -->
+
+ { rl__is_semi_join(JoinType, Exprn, SemiJoinInfo) },
+
+ dag_get_rl_opt_info(RLOptInfo),
+ { rl_opt_info_get_module_info(ModuleInfo, RLOptInfo, _) },
+
+ { rl__is_trivial_join(ModuleInfo, JoinType, Exprn, SemiJoinInfo,
+ TrivialJoinInfo) },
+
rl_block_opt__get_relation_id(NodeRels, Input1Loc, Input1),
rl_block_opt__get_relation_id(NodeRels, Input2Loc, Input2),
- { rl_block_opt__one_output(NodeOutputs, Output) }.
+ { rl_block_opt__one_output(NodeOutputs, Output) },
+ { JoinInstr = join(Output, Input1, Input2, JoinType, Exprn,
+ SemiJoinInfo, TrivialJoinInfo) - "" }.
+
rl_block_opt__generate_instr(_, NodeOutputs, NodeRels,
subtract(Input1Loc, Input2Loc, Type, Exprn),
Index: rl_dump.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_dump.m,v
retrieving revision 1.4
diff -u -u -r1.4 rl_dump.m
--- rl_dump.m 1999/08/14 04:52:26 1.4
+++ rl_dump.m 2000/02/22 02:11:55
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -102,14 +102,41 @@
%-----------------------------------------------------------------------------%
rl_dump__write_instruction(ModuleInfo, RelationInfo,
- join(Output, Input1, Input2, JoinType, Exprn) - Comment) -->
+ join(Output, Input1, Input2, JoinType, Exprn,
+ SemiJoinInfo, TrivialJoinInfo) - Comment) -->
rl_dump__write_output_rel(RelationInfo, Output),
io__write_string(" = join("),
rl_dump__write_relation_id(RelationInfo, Input1),
comma,
rl_dump__write_relation_id(RelationInfo, Input2),
comma,
+ io__nl,
+ io__write_string("\t\t"),
rl_dump__write_join_type(ModuleInfo, JoinType),
+ (
+ { SemiJoinInfo = yes(SemiTuple) },
+ io__write_string(" (semi-join tuple "),
+ io__write(SemiTuple),
+ io__write_string(")")
+ ;
+ { SemiJoinInfo = no }
+ ),
+ (
+ { TrivialJoinInfo = yes(trivial_join_info(Tuple,
+ MaybeProject)) },
+ io__write_string(" (trivial join input "),
+ io__write(Tuple),
+ (
+ { MaybeProject = yes(_) },
+ io__write_string(" projected")
+ ;
+ { MaybeProject = no },
+ io__write_string(" not projected")
+ ),
+ io__write_string(")")
+ ;
+ { TrivialJoinInfo = no }
+ ),
comma,
io__nl,
rl_dump__write_goal(ModuleInfo, Exprn),
@@ -369,6 +396,12 @@
rl_dump__write_join_type(_, nested_loop) -->
io__write_string("nested_loop").
+rl_dump__write_join_type(_, hash(Attrs1, Attrs2)) -->
+ io__write_string("hash("),
+ rl_dump__write_list(io__write, ", ", Attrs1),
+ io__write_string(", "),
+ rl_dump__write_list(io__write, ", ", Attrs2),
+ io__write_string(")").
rl_dump__write_join_type(_, sort_merge(Attr1, Attr2)) -->
io__write_string("sort_merge("),
rl_dump__write_sort_spec(Attr1),
@@ -381,26 +414,26 @@
comma,
rl_dump__write_key_range(ModuleInfo, Range),
io__write_string(")").
-rl_dump__write_join_type(_, cross) -->
- io__write_string("cross").
-rl_dump__write_join_type(_, semi) -->
- io__write_string("semi").
:- pred rl_dump__write_subtract_type(module_info::in, subtract_type::in,
io__state::di, io__state::uo) is det.
-rl_dump__write_subtract_type(_, nested_loop) -->
- io__write_string("nested_loop").
-rl_dump__write_subtract_type(_, semi) -->
- io__write_string("semi").
-rl_dump__write_subtract_type(_, sort_merge(SortAttr1, SortAttr2)) -->
- io__write_string("sort_merge("),
+rl_dump__write_subtract_type(_, semi_nested_loop) -->
+ io__write_string("semi_nested_loop").
+rl_dump__write_subtract_type(_, semi_sort_merge(SortAttr1, SortAttr2)) -->
+ io__write_string("semi_sort_merge("),
rl_dump__write_sort_spec(SortAttr1),
comma,
rl_dump__write_sort_spec(SortAttr2),
io__write_string(")").
-rl_dump__write_subtract_type(ModuleInfo, index(Spec, Range)) -->
- io__write_string("index("),
+rl_dump__write_subtract_type(_, semi_hash(Attrs1, Attrs2)) -->
+ io__write_string("semi_hash("),
+ rl_dump__write_list(io__write, ", ", Attrs1),
+ io__write_string(", "),
+ rl_dump__write_list(io__write, ", ", Attrs2),
+ io__write_string(")").
+rl_dump__write_subtract_type(ModuleInfo, semi_index(Spec, Range)) -->
+ io__write_string("semi_index("),
mercury_output_index_spec(Spec),
comma,
rl_dump__write_key_range(ModuleInfo, Range),
Index: rl_exprn.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_exprn.m,v
retrieving revision 1.12
diff -u -u -r1.12 rl_exprn.m
--- rl_exprn.m 1999/10/25 03:49:36 1.12
+++ rl_exprn.m 2000/02/22 02:12:02
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -54,21 +54,51 @@
:- import_module hlds_module, hlds_pred, rl, rl_code, rl_file, prog_data.
:- import_module list.
+ % rl_exprn__generate_compare_exprn(ModuleInfo, SortSpec,
+ % InputSchema, CompareCodes).
+ %
% Generate an expression to compare tuples with the
% given schema on the given attributes.
:- pred rl_exprn__generate_compare_exprn(module_info::in, sort_spec::in,
list(type)::in, list(bytecode)::out) is det.
+ % rl_exprn__generate_sort_merge_compare_exprn(ModuleInfo, Attrs1,
+ % Schema1, Attrs2, Schema2, CompareCodes).
+ %
+ % Generate an expression to compare the join attributes in
+ % a sort-merge equi-join.
+:- pred rl_exprn__generate_sort_merge_compare_exprn(module_info::in,
+ sort_spec::in, list(type)::in, sort_spec::in, list(type)::in,
+ list(bytecode)::out) is det.
+
+ % rl_exprn__generate_key_range(ModuleInfo, KeyRange, ExprnCode,
+ % NumParams, LowerBoundSchema, UpperBoundSchema,
+ % MaxTermDepth, ExprnVarTypes).
+ %
% Generate an expression to produce the upper and lower
% bounds for a B-tree access.
:- pred rl_exprn__generate_key_range(module_info::in, key_range::in,
list(bytecode)::out, int::out, list(type)::out, list(type)::out,
int::out, list(type)::out) is det.
+
+ % rl_exprn__generate_hash_function(ModuleInfo, HashAttrs,
+ % InputSchema, ExprnCode).
+ %
+ % Generate an expression to compute a hash value for the given
+ % attributes of a tuple.
+:- pred rl_exprn__generate_hash_function(module_info::in, list(int)::in,
+ list(type)::in, list(bytecode)::out) is det.
+ % rl_exprn__generate(ModuleInfo, Goal, ExprnCode, NumParams,
+ % ExprnMode, ExprnVarTypes).
+ %
% Generate an expression for a join/project/subtract condition.
:- pred rl_exprn__generate(module_info::in, rl_goal::in, list(bytecode)::out,
int::out, exprn_mode::out, list(type)::out) is det.
+ % rl_exprn__aggregate(ModuleInfo, InitAccPred, UpdateAccPred,
+ % GrpByType, NonGrpByType, AccType, ExprnCode, Decls).
+ %
% Given the closures used to create the initial accumulator for each
% group and update the accumulator for each tuple, create
% an expression to evaluate the aggregate.
@@ -97,18 +127,39 @@
rl_exprn__generate_compare_exprn(_ModuleInfo, Spec, Schema, Code) :-
(
Spec = attributes(Attrs0),
- list__map(
- (pred((Attr0 - Dir)::in, (Attr - Dir)::out) is det :-
- rl_exprn__adjust_arg_number(Attr0, Attr)
- ),
- Attrs0, Attrs),
- list__foldl(rl_exprn__generate_compare_instrs(Schema),
- Attrs, empty, CompareCode)
+
+ % We're comparing corresponding attributes from each tuple.
+ assoc_list__from_corresponding_lists(Attrs0, Attrs0,
+ CompareAttrs)
;
Spec = sort_var(_),
error("rl_exprn__generate_compare_exprn: unbound sort_var")
),
+ rl_exprn__do_generate_compare_exprn(Schema, CompareAttrs, Code).
+
+rl_exprn__generate_sort_merge_compare_exprn(_ModuleInfo, Spec1, Schema1,
+ Spec2, _Schema2, Code) :-
+
+ (
+ Spec1 = attributes(Attrs1),
+ Spec2 = attributes(Attrs2)
+ ->
+ assoc_list__from_corresponding_lists(Attrs1, Attrs2,
+ CompareAttrs)
+ ;
+ error(
+ "rl_exprn__generate_sort_merge_compare_exprn: unbound sort_var")
+ ),
+ rl_exprn__do_generate_compare_exprn(Schema1, CompareAttrs, Code).
+:- pred rl_exprn__do_generate_compare_exprn(list(type)::in,
+ assoc_list(pair(int, sort_dir))::in, list(bytecode)::out) is det.
+
+rl_exprn__do_generate_compare_exprn(Schema1, CompareAttrs, Code) :-
+
+ list__foldl(rl_exprn__generate_compare_instrs(Schema1),
+ CompareAttrs, empty, CompareCode),
+
ExprnCode =
tree(node([rl_PROC_expr_frag(2)]),
tree(CompareCode,
@@ -123,16 +174,23 @@
list__condense(Instrs0, Code).
:- pred rl_exprn__generate_compare_instrs(list(type)::in,
- pair(int, sort_dir)::in, byte_tree::in, byte_tree::out) is det.
+ pair(pair(int, sort_dir))::in, byte_tree::in, byte_tree::out) is det.
+
+rl_exprn__generate_compare_instrs(Types1, (Attr1a - Dir1) - (Attr2a - Dir2),
+ Code0, Code) :-
+ require(unify(Dir1, Dir2),
+ "rl_exprn__generate_compare_instrs: sort directions not equal"),
-rl_exprn__generate_compare_instrs(Types, Attr - Dir, Code0, Code) :-
- list__index0_det(Types, Attr, Type),
+ rl_exprn__adjust_arg_number(Attr1a, Attr1),
+ rl_exprn__adjust_arg_number(Attr2a, Attr2),
+
+ list__index0_det(Types1, Attr1, Type),
rl_exprn__type_to_aditi_type(Type, AType),
rl_exprn__compare_bytecode(AType, CompareByteCode),
- rl_exprn__get_input_field_code(one, AType, Attr, FieldCode1),
- rl_exprn__get_input_field_code(two, AType, Attr, FieldCode2),
+ rl_exprn__get_input_field_code(one, AType, Attr1, FieldCode1),
+ rl_exprn__get_input_field_code(two, AType, Attr2, FieldCode2),
(
- Dir = ascending,
+ Dir1 = ascending,
CompareAttr = node([
FieldCode1,
FieldCode2,
@@ -140,7 +198,7 @@
rl_EXP_return_if_nez
])
;
- Dir = descending,
+ Dir1 = descending,
CompareAttr = node([
FieldCode2,
FieldCode1,
@@ -149,6 +207,55 @@
])
),
Code = tree(Code0, CompareAttr).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+rl_exprn__generate_hash_function(_ModuleInfo, Attrs0, Schema, Code) :-
+ list__map(rl_exprn__adjust_arg_number, Attrs0, Attrs),
+ IsFirst = yes,
+ rl_exprn__generate_hash_function_2(Attrs, Schema, IsFirst,
+ empty, HashCode),
+ ExprnCode =
+ tree(node([rl_PROC_expr_frag(2)]),
+ tree(HashCode,
+ node([rl_EXP_hash_result, rl_PROC_expr_end])
+ )),
+
+ tree__flatten(ExprnCode, Instrs0),
+ list__condense(Instrs0, Code).
+
+:- pred rl_exprn__generate_hash_function_2(list(int)::in, list(type)::in,
+ bool::in, byte_tree::in, byte_tree::out) is det.
+
+rl_exprn__generate_hash_function_2([], _, _, Code, Code).
+rl_exprn__generate_hash_function_2([Attr | Attrs], Schema,
+ IsFirst, Code0, Code) :-
+ list__index0_det(Schema, Attr, Type),
+ rl_exprn__type_to_aditi_type(Type, AType),
+ rl_exprn__hash_bytecode(AType, HashCode),
+ rl_exprn__get_input_field_code(one, AType, Attr, FieldCode),
+ ( IsFirst = no ->
+ CombineCode = node([rl_EXP_hash_combine])
+ ;
+ CombineCode = empty
+ ),
+
+ Code1 =
+ tree(Code0,
+ tree(node([FieldCode, HashCode]),
+ CombineCode
+ )),
+ IsFirst1 = no,
+ rl_exprn__generate_hash_function_2(Attrs, Schema, IsFirst1,
+ Code1, Code).
+
+:- pred rl_exprn__hash_bytecode(aditi_type::in, bytecode::out) is det.
+
+rl_exprn__hash_bytecode(int, rl_EXP_int_hash).
+rl_exprn__hash_bytecode(string, rl_EXP_str_hash).
+rl_exprn__hash_bytecode(float, rl_EXP_flt_hash).
+rl_exprn__hash_bytecode(term(_), rl_EXP_term_hash).
%-----------------------------------------------------------------------------%
Index: rl_key.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_key.m,v
retrieving revision 1.4
diff -u -u -r1.4 rl_key.m
--- rl_key.m 1999/08/25 06:34:02 1.4
+++ rl_key.m 2000/02/22 02:12:09
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -41,6 +41,11 @@
list(prog_var)::in, list(prog_var)::in, index_spec::in,
list(rl_var_bounds)::in, list(key_range)::out) is semidet.
+ % Succeed if a join is an equi-join, returning the list
+ % of arguments in each tuple which must be equivalent.
+:- pred rl_key__is_equijoin(rl_goal_inputs::in, list(rl_var_bounds)::in,
+ list(int)::out, list(int)::out) is semidet.
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -361,6 +366,93 @@
ConsId1, ConsId2, ConsId),
ConsId = ConsId1
).
+
+%-----------------------------------------------------------------------------%
+
+rl_key__is_equijoin(two_inputs(Args1, Args2), [VarBound0 | VarBounds],
+ Attrs1, Attrs2) :-
+ %
+ % For each attribute of the first tuple, work out which
+ % attributes of the second must be equal for the join
+ % condition to succeed.
+ % XXX we don't yet handle cases such as p(X, Y), p(X + 10, Z).
+ %
+ rl_key__restrict_bounds_to_arg_vars(Args1, Args2,
+ VarBound0, EqArgs0),
+ list__foldl(rl_key__intersect_branch_eq_args, VarBounds,
+ EqArgs0, EqArgs),
+ EqArgs \= [],
+
+ %
+ % For each attribute of the first tuple, choose one attribute
+ % of the second which must be equal.
+ %
+ list__map(rl_key__var_and_eq_args_to_attr_pair(Args1, Args2),
+ EqArgs, AttrPairs),
+ assoc_list__keys(AttrPairs, Attrs1),
+ assoc_list__values(AttrPairs, Attrs2).
+
+:- pred rl_key__var_and_eq_args_to_attr_pair(list(prog_var)::in,
+ list(prog_var)::in, pair(prog_var, set(prog_var))::in,
+ pair(int)::out) is det.
+
+rl_key__var_and_eq_args_to_attr_pair(Args1, Args2, Arg1 - EqArgs2,
+ AttrPair) :-
+ (
+ list__nth_member_search(Args1, Arg1, Attr1),
+ set__to_sorted_list(EqArgs2, EqArgsList2),
+ EqArgsList2 = [Arg2 | _],
+ list__nth_member_search(Args2, Arg2, Attr2)
+ ->
+ AttrPair = Attr1 - Attr2
+ ;
+ error("rl_key__var_and_eq_args_to_attr_pair")
+ ).
+
+:- pred rl_key__intersect_branch_eq_args(rl_var_bounds::in,
+ assoc_list(prog_var, set(prog_var))::in,
+ assoc_list(prog_var, set(prog_var))::out) is semidet.
+
+rl_key__intersect_branch_eq_args(Bounds, EqArgs0, EqArgs) :-
+ list__filter_map(rl_key__intersect_eq_args(Bounds), EqArgs0, EqArgs),
+ EqArgs \= [].
+
+:- pred rl_key__intersect_eq_args(rl_var_bounds::in,
+ pair(prog_var, set(prog_var))::in,
+ pair(prog_var, set(prog_var))::out) is semidet.
+
+rl_key__intersect_eq_args(Bounds, Var - EqVars0, Var - EqVars) :-
+ map__search(Bounds, Var, VarBounds),
+ rl_key__extract_bounds_eq_vars(VarBounds, BoundsEqArgs),
+ set__intersect(EqVars0, BoundsEqArgs, EqVars),
+ \+ set__empty(EqVars).
+
+:- pred rl_key__restrict_bounds_to_arg_vars(list(prog_var)::in,
+ list(prog_var)::in, rl_var_bounds::in,
+ assoc_list(prog_var, set(prog_var))::out) is det.
+
+rl_key__restrict_bounds_to_arg_vars(Args, ArgsOfOtherTuple,
+ Bounds0, ArgsAndEqOtherArgs) :-
+ set__list_to_set(ArgsOfOtherTuple, ArgsOfOtherTupleSet),
+ list__filter_map(
+ (pred(Arg::in, ArgAndEqOtherArgs::out) is semidet :-
+ map__search(Bounds0, Arg, ArgBounds),
+
+ rl_key__extract_bounds_eq_vars(ArgBounds,
+ BoundsEqArgs),
+ set__intersect(BoundsEqArgs, ArgsOfOtherTupleSet,
+ EqOtherArgs),
+ \+ set__empty(EqOtherArgs),
+ ArgAndEqOtherArgs = Arg - EqOtherArgs
+ ), Args, ArgsAndEqOtherArgs).
+
+:- pred rl_key__extract_bounds_eq_vars(pair(key_term)::in,
+ set(prog_var)::out) is det.
+
+rl_key__extract_bounds_eq_vars(LBound - UBound, BoundsEqArgs) :-
+ LBound = _ - LessThanOrEqVars,
+ UBound = _ - GreaterThanOrEqVars,
+ set__intersect(LessThanOrEqVars, GreaterThanOrEqVars, BoundsEqArgs).
%-----------------------------------------------------------------------------%
Index: rl_out.pp
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_out.pp,v
retrieving revision 1.9
diff -u -u -r1.9 rl_out.pp
--- rl_out.pp 1999/08/25 06:34:03 1.9
+++ rl_out.pp 2000/02/22 02:45:21
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -58,7 +58,8 @@
:- import_module code_util, hlds_data, hlds_pred, prog_data, prog_out.
:- import_module llds, globals, options, rl_code, tree, type_util, passes_aux.
-:- import_module rl_file, getopt, modules, prog_util, magic_util.
+:- import_module rl_file, getopt, modules, prog_util, magic_util, hlds_goal.
+:- import_module code_aux.
#if INCLUDE_ADITI_OUTPUT % See ../Mmake.common.in.
:- import_module rl_exprn.
@@ -556,70 +557,10 @@
:- pred rl_out__generate_instr(rl_instruction::in, byte_tree::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out__generate_instr(join(Output, Input1, Input2, Type, Cond) - _, Code) -->
- (
- { Type = nested_loop },
- rl_out__generate_join(rl_PROC_join_nl, Output,
- Input1, Input2, Cond, Code)
- ;
- { Type = sort_merge(_, _) },
- rl_out__generate_join(rl_PROC_join_sm, Output,
- Input1, Input2, Cond, Code)
- ;
- { Type = index(IndexSpec, Range) },
- { rl_out__index_spec_to_string(IndexSpec, IndexStr) },
- rl_out_info_assign_const(string(IndexStr), IndexConst),
- rl_out__generate_stream(Input1, Stream1Code),
- rl_out_info_get_relation_addr(Input2, Input2Addr),
- rl_out__generate_key_range(Range, RangeExprn),
- rl_out_info_get_output_relation_schema_offset(Output,
- OutputSchemaOffset),
- rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
- { InstrCode =
- tree(node([rl_PROC_join_index_simple]),
- tree(Stream1Code,
- node([
- rl_PROC_indexed_var(Input2Addr, 0, IndexConst),
- rl_PROC_expr(RangeExprn),
- rl_PROC_expr(CondExprn)
- ])
- )) },
- rl_out__generate_stream_instruction(Output, InstrCode, Code)
- ;
- { Type = cross },
- rl_out__generate_join(rl_PROC_join_cross, Output,
- Input1, Input2, Cond, Code)
- ;
- { Type = semi },
- %
- % Optimize a common case here - if the output does not depend
- % on the second relation, we generate this as:
- % if (empty(rel2)) {
- % init(output);
- % } else {
- % output = rel1;
- % }
- %
- % This happens for joins with zero-arity input relations.
- (
- { rl__goal_is_independent_of_input(two,
- Cond, _Cond1) }
- ->
- rl_out__generate_stream(Input1, Stream1Code),
- rl_out__generate_stream(Input2, Stream2Code),
- { CondCode =
- tree(node([rl_PROC_empty]),
- Stream2Code) },
- rl_out__generate_instr(init(Output) - "", ThenCode),
- rl_out__generate_stream_instruction(Output,
- Stream1Code, ElseCode),
- rl_out__generate_ite(CondCode, ThenCode, ElseCode,
- Code)
- ;
- rl_out__generate_join(rl_PROC_join_sm, Output,
- Input1, Input2, Cond, Code)
- )
- ).
+rl_out__generate_instr(join(Output, Input1, Input2, Type, Cond,
+ SemiJoin, TrivialJoin) - _, Code) -->
+ rl_out__generate_join(Output, Input1, Input2, Type,
+ SemiJoin, TrivialJoin, Cond, Code).
rl_out__generate_instr(subtract(Output, Input1, Input2, Type, Cond) - _,
Code) -->
@@ -629,16 +570,18 @@
OutputSchemaOffset),
rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
(
- { Type = nested_loop },
- { SubtractCode = rl_PROC_subtract_nl }
- ;
- { Type = semi },
+ { Type = semi_nested_loop },
{ SubtractCode = rl_PROC_semisubtract_nl }
+ ;
+ { Type = semi_sort_merge(_, _) },
+ { error(
+ "rl_out__generate_instr: subtract_sm not yet implemented") }
;
- { Type = sort_merge(_, _) },
- { SubtractCode = rl_PROC_subtract_sm }
+ { Type = semi_hash(_, _) },
+ { error(
+ "rl_out__generate_instr: subtract_hash not yet implemented") }
;
- { Type = index(_IndexSpec, _) },
+ { Type = semi_index(_IndexSpec, _) },
{ error(
"rl_out__generate_instr: subtract_index not yet implemented") }
),
@@ -665,97 +608,8 @@
rl_out__generate_stream_instruction(Output, InstrCode, Code).
rl_out__generate_instr(project(Output, Input, Cond0,
OtherOutputs, ProjectType) - _, Code) -->
- rl_out_info_get_output_relation_schema_offset(Output,
- OutputSchemaOffset),
-
- % If the produced tuple is independent of the input tuple,
- % generate:
- % if (empty(Input)) {
- % init(Output);
- % } else
- % init(Output);
- % insert_tuple(Output, Tuple);
- % }
- %
- % This can happen for tables of facts.
- %
- % Projections of this type are never combined with
- % other projections of the same input relation in the
- % one instruction by rl_block_opt.m.
- (
- { OtherOutputs = [] },
- { rl__goal_is_independent_of_input(one, Cond0, Cond) }
- ->
- rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
- rl_out__generate_stream(Input, StreamCode),
- { CondCode = tree(node([rl_PROC_empty]), StreamCode) },
- rl_out__generate_instr(init(Output) - "", ThenCode),
- { TupleCode = node([
- rl_PROC_insert_tuple_stream,
- rl_PROC_stream,
- rl_PROC_empty_stream(OutputSchemaOffset),
- rl_PROC_stream_end,
- rl_PROC_expr(CondExprn)
- ]) },
- rl_out__generate_stream_instruction(Output, TupleCode,
- ElseCode),
- rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code)
- ;
- (
- { ProjectType = filter },
- rl_out__generate_stream(Input, StreamCode)
- ;
- % For an indexed project/select we do a btree_scan
- % to select out the range of tuples we're interested
- % in, then proceed as normal.
- { ProjectType = index(IndexSpec, Range) },
- { rl_out__index_spec_to_string(IndexSpec, IndexStr) },
- rl_out_info_get_relation_addr(Input, InputAddr),
- rl_out_info_assign_const(string(IndexStr), IndexConst),
- rl_out__generate_key_range(Range, RangeExprn),
- { StreamCode = node([
- rl_PROC_stream,
- rl_PROC_btree_scan,
- rl_PROC_indexed_var(InputAddr, 0, IndexConst),
- rl_PROC_expr(RangeExprn),
- rl_PROC_stream_end
- ]) }
- ),
-
- rl_out__generate_exprn(Cond0, OutputSchemaOffset, CondExprn),
-
- %
- % Initialise the other output relations.
- %
- { assoc_list__keys(OtherOutputs, OtherOutputRels) },
- list__map_foldl(
- (pred(TheOutput::in, RelInitCode::out, in, out) is det -->
- rl_out__generate_instr(init(TheOutput) - "",
- RelInitCode)
- ),
- OtherOutputRels, OtherOutputInitCodeList),
- { list__foldl(
- (pred(InitCode::in, Tree0::in, Tree::out) is det :-
- Tree = tree(Tree0, InitCode)
- ),
- OtherOutputInitCodeList, empty, OtherOutputInitCode) },
-
- { list__map(rl__output_rel_relation,
- OtherOutputRels, OtherOutputRelations) },
- rl_out__get_rel_var_list(OtherOutputRelations, VarListCode),
- list__foldl2(rl_out__generate_project_exprn, OtherOutputs,
- empty, ExprnListCode),
- { InstrCode =
- tree(node([rl_PROC_project_tee]),
- tree(StreamCode,
- tree(node([rl_PROC_expr(CondExprn)]),
- tree(VarListCode,
- tree(ExprnListCode,
- node([rl_PROC_expr_list_nil])
- ))))) },
- rl_out__generate_stream_instruction(Output, InstrCode, Code0),
- { Code = tree(OtherOutputInitCode, Code0) }
- ).
+ rl_out__generate_project(Output, Input, Cond0, OtherOutputs,
+ ProjectType, Code).
rl_out__generate_instr(union(Output, Inputs, Type) - _, Code) -->
{ UnionCode = rl_PROC_union_sm },
{ Type = sort_merge(Spec) },
@@ -955,26 +809,383 @@
%-----------------------------------------------------------------------------%
-:- pred rl_out__generate_join(bytecode::in, output_rel::in,
- relation_id::in, relation_id::in, rl_goal::in,
- byte_tree::out, rl_out_info::in, rl_out_info::out) is det.
+:- pred rl_out__generate_join(output_rel::in, relation_id::in,
+ relation_id::in, join_type::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_info)::in, rl_goal::in, byte_tree::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__generate_join(Output, Input1a, Input2a, JoinType0, MaybeSemiJoin,
+ MaybeTrivialJoin, Cond0, Code) -->
+ %
+ % Work out the bytecode to use for the join, and whether the
+ % join is actually a semi-join.
+ %
+ { rl_out__compute_join_bytecode(JoinType0, MaybeSemiJoin,
+ JoinBytecode, SwapInputs) },
+
+ {
+ MaybeSemiJoin = yes(_),
+ rl__strip_goal_outputs(Cond0, Cond1)
+ ;
+ MaybeSemiJoin = no,
+ Cond1 = Cond0
+ },
+
+ {
+ SwapInputs = yes,
+ Input1 = Input2a,
+ Input2 = Input1a,
+ rl__swap_goal_inputs(Cond1, Cond),
+ rl__swap_join_type_inputs(JoinType0, JoinType)
+ ;
+ SwapInputs = no,
+ Input1 = Input1a,
+ Input2 = Input2a,
+ Cond = Cond1,
+ JoinType = JoinType0
+ },
+
+ %
+ % Optimize a common case here - if the join condition does not
+ % depend on the second relation, we generate this as:
+ % if (empty(rel2)) {
+ % init(output);
+ % } else {
+ % output = project(rel1);
+ % }
+ %
+ % This happens often for joins with zero-arity input relations.
+ %
+ % The projection will be unnecessary for a semi-join where
+ % the condition is deterministic.
+ %
+ (
+ { MaybeTrivialJoin = yes(TrivialJoinInfo) },
+ { TrivialJoinInfo = trivial_join_info(ProjectTupleNum0,
+ MaybeProjectType) },
+ {
+ SwapInputs = yes,
+ rl__swap_tuple_num(ProjectTupleNum0, ProjectTupleNum)
+ ;
+ SwapInputs = no,
+ ProjectTupleNum = ProjectTupleNum0
+ },
+
+ {
+ ProjectTupleNum = one,
+ ProjectInput = Input1,
+ TestRel = Input2
+ ;
+ ProjectTupleNum = two,
+ ProjectInput = Input2,
+ TestRel = Input1
+ },
+
+ (
+ { MaybeProjectType = yes(ProjectType) },
+ { rl__swap_tuple_num(ProjectTupleNum, InputToRemove) },
+ { rl__remove_goal_input(InputToRemove,
+ Cond, ProjectCond) },
+ { ProjectInstr = project(Output, ProjectInput,
+ ProjectCond, [], ProjectType) - "" },
+ rl_out__generate_instr(ProjectInstr, ElseCode)
+ ;
+ { MaybeProjectType = no },
+ rl_out__maybe_materialise(Output,
+ ProjectInput, ElseCode)
+ ),
+
+ rl_out__generate_stream(TestRel, TestStreamCode),
+ { CondCode = tree(node([rl_PROC_empty]), TestStreamCode) },
+ rl_out__generate_instr(init(Output) - "", ThenCode),
+ rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code)
+ ;
+ { MaybeTrivialJoin = no },
+ rl_out__generate_join_2(Output, Input1, Input2,
+ JoinType, JoinBytecode, Cond, Code)
+ ).
+
+:- pred rl_out__compute_join_bytecode(join_type::in, maybe(semi_join_info)::in,
+ bytecode::out, bool::out) is det.
+
+rl_out__compute_join_bytecode(nested_loop, no, rl_PROC_join_nl, no).
+rl_out__compute_join_bytecode(nested_loop, yes(Tuple),
+ rl_PROC_semijoin_nl, Swap) :-
+ rl_out__should_swap_inputs(Tuple, Swap).
+
+rl_out__compute_join_bytecode(sort_merge(_, _), no, rl_PROC_join_sm, no).
+rl_out__compute_join_bytecode(sort_merge(_, _), yes(Tuple),
+ rl_PROC_semijoin_sm, Swap) :-
+ rl_out__should_swap_inputs(Tuple, Swap).
+
+rl_out__compute_join_bytecode(hash(_, _), no, rl_PROC_join_hj, no).
+rl_out__compute_join_bytecode(hash(_, _), yes(Tuple),
+ rl_PROC_semijoin_hj, Swap) :-
+ rl_out__should_swap_inputs(Tuple, Swap).
+
+rl_out__compute_join_bytecode(index(_, _), no, rl_PROC_join_index_simple, no).
+rl_out__compute_join_bytecode(index(_, _), yes(Tuple),
+ rl_PROC_semijoin_index, no) :-
+ require(unify(Tuple, one),
+ "indexed semi_join doesn't return first tuple").
+
+ % For semi_joins, the first input tuple is the one returned.
+:- pred rl_out__should_swap_inputs(tuple_num::in, bool::out) is det.
+
+rl_out__should_swap_inputs(one, no).
+rl_out__should_swap_inputs(two, yes).
+
+:- pred rl_out__generate_join_2(output_rel::in, relation_id::in,
+ relation_id::in, join_type::in, bytecode::in,
+ rl_goal::in, byte_tree::out, rl_out_info::in, rl_out_info::out) is det.
-rl_out__generate_join(JoinCode, Output, Input1, Input2, Cond, Code) -->
+rl_out__generate_join_2(Output, Input1, Input2, JoinType,
+ JoinBytecode, Cond, Code) -->
+ (
+ { JoinType = nested_loop },
+ rl_out__generate_join_3(JoinBytecode, Output,
+ Input1, Input2, [], Cond, Code)
+ ;
+ { JoinType = hash(Attrs1, Attrs2) },
+ %
+ % Hash values are not necessarily unique, so
+ % the entire join condition must run when
+ % performing the nested loop join on tuples
+ % with the same hash value.
+ %
+ rl_out__generate_hash_exprn(Input1, Attrs1, HashExprn1),
+ rl_out__generate_hash_exprn(Input2, Attrs2, HashExprn2),
+ rl_out__generate_join_3(JoinBytecode, Output,
+ Input1, Input2, [HashExprn1, HashExprn2], Cond, Code)
+ ;
+ { JoinType = sort_merge(Spec1, Spec2) },
+ rl_out_info_get_relation_schema(Input1, Schema1),
+ rl_out_info_get_relation_schema(Input1, Schema2),
+ rl_out__generate_sort_merge_compare_exprn(Spec1, Schema1,
+ Spec2, Schema2, CompareExprn),
+
+ %
+ % XXX We should strip out the parts of the join
+ % condition which are already tested by the CompareExprns.
+ %
+ rl_out__generate_join_3(JoinBytecode, Output,
+ Input1, Input2, [CompareExprn],
+ Cond, Code)
+ ;
+ { JoinType = index(IndexSpec, Range) },
+ { rl_out__index_spec_to_string(IndexSpec, IndexStr) },
+ rl_out_info_assign_const(string(IndexStr), IndexConst),
+ rl_out__generate_stream(Input1, Stream1Code),
+ rl_out_info_get_relation_addr(Input2, Input2Addr),
+ rl_out__generate_key_range(Range, RangeExprn),
+ rl_out_info_get_output_relation_schema_offset(Output,
+ OutputSchemaOffset),
+ %
+ % XXX We should strip out the parts of the join
+ % condition which are already tested by the comparison
+ % against the ends of the key range.
+ %
+ rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
+ { InstrCode =
+ tree(node([JoinBytecode]),
+ tree(Stream1Code,
+ node([
+ rl_PROC_indexed_var(Input2Addr, 0, IndexConst),
+ rl_PROC_expr(RangeExprn),
+ rl_PROC_expr(CondExprn)
+ ])
+ )) },
+ rl_out__generate_stream_instruction(Output, InstrCode, Code)
+ ).
+
+:- pred rl_out__generate_join_3(bytecode::in, output_rel::in,
+ relation_id::in, relation_id::in,
+ list(int)::in, rl_goal::in, byte_tree::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__generate_join_3(JoinCode, Output, Input1, Input2,
+ ExtraExprns, Cond, Code) -->
rl_out_info_get_output_relation_schema_offset(Output,
OutputSchemaOffset),
rl_out__generate_stream(Input1, Stream1Code),
rl_out__generate_stream(Input2, Stream2Code),
rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
+ { list__append(ExtraExprns, [CondExprn], Exprns) },
+ { list__map(pred(Exprn::in, rl_PROC_expr(Exprn)::out) is det,
+ Exprns, ExprnInstrs) },
{ InstrCode =
tree(node([JoinCode]),
tree(Stream1Code,
tree(Stream2Code,
- node([rl_PROC_expr(CondExprn)])
+ node(ExprnInstrs)
))) },
rl_out__generate_stream_instruction(Output, InstrCode, Code).
%-----------------------------------------------------------------------------%
+:- pred rl_out__generate_project(output_rel::in, relation_id::in,
+ rl_goal::in, assoc_list(output_rel, rl_goal)::in,
+ project_type::in, byte_tree::out, rl_out_info::in,
+ rl_out_info::out) is det.
+
+rl_out__generate_project(Output, Input, Cond0, OtherOutputs,
+ ProjectType, Code) -->
+ rl_out_info_get_output_relation_schema_offset(Output,
+ OutputSchemaOffset),
+
+ %
+ % If the goal passes the input tuple through unmodified,
+ % the projection is actually a selection.
+ %
+ { rl__goal_returns_input_tuple(Cond0, one) ->
+ rl__strip_goal_outputs(Cond0, Cond1)
+ ;
+ Cond1 = Cond0
+ },
+
+ rl_out_info_get_module_info(ModuleInfo),
+ { rl_out__is_trivial_project(ModuleInfo, ProjectType,
+ Cond1, ProjectIsTrivial) },
+ (
+ { ProjectIsTrivial = yes }
+ ->
+ %
+ % Just copy the input to the output unmodified.
+ %
+ rl_out__maybe_materialise(Output, Input, Code)
+ ;
+ { OtherOutputs = [] },
+ { rl__goal_is_independent_of_input(one, Cond0) }
+ ->
+ %
+ % If the produced tuple is independent of the input tuple,
+ % generate:
+ % if (empty(Input)) {
+ % init(Output);
+ % } else
+ % init(Output);
+ % insert_tuple(Output, Tuple);
+ % }
+ %
+ % This can happen for tables of facts.
+ %
+ % Projections of this type are never combined with
+ % other projections of the same input relation in the
+ % one instruction by rl_block_opt.m.
+ %
+ { rl__remove_goal_input(one, Cond0, Cond) },
+ rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
+ rl_out__generate_stream(Input, StreamCode),
+ { CondCode = tree(node([rl_PROC_empty]), StreamCode) },
+ rl_out__generate_instr(init(Output) - "", ThenCode),
+ { TupleCode = node([
+ rl_PROC_insert_tuple_stream,
+ rl_PROC_stream,
+ rl_PROC_empty_stream(OutputSchemaOffset),
+ rl_PROC_stream_end,
+ rl_PROC_expr(CondExprn)
+ ]) },
+ rl_out__generate_stream_instruction(Output, TupleCode,
+ ElseCode),
+ rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code)
+ ;
+ (
+ { ProjectType = filter },
+ rl_out__generate_stream(Input, StreamCode)
+ ;
+ %
+ % For an indexed project/select we do a btree_scan
+ % to select out the range of tuples we're interested
+ % in, then proceed as normal.
+ %
+ % XXX We should strip out the parts of the join
+ % condition which are already tested by the
+ % CompareExprns. The project_tee operation
+ % may not be necessary.
+ %
+
+ { ProjectType = index(IndexSpec, Range) },
+ { rl_out__index_spec_to_string(IndexSpec, IndexStr) },
+ rl_out_info_get_relation_addr(Input, InputAddr),
+ rl_out_info_assign_const(string(IndexStr), IndexConst),
+ rl_out__generate_key_range(Range, RangeExprn),
+ { StreamCode = node([
+ rl_PROC_stream,
+ rl_PROC_btree_scan,
+ rl_PROC_indexed_var(InputAddr, 0, IndexConst),
+ rl_PROC_expr(RangeExprn),
+ rl_PROC_stream_end
+ ]) }
+ ),
+
+ rl_out__generate_exprn(Cond0, OutputSchemaOffset, CondExprn),
+
+ %
+ % Initialise the other output relations.
+ %
+ { assoc_list__keys(OtherOutputs, OtherOutputRels) },
+ list__map_foldl(
+ (pred(TheOutput::in, RelInitCode::out, in, out) is det -->
+ rl_out__generate_instr(init(TheOutput) - "",
+ RelInitCode)
+ ),
+ OtherOutputRels, OtherOutputInitCodeList),
+ { list__foldl(
+ (pred(InitCode::in, Tree0::in, Tree::out) is det :-
+ Tree = tree(Tree0, InitCode)
+ ),
+ OtherOutputInitCodeList, empty, OtherOutputInitCode) },
+
+ { list__map(rl__output_rel_relation,
+ OtherOutputRels, OtherOutputRelations) },
+ rl_out__get_rel_var_list(OtherOutputRelations, VarListCode),
+ list__foldl2(rl_out__generate_project_exprn, OtherOutputs,
+ empty, ExprnListCode),
+ { InstrCode =
+ tree(node([rl_PROC_project_tee]),
+ tree(StreamCode,
+ tree(node([rl_PROC_expr(CondExprn)]),
+ tree(VarListCode,
+ tree(ExprnListCode,
+ node([rl_PROC_expr_list_nil])
+ ))))) },
+ rl_out__generate_stream_instruction(Output, InstrCode, Code0),
+ { Code = tree(OtherOutputInitCode, Code0) }
+ ).
+
+ %
+ % Check whether a projection is needed.
+ % A projection is not needed if it is a selection
+ % (there is no output tuple) and the selection condition
+ % is deterministic.
+ %
+:- pred rl_out__is_trivial_project(module_info::in, project_type::in,
+ rl_goal::in, bool::out) is det.
+
+rl_out__is_trivial_project(ModuleInfo, ProjectType, RLGoal, IsTrivial) :-
+ (
+ ProjectType = filter,
+ (
+ \+ rl__goal_produces_tuple(RLGoal),
+ Goals = RLGoal ^ goal,
+
+ rl__goal_can_be_removed(ModuleInfo, Goals)
+ ->
+ IsTrivial = yes
+ ;
+ IsTrivial = no
+ )
+ ;
+ %
+ % Indexed projections contain a selection
+ % which must always be performed.
+ %
+ ProjectType = index(_, _),
+ IsTrivial = no
+ ).
+
+%-----------------------------------------------------------------------------%
+
% Copy any arguments which are needed again later to a temporary
% location. The called procedure can then do what it likes to
% the new variable (except changing the contents of the relation
@@ -1259,6 +1470,33 @@
))))) }
).
+:- pred rl_out__maybe_materialise(output_rel::in, relation_id::in,
+ byte_tree::out, rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__maybe_materialise(OutputRel, Input, Code) -->
+ { OutputRel = output_rel(Output, Indexes) },
+ rl_out_info_get_relation_type(Input, InputType),
+ rl_out_info_get_relation_type(Output, OutputType),
+
+ (
+ { InputType = temporary(stream) },
+ { OutputType = temporary(materialised) }
+ ->
+ rl_out_info_get_relation_addr(Input, InputAddr),
+ { LockSpec = 0 }, % default,
+ rl_out__generate_stream_instruction(OutputRel,
+ node([rl_PROC_var(InputAddr, LockSpec)]), Code)
+ ;
+ rl_out__generate_instr(ref(Output, Input) - "", RefCode),
+ ( { Indexes = [] } ->
+ { IndexCode = empty }
+ ;
+ rl_out__generate_instr(add_index(OutputRel) - "",
+ IndexCode)
+ ),
+ { Code = tree(RefCode, IndexCode) }
+ ).
+
%-----------------------------------------------------------------------------%
:- pred rl_out__generate_stream_list(list(relation_id)::in, byte_tree::out,
@@ -1503,6 +1741,43 @@
rl_out_info_set_compare_exprns(CompareExprns)
).
+ % Generate an expression to compare the join attributes
+ % in a sort-merge equi-join.
+:- pred rl_out__generate_sort_merge_compare_exprn(sort_spec::in,
+ list(type)::in, sort_spec::in, list(type)::in, int::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__generate_sort_merge_compare_exprn(Attrs1, Schema1,
+ Attrs2, Schema2, ExprnNum) -->
+ rl_out_info_get_sort_merge_compare_exprns(CompareExprns0),
+ rl_out__schema_to_string(Schema1, Schema1Offset),
+ rl_out__schema_to_string(Schema2, Schema2Offset),
+
+ { CompareExprnId = (Attrs1 - Schema1Offset)
+ - (Attrs2 - Schema2Offset) },
+
+ ( { map__search(CompareExprns0, CompareExprnId, ExprnNum0) } ->
+ { ExprnNum = ExprnNum0 }
+ ;
+ rl_out_info_get_module_info(ModuleInfo),
+ { rl_exprn__generate_sort_merge_compare_exprn(ModuleInfo,
+ Attrs1, Schema1, Attrs2, Schema2, Instrs) },
+
+ % Comparison expressions don't use any variables
+ % or create an output tuple.
+ rl_out__schema_to_string([], EmptySchemaOffset),
+
+ % Nothing is built on the stack, so this will be enough.
+ { StackSize = 10 },
+ { Decls = [] },
+ rl_out__package_exprn(Instrs, 2, test, EmptySchemaOffset,
+ EmptySchemaOffset, StackSize, Decls, ExprnNum),
+
+ { map__det_insert(CompareExprns0, CompareExprnId,
+ ExprnNum, CompareExprns) },
+ rl_out_info_set_sort_merge_compare_exprns(CompareExprns)
+ ).
+
:- pred rl_out__generate_key_range(key_range::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
@@ -1521,6 +1796,33 @@
Output1SchemaOffset, Output2SchemaOffset, StackSize,
Decls, RangeExprn).
+:- pred rl_out__generate_hash_exprn(relation_id::in, list(int)::in, int::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__generate_hash_exprn(Input, Attrs, ExprnNum) -->
+ rl_out_info_get_hash_exprns(HashExprns0),
+ rl_out_info_get_relation_schema(Input, InputSchema),
+ rl_out__schema_to_string(InputSchema, InputSchemaOffset),
+ ( { map__search(HashExprns0, Attrs - InputSchemaOffset, ExprnNum0) } ->
+ { ExprnNum = ExprnNum0 }
+ ;
+ rl_out_info_get_module_info(ModuleInfo),
+ { rl_exprn__generate_hash_function(ModuleInfo,
+ Attrs, InputSchema, ExprnCode) },
+ rl_out__schema_to_string([], EmptySchemaOffset),
+
+ % Nothing is built on the stack, so this will be enough.
+ { StackSize = 10 },
+ { NumParams = 1 },
+ { Decls = [] },
+ rl_out__package_exprn(ExprnCode, NumParams, test,
+ EmptySchemaOffset, EmptySchemaOffset, StackSize,
+ Decls, ExprnNum),
+ { map__det_insert(HashExprns0, Attrs - InputSchemaOffset,
+ ExprnNum, HashExprns) },
+ rl_out_info_set_hash_exprns(HashExprns)
+ ).
+
:- pred rl_out__package_exprn(list(bytecode)::in, int::in, exprn_mode::in,
int::in, int::in, int::in, list(type)::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
@@ -1543,43 +1845,57 @@
:- type rl_out_info
---> rl_out_info(
- int, % PC
- compare_exprns,
- map(relation_id, int), % relation vars
- int, % next relation address
- map(relation_id, relation_info),
- map(label_id, int), % proc label offsets
- unit,
- module_info,
- int, % expression PC
- map(rl_const, int), % procedure consts
- int, % next proc const address
- int, % next materialise number -
- % used for debugging the
- % generated code.
- unit,
- unit,
- unit,
- int, % next proc label.
- list(procedure), % procedure bytecodes
+ module_info :: module_info,
+
+ pc :: int,
+
+ procs :: list(procedure), % bytecodes for each procedure,
% in reverse order.
- unit,
- unit,
- unit,
- set(relation), % permanent relations.
- list(variable), % variables used in
+
+
+ %
+ % Tables used to avoid generating multiple
+ % copies of the expressions used to
+ % compare tuples and compute hash values.
+ %
+ compare_exprns :: compare_exprns,
+ sort_merge_compare_exprns :: sort_merge_compare_exprns,
+ hash_exprns :: hash_exprns,
+
+ permanent_relations :: set(relation),
+
+ relation_addrs :: map(relation_id, int), % relation vars
+ next_relation_addr :: int, % next relation address
+
+ relation_variables :: list(variable),
+ % variables used in
% reverse order.
- list(expression), % expressions for the current
+
+ relations :: map(relation_id, relation_info),
+
+ proc_labels :: map(label_id, int), % proc label offsets
+ next_proc_label :: int,
+
+ consts :: map(rl_const, int), % procedure consts
+ next_const :: int, % next proc const address
+
+ next_materialise :: int, % next materialise number -
+ % used for debugging the
+ % generated code.
+
+ exprns :: list(expression), % expressions for the current
% procedure in reverse order.
- int, % next expression.
- multi_map(int, int) % temporary relation variables:
+ next_exprn :: int, % next expression.
+
+ tmp_vars :: multi_map(int, int)
+ % temporary relation variables:
% map from schema constant
% to list of variables.
% These must only be used
% within one rl.m instruction.
).
- % We only want to generate a single comparison expression for
+ % We only want to generate a single comparison or hash expression for
% each combination of attributes and types.
% Key:
% The int gives the offset of the schema of the input relation
@@ -1588,70 +1904,113 @@
% The number of the expression.
:- type compare_exprns == map(pair(sort_spec, int), int).
+ % The comparison in a sort-merge join takes for each relation
+ % the list of attributes being joined on and the schema offset.
+:- type sort_merge_compare == pair(pair(sort_spec, int)).
+:- type sort_merge_compare_exprns == map(sort_merge_compare, int).
+
+:- type hash_exprns == map(pair(list(int), int), int).
+
%-----------------------------------------------------------------------------%
:- pred rl_out_info_init(module_info::in, rl_out_info::out) is det.
rl_out_info_init(ModuleInfo, Info0) :-
map__init(CompareExprns),
+ map__init(SortMergeCompareExprns),
+ map__init(HashExprns),
map__init(Relations),
map__init(RelationAddrs),
map__init(Consts),
map__init(Labels),
- set__init(PermRels),
map__init(TmpVars),
PC = 0,
FirstRelAddr = 0,
FirstConst = 1,
FirstMaterialise = 1,
- Label = 0,
- NextExprn = 0,
- Info0 = rl_out_info(PC, CompareExprns, RelationAddrs, FirstRelAddr,
- Relations, Labels, unit, ModuleInfo, PC, Consts,
- FirstConst, FirstMaterialise, unit, unit, unit, Label,
- [], unit, unit, unit, PermRels, [], [],
- NextExprn, TmpVars).
+ FirstLabel = 0,
+ Exprns = [],
+ FirstExprn = 0,
+ Procs = [],
+ set__init(PermanentRelations),
+ RelationVariables = [],
+
+ Info0 = rl_out_info(ModuleInfo, PC, Procs,
+ CompareExprns, SortMergeCompareExprns, HashExprns,
+ PermanentRelations, RelationAddrs, FirstRelAddr,
+ RelationVariables, Relations, Labels, FirstLabel,
+ Consts, FirstConst, FirstMaterialise, Exprns,
+ FirstExprn, TmpVars).
:- pred rl_out_info_init_proc(map(relation_id, relation_info)::in,
list(relation_id)::in, rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_init_proc(Relations, _Args, Info0, Info) :-
- map__init(Labels),
- map__init(RelationAddrs),
- map__init(CompareExprns),
- PC = 0,
- Label = 0,
- NextExprn = 0,
- map__init(TmpVars),
- Info0 = rl_out_info(_, _, _, NextAddr, _, _, _,
- ModuleInfo, _, ProcConsts, NextConst, Materialise, _, _,
- _, _, Procs, _, _, _, PermRelations, Variables, _, _, _),
- Info = rl_out_info(PC, CompareExprns, RelationAddrs, NextAddr,
- Relations, Labels, unit, ModuleInfo, PC, ProcConsts,
- NextConst, Materialise, unit, unit, unit, Label, Procs,
- unit, unit, unit, PermRelations, Variables, [],
- NextExprn, TmpVars).
+rl_out_info_init_proc(Relations, _Args) -->
+ ^ relations := Relations,
+
+ { map__init(Labels) },
+ ^ proc_labels := Labels,
+ ^ next_proc_label := 0,
+
+ { map__init(RelationAddrs) },
+ ^ relation_addrs := RelationAddrs,
+
+ { map__init(CompareExprns) },
+ ^ compare_exprns := CompareExprns,
+
+ { map__init(HashExprns) },
+ ^ hash_exprns := HashExprns,
+
+ ^ pc := 0,
+ ^ exprns := [],
+ ^ next_exprn := 0,
+
+ { map__init(TmpVars) },
+ ^ tmp_vars := TmpVars.
+
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_compare_exprns(compare_exprns::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_compare_exprns(Exprns, Info, Info) :-
- Info = rl_out_info(_,Exprns,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,_,_,_,_,_,_,_).
+rl_out_info_get_compare_exprns(Exprns) --> Exprns =^ compare_exprns.
:- pred rl_out_info_set_compare_exprns(compare_exprns::in,
rl_out_info::in, rl_out_info::out) is det.
+
+rl_out_info_set_compare_exprns(Exprns) --> ^ compare_exprns := Exprns.
+
+%-----------------------------------------------------------------------------%
+
+:- pred rl_out_info_get_sort_merge_compare_exprns(
+ sort_merge_compare_exprns::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out_info_get_sort_merge_compare_exprns(Exprns) -->
+ Exprns =^ sort_merge_compare_exprns.
+
+:- pred rl_out_info_set_sort_merge_compare_exprns(
+ sort_merge_compare_exprns::in,
+ rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_set_compare_exprns(Exprns, Info0, Info) :-
- Info0 = rl_out_info(A,_,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,W,X,Y),
- Info = rl_out_info(A,Exprns,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,
- V,W,X,Y).
+rl_out_info_set_sort_merge_compare_exprns(Exprns) -->
+ ^ sort_merge_compare_exprns := Exprns.
%-----------------------------------------------------------------------------%
+:- pred rl_out_info_get_hash_exprns(hash_exprns::out, rl_out_info::in,
+ rl_out_info::out) is det.
+
+rl_out_info_get_hash_exprns(HashExprns) --> HashExprns =^ hash_exprns.
+
+:- pred rl_out_info_set_hash_exprns(hash_exprns::in, rl_out_info::in,
+ rl_out_info::out) is det.
+
+rl_out_info_set_hash_exprns(HashExprns) --> ^ hash_exprns := HashExprns.
+
+%-----------------------------------------------------------------------------%
+
:- pred rl_out_info_get_relation_addr(relation_id::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
@@ -1670,18 +2029,13 @@
:- pred rl_out_info_get_relation_addrs(map(relation_id, int)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_relation_addrs(Addrs, Info, Info) :-
- Info = rl_out_info(_,_,Addrs,_,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,_,_,_,_,_,_,_).
+rl_out_info_get_relation_addrs(Addrs) -->
+ Addrs =^ relation_addrs.
:- pred rl_out_info_set_relation_addrs(map(relation_id, int)::in,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_set_relation_addrs(Addrs, Info0, Info) :-
- Info0 = rl_out_info(A,B,_,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,W,X,Y),
- Info = rl_out_info(A,B,Addrs,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,
- V,W,X,Y).
+rl_out_info_set_relation_addrs(Addrs) --> ^ relation_addrs := Addrs.
:- pred rl_out_info_add_relation_variable(int::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
@@ -1696,116 +2050,89 @@
:- pred rl_out_info_add_relation_variable_2(int::in, int::in,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_add_relation_variable_2(Name, Schema, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,Vars0,W,X,Y),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,
- [variable(Name, Schema) | Vars0], W,X,Y).
+rl_out_info_add_relation_variable_2(Name, Schema) -->
+ Vars0 =^ relation_variables,
+ ^ relation_variables := [variable(Name, Schema) | Vars0].
:- pred rl_out_info_get_next_relation_addr(int::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_next_relation_addr(NextAddr0, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,NextAddr0,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,W,X,Y),
- NextAddr is NextAddr0 + 1,
- Info = rl_out_info(A,B,C,NextAddr,E,F,G,H,
- I,J,K,L,M, N,O,P,Q,R,S,T,U,V,W,X,Y).
+rl_out_info_get_next_relation_addr(NextAddr0) -->
+ NextAddr0 =^ next_relation_addr,
+ ^ next_relation_addr := NextAddr0 + 1.
:- pred rl_out_info_get_relation_variables(list(variable)::out,
rl_out_info::in, rl_out_info::out) is det.
rl_out_info_get_relation_variables(Vars, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- Vars0,_,_,_),
- list__reverse(Vars0, Vars).
+ list__reverse(Info ^ relation_variables, Vars).
%-----------------------------------------------------------------------------%
:- pred rl_out_info_add_label(label_id::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_add_label(LabelId, NextLabel, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,Labels0,G,H,I,J,K,L,M,N,O,NextLabel,
- Q,R,S,T,U,V,W,X,Y),
- map__det_insert(Labels0, LabelId, NextLabel, Labels),
- NextLabel1 is NextLabel + 1,
- Info = rl_out_info(A,B,C,D,E,Labels,G,H,I,J,K,L,M,N,O,NextLabel1,
- Q,R,S,T,U,V,W,X,Y).
+rl_out_info_add_label(LabelId, NextLabel) -->
+ rl_out_info_add_label(NextLabel),
+ Labels0 =^ proc_labels,
+ { map__det_insert(Labels0, LabelId, NextLabel, Labels) },
+ ^ proc_labels := Labels.
:- pred rl_out_info_add_label(int::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_add_label(NextLabel, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,NextLabel,
- Q,R,S,T,U,V,W,X,Y),
- NextLabel1 is NextLabel + 1,
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,NextLabel1,
- Q,R,S,T,U,V,W,X,Y).
+rl_out_info_add_label(NextLabel) -->
+ NextLabel =^ next_proc_label,
+ ^ next_proc_label := NextLabel + 1.
:- pred rl_out_info_get_labels(map(label_id, int)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_labels(Labels, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,Labels,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,_,_,_,_,_).
+rl_out_info_get_labels(Labels) --> Labels =^ proc_labels.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_module_info(module_info::out, rl_out_info::in,
rl_out_info::out) is det.
-rl_out_info_get_module_info(ModuleInfo, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,ModuleInfo,
- _,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_).
+rl_out_info_get_module_info(ModuleInfo) --> ModuleInfo =^ module_info.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_assign_const(rl_const::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_assign_const(Const, ConstOffset, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,Consts0,NextAddr0,
- L,M,N,O,P,Q,R,S,T,U,V,W,X,Y),
- ( map__search(Consts0, Const, Addr1) ->
- ConstOffset = Addr1,
- NextAddr = NextAddr0,
- Consts = Consts0
- ;
- map__det_insert(Consts0, Const, NextAddr0, Consts),
- ConstOffset = NextAddr0,
- NextAddr is NextAddr0 + 1
- ),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,Consts,NextAddr,
- L,M,N,O,P,Q,R,S,T,U,V,W,X,Y).
+rl_out_info_assign_const(Const, ConstOffset) -->
+ Consts0 =^ consts,
+ ( { map__search(Consts0, Const, ConstOffset0) } ->
+ { ConstOffset = ConstOffset0 }
+ ;
+ ConstOffset =^ next_const,
+ { map__det_insert(Consts0, Const, ConstOffset, Consts) },
+ ^ consts := Consts,
+ ^ next_const := ConstOffset + 1
+ ).
:- pred rl_out_info_get_consts(map(rl_const, int)::out,
- rl_out_info::in,
- rl_out_info::out) is det.
+ rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_consts(Consts, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,Consts,
- _,_,_,_,_,_,_,_,_,_,_,_,_,_,_).
+rl_out_info_get_consts(Consts) --> Consts =^ consts.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_next_materialise_id(int::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_next_materialise_id(MaterialiseId, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,
- MaterialiseId, M,N,O,P,Q,R,S,T,U,V,W,X,Y),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,
- MaterialiseId + 1, M,N,O,P,Q,R,S,T,U,V,W,X,Y).
+rl_out_info_get_next_materialise_id(MaterialiseId) -->
+ MaterialiseId =^ next_materialise,
+ ^ next_materialise := MaterialiseId + 1.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_relations(map(relation_id, relation_info)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_relations(Relations, Info, Info) :-
- Info = rl_out_info(_,_,_,_,Relations,
- _,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_).
+rl_out_info_get_relations(Relations) --> Relations =^ relations.
%-----------------------------------------------------------------------------%
@@ -1858,76 +2185,61 @@
:- pred rl_out_info_incr_pc(int::in, rl_out_info::in,
rl_out_info::out) is det.
-rl_out_info_incr_pc(Incr, Info0, Info) :-
- Info0 = rl_out_info(PC0,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,
- S,T,U,V,W,X,Y),
- PC = PC0 + Incr,
- Info = rl_out_info(PC,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,
- T,U,V,W,X,Y).
+rl_out_info_incr_pc(Incr) -->
+ PC0 =^ pc,
+ ^ pc := PC0 + Incr.
:- pred rl_out_info_get_pc(int::out, rl_out_info::in,
rl_out_info::out) is det.
-rl_out_info_get_pc(PC0, Info, Info) :-
- Info = rl_out_info(PC0,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,_,_,_,_,_).
+rl_out_info_get_pc(PC) --> PC =^ pc.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_add_proc(procedure::in,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_add_proc(Proc, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Procs0,
- R,S,T,U,V,W,X,Y),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,[Proc | Procs0],
- R,S,T,U,V,W,X,Y).
+rl_out_info_add_proc(Proc) -->
+ Procs0 =^ procs,
+ ^ procs := [Proc | Procs0].
:- pred rl_out_info_get_procs(list(procedure)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_procs(Procs, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,Procs0,
- _,_,_,_,_,_,_,_),
- list__reverse(Procs0, Procs).
+rl_out_info_get_procs(Procs) -->
+ Procs0 =^ procs,
+ { list__reverse(Procs0, Procs) }.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_permanent_relations(set(relation)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_permanent_relations(Rels, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- Rels,_,_,_,_).
+rl_out_info_get_permanent_relations(Rels) --> Rels =^ permanent_relations.
:- pred rl_out_info_set_permanent_relations(set(relation)::in,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_set_permanent_relations(Rels, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,_,V,W,X,Y),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,Rels, V,W,X,Y).
+rl_out_info_set_permanent_relations(Rels) --> ^ permanent_relations := Rels.
%-----------------------------------------------------------------------------%
:- pred rl_out_info_get_proc_expressions(list(expression)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_proc_expressions(Exprns, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,Exprns0,_,_),
- list__reverse(Exprns0, Exprns).
+rl_out_info_get_proc_expressions(Exprns) -->
+ Exprns0 =^ exprns,
+ { list__reverse(Exprns0, Exprns) }.
:- pred rl_out_info_add_expression(expression::in, int::out,
rl_out_info::in, rl_out_info::out) is det.
+
+rl_out_info_add_expression(Exprn, NextExprn0) -->
+ Exprns0 =^ exprns,
+ NextExprn0 =^ next_exprn,
-rl_out_info_add_expression(Exprn, NextExprn0, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,Exprns0,NextExprn0,Y),
- NextExprn is NextExprn0 + 1,
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,[Exprn | Exprns0], NextExprn,Y).
+ ^ exprns := [Exprn | Exprns0],
+ ^ next_exprn := NextExprn0 + 1.
%-----------------------------------------------------------------------------%
@@ -1969,18 +2281,12 @@
:- pred rl_out_info_get_tmp_vars(multi_map(int, int)::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_get_tmp_vars(TmpVars, Info, Info) :-
- Info = rl_out_info(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,
- _,_,_,_, TmpVars).
+rl_out_info_get_tmp_vars(TmpVars) --> TmpVars =^ tmp_vars.
:- pred rl_out_info_set_tmp_vars(multi_map(int, int)::in,
rl_out_info::in, rl_out_info::out) is det.
-rl_out_info_set_tmp_vars(TmpVars, Info0, Info) :-
- Info0 = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,W,X,_),
- Info = rl_out_info(A,B,C,D,E,F,G,H,I,J,K,L,M,
- N,O,P,Q,R,S,T,U,V,W,X,TmpVars).
+rl_out_info_set_tmp_vars(TmpVars) --> ^ tmp_vars := TmpVars.
#else % !INCLUDE_ADITI_OUTPUT
#endif
Index: rl_relops.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_relops.m,v
retrieving revision 1.3
diff -u -u -r1.3 rl_relops.m
--- rl_relops.m 1999/08/14 04:52:26 1.3
+++ rl_relops.m 2000/02/22 02:53:50
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -206,20 +206,8 @@
rl_relops__join(InputRel1, InputRel2, Args1, Args2, InstMap,
JoinCondGoals, OutputVars, OutputSchema, OutputRel, Code) -->
rl_relops__join_2(InputRel1, InputRel2, Args1, Args2, InstMap,
- JoinCondGoals, OutputVars, OutputSchema, JoinOutputRel,
- JoinType, JoinOutputs, JoinCode),
-
- % Semi-join doesn't create an output tuple, so we may need
- % to do a projection on the output relation.
- ( { JoinType = semi } ->
- rl_relops__select_and_project(JoinOutputRel, OutputRel,
- JoinOutputs, OutputVars, InstMap, JoinCondGoals,
- ProjectCode)
- ;
- { ProjectCode = empty },
- { OutputRel = JoinOutputRel }
- ),
- { Code = tree(JoinCode, ProjectCode) }.
+ JoinCondGoals, OutputVars, OutputSchema, OutputRel,
+ _JoinType, _JoinOutputs, Code).
:- pred rl_relops__join_2(relation_id::in, relation_id::in, list(prog_var)::in,
list(prog_var)::in, instmap::in, list(hlds_goal)::in,
@@ -237,24 +225,16 @@
{ rl_relops__maybe_reverse_inputs(ReverseInputs,
Args1, Args2, ReorderedArgs1, ReorderedArgs2) },
- ( { JoinType = semi } ->
- rl_info_get_proc_info(ProcInfo),
- { proc_info_vartypes(ProcInfo, VarTypes) },
- { map__apply_to_list(JoinOutputs, VarTypes, JoinOutputTypes) },
- { JoinOutputSchema = schema(JoinOutputTypes) },
- { MaybeOutputs = no }
- ;
- { JoinOutputSchema = OutputSchema },
- { MaybeOutputs = yes(OutputVars) }
- ),
-
rl_relops__goal(InstMap, two_inputs(ReorderedArgs1, ReorderedArgs2),
- MaybeOutputs, JoinCondGoals, JoinCond),
+ yes(OutputVars), JoinCondGoals, JoinCond),
rl_info__comment(Comment),
- rl_info_get_new_temporary(JoinOutputSchema, OutputRel),
+ rl_info_get_new_temporary(OutputSchema, OutputRel),
+ { TrivialJoin = no },
+ { SemiJoin = no },
{ Code = node([join(output_rel(OutputRel, []), ReorderedInput1,
- ReorderedInput2, JoinType, JoinCond) - Comment]) }.
+ ReorderedInput2, JoinType, JoinCond,
+ SemiJoin, TrivialJoin) - Comment]) }.
rl_relops__diff_diff_join(DiffRel1, FullRel1, DiffRel2, FullRel2,
Args1, Args2, InstMap, JoinCondGoals, RuleOutputs,
@@ -274,51 +254,25 @@
},
rl_relops__union(yes, RuleSchema, [OutputRel1, OutputRel2],
- no, UnionResult, UnionCode),
+ no, RuleResult, UnionCode),
- % Delay the projection until after the union so that the
- % projection isn't run on duplicates tuples in each relation.
- ( { JoinType = semi } ->
- rl_relops__select_and_project(UnionResult, RuleResult,
- JoinOutputs, RuleOutputs, InstMap, JoinCondGoals,
- ProjectCode)
- ;
- { RuleResult = UnionResult },
- { ProjectCode = empty }
- ),
{ JoinCode =
tree(JoinCode1,
tree(JoinCode2,
- tree(UnionCode,
- ProjectCode
- ))) }.
+ UnionCode
+ )) }.
- % If the outputs of a join are the same as the attributes
- % of an input relation, we can do a semi-join. If so, the
- % inputs may need to be reversed so that the relation from
- % which the outputs are to be taken is the first argument
- % of the join.
- % XXX Aditi's implementation of semi-join is buggy.
+ % All joins start out as nested loop joins, and are specialized later.
:- pred rl_relops__classify_join_condition(list(prog_var)::in,
list(prog_var)::in, list(prog_var)::in, list(hlds_goal)::in,
join_type::out, list(prog_var)::out, bool::out,
rl_info::rl_info_di, rl_info::rl_info_uo) is det.
-rl_relops__classify_join_condition(Args1, Args2, Outputs, _Goals,
+rl_relops__classify_join_condition(_, _, Outputs, _,
Type, JoinOutputs, ReverseInputRels) -->
- { Args1 = Outputs, semidet_fail ->
- Type = semi,
- ReverseInputRels = no,
- JoinOutputs = Args1
- ; Args2 = Outputs, semidet_fail ->
- Type = semi,
- ReverseInputRels = yes,
- JoinOutputs = Args2
- ;
- Type = nested_loop,
- ReverseInputRels = no,
- JoinOutputs = Outputs
- }.
+ { Type = nested_loop },
+ { ReverseInputRels = no },
+ { JoinOutputs = Outputs }.
:- pred rl_relops__maybe_reverse_inputs(bool::in,
T::in, T::in, T::out, T::out) is det.
@@ -348,10 +302,12 @@
ProjectCode
) }.
+ % All subtracts start out as semi_nested_loop subtracts,
+ % and are specialized later.
:- pred rl_relops__classify_subtract_condition(list(hlds_goal)::in,
subtract_type::out, rl_info::rl_info_di, rl_info::rl_info_uo) is det.
-rl_relops__classify_subtract_condition(_, semi) --> [].
+rl_relops__classify_subtract_condition(_, semi_nested_loop) --> [].
rl_relops__difference(OldRel, NewRel, DiffRel, Code) -->
rl_info_get_relation_schema(OldRel, Schema),
Index: rl_sort.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_sort.m,v
retrieving revision 1.5
diff -u -u -r1.5 rl_sort.m
--- rl_sort.m 1999/08/25 06:34:03 1.5
+++ rl_sort.m 2000/02/22 02:54:09
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -7,18 +7,17 @@
% Main author: stayl
%
% Work out what sorting and indexing is available, and introduce
-% sort-merge or indexed operations where possible.
+% sort-merge, hashed or indexed operations where possible.
%
% Remove unnecessary sort and add_index operations.
%
%
% Eventually this module should:
%
-% Generate sort and add_index instructions where required. This should be
-% performed after other optimization passes which introduce sort-merge
-% operations. (There are none yet). At the moment sorts are inserted where
-% they might be required by rl_gen.m, but for example a union may be optimized
-% into a union_diff and no longer require sorted input.
+% Generate sort and add_index instructions where required.
+% At the moment sorts are inserted where they might be required by
+% rl_gen.m, but for example a union may be optimized into a union_diff
+% and no longer require sorted input.
%
% For some operations such as sort-merge union, all that is required
% is that all inputs are sorted on all of their attributes.
@@ -624,11 +623,11 @@
sort_info::in, sort_info::out) is det.
rl_sort__instr_needed(BlockId,
- join(_Output, Input1, Input2, Type, _Exprn) - _) -->
+ join(_Output, Input1, Input2, Type, _Exprn, _, _) - _) -->
(
{ Type = nested_loop }
;
- { Type = semi }
+ { Type = hash(_, _) }
;
{ Type = sort_merge(SortSpec1, SortSpec2) },
rl_sort__add_relation_sortedness(BlockId, sort(SortSpec1),
@@ -639,23 +638,21 @@
{ Type = index(Index, _) },
rl_sort__add_relation_sortedness(BlockId, index(Index),
Input2)
- ;
- { Type = cross }
).
rl_sort__instr_needed(BlockId,
subtract(_Output, Input1, Input2, Type, _Exprn) - _) -->
(
- { Type = nested_loop }
+ { Type = semi_nested_loop }
;
- { Type = semi }
+ { Type = semi_hash(_, _) }
;
- { Type = sort_merge(SortSpec1, SortSpec2) },
+ { Type = semi_sort_merge(SortSpec1, SortSpec2) },
rl_sort__add_relation_sortedness(BlockId, sort(SortSpec1),
Input1),
rl_sort__add_relation_sortedness(BlockId, sort(SortSpec2),
Input2)
;
- { Type = index(Index, _) },
+ { Type = semi_index(Index, _) },
rl_sort__add_relation_sortedness(BlockId, index(Index),
Input2)
).
@@ -781,7 +778,7 @@
sort_info::in, sort_info::out) is det.
rl_sort__instr_avail(BlockId,
- join(Output, _Input1, _Input2, _Type, _Exprn) - _) -->
+ join(Output, _Input1, _Input2, _Type, _Exprn, _, _) - _) -->
rl_sort__handle_output_indexing(BlockId, Output).
rl_sort__instr_avail(BlockId,
subtract(Output, _Input1, _Input2, _Type, _Exprn) - _) -->
@@ -953,7 +950,7 @@
rl_sort__specialize_instr(BlockId, Instr0, Instrs0, Instrs) -->
(
- { Instr0 = join(Output, Input1, Input2, Type, Exprn)
+ { Instr0 = join(Output, Input1, Input2, Type, Exprn, _, _)
- Comment }
->
rl_sort__specialize_join(Instr0, Output, Input1, Input2,
@@ -978,10 +975,47 @@
sort_info::in, sort_info::out) is det.
rl_sort__specialize_join(Instr0, Output, Input1, Input2, Exprn,
- _Type, Comment, Instrs0, Instrs,
+ JoinType, Comment, Instrs0, Instrs,
SortInfo0, SortInfo) :-
SortInfo0 = sort_info(Sortedness0, SortVars, RLInfo0),
Sortedness0 = sortedness(RelSortMap, _),
+
+ rl_sort__introduce_indexed_join(RelSortMap, Output, Input1, Input2,
+ JoinType, Exprn, Comment, MaybeIndexJoinInstrs,
+ RLInfo0, RLInfo1),
+ ( MaybeIndexJoinInstrs = yes(IndexJoinInstrs) ->
+ RLInfo = RLInfo1,
+ JoinInstrs = IndexJoinInstrs
+ ;
+ rl_sort__introduce_sort_join(RelSortMap,
+ Output, Input1, Input2, JoinType, Exprn, Comment,
+ MaybeSortJoinInstrs, RLInfo1, RLInfo2),
+ ( MaybeSortJoinInstrs = yes(SortJoinInstrs) ->
+ RLInfo = RLInfo2,
+ JoinInstrs = SortJoinInstrs
+ ;
+ rl_sort__introduce_hash_join(Output,
+ Input1, Input2, JoinType, Exprn, Comment,
+ MaybeHashJoinInstrs, RLInfo2, RLInfo),
+ ( MaybeHashJoinInstrs = yes(HashJoinInstrs) ->
+ JoinInstrs = HashJoinInstrs
+ ;
+ JoinInstrs = [Instr0]
+ )
+ )
+ ),
+ list__reverse(JoinInstrs, RevJoinInstrs),
+ list__append(RevJoinInstrs, Instrs0, Instrs),
+ SortInfo = sort_info(Sortedness0, SortVars, RLInfo).
+
+:- pred rl_sort__introduce_indexed_join(relation_sort_map::in, output_rel::in,
+ relation_id::in, relation_id::in, join_type::in,
+ rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+
+rl_sort__introduce_indexed_join(RelSortMap, Output, Input1, Input2, _JoinType0,
+ Exprn, Comment, MaybeIndexJoinInstrs, RLInfo0, RLInfo) :-
+
rl_opt_info_get_relation_info_map(RelMap, RLInfo0, RLInfo1),
rl_sort__get_relation_indexes(RelSortMap, RelMap,
Input1, Input1Indexes, IsBaseRelation1),
@@ -989,11 +1023,10 @@
Input2, Input2Indexes, IsBaseRelation2),
( Input1Indexes = [], Input2Indexes = [] ->
- % XXX maybe introduce sort-merge joins.
- Instrs = [Instr0 | Instrs0],
+ MaybeIndexJoinInstrs = no,
RLInfo = RLInfo1
;
- rl_opt_info_get_module_info(ModuleInfo, RLInfo1, RLInfo2),
+ rl_opt_info_get_module_info(ModuleInfo, RLInfo1, RLInfo),
rl_sort__find_useful_join_indexes(ModuleInfo, Input1Indexes,
Exprn, one, IndexRanges1),
rl_sort__find_useful_join_indexes(ModuleInfo, Input2Indexes,
@@ -1001,7 +1034,6 @@
% XXX the choice of index here is slightly cheap and nasty
% when there are multiple possibilities.
- RLInfo = RLInfo2,
(
IndexRanges1 = [],
IndexRanges2 = [],
@@ -1063,14 +1095,16 @@
JoinInput1 = Input1,
JoinInput2 = Input2
),
+ SemiJoin = no,
+ TrivialJoin = no,
JoinInstr = join(Output, JoinInput1, JoinInput2,
- JoinType, Exprn1) - Comment
+ JoinType, Exprn1, SemiJoin,
+ TrivialJoin) - Comment,
+ MaybeIndexJoinInstrs = yes([JoinInstr])
;
- JoinInstr = Instr0
- ),
- Instrs = [JoinInstr | Instrs0]
- ),
- SortInfo = sort_info(Sortedness0, SortVars, RLInfo).
+ MaybeIndexJoinInstrs = no
+ )
+ ).
:- pred rl_sort__find_useful_join_indexes(module_info::in,
list(index_spec)::in, rl_goal::in, tuple_num::in,
@@ -1111,6 +1145,136 @@
%-----------------------------------------------------------------------------%
+:- pred rl_sort__introduce_sort_join(relation_sort_map::in, output_rel::in,
+ relation_id::in, relation_id::in, join_type::in,
+ rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+
+rl_sort__introduce_sort_join(SortMap, Output, Input1, Input2, _JoinType0,
+ Exprn, Comment, MaybeSortJoinInstrs, RLInfo, RLInfo) :-
+ Exprn = rl_goal(_, _, _, _, Inputs, _, _, VarBounds),
+ (
+ rl_key__is_equijoin(Inputs, VarBounds, Attrs1, Attrs2),
+
+ map__search(SortMap, Input1, SortSpecs1),
+ find_equijoin_sort_spec(Attrs1, SortSpecs1, SortSpec1),
+
+ map__search(SortMap, Input2, SortSpecs2),
+ find_equijoin_sort_spec(Attrs2, SortSpecs2, SortSpec2)
+ ->
+ JoinType = sort_merge(SortSpec1, SortSpec2),
+ SemiJoin = no,
+ TrivialJoin = no,
+ JoinInstr = join(Output, Input1, Input2,
+ JoinType, Exprn, SemiJoin, TrivialJoin) - Comment,
+ MaybeSortJoinInstrs = yes([JoinInstr])
+ ;
+ MaybeSortJoinInstrs = no
+ ).
+
+ %
+ % Look for sort_specs which match all equijoin attributes.
+ % We could look for partial matches, but that could
+ % cause inefficient code to be generated if the attributes
+ % sorted on are not selective enough - we could end
+ % up doing nested loop joins on large numbers of tuples.
+ %
+:- pred find_equijoin_sort_spec(list(int)::in, map(sort_index, sort_req)::in,
+ sort_spec::out) is semidet.
+
+find_equijoin_sort_spec(Attrs, SortSpecs0, SortSpec) :-
+
+ find_definite_sort_specs(SortSpecs0, SortSpecs),
+ list__filter_map(matching_sort_spec(Attrs),
+ SortSpecs, MatchingSortSpecs),
+ MatchingSortSpecs = [SortSpec | _].
+
+ %
+ % Succeed if the sort_spec sorts on all the given
+ % attributes in the correct order.
+ %
+:- pred matching_sort_spec(list(int)::in,
+ sort_spec::in, sort_spec::out) is semidet.
+
+matching_sort_spec(AttrNums, Spec0, Spec) :-
+ Spec0 = attributes(SortAttrs0),
+ assoc_list__keys(SortAttrs0, SortAttrNums0),
+ assoc_list__values(SortAttrs0, SortDirs0),
+ list__length(AttrNums, NumRequiredAttrs),
+
+ % The sort_spec can sort on more attributes -
+ % take the prefix that is needed.
+ list__take(NumRequiredAttrs, SortAttrNums0, AttrNums),
+ list__take(NumRequiredAttrs, SortDirs0, SortDirs),
+ assoc_list__from_corresponding_lists(AttrNums, SortDirs, SortAttrs),
+ Spec = attributes(SortAttrs).
+
+:- pred find_definite_sort_specs(map(sort_index, sort_req)::in,
+ list(sort_spec)::out) is det.
+
+find_definite_sort_specs(SortMap, SortSpecs) :-
+ map__foldl(
+ (pred(SortIndex::in, SortReq::in, Specs0::in, Specs::out) is det :-
+ (
+ SortReq = sort_req(definite, _),
+ (
+ SortIndex = sort(SortSpec),
+ SortSpec = attributes(SortAttrs),
+ \+ (
+ % We could probably handle
+ % relations sorted in descending
+ % order, but it might be a bit
+ % trickier. We don't generate
+ % sort instructions to produce
+ % reverse sorted relations, so
+ % it doesn't matter.
+ list__member(SortAttr, SortAttrs),
+ SortAttr = _ - descending
+ )
+ ;
+ % B-tree indexed relations are sorted
+ % on the indexed attributes.
+ SortIndex = index(IndexSpec),
+ IndexSpec = index_spec(IndexType, Attrs),
+ ( IndexType = unique_B_tree
+ ; IndexType = non_unique_B_tree
+ ),
+ list__length(Attrs, NumAttrs),
+ list__duplicate(NumAttrs, ascending, SortDirs),
+ assoc_list__from_corresponding_lists(Attrs,
+ SortDirs, SortAttrs),
+ SortSpec = attributes(SortAttrs)
+ )
+ ->
+ Specs = [SortSpec | Specs0]
+ ;
+ Specs = Specs0
+ )
+ ), SortMap, [], SortSpecs).
+
+:- pred rl_sort__introduce_hash_join(output_rel::in,
+ relation_id::in, relation_id::in, join_type::in,
+ rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+
+rl_sort__introduce_hash_join(Output, Input1, Input2, _JoinType0, Exprn,
+ Comment, MaybeHashJoinInstrs, RLInfo, RLInfo) :-
+ Exprn = rl_goal(_, _, _, _, Inputs, _, _, VarBounds),
+ (
+ rl_key__is_equijoin(Inputs, VarBounds, Attrs1, Attrs2)
+ ->
+ JoinType = hash(Attrs1, Attrs2),
+ SemiJoin = no,
+ TrivialJoin = no,
+ JoinInstr = join(Output, Input1, Input2,
+ JoinType, Exprn, SemiJoin, TrivialJoin) - Comment,
+ MaybeHashJoinInstrs = yes([JoinInstr])
+ ;
+ MaybeHashJoinInstrs = no
+ ).
+
+%-----------------------------------------------------------------------------%
+
% Work out which index could be used for a project.
:- pred rl_sort__specialize_project(rl_instruction::in, output_rel::in,
relation_id::in, rl_goal::in, assoc_list(output_rel, rl_goal)::in,
@@ -1374,8 +1538,8 @@
rl_instruction::in, rl_instruction::out) is det.
rl_sort__map_sort_and_index_specs(OutputPred, IndexPred, SortPred,
- join(Output0, B, C, Type0, E) - F,
- join(Output, B, C, Type, E) - F) :-
+ join(Output0, B, C, Type0, E, F, G) - H,
+ join(Output, B, C, Type, E, F, G) - H) :-
call(OutputPred, Output0, Output),
( Type0 = sort_merge(Sort1a, Sort2a) ->
call(SortPred, Sort1a, Sort1),
@@ -1391,13 +1555,13 @@
subtract(Output0, B, C, Type0, E) - F,
subtract(Output, B, C, Type, E) - F) :-
call(OutputPred, Output0, Output),
- ( Type0 = sort_merge(Sort1a, Sort2a) ->
+ ( Type0 = semi_sort_merge(Sort1a, Sort2a) ->
call(SortPred, Sort1a, Sort1),
call(SortPred, Sort2a, Sort2),
- Type = sort_merge(Sort1, Sort2)
- ; Type0 = index(Index0, Range) ->
+ Type = semi_sort_merge(Sort1, Sort2)
+ ; Type0 = semi_index(Index0, Range) ->
call(IndexPred, Index0, Index),
- Type = index(Index, Range)
+ Type = semi_index(Index, Range)
;
Type = Type0
).
Index: rl_stream.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_stream.m,v
retrieving revision 1.2
diff -u -u -r1.2 rl_stream.m
--- rl_stream.m 1999/05/19 04:32:57 1.2
+++ rl_stream.m 2000/02/22 02:54:18
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% Copyright (C) 1998-1999 University of Melbourne.
+% Copyright (C) 1998-2000 University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
@@ -364,7 +364,8 @@
:- pred rl_stream__must_materialise_rels(rl_instruction, list(relation_id)).
:- mode rl_stream__must_materialise_rels(in, out) is det.
-rl_stream__must_materialise_rels(join(Output, _, _, _, _) - _, Materialise) :-
+rl_stream__must_materialise_rels(join(Output, _, _, _, _, _, _) - _,
+ Materialise) :-
rl_stream__output_is_indexed(Output, Materialise).
rl_stream__must_materialise_rels(subtract(Output, _, _, _, _) - _,
Materialise) :-
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list