[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