Changeset: ab372197b4af for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=ab372197b4af
Modified Files:
sql/backends/monet5/sql_upgrades.c
sql/common/sql_types.c
sql/server/rel_exp.c
sql/server/rel_optimizer.c
sql/server/rel_out2inner_join.txt
sql/test/Tests/50ways.stable.out
sql/test/osm/Tests/drop_constraint_bug.stable.out
sql/test/subquery/Tests/correlated.stable.out
sql/test/subquery/Tests/subquery5.stable.out
Branch: out2in
Log Message:
Implement out2inner join optimizer.
diffs (truncated from 349 to 300 lines):
diff --git a/sql/backends/monet5/sql_upgrades.c
b/sql/backends/monet5/sql_upgrades.c
--- a/sql/backends/monet5/sql_upgrades.c
+++ b/sql/backends/monet5/sql_upgrades.c
@@ -2789,7 +2789,7 @@ sql_update_semantics(Client c)
{
char* update_query =
"update sys.functions set semantics = false where type <> 6 and func
not ilike '%CREATE FUNCTION%' and name in
('length','octet_length','>','>=','<','<=','min','max','sql_min','sql_max','least','greatest','sum','prod','mod','and',\n"
-
"'or','xor','not','sql_mul','sql_div','sql_sub','sql_add','bit_and','bit_or','bit_xor','bit_not','left_shift','right_shift','abs','sign','scale_up','scale_down','round','power','floor','ceil','ceiling','sin','cos','tan','asin',\n"
+
"'xor','not','sql_mul','sql_div','sql_sub','sql_add','bit_and','bit_or','bit_xor','bit_not','left_shift','right_shift','abs','sign','scale_up','scale_down','round','power','floor','ceil','ceiling','sin','cos','tan','asin',\n"
"'acos','atan','sinh','cot','cosh','tanh','sqrt','exp','log','ln','log10','log2','pi','curdate','current_date','curtime','current_time','current_timestamp','localtime','localtimestamp','local_timezone','century','decade','year',\n"
"'quarter','month','day','dayofyear','weekofyear','dayofweek','dayofmonth','week','hour','minute','second','strings','locate','charindex','splitpart','substring','substr','truncate','concat','ascii','code','right','left','upper',\n"
"'ucase','lower','lcase','trim','ltrim','rtrim','lpad','rpad','insert','replace','repeat','space','char_length','character_length','soundex','qgramnormalize');";
diff --git a/sql/common/sql_types.c b/sql/common/sql_types.c
--- a/sql/common/sql_types.c
+++ b/sql/common/sql_types.c
@@ -1616,7 +1616,7 @@ sqltypeinit( sql_allocator *sa)
sql_create_analytic(sa, "listagg", "sql", "str_group_concat",
SCALE_NONE, STR, 2, STR, STR);
sql_create_func(sa, "and", "calc", "and", FALSE, FALSE, SCALE_FIX, 0,
BIT, 2, BIT, BIT);
- sql_create_func(sa, "or", "calc", "or", FALSE, FALSE, SCALE_FIX, 0,
BIT, 2, BIT, BIT);
+ sql_create_func(sa, "or", "calc", "or", TRUE, FALSE, SCALE_FIX, 0,
BIT, 2, BIT, BIT);
sql_create_func(sa, "xor", "calc", "xor", FALSE, FALSE, SCALE_FIX, 0,
BIT, 2, BIT, BIT);
sql_create_func(sa, "not", "calc", "not", FALSE, FALSE, SCALE_FIX, 0,
BIT, 1, BIT);
diff --git a/sql/server/rel_exp.c b/sql/server/rel_exp.c
--- a/sql/server/rel_exp.c
+++ b/sql/server/rel_exp.c
@@ -326,6 +326,7 @@ exp_op( sql_allocator *sa, list *l, sql_
e->card = CARD_ATOM; /* unop returns a single atom */
e->l = l;
e->f = f;
+ e->semantics = f->func->semantics;
fres = exp_subtype(e);
/* corner case if the output of the function is void, set the type to
one of the inputs */
@@ -1666,10 +1667,10 @@ exp_is_cmp_exp_is_false(mvc *sql, sql_ex
* Other cases in is-semantics are unspecified.
*/
if (e->flag == cmp_equal && !e->anti) {
- return (exp_is_null(sql, l) && exp_is_null(sql, r));
+ return ((exp_is_null(sql, l) && exp_is_not_null(sql, r)) ||
(exp_is_not_null(sql, l) && exp_is_null(sql, r)));
}
if (((e->flag == cmp_notequal) && !e->anti) || ((e->flag == cmp_equal) &&
e->anti) ) {
- return ((exp_is_null(sql, l) && exp_is_not_null(sql, r))) ||
((exp_is_not_null(sql, l) && exp_is_null(sql, r)));
+ return ((exp_is_null(sql, l) && exp_is_null(sql, r)) ||
(exp_is_not_null(sql, l) && exp_is_not_null(sql, r)));
}
return false;
@@ -1790,6 +1791,19 @@ exp_is_null(mvc *sql, sql_exp *e )
case e_convert:
return exp_is_null(sql, e->l);
case e_func:
+ if (!e->semantics && e->l) {
+ /* This is a call to a function with no-nil semantics.
+ * If one of the parameters is null the expression
itself is null
+ */
+ list* l = e->l;
+ for(node* n = l->h; n; n=n->next) {
+ sql_exp* p = n->data;
+ if (exp_is_null(sql, p)) {
+ return true;
+ }
+ }
+ }
+ return 0;
case e_aggr:
case e_column:
case e_cmp:
diff --git a/sql/server/rel_optimizer.c b/sql/server/rel_optimizer.c
--- a/sql/server/rel_optimizer.c
+++ b/sql/server/rel_optimizer.c
@@ -9037,6 +9037,154 @@ rel_merge_table_rewrite(mvc *sql, sql_re
return rel;
}
+static bool is_non_trivial_select_applied_to_outer_join(sql_rel *rel) {
+ return is_select(rel->op) && rel->exps && is_outerjoin(((sql_rel*)
rel->l)->op);
+}
+
+extern list *list_append_before(list *l, node *n, void *data);
+
+static void replace_column_references_with_nulls_2(mvc *sql, list* crefs,
sql_exp* e);
+
+static void
+replace_column_references_with_nulls_1(mvc *sql, list* crefs, list* exps) {
+ for(node* n = exps->h; n; n=n->next) {
+ sql_exp* e = n->data;
+ replace_column_references_with_nulls_2(sql, crefs, e);
+ }
+}
+
+static void
+replace_column_references_with_nulls_2(mvc *sql, list* crefs, sql_exp* e) {
+ if (e == NULL) {
+ return;
+ }
+
+ switch (e->type) {
+ case e_column:
+ for(node* n = crefs->h; n; n=n->next) {
+ sql_exp* c = n->data;
+
+ if (exp_match(e, c)) {
+ e->type = e_atom;
+ e->l = atom_general(sql->sa, &e->tpe, NULL);
+ e->r = e->f = NULL;
+ break;
+ }
+ }
+ break;
+ case e_cmp:
+ switch (e->flag) {
+ case cmp_gt:
+ case cmp_gte:
+ case cmp_lte:
+ case cmp_lt:
+ case cmp_equal:
+ case cmp_notequal:
+ {
+ sql_exp* l = e->l;
+ sql_exp* r = e->l;
+ sql_exp* f = e->f;
+
+ replace_column_references_with_nulls_2(sql, crefs, l);
+ replace_column_references_with_nulls_2(sql, crefs, r);
+ replace_column_references_with_nulls_2(sql, crefs, f);
+ break;
+ }
+ case cmp_or:
+ {
+ list* l = e->l;
+ list* r = e->r;
+ replace_column_references_with_nulls_1(sql, crefs, l);
+ replace_column_references_with_nulls_1(sql, crefs, r);
+ break;
+ }
+ default:
+ break;
+ }
+ break;
+ case e_func:
+ {
+ list* l = e->l;
+ replace_column_references_with_nulls_1(sql, crefs, l);
+ break;
+ }
+ case e_convert:
+ {
+ sql_exp* l = e->l;
+ replace_column_references_with_nulls_2(sql, crefs, l);
+ break;
+ }
+ default:
+ break;
+ }
+}
+
+static sql_rel *
+out2inner(mvc *sql, sql_rel* sel, sql_rel* join, sql_rel* inner_join_side, int
*changes, operator_type new_type) {
+
+ list* select_predicates = exps_copy(sql, sel->exps);
+
+ if (!is_base(inner_join_side->op) &&
!is_simple_project(inner_join_side->op)) {
+ // Nothing to do here.
+ return sel;
+ }
+
+ list* inner_join_column_references = inner_join_side->exps;
+
+ for(node* n = select_predicates->h; n; n=n->next) {
+ sql_exp* e = n->data;
+ replace_column_references_with_nulls_2(sql,
inner_join_column_references, e);
+
+ if (exp_is_false(sql, e)) {
+ join->op = new_type;
+ (*changes)++;
+ break;
+ }
+ }
+
+ return sel;
+}
+
+static sql_rel *
+rel_out2inner(mvc *sql, sql_rel *rel, int *changes) {
+
+ if (!is_non_trivial_select_applied_to_outer_join(rel)) {
+ // Nothing to do here.
+ return rel;
+ }
+
+ sql_rel* join = (sql_rel*) rel->l;
+
+ if (rel_is_ref(join)) {
+ /* Do not alter a multi-referenced join relation.
+ * This is problematic for e.g. the plan of a merge statement.
+ * */
+ return rel;
+ }
+
+ sql_rel* inner_join_side;
+ if (is_left(join->op)) {
+ inner_join_side = join->r;
+ return out2inner(sql, rel, join, inner_join_side, changes, op_join);
+ }
+ else if (is_right(join->op)) {
+ inner_join_side = join->l;
+ return out2inner(sql, rel, join, inner_join_side, changes, op_join);
+ }
+ else /*full outer join*/ {
+ // First check if left side can degenerate from full outer join to
just right outer join.
+ inner_join_side = join->r;
+ rel = out2inner(sql, rel, join, inner_join_side, changes, op_right);
+ /* Now test if the right side can degenerate to
+ * a normal inner join or a left outer join
+ * depending on the result of previous call to out2inner.
+ */
+
+ inner_join_side = join->l;
+ return out2inner(sql, rel, join, inner_join_side, changes,
is_right(join->op)? op_join: op_left);
+ }
+}
+
static sql_rel*
exp_skip_output_parts(sql_rel *rel)
{
@@ -9247,6 +9395,7 @@ optimize_rel(mvc *sql, sql_rel *rel, int
if (gp.cnt[op_join] || gp.cnt[op_left] || gp.cnt[op_right] ||
gp.cnt[op_full] || gp.cnt[op_semi] || gp.cnt[op_anti]) {
rel = rel_remove_empty_join(sql, rel, &changes);
+ rel = rel_visitor_topdown(sql, rel, &rel_out2inner, &changes);
rel = rel_visitor_bottomup(sql, rel, &rel_join2semijoin,
&changes);
if (!gp.cnt[op_update])
rel = rel_join_order(sql, rel);
@@ -9328,6 +9477,7 @@ optimize_rel(mvc *sql, sql_rel *rel, int
rel = rel_visitor_topdown(sql, rel, &rel_merge_table_rewrite,
&changes);
if (level <= 0 && mvc_debug_on(sql,8))
rel = rel_visitor_topdown(sql, rel, &rel_add_dicts, &changes);
+
*g_changes = changes;
return rel;
}
diff --git a/sql/server/rel_out2inner_join.txt
b/sql/server/rel_out2inner_join.txt
--- a/sql/server/rel_out2inner_join.txt
+++ b/sql/server/rel_out2inner_join.txt
@@ -5,8 +5,8 @@ Say we have two single integer column ta
create table foo (i int);
insert into foo values (10), (40), (20), (5);
-create table bar (i int);
-insert into bar values (30), (20), (50), (40);
+create table bar (i int, j int);
+insert into bar values (30, 300), (20, 200), (50, 500), (40, 400);
select * from foo;
+------+
@@ -28,7 +28,7 @@ select * from bar;
+------+
We compute the following outer join
-select * from foo left join bar on foo.i = bar.i where bar.i is not null;
+select foo.i, bar.i from foo left join bar on foo.i = bar.i where bar.j is not
null;
+------+------+
| i | i |
+======+======+
diff --git a/sql/test/Tests/50ways.stable.out b/sql/test/Tests/50ways.stable.out
--- a/sql/test/Tests/50ways.stable.out
+++ b/sql/test/Tests/50ways.stable.out
@@ -174,7 +174,10 @@ stdout of test '50ways` in directory 'sq
% tinyint # type
% 2 # length
[ 29 ]
-% .s # table_name
+#SELECT DISTINCT S.SNAME
+# FROM S NATURAL LEFT JOIN SP
+# WHERE SP.PNR = 'P2';
+% sys.s # table_name
% sname # name
% varchar # type
% 0 # length
@@ -184,7 +187,10 @@ stdout of test '50ways` in directory 'sq
% tinyint # type
% 2 # length
[ 30 ]
-% .s # table_name
+#SELECT DISTINCT S.SNAME
+# FROM S LEFT JOIN SP USING ( SNR )
+# WHERE SP.PNR = 'P2';
+% sys.s # table_name
% sname # name
% varchar # type
% 0 # length
@@ -194,7 +200,10 @@ stdout of test '50ways` in directory 'sq
% tinyint # type
% 2 # length
[ 31 ]
-% .s # table_name
+#SELECT DISTINCT S.SNAME
+# FROM S LEFT JOIN SP ON S.SNR = SP.SNR
+# WHERE SP.PNR = 'P2';
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
