Changeset: 5ccab190745e for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/5ccab190745e
Modified Files:
sql/server/rel_optimizer.c
sql/storage/store.c
sql/test/miscellaneous/Tests/simple_plans.test
Branch: antipush
Log Message:
Update join2semi optimizer to use the new unique flag and fixed a bug on the
unique flag propagation on storage. I should backport it into Jul2021
diffs (263 lines):
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
@@ -5280,12 +5280,16 @@ rel_push_join_down_outer(visitor *v, sql
return rel;
}
-static bool
+#define NO_PROJECTION_FOUND 0
+#define MAY_HAVE_DUPLICATE_NULLS 1
+#define ALL_VALUES_DISTINCT 2
+
+static int
find_projection_for_join2semi(sql_rel *rel)
{
- if (is_project(rel->op) && !is_union(rel->op)) {
+ if (is_simple_project(rel->op) || is_groupby(rel->op) ||
is_inter(rel->op) || is_except(rel->op) || is_basetable(rel->op) ||
(is_union(rel->op) && need_distinct(rel))) {
if (rel->card < CARD_AGGR) /* const or groupby without group by
exps */
- return true;
+ return ALL_VALUES_DISTINCT;
if (list_length(rel->exps) == 1) {
sql_exp *e = rel->exps->h->data;
/* a single group by column in the projection list from
a group by relation is guaranteed to be unique, but not an aggregate */
@@ -5295,28 +5299,32 @@ find_projection_for_join2semi(sql_rel *r
bool underjoin = false;
/* if just one groupby column is projected or
the relation needs distinct values and one column is projected or is a primary
key, it will be distinct */
- if ((is_groupby(rel->op) && list_length(rel->r)
== 1 && exps_find_exp(rel->r, e)) ||
- (is_simple_project(rel->op) &&
need_distinct(rel) && list_length(rel->exps) == 1) || find_prop(e->p,
PROP_HASHCOL))
- return true;
-
- if ((found =
rel_find_exp_and_corresponding_rel(rel->l, e, &res, &underjoin)) && !underjoin)
{ /* grouping column on inner relation */
- if ((is_simple_project(res->op) &&
need_distinct(res) && list_length(res->exps) == 1) || find_prop(found->p,
PROP_HASHCOL))
- return true;
+ if ((is_groupby(rel->op) && list_length(rel->r)
== 1 && exps_find_exp(rel->r, e)) || (need_distinct(rel) &&
list_length(rel->exps) == 1))
+ return ALL_VALUES_DISTINCT;
+ if (is_unique(e))
+ return has_nil(e) ?
MAY_HAVE_DUPLICATE_NULLS : ALL_VALUES_DISTINCT;
+
+ if ((is_simple_project(rel->op) ||
is_groupby(rel->op) || is_inter(rel->op) || is_except(rel->op)) &&
+ (found =
rel_find_exp_and_corresponding_rel(rel->l, e, &res, &underjoin)) && !underjoin)
{ /* grouping column on inner relation */
+ if (need_distinct(res) &&
list_length(res->exps) == 1)
+ return ALL_VALUES_DISTINCT;
+ if (is_unique(found))
+ return has_nil(e) ?
MAY_HAVE_DUPLICATE_NULLS : ALL_VALUES_DISTINCT;
if (found->type == e_column &&
found->card <= CARD_AGGR) {
if (!is_groupby(res->op) &&
list_length(res->exps) != 1)
- return false;
+ return
NO_PROJECTION_FOUND;
for (node *n = res->exps->h ; n
; n = n->next) { /* must be the single column in the group by expression list */
sql_exp *e = n->data;
if (e != found &&
e->type == e_column)
- return false;
+ return
NO_PROJECTION_FOUND;
}
- return true;
+ return ALL_VALUES_DISTINCT;
}
}
}
}
}
- return false;
+ return NO_PROJECTION_FOUND;
}
static sql_rel *
@@ -5327,23 +5335,28 @@ find_candidate_join2semi(visitor *v, sql
return NULL;
if (rel->op == op_join && !list_empty(rel->exps)) {
sql_rel *l = rel->l, *r = rel->r;
+ int foundr = 0, foundl = 0, found = 0;
bool ok = false;
- if (find_projection_for_join2semi(r)) {
+ foundr = find_projection_for_join2semi(r);
+ if (foundr < ALL_VALUES_DISTINCT)
+ foundl = find_projection_for_join2semi(l);
+ if (foundr && foundr > foundl) {
*swap = false;
- ok = true;
- } else if (find_projection_for_join2semi(l)) {
+ found = foundr;
+ } else if (foundl) {
*swap = true;
- ok = true;
- }
-
- if (ok) {
+ found = foundl;
+ }
+
+ if ((ok = found > 0)) {
ok = false;
/* if all join expressions can be pushed down or have
function calls, then it cannot be rewritten into a semijoin */
for (node *n=rel->exps->h; n && !ok; n = n->next) {
sql_exp *e = n->data;
- ok |= e->type == e_cmp && (e->flag == cmp_equal
|| e->flag == mark_in) && !exp_has_func(e) && !rel_rebind_exp(v->sql, l, e) &&
!rel_rebind_exp(v->sql, r, e);
+ ok |= e->type == e_cmp && e->flag == cmp_equal
&& !exp_has_func(e) && !rel_rebind_exp(v->sql, l, e) && !rel_rebind_exp(v->sql,
r, e) &&
+ (found == ALL_VALUES_DISTINCT ||
!is_semantics(e) || (!has_nil((sql_exp *)e->l) && !has_nil((sql_exp *)e->r)));
}
}
@@ -5606,7 +5619,7 @@ score_gbe(visitor *v, sql_rel *rel, sql_
if (e->card == CARD_ATOM) /* constants are trivial to group */
res += 1000;
/* can we find out if the underlying table is sorted */
- if (find_prop(e->p, PROP_HASHCOL) || (c && v->storage_based_opt &&
mvc_is_unique(v->sql, c))) /* distinct columns */
+ if (is_unique(e) || find_prop(e->p, PROP_HASHCOL) || (c &&
v->storage_based_opt && mvc_is_unique(v->sql, c))) /* distinct columns */
res += 700;
if (c && v->storage_based_opt && mvc_is_sorted(v->sql, c))
res += 500;
diff --git a/sql/storage/store.c b/sql/storage/store.c
--- a/sql/storage/store.c
+++ b/sql/storage/store.c
@@ -420,12 +420,14 @@ load_idxcolumn(sql_trans *tr, sql_idx *
kc->c = find_sql_column(i->t, v);
assert(kc->c);
list_append(i->columns, kc);
- if (hash_index(i->type))
- kc->c->unique = 1;
- if (hash_index(i->type) && list_length(i->columns) > 1) {
- /* Correct the unique flag of the keys first column */
- sql_kc *ic1 = i->columns->h->data;
- ic1->c->unique = kc->c->unique = 2;
+ if (hash_index(i->type)) {
+ if (list_length(i->columns) == 1) {
+ kc->c->unique = 1;
+ } else {
+ /* Correct unique flag of first key column */
+ sql_kc *ic1 = i->columns->h->data;
+ ic1->c->unique = kc->c->unique = 2;
+ }
}
}
@@ -3238,7 +3240,7 @@ sql_trans_copy_idx( sql_trans *tr, sql_t
sql_table *sysidx = find_sql_table(tr, syss, "idxs");
sql_table *sysic = find_sql_table(tr, syss, "objects");
node *n;
- int nr, unique = 0, res = LOG_OK;
+ int nr, res = LOG_OK;
sql_table *dup = NULL;
if ((res = new_table(tr, t, &dup)))
@@ -3252,15 +3254,19 @@ sql_trans_copy_idx( sql_trans *tr, sql_t
ni->key = NULL;
ATOMIC_PTR_INIT(&ni->data, NULL);
- if (i->type == hash_idx && list_length(i->columns) == 1)
- unique = 1;
for (n = i->columns->h, nr = 0; n; n = n->next, nr++) {
sql_kc *okc = n->data, *ic;
list_append(ni->columns, ic = kc_dup(tr, okc, t));
- if (ic->c->unique != (unique & !okc->c->null))
- okc->c->unique = ic->c->unique = (unique &
(!okc->c->null));
-
+ if (i->type == hash_idx) {
+ if (nr == 0) {
+ ic->c->unique = 1;
+ } else {
+ /* Correct unique flag of first key column */
+ sql_kc *ic1 = ni->columns->h->data;
+ ic1->c->unique = ic->c->unique = 2;
+ }
+ }
if ((res = store->table_api.table_insert(tr, sysic,
&ni->base.id, &ic->c->base.name, &nr, ATOMnilptr(TYPE_int)))) {
idx_destroy(store, ni);
return res;
@@ -5547,10 +5553,14 @@ create_sql_ic(sqlstore *store, sql_alloc
list_append(i->columns, ic);
(void)store;
- if (hash_index(i->type) && list_length(i->columns) > 1) {
- /* Correct the unique flag of the keys first column */
- sql_kc *ic1 = i->columns->h->data;
- ic1->c->unique = c->unique = 2;
+ if (hash_index(i->type)) {
+ if (list_length(i->columns) == 1) {
+ c->unique = 1;
+ } else {
+ /* Correct unique flag of first key column */
+ sql_kc *ic1 = i->columns->h->data;
+ ic1->c->unique = c->unique = 2;
+ }
}
/* should we switch to oph_idx ? */
@@ -6427,10 +6437,14 @@ sql_trans_create_ic(sql_trans *tr, sql_i
ic->c = c;
list_append(i->columns, ic);
- if (hash_index(i->type) && list_length(i->columns) > 1) {
- /* Correct the unique flag of the keys first column */
- sql_kc *ic1 = i->columns->h->data;
- ic1->c->unique = c->unique = 2;
+ if (hash_index(i->type)) {
+ if (list_length(i->columns) == 1) {
+ c->unique = 1;
+ } else {
+ /* Correct unique flag of first key column */
+ sql_kc *ic1 = i->columns->h->data;
+ ic1->c->unique = c->unique = 2;
+ }
}
if ((res = store->table_api.table_insert(tr, sysic, &i->base.id,
&ic->c->base.name, &nr, ATOMnilptr(TYPE_int))))
diff --git a/sql/test/miscellaneous/Tests/simple_plans.test
b/sql/test/miscellaneous/Tests/simple_plans.test
--- a/sql/test/miscellaneous/Tests/simple_plans.test
+++ b/sql/test/miscellaneous/Tests/simple_plans.test
@@ -588,6 +588,50 @@ project (
) [ "x"."x", "x"."y" ]
statement ok
+create table testkeys (a int primary key, b int unique)
+
+statement ok rowcount 3
+insert into testkeys values (1,1),(2,2),(3,3)
+
+# The following joins can be converted into semijoins
+plan select y from (values (1),(2),(cast(3 as int))) y(y) inner join testkeys
on y.y = testkeys.a
+project (
+| semijoin (
+| | [ [ int "1", int "2", int "3" ] as "y"."y" ],
+| | table("sys"."testkeys") [ "testkeys"."a" NOT NULL UNIQUE HASHCOL ]
+| ) [ "y"."y" = "testkeys"."a" NOT NULL HASHCOL ]
+) [ "y"."y" ]
+
+plan select y from (values (1),(2),(cast(3 as int))) y(y) inner join testkeys
on y.y = testkeys.b
+project (
+| semijoin (
+| | [ [ int "1", int "2", int "3" ] as "y"."y" ],
+| | table("sys"."testkeys") [ "testkeys"."b" UNIQUE HASHCOL ]
+| ) [ "y"."y" = "testkeys"."b" HASHCOL ]
+) [ "y"."y" ]
+
+query T nosort
+plan select y from (values (1),(2),(cast(3 as int))) y(y) inner join testkeys
on y.y = testkeys.a or (y.y is null and testkeys.a is null)
+----
+project (
+| semijoin (
+| | [ [ int "1", int "2", int "3" ] as "y"."y" ],
+| | table("sys"."testkeys") [ "testkeys"."a" NOT NULL UNIQUE HASHCOL ]
+| ) [ "y"."y" = "testkeys"."a" NOT NULL HASHCOL ]
+) [ "y"."y" ]
+
+# Here the inner join cannot be converted to a semijoin
+query T nosort
+plan select y from (values (1),(2),(cast(3 as int))) y(y) inner join testkeys
on y.y = testkeys.b or (y.y is null and testkeys.b is null)
+----
+project (
+| join (
+| | [ [ int "1", int "2", int "3" ] as "y"."y" ],
+| | table("sys"."testkeys") [ "testkeys"."b" UNIQUE HASHCOL ]
+| ) [ "y"."y" * = "testkeys"."b" HASHCOL ]
+) [ "y"."y" ]
+
+statement ok
rollback
statement ok
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
