Changeset: 20183131a788 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=20183131a788
Modified Files:
sql/backends/monet5/rel_bin.c
sql/backends/monet5/sql_statement.c
sql/backends/monet5/sql_statement.h
sql/server/rel_graph.c
sql/server/rel_optimizer.c
Branch: graph0
Log Message:
CODEGEN: generate the instructions to retrieve a shortest path
diffs (truncated from 411 to 300 lines):
diff --git a/sql/backends/monet5/rel_bin.c b/sql/backends/monet5/rel_bin.c
--- a/sql/backends/monet5/rel_bin.c
+++ b/sql/backends/monet5/rel_bin.c
@@ -4809,7 +4809,7 @@ rel2bin_graph(backend *be, sql_rel* rel,
list *lst1 = NULL; // temporary list
int spfw_flags = 0; // spfw flags
stmt *query = NULL; // query parameters
- stmt *weights = NULL; // input columns to generate the weights
+ stmt *shortest_paths = NULL; // input columns to generate the weights &
the list of attributes for the paths
stmt *spfw = NULL; // shortest path operator
// avoid to deal with the virtual OIDs (VOID) type, they are just an
@@ -4817,8 +4817,7 @@ rel2bin_graph(backend *be, sql_rel* rel,
// for more extreme cases
#define void2oid(statement) stmt_gr8_void2oid(be, statement)
- // debugging
- printf("[rel2bin_graph] input: %s\n", dump_rel(sql, rel));
+// printf("[rel2bin_graph] input: %s\n", dump_rel(sql, rel)); // DEBUG ONLY
// first construct the depending relations
left = subrel_bin(be, rel->l, refs);
@@ -4908,30 +4907,51 @@ rel2bin_graph(backend *be, sql_rel* rel,
}
} while(0);
- // weights
+ // weights & paths
lst1 = sa_list(sql->sa);
- for(node *n = graph_ptr->spfw->h; n; n = n->next){
+ for(node* n = graph_ptr->spfw->h; n; n = n->next){
sql_exp* e = n->data;
- stmt *s = NULL;
-
- if(!exp_is_atom(e)){ // no need to generate a weight for a bfs
- s = exp_bin(be, e, edges, NULL, NULL, NULL, NULL, NULL);
- assert(s != NULL && "Weight expression is NULL");
- if(!s) return NULL;
+ stmt* s = NULL;
+ if(e->flag & GRAPH_EXPR_COST){
+ if(!exp_is_atom(e)){ // no need to generate a weight
for a bfs
+ s = exp_bin(be, e, edges, NULL, NULL, NULL,
NULL, NULL);
+ assert(s != NULL && "Weight expression is
NULL");
+ if(!s) return NULL;
+ } else {
+ s = stmt_none(be);
+ }
+ s->flag |= GRAPH_EXPR_COST;
+ } else if (e->flag & GRAPH_EXPR_SHORTEST_PATH){
+ list* arguments = e->l;
+ list* attributes = sa_list(sql->sa);
+
+ assert(e->type == e_aggr && "Expecting SYS.NEST");
+ for(node* m = arguments->h; m; m = m->next){
+ sql_exp* me = m->data;
+ stmt* ms = exp_bin(be, me, edges, NULL, NULL,
NULL, NULL, NULL);
+ if(!ms) return NULL; // error
+ list_append(attributes, ms);
+ }
+ assert(list_length(attributes) > 0);
+ s = stmt_list(be, attributes);
+ s->flag |= GRAPH_EXPR_SHORTEST_PATH;
+ } else {
+ assert(0 && "Invalid expression type");
+ return NULL;
}
-
+ assert(s != NULL);
list_append(lst1, s);
}
- weights = stmt_list(be, lst1); lst1 = NULL;
+ shortest_paths = stmt_list(be, lst1); lst1 = NULL;
// invoke the spfw operator
- spfw = stmt_gr8_spfw(be, query, edge_src, edge_dst, weights,
spfw_flags);
+ spfw = stmt_gr8_spfw(be, query, edge_src, edge_dst, shortest_paths,
spfw_flags);
// finally project back the result
lst1 = sa_list(sql->sa);
do { // restrict the scope
stmt *jl = NULL, *jr = NULL;
- int cost_index = 2;
+ int op_out_index = 2;
// start with the lhs
jl = stmt_result(be, spfw, 0);
@@ -4958,13 +4978,21 @@ rel2bin_graph(backend *be, sql_rel* rel,
}
}
- // append the computed costs
- for(node* n = graph_ptr->spfw->h; n; n = n->next){
+ // append the computed costs & paths
+ assert(list_length(graph_ptr->spfw) ==
list_length(shortest_paths->op4.lval));
+ for(node *n = graph_ptr->spfw->h, *m =
shortest_paths->op4.lval->h; n; n = n->next, m = m->next){
sql_exp* e = n->data;
- stmt* s = stmt_result(be, spfw, cost_index);
+ stmt* s = stmt_result(be, spfw, op_out_index);
stmt* c = stmt_alias(be, s, exp_relname(e),
exp_name(e));
+
+ // in case of a path to compute, we need to record the
associated attributes of the nested table
+ if(e->flag & GRAPH_EXPR_SHORTEST_PATH){
+ stmt* attributes = m->data;
+ s->op4.lval = attributes->op4.lval; //
stmt_result
+ }
+
list_append(lst1, c);
- cost_index++;
+ op_out_index++;
}
} while (0);
@@ -5102,7 +5130,7 @@ output_rel_bin(backend *be, sql_rel *rel
int sqltype = sql->type;
stmt *s = subrel_bin(be, rel, refs);
- printf("[output_rel_bin] %s\n", mal2str(be->mb, 0, be->mb->stop));
+// printf("[output_rel_bin] %s\n", mal2str(be->mb, 0, be->mb->stop));
if (sqltype == Q_SCHEMA)
sql->type = sqltype; /* reset */
diff --git a/sql/backends/monet5/sql_statement.c
b/sql/backends/monet5/sql_statement.c
--- a/sql/backends/monet5/sql_statement.c
+++ b/sql/backends/monet5/sql_statement.c
@@ -19,6 +19,8 @@
#include "mal_debugger.h"
#include "opt_prelude.h"
+#include "nested_table.h"
+
#include <stdio.h>
#include <string.h>
@@ -2875,8 +2877,8 @@ stmt *stmt_unnest(backend *be, stmt *nes
stmt* s = NULL;
q = newStmt(be->mb, "nestedtable", "unnest1");
- getArg(q, 0) = newTmpVariable(be->mb, TYPE_bat);
- q = pushReturn(be->mb, q, newTmpVariable(be->mb, TYPE_bat));
+ getArg(q, 0) = newTmpVariable(be->mb, newBatType(TYPE_oid));
+ q = pushReturn(be->mb, q, newTmpVariable(be->mb, newBatType(TYPE_oid)));
assert(nested_attribute != NULL && nested_attribute->nr > 0);
q = pushArgument(be->mb, q, nested_attribute->nr);
@@ -3523,8 +3525,17 @@ list *list_nested_attributes(stmt* st){
return list_nested_attributes(st->op2);
case st_convert:
return NULL;
+ case st_gr8_concat:
+ if(list_length(st->op4.lval)){
+ // assume all concatenated columns refer to the same
table expressions
+ return list_nested_attributes(st->op4.lval->h->data);
+ } else {
+ return NULL;
+ }
case st_join: // projection
return st->op4.lval;
+ case st_result: // rel2bin_graph records the attributes in the output
column
+ return st->op4.lval;
case st_temp:
return NULL;
case st_bat: // implies storage
@@ -3535,7 +3546,7 @@ list *list_nested_attributes(stmt* st){
case st_var: // implies storage
return NULL;
default:
-// assert(0 && "Statement type not handled");
+ assert(0 && "Statement type not handled");
fprintf(stderr, "[list_nested_attributes] Statement type not
handled: %d\n", st->type);
}
@@ -3715,7 +3726,7 @@ stmt_gr8_intersect_join_lists(backend *b
stmt *
-stmt_gr8_spfw(backend *be, stmt *query, stmt *edge_from, stmt *edge_to, stmt
*weights, int global_flags) {
+stmt_gr8_spfw(backend *be, stmt *query, stmt *edge_from, stmt *edge_to, stmt
*shortest_paths, int global_flags) {
InstrPtr q = NULL;
stmt *s = NULL;
int num_output_cols = 2; // number of output columns from the operator
@@ -3724,10 +3735,10 @@ stmt_gr8_spfw(backend *be, stmt *query,
// Validate the input parameters
assert(query->type == st_list && "Invalid parameter type");
assert(list_length(query->op4.lval) == 4 && "Expected 4 input
parameters: left & right candidate ids, left & right vertex ids");
- assert(weights->type == st_list && "Invalid parameter type");
+ assert(shortest_paths->type == st_list && "Invalid parameter type");
// prepare the query
- mnstr_printf(stream, "<spfw from='codegen'>\n");
+ mnstr_printf(stream, "<spfw author='codegen'>\n");
// is this a join?
if(global_flags & SPFW_JOIN){
@@ -3744,11 +3755,26 @@ stmt_gr8_spfw(backend *be, stmt *query,
q = newStmt(be->mb, "graph", "spfw");
if(q == NULL) return NULL; // error
// output values
- getArg(q, 0) = newTmpVariable(be->mb, TYPE_bat); // left candidate list
- q = pushReturn(be->mb, q, newTmpVariable(be->mb, TYPE_bat)); // right
candidate list
+ getArg(q, 0) = newTmpVariable(be->mb, newBatType(TYPE_oid)); // left
candidate list
+ q = pushReturn(be->mb, q, newTmpVariable(be->mb,
newBatType(TYPE_oid))); // right candidate list
// add the shortest paths
- for(node *n = weights->op4.lval->h; n; n = n->next){
- q = pushReturn(be->mb, q, newTmpVariable(be->mb, TYPE_bat));
+ for(node *n = shortest_paths->op4.lval->h; n; n = n->next){ // cost or
path
+ // find the type of the returned bat
+ stmt* s0 = n->data;
+ int ret_type = -1;
+ if(s0->flag & GRAPH_EXPR_COST){
+ if(s0->type == st_none){ // bfs
+ ret_type = TYPE_lng;
+ } else {
+ ret_type = tail_type(s0)->type->localtype;
+ }
+ } else if (s0->flag & GRAPH_EXPR_SHORTEST_PATH){
+ ret_type = TYPE_nested_table;
+ } else {
+ assert(0 && "Invalid expression");
+ }
+
+ q = pushReturn(be->mb, q, newTmpVariable(be->mb,
newBatType(ret_type)));
num_output_cols++;
}
@@ -3760,8 +3786,10 @@ stmt_gr8_spfw(backend *be, stmt *query,
}
EVIL_PUSH(edge_from);
EVIL_PUSH(edge_to);
- for(node *n = weights->op4.lval->h; n; n = n->next){ // weights
- EVIL_PUSH(n->data);
+ for(node *n = shortest_paths->op4.lval->h; n; n = n->next){ // weights
+ stmt* s = n->data;
+ if (!(s->flag & GRAPH_EXPR_COST)) continue;
+ EVIL_PUSH(s); // nil if we need a bfs
}
#undef EVIL_PUSH
@@ -3786,14 +3814,29 @@ stmt_gr8_spfw(backend *be, stmt *query,
do {
int ret_spfw = 2; // 0 = jl, 1 = jr
int arg_spfw = q->retc + 7;
+ node* n = shortest_paths->op4.lval->h;
mnstr_printf(stream, "\t<subexpr>\n");
- for(node *n = weights->op4.lval->h; n; n = n->next){
+ while(n){
+ stmt* stmt_weight = n->data;
+ bool compute_path = false;
+
+ assert(stmt_weight->flag & GRAPH_EXPR_COST);
+ n = n->next;
+ if(n && (((stmt*) n->data)->flag &
GRAPH_EXPR_SHORTEST_PATH)){
+ compute_path = true;
+ n = n->next;
+ }
+
mnstr_printf(stream, "\t\t<shortest_path>\n");
- mnstr_printf(stream, "\t\t\t<column name='output'
pos='%d' />\n", ret_spfw++);
- if(n->data) // weighted shortest path?
- mnstr_printf(stream, "\t\t\t<column
name='weights' pos='%d' />\n", arg_spfw);
+ mnstr_printf(stream, "\t\t\t<column name='out_cost'
pos='%d' />\n", ret_spfw++);
+ if(compute_path){ // retrieve the paths?
+ mnstr_printf(stream, "\t\t\t<column
name='out_path' pos='%d' />\n", ret_spfw++);
+ }
+ if(stmt_weight && stmt_weight->type != st_none) { //
weighted shortest path?
+ mnstr_printf(stream, "\t\t\t<column
name='in_weights' pos='%d' />\n", arg_spfw);
+ }
arg_spfw++; // increment anyway as we are pushing a
dummy argument as nil if this is BFS
mnstr_printf(stream, "\t\t</shortest_path>\n");
}
@@ -3801,7 +3844,6 @@ stmt_gr8_spfw(backend *be, stmt *query,
mnstr_printf(stream, "\t</subexpr>\n");
} while (0);
-
// save the query description
do {
char *spfw_argument_buffer = NULL;
@@ -3819,7 +3861,6 @@ stmt_gr8_spfw(backend *be, stmt *query,
record_ptr = defConstant(be->mb, TYPE_str, &record);
q->argv[q->retc] = record_ptr;
-
free(spfw_argument_buffer);
mnstr_destroy(stream); stream = NULL;
} while(0);
@@ -3831,7 +3872,7 @@ stmt_gr8_spfw(backend *be, stmt *query,
s->flag = global_flags;
s->op1 = query;
s->op2 = stmt_list(be, append(append(sa_list(be->mvc->sa), edge_from),
edge_to));
- s->op3 = weights;
+ s->op3 = shortest_paths;
// just required >= 1 to avoid projecting a column out of a constant
when looking
// for the shortest paths
s->nrcols = num_output_cols; /* = i*/
diff --git a/sql/backends/monet5/sql_statement.h
b/sql/backends/monet5/sql_statement.h
--- a/sql/backends/monet5/sql_statement.h
+++ b/sql/backends/monet5/sql_statement.h
@@ -248,7 +248,7 @@ extern stmt *stmt_gr8_concat(backend *be
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
