Changeset: 69a130fd3718 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=69a130fd3718
Modified Files:
sql/server/rel_exp.c
sql/server/rel_graph.c
sql/server/rel_graph.h
sql/server/rel_optimizer.c
sql/server/rel_rel.c
Branch: graph0
Log Message:
QRW: DCE pass for both SYS.NEST and paths
Unify the same logic to mark & remove the unused attributes in the DCE
pass for both the SYS.NEST aggregate and the graph shortest path
operator. There might still be a latent and occasional bug where the
list of attributes for a scalar function is not NULL even when the
type is not a nested table. Currently I am not able to reproduce it
anymore though :/
diffs (truncated from 338 to 300 lines):
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
@@ -214,6 +214,7 @@ exp_op( sql_allocator *sa, list *l, sql_
e->card = CARD_MULTI;
e->l = l;
e->f = f;
+ assert(exp_subtype(e) == NULL || exp_subtype(e)->attributes == NULL);
return e;
}
diff --git a/sql/server/rel_graph.c b/sql/server/rel_graph.c
--- a/sql/server/rel_graph.c
+++ b/sql/server/rel_graph.c
@@ -180,6 +180,49 @@ static list* bind_shortest_path_return(m
}
}
+// create the column needed to compute the spfw expr~
+static sql_exp* create_compute_path_expr(mvc *sql, sql_rel* rel_edges){
+ sql_schema* schema_sys = NULL;
+ sql_subtype* type_nested_table = NULL;
+ sql_subaggr* aggregate = NULL;
+ list* arguments = NULL; // the parameters of SYS.NEST (i.e. all columns
produced by rel_edges)
+ sql_exp* result = NULL; // the generated expression
+ list* nt_attributes = NULL; // the attributes associated to the nested
table type
+
+ assert(rel_edges != NULL);
+
+ schema_sys = mvc_bind_schema(sql, "sys");
+ assert(schema_sys != NULL && "Unable to find the schema 'sys'");
+ type_nested_table = sql_bind_subtype(sql->sa, "nested_table", 0, 0);
+ assert(type_nested_table != NULL && "Unable to find type
'nested_table'");
+
+ aggregate = sql_bind_aggr(sql->sa, schema_sys, "nest",
type_nested_table);
+ assert(aggregate != NULL && "Unable to bind the sys.nest aggregate");
+
+ arguments = rel_projections(sql, rel_edges, /*tname=*/ NULL, true, /*
intern = */ false);
+
+ // we use an aggregate expression to express the path to compute just
to have
+ // a similar DCE pass for nested tables. However codegen only looks for
the flag
+ // GRAPH_EXPR_SHORTEST_PATH.
+ // Not sure how the flags nil & no_nil can affect the generated
expression
+ result = exp_aggr(sql->sa, arguments, aggregate, /* distinct = */
FALSE, TRUE, CARD_MULTI, have_nil(arguments));
+ result->flag |= GRAPH_EXPR_SHORTEST_PATH;
+
+ // record the attributes for the nested table
+ type_nested_table = aggregate->res->h->data;
+ nt_attributes = sa_list(sql->sa);
+ for(node* n = arguments->h; n; n = n->next){
+ sql_exp* e = n->data;
+ list_append(nt_attributes, exp_column(sql->sa, exp_relname(e),
exp_name(e), exp_subtype(e), exp_card(e), has_nil(e), is_intern(e)));
+ }
+ type_nested_table->attributes = nt_attributes;
+
+ // finally provide a unique label
+ result = exp_label(sql->sa, result, ++sql->label);
+
+ return result;
+}
+
static list* bind_shortest_path_graph(mvc *sql, sql_graph *graph, dlist
*parse_tree, bool compute_path){
const char* table_ref = NULL; // the table referred (optional)
symbol* expr_weight = NULL; // the expression inside CHEAPEST SUM ( ...
);
@@ -274,21 +317,8 @@ static list* bind_shortest_path_graph(mv
// otherwise we need to create an hoc column & register
in the list graph->spfw
// to represent the path to compute
- if(!column_path) {
- const char* label = make_label(sql->sa,
++sql->label);
- sql_subtype* type = sql_bind_subtype(sql->sa,
"nested_table", 0, 0);
-
- assert(type != NULL && "Cannot find the
'nested_table' type");
- // record the columns composing the
nested_table type, from the edge table
- type->attributes = exps_copy(sql->sa,
rel_projections(sql, edges, NULL, /* settname = */ true, /* intern = */ false));
- // set the relation name to label
- for(node* n = type->attributes->h; n; n =
n->next){
- sql_exp* ne = n->data;
- ne->rname = label;
- }
-
- column_path = exp_column(sql->sa, label, label,
type, CARD_MULTI, /* has_nil = */ FALSE, /* is_intern = */ FALSE);
- column_path->flag |= GRAPH_EXPR_SHORTEST_PATH;
+ if(!column_path){
+ column_path = create_compute_path_expr(sql,
edges);
// record the column in the 'spfw' list
if(duplicate){
@@ -374,48 +404,3 @@ list* rel_graph_shortest_path(mvc *sql,
return result; // this can be an exp~ or NULL + an error set
}
}
-
-
-/*****************************************************************************
- * *
- * Bind an expression produced by a graph operator *
- * *
- *****************************************************************************/
-// Attempt to bind the column with table name `tbl_name' and column name
`col_name'
-// to one of the expression generated by the graph operator (i.e. a shortest
path).
-// It returns the expression bound if found, NULL otherwise.
-sql_exp* graph_bind_spfw(sql_rel* rel, const char* tbl_name, const char*
col_name){
- sql_graph* graph_ptr = NULL;
-
- assert(rel && is_graph(rel->op) && "The given operator is not a graph");
- graph_ptr = (sql_graph*) rel;
-
- // all expressions associated to a graph operator need to have a table
name
- if(!tbl_name) return NULL;
-
- for(node* n = graph_ptr->spfw->h; n; n = n->next){
- sql_exp* candidate = n->data;
-
- if(candidate->flag & GRAPH_EXPR_COST){
- if(strcmp(tbl_name, candidate->rname) == 0 &&
strcmp(col_name, candidate->name) == 0){
- return candidate;
- }
- } else if (candidate->flag & GRAPH_EXPR_SHORTEST_PATH){
- assert(candidate->type == e_column && "Paths should be
columns");
- if(strcmp(tbl_name, candidate->rname) == 0){
- assert(candidate->tpe.type->eclass ==
EC_NESTED_TABLE && "Expected a nested table (class)");
- assert(candidate->tpe.attributes != NULL &&
"Expected a nested table (attrs)");
- if(strcmp(col_name, candidate->name) == 0){ //
fetch the nested table
- return candidate;
- }
-
- candidate =
exps_bind_column(candidate->tpe.attributes, col_name, NULL);
- assert(candidate != NULL && "How was it able to
match the table name and not the column name?");
- return candidate;
- }
- }
- }
-
- // not found
- return NULL;
-}
diff --git a/sql/server/rel_graph.h b/sql/server/rel_graph.h
--- a/sql/server/rel_graph.h
+++ b/sql/server/rel_graph.h
@@ -19,6 +19,4 @@ sql_graph* rel_graph_create(sql_allocato
sql_graph* rel_graph_move(mvc* sql, sql_rel* graph_old, sql_rel* l, sql_rel*
r, sql_exp* e);
sql_rel* rel_graph_move2rel(mvc* sql, sql_rel* graph_old, sql_rel* l, sql_rel*
r, sql_exp* e);
-sql_exp* graph_bind_spfw(sql_rel* rel, const char* relname, const char*
colname);
-
#endif /* _REL_GRAPH_H_ */
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
@@ -6006,15 +6006,11 @@ exp_nested_table_mark_used(sql_exp* exp_
}
if(exp_down->type == e_aggr /*&& exp_nest->f ~ "sys.nest"*/){
- sql_subaggr* subaggr = NULL;
- sql_subtype* type = NULL;
+ sql_subtype* type = exp_subtype(exp_down);
exp_nest = exp_down;
- subaggr = exp_nest->f;
- assert(list_length(subaggr->res) == 1);
- type = subaggr->res->h->data;
- assert(type->attributes != NULL);
-
+
+ assert(type != NULL && type->attributes != NULL);
target_attributes = type->attributes;
} else {
assert(exp_down->type == e_column);
@@ -6398,21 +6394,22 @@ rel_mark_used(mvc *sql, sql_rel *rel, in
if(e->flag & GRAPH_EXPR_COST){
exp_mark_used(graph_ptr->edges, e);
} else if(e->flag & GRAPH_EXPR_SHORTEST_PATH){
- int nr = 0;
-
- assert(e->tpe.attributes != NULL && "Expected a
nested table as type");
- for(node* m = e->tpe.attributes->h; m; m =
m->next){
+ list* arguments = e->l;
+ bool shortest_path_used = false;
+
+ assert(e->type == e_aggr && "Expecting
SYS.NEST(...) as the function to create the path");
+ assert(list_length(arguments) >= 1 && "SYS.NEST
with no parameters. Is the edge table empty?");
+ for(node* m = arguments->h; m; m = m->next){
sql_exp* me = m->data;
- // since unnest is not a barrier in the
DCE analysis, we need to explicitly
+ // since the graph operators are not
barriers in the DCE analysis, we need to explicitly
// check whether the attribute has been
marked earlier
if(me->used){
- nr++;
- exp_mark_used(graph_ptr->edges,
e);
+ int mark =
exp_mark_used(graph_ptr->edges, me);
+ assert(mark > 0 && "All
arguments should be marked in the subrel");
+ shortest_path_used = true;
}
}
- if(nr == list_length(e->tpe.attributes)){
- e->used = 1;
- }
+ e->used = shortest_path_used;
} else {
assert(0 && "Invalid graph expression");
}
@@ -6438,6 +6435,42 @@ exps_remove_unused(mvc* sql, list* exps)
return new_exps;
}
+// DCE for the nested tables
+// It alters the flags e->used, the actual subtype && the params in case of
SYS.NEST
+static void
+exp_nested_table_remove_unused(mvc* sql, sql_exp* e){
+ sql_subtype* type;
+ list** nt_attributes_ptr = NULL;
+ list* new_nt_attributes = NULL;
+
+ // if the expression is not used, it is going to be removed all
together by the rest of the DCE
+ if(!e->used) return;
+
+ type = exp_subtype(e);
+ if(!type) return; // uh? thsi expression doesn't have a type..
+
+ nt_attributes_ptr = &(type->attributes);
+ if(!(nt_attributes_ptr && *nt_attributes_ptr)) return; // this is not a
nested table
+
+ // alter the attributes in the subtype
+ new_nt_attributes = exps_remove_unused(sql, *nt_attributes_ptr);
+ *nt_attributes_ptr = new_nt_attributes;
+ if(!list_length(new_nt_attributes)){
+ e->used = 0; // it removed all the sub-attributes in the column
+ return; // this expression needs to be completely removed by
the DCE
+ }
+
+ // alter the parameters for SYS.NEST
+ if(e->type == e_aggr /* => rel->op == op_groupby*/){ // SYS.NEST(...)
+ list* new_nt_arguments = NULL;
+
+ assert(list_length(e->l) >= 1);
+
+ new_nt_arguments = exps_remove_unused(sql, e->l);
+ e->l = new_nt_arguments;
+ }
+}
+
static sql_rel *
rel_remove_unused(mvc *sql, sql_rel *rel)
@@ -6534,35 +6567,7 @@ rel_remove_unused(mvc *sql, sql_rel *rel
for(n=rel->exps->h; n; n = n->next) {
sql_exp *e = n->data;
- // DCE for nested tables
- if (e->used) {
- list** nt_attributes_ptr = NULL;
- list** nt_arguments_ptr = NULL; // in
case of sys.nest
-
- if(rel->op == op_project){ // do not
use is_project(rel->op) as it also includes the group by (subtle bug)
- nt_attributes_ptr =
&(e->tpe.attributes);
- } else if (rel->op == op_groupby &&
e->f){ // sys.nest ( ... )
- sql_subaggr* aggr = e->f;
- if(list_length(aggr->res) == 1){
- sql_subtype* type =
aggr->res->h->data;
- nt_attributes_ptr =
&(type->attributes);
- nt_arguments_ptr =
(list**) &(e->l);
-
- }
- }
- if(nt_attributes_ptr &&
*nt_attributes_ptr) {
- list* new_nt_attributes =
exps_remove_unused(sql, *nt_attributes_ptr);
- *nt_attributes_ptr =
new_nt_attributes;
-
if(!list_length(new_nt_attributes)){
- e->used = 0; // it
removed all the sub-attributes in the column
- }
- }
-
- if(e->used && nt_arguments_ptr){
- list* new_nt_arguments =
exps_remove_unused(sql, *nt_arguments_ptr);
- *nt_arguments_ptr =
new_nt_arguments;
- }
- }
+ exp_nested_table_remove_unused(sql, e);
if(e->used){ // nt analysis might have changed
this flag
append(exps, e);
@@ -6628,8 +6633,13 @@ rel_remove_unused(mvc *sql, sql_rel *rel
for(node* n = graph_ptr->spfw->h; n && !needed; n = n->next){
sql_exp* e = n->data;
needed = !(e->used);
+
+ // nested tables
if (!needed && (e->flag & GRAPH_EXPR_SHORTEST_PATH)){
- for (node *m = e->tpe.attributes->h; m &&
!needed; m = m->next){
+ sql_subtype* t = exp_subtype(e);
+ assert(t != NULL && t->attributes != NULL);
+
+ for (node *m = t->attributes->h; m && !needed;
m = m->next){
sql_exp* me = m->data;
if(!me->used){
needed = 1;
@@ -6642,23 +6652,10 @@ rel_remove_unused(mvc *sql, sql_rel *rel
list* exps = sa_list(sql->sa);
for(node* n = graph_ptr->spfw->h; n; n = n->next){
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
