You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@age.apache.org by jg...@apache.org on 2022/03/15 23:57:09 UTC
[incubator-age] branch master updated: Add VLE performance enhancements
This is an automated email from the ASF dual-hosted git repository.
jgemignani pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-age.git
The following commit(s) were added to refs/heads/master by this push:
new 3a6e247 Add VLE performance enhancements
3a6e247 is described below
commit 3a6e24752fe029d659018110ae9cda5d9ffdc2e5
Author: John Gemignani <jr...@gmail.com>
AuthorDate: Thu Mar 10 14:14:36 2022 -0800
Add VLE performance enhancements
Added to the VLE code a local context LRU cache to improve
performance.
The following command demonstrates an issue with the VLE and
SRFs -
MATCH (u)-[*]-() RETURN COUNT(1);
This command will repeatedly call the VLE SRF with different
starting vertices until all vertices matching u are exhausted.
However, the issue is, each of these vertices will initiate a
new SRF call - not a continuation of the same SRF. These new
calls have to rebuild all of the local structures for the same
VLE grammar node. This ends up taking a lot of time and resources.
To resolve this a simple LRU based cache was added for these local
VLE contexts and keyed on the grammar node id. This id was added so
that each VLE grammar node would be unique and therefore, reusable
for repeated calls using the same grammar node.
Added split edge lists for the edges stored for each vertex. This
comprises 3 edge lists to improve performance for directional cases.
Originally, all edges entering and exiting a vertex were stored in
the 'edges' list. Now the edges are stored in edges_in, edges_out,
and edges_self. This allows directed searchs to avoid checking edges
that don't meet the direction criteria.
Added new logic for matching an edge in function is_an_edge_match.
It now uses agtype_deep_contains for comparisons.
Added the cypher function age_vertex_stats which will return vertex
statistics. This function is helpful for debugging graphs.
Added a grammar rule to allow functions to be used as the parent of
an indirection. As in the following example -
MATCH (u) WHERE vertex_stats(u).in_degree > 10 RETURN vertex_stats(u);
Additionally, a few small memory leaks were fixed.
Added regression tests.
All previous regression tests passed.
---
age--1.0.0.sql | 20 +
regress/expected/cypher_vle.out | 2 +-
regress/expected/expr.out | 49 +-
regress/sql/expr.sql | 12 +
src/backend/parser/cypher_expr.c | 7 +-
src/backend/parser/cypher_gram.y | 45 +-
src/backend/utils/adt/age_global_graph.c | 95 ++--
src/backend/utils/adt/age_graphid_ds.c | 12 +
src/backend/utils/adt/age_vle.c | 759 ++++++++++++++++++++-----------
src/include/utils/age_global_graph.h | 4 +-
src/include/utils/age_graphid_ds.h | 4 +
11 files changed, 703 insertions(+), 306 deletions(-)
diff --git a/age--1.0.0.sql b/age--1.0.0.sql
index a5212e0..10b3dea 100644
--- a/age--1.0.0.sql
+++ b/age--1.0.0.sql
@@ -3796,6 +3796,7 @@ STABLE
PARALLEL SAFE
AS 'MODULE_PATHNAME';
+-- original VLE function definition
CREATE FUNCTION ag_catalog.age_vle(IN agtype, IN agtype, IN agtype, IN agtype,
IN agtype, IN agtype, IN agtype,
OUT edges agtype)
@@ -3806,6 +3807,18 @@ CALLED ON NULL INPUT
PARALLEL UNSAFE -- might be safe
AS 'MODULE_PATHNAME';
+-- This is an overloaded function definition to allow for the VLE local context
+-- caching mechanism to coexist with the previous VLE version.
+CREATE FUNCTION ag_catalog.age_vle(IN agtype, IN agtype, IN agtype, IN agtype,
+ IN agtype, IN agtype, IN agtype, IN agtype,
+ OUT edges agtype)
+RETURNS SETOF agtype
+LANGUAGE C
+STABLE
+CALLED ON NULL INPUT
+PARALLEL UNSAFE -- might be safe
+AS 'MODULE_PATHNAME';
+
-- function to build an edge for a VLE match
CREATE FUNCTION ag_catalog.age_build_vle_match_edge(agtype, agtype)
RETURNS agtype
@@ -3904,6 +3917,13 @@ CREATE FUNCTION ag_catalog.age_unnest(agtype, block_types boolean = false)
PARALLEL SAFE
AS 'MODULE_PATHNAME';
+CREATE FUNCTION ag_catalog.age_vertex_stats(agtype, agtype)
+RETURNS agtype
+LANGUAGE c
+STABLE
+PARALLEL SAFE
+AS 'MODULE_PATHNAME';
+
--
-- End
--
diff --git a/regress/expected/cypher_vle.out b/regress/expected/cypher_vle.out
index 438b3e9..f461ee4 100644
--- a/regress/expected/cypher_vle.out
+++ b/regress/expected/cypher_vle.out
@@ -318,10 +318,10 @@ SELECT * FROM cypher('cypher_vle', $$MATCH p=(u:begin)-[*3..3]->(v:end) RETURN p
SELECT * FROM cypher('cypher_vle', $$MATCH p=(u:begin)-[*3..3]-(v:end) RETURN p $$) AS (e agtype);
[...]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ [...]
- [{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2533274790395905, "label": "bypass_edge", "end_id": 1688849860263937, "start_id": 1407374883553282, "p [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685253, "label": "alternate_edge", "end_id": 1407374883553282, "start_id": 1407374883553283, [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685253, "label": "alternate_edge", "end_id": 1407374883553282, "start_id": 1407374883553283, [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685253, "label": "alternate_edge", "end_id": 1407374883553282, "start_id": 1407374883553283, [...]
+ [{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2533274790395905, "label": "bypass_edge", "end_id": 1688849860263937, "start_id": 1407374883553282, "p [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685250, "label": "alternate_edge", "end_id": 1407374883553283, "start_id": 1407374883553282, [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685250, "label": "alternate_edge", "end_id": 1407374883553283, "start_id": 1407374883553282, [...]
[{"id": 844424930131969, "label": "begin", "properties": {}}::vertex, {"id": 2533274790395906, "label": "bypass_edge", "end_id": 844424930131969, "start_id": 1407374883553282, "properties": {"name": "bypass edge", "number": 2, "packages": [1, 3, 5, 7], "dangerous": {"type": "poisons", "level": "all"}}}::edge, {"id": 1407374883553282, "label": "middle", "properties": {}}::vertex, {"id": 2251799813685250, "label": "alternate_edge", "end_id": 1407374883553283, "start_id": 1407374883553282, [...]
diff --git a/regress/expected/expr.out b/regress/expected/expr.out
index f0b2626..aac5b29 100644
--- a/regress/expected/expr.out
+++ b/regress/expected/expr.out
@@ -5555,6 +5555,46 @@ SELECT * FROM cypher('VLE', $$MATCH (u)-[*..5]-(v) RETURN u, v$$) AS (u agtype,
---+---
(0 rows)
+-- Create a graph to test
+SELECT * FROM cypher('VLE', $$CREATE (b:begin)-[:edge {name: 'main edge', number: 1, dangerous: {type: "all", level: "all"}}]->(u1:middle)-[:edge {name: 'main edge', number: 2, dangerous: {type: "all", level: "all"}, packages: [2,4,6]}]->(u2:middle)-[:edge {name: 'main edge', number: 3, dangerous: {type: "all", level: "all"}}]->(u3:middle)-[:edge {name: 'main edge', number: 4, dangerous: {type: "all", level: "all"}}]->(e:end), (u1)-[:self_loop {name: 'self loop', number: 1, dangerous: {t [...]
+ b | e
+---------------------------------------------------------------------+--------------------------------------------------------------------
+ {"id": 844424930131969, "label": "begin", "properties": {}}::vertex | {"id": 1688849860263937, "label": "end", "properties": {}}::vertex
+(1 row)
+
+-- test vertex_stats command
+SELECT * FROM cypher('VLE', $$ MATCH (u) RETURN vertex_stats(u) $$) AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------------
+ {"id": 844424930131969, "label": "begin", "in_degree": 1, "out_degree": 2, "self_loops": 0}
+ {"id": 1407374883553281, "label": "middle", "in_degree": 3, "out_degree": 2, "self_loops": 1}
+ {"id": 1407374883553282, "label": "middle", "in_degree": 2, "out_degree": 4, "self_loops": 0}
+ {"id": 1407374883553283, "label": "middle", "in_degree": 3, "out_degree": 3, "self_loops": 0}
+ {"id": 1688849860263937, "label": "end", "in_degree": 4, "out_degree": 2, "self_loops": 1}
+(5 rows)
+
+-- test indirection operator for a function
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).self_loops <> 0 RETURN vertex_stats(u) $$) AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------------
+ {"id": 1407374883553281, "label": "middle", "in_degree": 3, "out_degree": 2, "self_loops": 1}
+ {"id": 1688849860263937, "label": "end", "in_degree": 4, "out_degree": 2, "self_loops": 1}
+(2 rows)
+
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).in_degree < vertex_stats(u).out_degree RETURN vertex_stats(u) $$) AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------------
+ {"id": 844424930131969, "label": "begin", "in_degree": 1, "out_degree": 2, "self_loops": 0}
+ {"id": 1407374883553282, "label": "middle", "in_degree": 2, "out_degree": 4, "self_loops": 0}
+(2 rows)
+
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).out_degree < vertex_stats(u).in_degree RETURN vertex_stats(u) $$) AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------------
+ {"id": 1407374883553281, "label": "middle", "in_degree": 3, "out_degree": 2, "self_loops": 1}
+ {"id": 1688849860263937, "label": "end", "in_degree": 4, "out_degree": 2, "self_loops": 1}
+(2 rows)
+
-- list functions relationships(), range(), keys()
SELECT create_graph('keys');
NOTICE: graph "keys" has been created
@@ -5854,9 +5894,16 @@ ERROR: labels() argument must be a vertex
-- Cleanup
--
SELECT * FROM drop_graph('VLE', true);
-NOTICE: drop cascades to 2 other objects
+NOTICE: drop cascades to 9 other objects
DETAIL: drop cascades to table "VLE"._ag_label_vertex
drop cascades to table "VLE"._ag_label_edge
+drop cascades to table "VLE".begin
+drop cascades to table "VLE".edge
+drop cascades to table "VLE".middle
+drop cascades to table "VLE"."end"
+drop cascades to table "VLE".self_loop
+drop cascades to table "VLE".alternate_edge
+drop cascades to table "VLE".bypass_edge
NOTICE: graph "VLE" has been dropped
drop_graph
------------
diff --git a/regress/sql/expr.sql b/regress/sql/expr.sql
index 0c5458e..45a95d4 100644
--- a/regress/sql/expr.sql
+++ b/regress/sql/expr.sql
@@ -2284,6 +2284,18 @@ SELECT * FROM cypher('VLE', $$MATCH (u)-[*0..1]-(v) RETURN u, v$$) AS (u agtype,
SELECT * FROM cypher('VLE', $$MATCH (u)-[*..1]-(v) RETURN u, v$$) AS (u agtype, v agtype);
SELECT * FROM cypher('VLE', $$MATCH (u)-[*..5]-(v) RETURN u, v$$) AS (u agtype, v agtype);
+-- Create a graph to test
+SELECT * FROM cypher('VLE', $$CREATE (b:begin)-[:edge {name: 'main edge', number: 1, dangerous: {type: "all", level: "all"}}]->(u1:middle)-[:edge {name: 'main edge', number: 2, dangerous: {type: "all", level: "all"}, packages: [2,4,6]}]->(u2:middle)-[:edge {name: 'main edge', number: 3, dangerous: {type: "all", level: "all"}}]->(u3:middle)-[:edge {name: 'main edge', number: 4, dangerous: {type: "all", level: "all"}}]->(e:end), (u1)-[:self_loop {name: 'self loop', number: 1, dangerous: {t [...]
+
+-- test vertex_stats command
+SELECT * FROM cypher('VLE', $$ MATCH (u) RETURN vertex_stats(u) $$) AS (result agtype);
+
+-- test indirection operator for a function
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).self_loops <> 0 RETURN vertex_stats(u) $$) AS (result agtype);
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).in_degree < vertex_stats(u).out_degree RETURN vertex_stats(u) $$) AS (result agtype);
+SELECT * FROM cypher('VLE', $$ MATCH (u) WHERE vertex_stats(u).out_degree < vertex_stats(u).in_degree RETURN vertex_stats(u) $$) AS (result agtype);
+
+
-- list functions relationships(), range(), keys()
SELECT create_graph('keys');
-- keys()
diff --git a/src/backend/parser/cypher_expr.c b/src/backend/parser/cypher_expr.c
index a7e17d4..81c9b64 100644
--- a/src/backend/parser/cypher_expr.c
+++ b/src/backend/parser/cypher_expr.c
@@ -934,9 +934,10 @@ static Node *transform_FuncCall(cypher_parsestate *cpstate, FuncCall *fn)
* is not empty. Then prepend the graph name if necessary.
*/
if ((list_length(targs) != 0) &&
- ((pg_strcasecmp("startNode", name) == 0 ||
- pg_strcasecmp("endNode", name) == 0 ||
- pg_strcasecmp("vle", name) == 0)))
+ (strcmp("startNode", name) == 0 ||
+ strcmp("endNode", name) == 0 ||
+ strcmp("vle", name) == 0 ||
+ strcmp("vertex_stats", name) == 0))
{
char *graph_name = cpstate->graph_name;
Datum d = string_to_agtype(graph_name);
diff --git a/src/backend/parser/cypher_gram.y b/src/backend/parser/cypher_gram.y
index b5ec362..fd4c21e 100644
--- a/src/backend/parser/cypher_gram.y
+++ b/src/backend/parser/cypher_gram.y
@@ -181,6 +181,7 @@
// unique name generation
#define UNIQUE_NAME_NULL_PREFIX "_unique_null_prefix"
static char *create_unique_name(char *prefix_name);
+static unsigned long get_a_unique_number(void);
// logical operators
static Node *make_or_expr(Node *lexpr, Node *rexpr, int location);
@@ -1007,8 +1008,12 @@ simple_path:
cypher_node *cnr = NULL;
Node *node = NULL;
int length = 0;
+ unsigned long unique_number = 0;
int location = 0;
+ /* get a unique number to identify this VLE node */
+ unique_number = get_a_unique_number();
+
/* get the location */
location = cr->location;
@@ -1138,6 +1143,9 @@ simple_path:
/* add in the direction as Const */
args = lappend(args, make_int_const(cr->dir, @2));
+ /* add in the unique number used to identify this VLE node */
+ args = lappend(args, make_int_const(unique_number, -1));
+
/* build the VLE function node */
cr->varlen = make_function_expr(list_make1(makeString("vle")),
args, @2);
@@ -1475,6 +1483,22 @@ expr:
errmsg("function already qualified"),
ag_scanner_errposition(@1, scanner)));
}
+ /* allow a function to be used as a parent of an indirection */
+ else if (IsA($1, FuncCall) && IsA($3, ColumnRef))
+ {
+ ColumnRef *cr = (ColumnRef*)$3;
+ List *fields = cr->fields;
+ Value *string = linitial(fields);
+
+ $$ = append_indirection($1, (Node*)string);
+ }
+ else if (IsA($1, FuncCall) && IsA($3, A_Indirection))
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("not supported A_Indirection indirection"),
+ ag_scanner_errposition(@1, scanner)));
+ }
/*
* All other types of expression indirections are currently not
* supported
@@ -2134,9 +2158,10 @@ static char *create_unique_name(char *prefix_name)
char *name = NULL;
char *prefix = NULL;
uint nlen = 0;
+ unsigned long unique_number = 0;
- /* STATIC VARIABLE unique_counter for name uniqueness */
- static unsigned long unique_counter = 0;
+ /* get a unique number */
+ unique_number = get_a_unique_number();
/* was a valid prefix supplied */
if (prefix_name == NULL || strlen(prefix_name) <= 0)
@@ -2150,13 +2175,13 @@ static char *create_unique_name(char *prefix_name)
}
/* get the length of the combinded string */
- nlen = snprintf(NULL, 0, "%s_%lu", prefix, unique_counter);
+ nlen = snprintf(NULL, 0, "%s_%lu", prefix, unique_number);
/* allocate the space */
name = palloc0(nlen + 1);
/* create the name */
- snprintf(name, nlen + 1, "%s_%lu", prefix, unique_counter);
+ snprintf(name, nlen + 1, "%s_%lu", prefix, unique_number);
/* if we created the prefix, we need to free it */
if (prefix_name == NULL || strlen(prefix_name) <= 0)
@@ -2164,8 +2189,14 @@ static char *create_unique_name(char *prefix_name)
pfree(prefix);
}
- /* increment the counter */
- unique_counter++;
-
return name;
}
+
+/* function to return a unique unsigned long number */
+static unsigned long get_a_unique_number(void)
+{
+ /* STATIC VARIABLE unique_counter for number uniqueness */
+ static unsigned long unique_counter = 0;
+
+ return unique_counter++;
+}
diff --git a/src/backend/utils/adt/age_global_graph.c b/src/backend/utils/adt/age_global_graph.c
index 18797ed..ca6a9ec 100644
--- a/src/backend/utils/adt/age_global_graph.c
+++ b/src/backend/utils/adt/age_global_graph.c
@@ -40,12 +40,14 @@
#define EDGE_HTAB_INITIAL_SIZE 1000000
/* internal data structures implementation */
+
/* vertex entry for the vertex_hastable */
typedef struct vertex_entry
{
graphid vertex_id; /* vertex id, it is also the hash key */
- ListGraphId *edges; /* A list of all (entering & exiting) edges'
- * graphids (int64s). */
+ ListGraphId *edges_in; /* List of entering edges graphids (int64) */
+ ListGraphId *edges_out; /* List of exiting edges graphids (int64) */
+ ListGraphId *edges_self; /* List of selfloop edges graphids (int64) */
Oid vertex_label_table_oid; /* the label table oid */
Datum vertex_properties; /* datum property value */
} vertex_entry;
@@ -95,7 +97,8 @@ static List *get_ag_labels_names(Snapshot snapshot, Oid graph_oid,
static bool insert_edge(GRAPH_global_context *ggctx, graphid edge_id,
Datum edge_properties, graphid start_vertex_id,
graphid end_vertex_id, Oid edge_label_table_oid);
-static bool insert_vertex_edge(GRAPH_global_context *ggctx, graphid vertex_id,
+static bool insert_vertex_edge(GRAPH_global_context *ggctx,
+ graphid start_vertex_id, graphid end_vertex_id,
graphid edge_id);
static bool insert_vertex_entry(GRAPH_global_context *ggctx, graphid vertex_id,
Oid vertex_label_table_oid,
@@ -279,7 +282,9 @@ static bool insert_vertex_entry(GRAPH_global_context *ggctx, graphid vertex_id,
/* set the datum vertex properties */
ve->vertex_properties = vertex_properties;
/* set the NIL edge list */
- ve->edges = NULL;
+ ve->edges_in = NULL;
+ ve->edges_out = NULL;
+ ve->edges_self = NULL;
/* we also need to store the vertex id for clean up of vertex lists */
ggctx->vertices = append_graphid(ggctx->vertices, vertex_id);
@@ -294,22 +299,53 @@ static bool insert_vertex_entry(GRAPH_global_context *ggctx, graphid vertex_id,
* Helper function to append one edge to an existing vertex in the current
* global vertex hashtable.
*/
-static bool insert_vertex_edge(GRAPH_global_context *ggctx, graphid vertex_id,
+static bool insert_vertex_edge(GRAPH_global_context *ggctx,
+ graphid start_vertex_id, graphid end_vertex_id,
graphid edge_id)
{
vertex_entry *value = NULL;
bool found = false;
+ bool is_selfloop = false;
- /* search for the vertex */
+ /* is it a self loop */
+ is_selfloop = (start_vertex_id == end_vertex_id);
+
+ /* search for the start vertex of the edge */
value = (vertex_entry *)hash_search(ggctx->vertex_hashtable,
- (void *)&vertex_id, HASH_FIND, &found);
+ (void *)&start_vertex_id, HASH_FIND,
+ &found);
/* vertices were preloaded so it must be there */
Assert(found);
+ if (!found)
+ {
+ return found;
+ }
+
+ /* if it is a self loop, add the edge to edges_self and we're done */
+ if (is_selfloop)
+ {
+ value->edges_self = append_graphid(value->edges_self, edge_id);
+ return found;
+ }
- /* add the edge to the edge list */
- value->edges = append_graphid(value->edges, edge_id);
+ /* add the edge to the edges_out list of the start vertex */
+ value->edges_out = append_graphid(value->edges_out, edge_id);
- return true;
+ /* search for the end vertex of the edge */
+ value = (vertex_entry *)hash_search(ggctx->vertex_hashtable,
+ (void *)&end_vertex_id, HASH_FIND,
+ &found);
+ /* vertices were preloaded so it must be there */
+ Assert(found);
+ if (!found)
+ {
+ return found;
+ }
+
+ /* add the edge to the edges_in list of the end vertex */
+ value->edges_in = append_graphid(value->edges_in, edge_id);
+
+ return found;
}
/* helper routine to load all vertices into the GRAPH global vertex hashtable */
@@ -494,30 +530,14 @@ static void load_edge_hashtable(GRAPH_global_context *ggctx)
elog(ERROR, "insert_edge: failed to insert");
}
- /* insert the edge into this vertex's edge list */
+ /* insert the edge into the start and end vertices edge lists */
inserted = insert_vertex_edge(ggctx, edge_vertex_start_id,
- edge_id);
+ edge_vertex_end_id, edge_id);
/* this insert must not fail */
if (!inserted)
{
elog(ERROR, "insert_vertex_edge: failed to insert");
}
-
- /*
- * Insert the edge into this vertex's edge list. UNLESS this is a
- * self loop (start == end vertex) because that would be adding it
- * twice.
- */
- if (edge_vertex_start_id != edge_vertex_end_id)
- {
- inserted = insert_vertex_edge(ggctx, edge_vertex_end_id,
- edge_id);
- /* this insert much not fail */
- if (!inserted)
- {
- elog(ERROR, "insert_vertex_edge: failed to insert");
- }
- }
}
/* end the scan and close the relation */
@@ -577,7 +597,9 @@ static void free_specific_GRAPH_global_context(GRAPH_global_context *ggctx)
Assert(found);
/* free the edge list associated with this vertex */
- free_ListGraphId(value->edges);
+ free_ListGraphId(value->edges_in);
+ free_ListGraphId(value->edges_out);
+ free_ListGraphId(value->edges_self);
/* move to the next vertex */
curr_vertex = next_vertex;
@@ -780,11 +802,22 @@ graphid get_vertex_entry_id(vertex_entry *ve)
return ve->vertex_id;
}
-ListGraphId *get_vertex_entry_edges(vertex_entry *ve)
+ListGraphId *get_vertex_entry_edges_in(vertex_entry *ve)
{
- return ve->edges;
+ return ve->edges_in;
}
+ListGraphId *get_vertex_entry_edges_out(vertex_entry *ve)
+{
+ return ve->edges_out;
+}
+
+ListGraphId *get_vertex_entry_edges_self(vertex_entry *ve)
+{
+ return ve->edges_self;
+}
+
+
Oid get_vertex_entry_label_table_oid(vertex_entry *ve)
{
return ve->vertex_label_table_oid;
diff --git a/src/backend/utils/adt/age_graphid_ds.c b/src/backend/utils/adt/age_graphid_ds.c
index 5cdcda3..dabf7f9 100644
--- a/src/backend/utils/adt/age_graphid_ds.c
+++ b/src/backend/utils/adt/age_graphid_ds.c
@@ -75,6 +75,18 @@ GraphIdNode *peek_stack_tail(ListGraphId *stack)
return stack->tail;
}
+/* return a reference to the head entry of a list */
+GraphIdNode *get_list_head(ListGraphId *list)
+{
+ return list->head;
+}
+
+/* get the size of the passed list */
+int64 get_list_size(ListGraphId *list)
+{
+ return list->size;
+}
+
/*
* Helper function to add a graphid to the end of a ListGraphId container.
* If the container is NULL, it creates the container with the entry.
diff --git a/src/backend/utils/adt/age_vle.c b/src/backend/utils/adt/age_vle.c
index 611c2e6..a676d09 100644
--- a/src/backend/utils/adt/age_vle.c
+++ b/src/backend/utils/adt/age_vle.c
@@ -36,6 +36,7 @@
#define EDGE_STATE_HTAB_INITIAL_SIZE 100000
#define EXISTS_HTAB_NAME "known edges"
#define EXISTS_HTAB_NAME_INITIAL_SIZE 1000
+#define MAXIMUM_NUMBER_OF_CACHED_LOCAL_CONTEXTS 5
/* edge state entry for the edge_state_hashtable */
typedef struct edge_state_entry
@@ -70,7 +71,7 @@ typedef struct VLE_local_context
graphid vsid; /* starting vertex id */
graphid veid; /* ending vertex id */
char *edge_label_name; /* edge label name for match */
- agtype_value *edge_conditions; /* edge property conditions for match */
+ agtype *edge_property_constraint; /* edge property constraint as agtype */
int64 lidx; /* lower (start) bound index */
int64 uidx; /* upper (end) bound index */
bool uidx_infinite; /* flag if the upper bound is omitted */
@@ -81,6 +82,10 @@ typedef struct VLE_local_context
ListGraphId *dfs_path_stack; /* dfs stack containing the path */
VLE_path_function path_function; /* which path function to use */
GraphIdNode *next_vertex; /* for VLE_FUNCTION_PATHS_TO */
+ int64 vle_grammar_node_id; /* the unique VLE grammar assigned node id */
+ bool use_cache; /* are we using VLE_local_context cache */
+ struct VLE_local_context *next; /* the next chained VLE_local_context */
+ bool is_dirty; /* is this VLE context reusable */
} VLE_local_context;
/*
@@ -100,14 +105,15 @@ typedef struct VLE_path_container
} VLE_path_container;
/* declarations */
+
+/* global variable to hold the per process global cached VLE_local contexts */
+static VLE_local_context *global_vle_local_contexts = NULL;
+
/* agtype functions */
-static agtype_iterator *get_next_object_pair(agtype_iterator *it,
- agtype_container *agtc,
- agtype_value *key,
- agtype_value *value);
static bool is_an_edge_match(VLE_local_context *vlelctx, edge_entry *ee);
/* VLE local context functions */
-static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo);
+static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo,
+ FuncCallContext *funcctx);
static void create_VLE_local_state_hashtable(VLE_local_context *vlelctx);
static void free_VLE_local_context(VLE_local_context *vlelctx);
/* VLE graph traversal functions */
@@ -128,8 +134,116 @@ static VLE_path_container *build_VLE_path_container(VLE_local_context *vlelctx);
static VLE_path_container *build_VLE_zero_container(VLE_local_context *vlelctx);
static agtype_value *build_path(VLE_path_container *vpc);
static agtype_value *build_edge_list(VLE_path_container *vpc);
+/* VLE_local_context cache management */
+static VLE_local_context *get_cached_VLE_local_context(int64 vle_node_id);
+static void cache_VLE_local_context(VLE_local_context *vlelctx);
/* definitions */
+
+/*
+ * Helper function to retrieve a cached VLE local context. It will also purge
+ * off any contexts beyond the maximum defined number of cached contexts. It
+ * will promote (a very basic LRU) the recently fetched context to the head of
+ * the list. If a context doesn't exist or is dirty, it will purge it off and
+ * return NULL.
+ */
+static VLE_local_context *get_cached_VLE_local_context(int64 vle_grammar_node_id)
+{
+ VLE_local_context *vlelctx = global_vle_local_contexts;
+ VLE_local_context *prev = global_vle_local_contexts;
+ VLE_local_context *next = NULL;
+ int cache_size = 0;
+
+ /* while we have contexts to check */
+ while (vlelctx != NULL)
+ {
+ /* purge any contexts past the maximum cache size */
+ if (cache_size > MAXIMUM_NUMBER_OF_CACHED_LOCAL_CONTEXTS)
+ {
+ /* set the next pointer to the context that follows */
+ next = vlelctx->next;
+
+ /* clear (unlink) the previous context's next pointer, if needed */
+ if (prev != NULL)
+ {
+ prev->next = NULL;
+ }
+
+ /* free the context */
+ free_VLE_local_context(vlelctx);
+
+ /* set to the next one */
+ vlelctx = next;
+
+ /* if there is another context beyond the max, we will re-enter */
+ continue;
+ }
+
+ /* if this context belongs to this grammar node */
+ if (vlelctx->vle_grammar_node_id == vle_grammar_node_id)
+ {
+ /* and isn't dirty */
+ if (vlelctx->is_dirty == false)
+ {
+ /* if the context isn't the head of the list, promote it */
+ if (vlelctx != prev)
+ {
+ /* adjust the links to cut out the node */
+ prev->next = vlelctx->next;
+ /* point the context to the old head of the list */
+ vlelctx->next = global_vle_local_contexts;
+ /* point the head to this context */
+ global_vle_local_contexts = vlelctx;
+ }
+ return vlelctx;
+ }
+ /* otherwise, clean and remove it, and return NULL */
+ else
+ {
+ /* set the top if necessary and unlink it */
+ if (prev == NULL)
+ {
+ global_vle_local_contexts = vlelctx->next;
+ }
+ else
+ {
+ prev->next = vlelctx->next;
+ }
+ /* now free it and return NULL */
+ free_VLE_local_context(vlelctx);
+ return NULL;
+ }
+ }
+ /* save the previous context */
+ prev = vlelctx;
+ /* get the next context */
+ vlelctx = vlelctx->next;
+ /* keep track of cache size */
+ cache_size++;
+ }
+ return vlelctx;
+}
+
+static void cache_VLE_local_context(VLE_local_context *vlelctx)
+{
+ /* if the context passed is null, just return */
+ if (vlelctx == NULL)
+ {
+ return;
+ }
+
+ /* if the global link is null, just assign it the local context */
+ if (global_vle_local_contexts == NULL)
+ {
+ global_vle_local_contexts = vlelctx;
+ return;
+ }
+
+ /* if there is a global link, add the local context to the top */
+ vlelctx->next = global_vle_local_contexts;
+ global_vle_local_contexts = vlelctx;
+}
+
/* helper function to create the local VLE edge state hashtable. */
static void create_VLE_local_state_hashtable(VLE_local_context *vlelctx)
{
@@ -163,107 +277,29 @@ static void create_VLE_local_state_hashtable(VLE_local_context *vlelctx)
}
/*
- * Helper function to step through an object's key/value pairs.
- * The function will return NULL if there is nothing to do. Otherwise,
- * it will return the iterator and the passed key and value agtype_values
- * will be populated. The function should initially be called with a NULL for
- * the iterator, to initialize it to the beginning of the object.
- *
- * Note: This function is only for OBJECT containers.
- */
-static agtype_iterator *get_next_object_pair(agtype_iterator *it,
- agtype_container *agtc,
- agtype_value *key,
- agtype_value *value)
-{
- agtype_iterator_token itok;
- agtype_value tmp;
-
- /* verify input params */
- Assert(agtc != NULL);
- Assert(key != NULL);
- Assert(value != NULL);
-
- /* check to see if the container is empty */
- if (AGTYPE_CONTAINER_SIZE(agtc) == 0)
- {
- return NULL;
- }
-
- /* if the passed iterator is NULL, this is the first time, create it */
- if (it == NULL)
- {
- /* initial the iterator */
- it = agtype_iterator_init(agtc);
- /* get the first token */
- itok = agtype_iterator_next(&it, &tmp, false);
- /* it should be WAGT_BEGIN_OBJECT */
- Assert(itok == WAGT_BEGIN_OBJECT);
- }
-
- /* the next token should be a key or the end of the object */
- itok = agtype_iterator_next(&it, &tmp, false);
- Assert(itok == WAGT_KEY || WAGT_END_OBJECT);
- /* if this is the end of the object return NULL */
- if (itok == WAGT_END_OBJECT)
- {
- return NULL;
- }
-
- /* this should be the key, copy it */
- if (itok == WAGT_KEY)
- {
- memcpy(key, &tmp, sizeof(agtype_value));
- }
-
- /*
- * The next token should be a value but, it could be a begin tokens for
- * arrays or objects. For those we don't want to step into them, just leave
- * them as is.
- */
- itok = agtype_iterator_next(&it, &tmp, true);
- Assert(itok == WAGT_VALUE);
- if (itok == WAGT_VALUE)
- {
- memcpy(value, &tmp, sizeof(agtype_value));
- }
-
- /* return the iterator */
- return it;
-}
-
-/*
- * Helper function to compare the edge conditions (properties we are looking
- * for in a matching edge) against an edge entry.
- *
- * Note: Currently the edge properties - to match - that are stored in the local
- * context are of type agtype_value (in memory) while those from the edge
- * are of agtype (on disk). This may change.
+ * Helper function to compare the edge constraint (properties we are looking
+ * for in a matching edge) against an edge entry's property.
*/
static bool is_an_edge_match(VLE_local_context *vlelctx, edge_entry *ee)
{
- agtype_value *agtv_edge_conditions = NULL;
- agtype *agt_edge_properties = NULL;
- agtype_iterator *iterator = NULL;
- agtype_container *agtc_edge_properties = NULL;
+ agtype *edge_property = NULL;
+ agtype_container *agtc_edge_property = NULL;
+ agtype_container *agtc_edge_property_constraint = NULL;
+ agtype_iterator *constraint_it = NULL;
+ agtype_iterator *property_it = NULL;
char *edge_label_name = NULL;
- int num_conditions = 0;
+ int num_edge_property_constraints = 0;
int num_edge_properties = 0;
- int num_matches = 0;
- int property_index = 0;
-
- /* for easier reading */
- agtv_edge_conditions = vlelctx->edge_conditions;
/* get the number of conditions from the prototype edge */
- num_conditions = agtv_edge_conditions->val.object.num_pairs;
+ num_edge_property_constraints = AGT_ROOT_COUNT(vlelctx->edge_property_constraint);
/*
* We only care about verifying that we have all of the property conditions.
* We don't care about extra unmatched properties. If there aren't any edge
- * conditions, then the edge passes by default.
+ * constraints, then the edge passes by default.
*/
- if (vlelctx->edge_label_name == NULL && num_conditions == 0)
+ if (vlelctx->edge_label_name == NULL && num_edge_property_constraints == 0)
{
return true;
}
@@ -271,18 +307,19 @@ static bool is_an_edge_match(VLE_local_context *vlelctx, edge_entry *ee)
/* get the edge label name from the oid */
edge_label_name = get_rel_name(get_edge_entry_label_table_oid(ee));
/* get our edge's properties */
- agt_edge_properties = DATUM_GET_AGTYPE_P(get_edge_entry_properties(ee));
- /* get the container */
- agtc_edge_properties = &agt_edge_properties->root;
+ edge_property = DATUM_GET_AGTYPE_P(get_edge_entry_properties(ee));
+ /* get the containers */
+ agtc_edge_property_constraint = &vlelctx->edge_property_constraint->root;
+ agtc_edge_property = &edge_property->root;
/* get the number of properties in the edge to be matched */
- num_edge_properties = AGTYPE_CONTAINER_SIZE(agtc_edge_properties);
+ num_edge_properties = AGTYPE_CONTAINER_SIZE(agtc_edge_property);
/*
* Check to see if the edge_properties object has AT LEAST as many pairs
- * to compare as the edge_conditions object has pairs. If not, it can't
- * possibly match.
+ * to compare as the edge_property_constraint object has pairs. If not, it
+ * can't possibly match.
*/
- if (num_conditions > num_edge_properties)
+ if (num_edge_property_constraints > num_edge_properties)
{
return false;
}
@@ -296,93 +333,12 @@ static bool is_an_edge_match(VLE_local_context *vlelctx, edge_entry *ee)
return false;
}
- if (num_conditions == 0)
- {
- return true;
- }
-
- /*
- * Iterate through the edge's properties, matching them against the
- * condtions required.
- */
- do
- {
- agtype_value edge_property_key = {0};
- agtype_value edge_property_value = {0};
-
- property_index++;
-
- /* get the next key/value pair from the edge_properties if it exists */
- iterator = get_next_object_pair(iterator, agtc_edge_properties,
- &edge_property_key,
- &edge_property_value);
-
- /* if there is a pair, see if the key is in the edge conditions */
- if (iterator != NULL)
- {
- agtype_value *condition_value = NULL;
-
- /* get the condition_value for the specified edge_property_key */
- condition_value = get_agtype_value_object_value(agtv_edge_conditions,
- edge_property_key.val.string.val,
- edge_property_key.val.string.len);
-
- /* if one exists, we have a key match */
- if (condition_value != NULL)
- {
- bool match = false;
-
- /* are they both scalars */
- if (IS_A_AGTYPE_SCALAR(condition_value) &&
- IS_A_AGTYPE_SCALAR(&edge_property_value))
- {
- match = compare_agtype_scalar_values(condition_value,
- &edge_property_value)
- == 0;
- }
- /* or are they both containers */
- else if (!IS_A_AGTYPE_SCALAR(condition_value) &&
- !IS_A_AGTYPE_SCALAR(&edge_property_value))
- {
- agtype *agt_condition = NULL;
- agtype_container *agtc_condition = NULL;
- agtype_container *agtc_property = NULL;
-
- /* serialize this condition */
- agt_condition = agtype_value_to_agtype(condition_value);
-
- /* put them into containers for comparison */
- agtc_condition = &agt_condition->root;
- agtc_property = edge_property_value.val.binary.data;
-
- /* check for an exact match */
- if (compare_agtype_containers_orderability(agtc_condition,
- agtc_property)
- == 0)
- {
- match = true;
- }
- }
-
- /* count matches */
- if (match)
- {
- num_matches++;
- }
- }
-
- /* check to see if a match is no longer possible */
- if ((num_edge_properties - property_index) <
- (num_conditions - num_matches))
- {
- pfree(iterator);
- return false;
- }
- }
- }
- while (iterator != NULL);
+ /* get the iterators */
+ constraint_it = agtype_iterator_init(agtc_edge_property_constraint);
+ property_it = agtype_iterator_init(agtc_edge_property);
- return true;
+ /* return the value of deep contains */
+ return agtype_deep_contains(&property_it, &constraint_it);
}
/*
@@ -401,6 +357,10 @@ static void free_VLE_local_context(VLE_local_context *vlelctx)
return;
}
+ /* free the stored graph name */
+ pfree(vlelctx->graph_name);
+ vlelctx->graph_name = NULL;
+
/* we need to free our state hashtable */
hash_destroy(vlelctx->edge_state_hashtable);
vlelctx->edge_state_hashtable = NULL;
@@ -418,6 +378,7 @@ static void free_VLE_local_context(VLE_local_context *vlelctx)
/* and finally the context itself */
pfree(vlelctx);
+ vlelctx = NULL;
}
/* helper function to check if our start and end vertices exist */
@@ -461,13 +422,122 @@ static void load_initial_dfs_stacks(VLE_local_context *vlelctx)
* Helper function to build the local VLE context. This is also the point
* where, if necessary, the global GRAPH contexts are created and freed.
*/
-static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo)
+static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo,
+ FuncCallContext *funcctx)
{
+ MemoryContext oldctx = NULL;
GRAPH_global_context *ggctx = NULL;
VLE_local_context *vlelctx = NULL;
agtype_value *agtv_temp = NULL;
+ agtype_value *agtv_object = NULL;
char *graph_name = NULL;
- Oid graph_oid;
+ Oid graph_oid = InvalidOid;
+ int64 vle_grammar_node_id = 0;
+ bool use_cache = false;
+
+ /*
+ * Get the VLE grammar node id, if it exists. Remember, we overload the
+ * age_vle function, for now, for backwards compatability
+ */
+ if (PG_NARGS() == 8)
+ {
+ /* get the VLE grammar node id */
+ agtv_temp = get_agtype_value("age_vle", AG_GET_ARG_AGTYPE_P(7),
+ AGTV_INTEGER, true);
+ vle_grammar_node_id = agtv_temp->val.int_value;
+
+ /* we are using the VLE local context cache, so set it */
+ use_cache = true;
+ }
+
+ /* fetch the VLE_local_context if it is cached */
+ vlelctx = get_cached_VLE_local_context(vle_grammar_node_id);
+
+ /* if we are caching VLE_local_contexts and this grammar node is cached */
+ if (use_cache && vlelctx != NULL)
+ {
+ /*
+ * No context change is needed here as the cache entry is in the proper
+ * context. Additionally, all of the modifications are either pointers
+ * to objects already in the proper context or primative types that will
+ * be stored in that context since the memory is allocated there.
+ */
+
+ /* get and update the start vertex id */
+ if (PG_ARGISNULL(1) || is_agtype_null(AG_GET_ARG_AGTYPE_P(1)))
+ {
+ vlelctx->vsid = get_graphid(vlelctx->next_vertex);
+ /* increment to the next vertex */
+ vlelctx->next_vertex = next_GraphIdNode(vlelctx->next_vertex);
+ }
+ else
+ {
+ agtv_temp = get_agtype_value("age_vle", AG_GET_ARG_AGTYPE_P(1),
+ AGTV_VERTEX, false);
+ if (agtv_temp != NULL && agtv_temp->type == AGTV_VERTEX)
+ {
+ agtv_temp = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_temp, "id");
+ }
+ else if (agtv_temp == NULL || agtv_temp->type != AGTV_INTEGER)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("start vertex argument must be a vertex or the integer id")));
+ }
+ vlelctx->vsid = agtv_temp->val.int_value;
+ }
+
+ /* get and update the end vertex id */
+ if (PG_ARGISNULL(2) || is_agtype_null(AG_GET_ARG_AGTYPE_P(2)))
+ {
+ vlelctx->veid = 0;
+ }
+ else
+ {
+ agtv_temp = get_agtype_value("age_vle", AG_GET_ARG_AGTYPE_P(2),
+ AGTV_VERTEX, false);
+ if (agtv_temp != NULL && agtv_temp->type == AGTV_VERTEX)
+ {
+ agtv_temp = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_temp, "id");
+ }
+ else if (agtv_temp == NULL || agtv_temp->type != AGTV_INTEGER)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("end vertex argument must be a vertex or the integer id")));
+ }
+ vlelctx->veid = agtv_temp->val.int_value;
+ }
+ vlelctx->is_dirty = true;
+
+ /* we need the SRF context to add in the edges to the stacks */
+ oldctx = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
+
+ /* load the initial edges into the dfs stacks */
+ load_initial_dfs_stacks(vlelctx);
+
+ /* switch back to the original context */
+ MemoryContextSwitchTo(oldctx);
+
+ /* return the context */
+ return vlelctx;
+ }
+
+ /* we are not using a cached VLE_local_context, so create a new one */
+
+ /*
+ * If we are going to cache this context, we need to use TopMemoryContext
+ * to save the contents of the context. Otherwise, we just use a regular
+ * context for SRFs
+ */
+ if (use_cache == true)
+ {
+ oldctx = MemoryContextSwitchTo(TopMemoryContext);
+ }
+ else
+ {
+ oldctx = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
+ }
/* get the graph name - this is a required argument */
agtv_temp = get_agtype_value("age_vle", AG_GET_ARG_AGTYPE_P(0),
@@ -486,6 +556,12 @@ static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo)
/* allocate and initialize local VLE context */
vlelctx = palloc0(sizeof(VLE_local_context));
+ /* store the cache usage */
+ vlelctx->use_cache = use_cache;
+
+ /* set the VLE grammar node id */
+ vlelctx->vle_grammar_node_id = vle_grammar_node_id;
+
/* set the graph name and id */
vlelctx->graph_name = graph_name;
vlelctx->graph_oid = graph_oid;
@@ -504,7 +580,6 @@ static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo)
{
elog(ERROR, "age_vle: empty graph");
}
-
/*
* Get the start vertex id - this is an optional parameter and determines
* which path function is used. If a start vertex isn't provided, we
@@ -576,8 +651,10 @@ static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo)
AGTV_EDGE, true);
/* get the edge prototype's property conditions */
- vlelctx->edge_conditions = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_temp,
- "properties");
+ agtv_object = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_temp, "properties");
+ /* store the properties as an agtype */
+ vlelctx->edge_property_constraint = agtype_value_to_agtype(agtv_object);
+
/* get the edge prototype's label name */
agtv_temp = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_temp, "label");
if (agtv_temp->type == AGTV_STRING &&
@@ -632,6 +709,22 @@ static VLE_local_context *build_local_vle_context(FunctionCallInfo fcinfo)
/* load in the starting edge(s) */
load_initial_dfs_stacks(vlelctx);
+ /* this is a new one so nothing follows it */
+ vlelctx->next = NULL;
+
+ /* mark as dirty */
+ vlelctx->is_dirty = true;
+
+ /* if this is to be cached, cache it */
+ if (use_cache == true)
+ {
+ cache_VLE_local_context(vlelctx);
+ }
+
+ /* switch back to the original context */
+ MemoryContextSwitchTo(oldctx);
+
+ /* return the new context */
return vlelctx;
}
@@ -998,106 +1091,148 @@ static bool is_edge_in_path(VLE_local_context *vlelctx, graphid edge_id)
* 3) Edge matches minimum edge properties specified.
*
* Note: The vertex must exist.
- * Note: Edge lists contain both entering and exiting edges. The direction
- * determines which is followed.
*/
static void add_valid_vertex_edges(VLE_local_context *vlelctx,
graphid vertex_id)
{
ListGraphId *vertex_stack = NULL;
ListGraphId *edge_stack = NULL;
+ ListGraphId *edges = NULL;
vertex_entry *ve = NULL;
- GraphIdNode *edge = NULL;
+ GraphIdNode *edge_in = NULL;
+ GraphIdNode *edge_out = NULL;
+ GraphIdNode *edge_self = NULL;
/* get the vertex entry */
ve = get_vertex_entry(vlelctx->ggctx, vertex_id);
/* there better be a valid vertex */
- Assert(ve != NULL);
+ if (ve == NULL)
+ {
+ elog(ERROR, "add_valid_vertex_edges: no vertex found");
+ }
+
/* point to stacks */
vertex_stack = vlelctx->dfs_vertex_stack;
edge_stack = vlelctx->dfs_edge_stack;
- /* get a pointer to the first edge */
- if (get_vertex_entry_edges(ve) != NULL)
+
+ /* set to the first edge for each edge list for the specified direction */
+ if (vlelctx->edge_direction == CYPHER_REL_DIR_RIGHT ||
+ vlelctx->edge_direction == CYPHER_REL_DIR_NONE)
{
- edge = peek_stack_head(get_vertex_entry_edges(ve));
+ edges = get_vertex_entry_edges_out(ve);
+ edge_out = (edges != NULL) ? get_list_head(edges) : NULL;
}
- else
+ if (vlelctx->edge_direction == CYPHER_REL_DIR_LEFT ||
+ vlelctx->edge_direction == CYPHER_REL_DIR_NONE)
{
- edge = NULL;
+ edges = get_vertex_entry_edges_in(ve);
+ edge_in = (edges != NULL) ? get_list_head(edges) : NULL;
}
- /* add in the vertex's edge(s) */
- while (edge != NULL)
+ /* set to the first selfloop edge */
+ edges = get_vertex_entry_edges_self(ve);
+ edge_self = (edges != NULL) ? get_list_head(edges) : NULL;
+
+ /* add in valid vertex edges */
+ while (edge_out != NULL || edge_in != NULL || edge_self != NULL)
{
edge_entry *ee = NULL;
edge_state_entry *ese = NULL;
graphid edge_id;
- /* get the edge_id */
- edge_id = get_graphid(edge);
+ /* get the edge_id from the next available edge*/
+ if (edge_out != NULL)
+ {
+ edge_id = get_graphid(edge_out);
+ }
+ else if (edge_in != NULL)
+ {
+ edge_id = get_graphid(edge_in);
+ }
+ else
+ {
+ edge_id = get_graphid(edge_self);
+ }
/*
* This is a fast existence check, relative to the hash search, for when
- * the path stack is small.
+ * the path stack is small. If the edge is in the path, we skip it.
*/
if (get_stack_size(vlelctx->dfs_path_stack) < 10 &&
is_edge_in_path(vlelctx, edge_id))
{
- edge = next_GraphIdNode(edge);
+ /* set to the next available edge */
+ if (edge_out != NULL)
+ {
+ edge_out = next_GraphIdNode(edge_out);
+ }
+ else if (edge_in != NULL)
+ {
+ edge_in = next_GraphIdNode(edge_in);
+ }
+ else
+ {
+ edge_self = next_GraphIdNode(edge_self);
+ }
continue;
}
/* get the edge entry */
ee = get_edge_entry(vlelctx->ggctx, edge_id);
/* it better exist */
- Assert(ee != NULL);
-
- /* is the edge going in the correct direction */
- if ((vlelctx->edge_direction == CYPHER_REL_DIR_NONE) ||
- (vertex_id == get_edge_entry_start_vertex_id(ee) &&
- vlelctx->edge_direction == CYPHER_REL_DIR_RIGHT) ||
- (vertex_id == get_edge_entry_end_vertex_id(ee) &&
- vlelctx->edge_direction == CYPHER_REL_DIR_LEFT))
+ if (ee == NULL)
{
- /* get its state */
- ese = get_edge_state(vlelctx, edge_id);
- /*
- * Don't add any edges that we have already seen because they will
- * cause a loop to form.
- */
- if (!ese->used_in_path)
+ elog(ERROR, "add_valid_vertex_edges: no edge found");
+ }
+ /* get its state */
+ ese = get_edge_state(vlelctx, edge_id);
+ /*
+ * Don't add any edges that we have already seen because they will
+ * cause a loop to form.
+ */
+ if (!ese->used_in_path)
+ {
+ /* validate the edge if it hasn't been already */
+ if (!ese->has_been_matched && is_an_edge_match(vlelctx, ee))
{
- /* validate the edge if it hasn't been already */
- if (!ese->has_been_matched && is_an_edge_match(vlelctx, ee))
- {
- ese->has_been_matched = true;
- ese->matched = true;
- }
- else if (!ese->has_been_matched)
- {
- ese->has_been_matched = true;
- ese->matched = false;
- }
- /* if it is a match, add it */
- if (ese->has_been_matched && ese->matched)
- {
- /*
- * We need to maintain our source vertex for each edge added
- * if the edge_direction is CYPHER_REL_DIR_NONE. This is due
- * to the edges having a fixed direction and the dfs
- * algorithm working strictly through edges. With an
- * un-directional VLE edge, you don't know the vertex that
- * you just came from. So, we need to store it.
- */
- if (vlelctx->edge_direction == CYPHER_REL_DIR_NONE)
- {
- push_graphid_stack(vertex_stack,
- get_vertex_entry_id(ve));
- }
- push_graphid_stack(edge_stack, edge_id);
- }
+ ese->has_been_matched = true;
+ ese->matched = true;
+ }
+ else if (!ese->has_been_matched)
+ {
+ ese->has_been_matched = true;
+ ese->matched = false;
+ }
+ /* if it is a match, add it */
+ if (ese->has_been_matched && ese->matched)
+ {
+ /*
+ * We need to maintain our source vertex for each edge added
+ * if the edge_direction is CYPHER_REL_DIR_NONE. This is due
+ * to the edges having a fixed direction and the dfs
+ * algorithm working strictly through edges. With an
+ * un-directional VLE edge, you don't know the vertex that
+ * you just came from. So, we need to store it.
+ */
+ if (vlelctx->edge_direction == CYPHER_REL_DIR_NONE)
+ {
+ push_graphid_stack(vertex_stack, get_vertex_entry_id(ve));
+ }
+ push_graphid_stack(edge_stack, edge_id);
}
}
- edge = next_GraphIdNode(edge);
+ /* get the next working edge */
+ if (edge_out != NULL)
+ {
+ edge_out = next_GraphIdNode(edge_out);
+ }
+ else if (edge_in != NULL)
+ {
+ edge_in = next_GraphIdNode(edge_in);
+ }
+ else
+ {
+ edge_self = next_GraphIdNode(edge_self);
+ }
}
}
@@ -1485,11 +1620,8 @@ Datum age_vle(PG_FUNCTION_ARGS)
/* create a function context for cross-call persistence */
funcctx = SRF_FIRSTCALL_INIT();
- /* switch to memory context appropriate for multiple function calls */
- oldctx = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
-
/* build the local vle context */
- vlelctx = build_local_vle_context(fcinfo);
+ vlelctx = build_local_vle_context(fcinfo, funcctx);
/*
* Point the function call context's user pointer to the local VLE
@@ -1497,8 +1629,6 @@ Datum age_vle(PG_FUNCTION_ARGS)
*/
funcctx->user_fctx = vlelctx;
- MemoryContextSwitchTo(oldctx);
-
/* if we are starting from zero [*0..x] flag it */
if (vlelctx->lidx == 0)
{
@@ -1618,8 +1748,14 @@ Datum age_vle(PG_FUNCTION_ARGS)
/* otherwise, we are done and we need to cleanup and signal done */
else
{
- /* free the local context */
- free_VLE_local_context(vlelctx);
+ /* mark local context as clean */
+ vlelctx->is_dirty = false;
+
+ /* free the local context, if we aren't caching it */
+ if (vlelctx->use_cache == false)
+ {
+ free_VLE_local_context(vlelctx);
+ }
/* signal that we are done */
SRF_RETURN_DONE(funcctx);
@@ -1880,7 +2016,7 @@ Datum age_materialize_vle_edges(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(agtype_value_to_agtype(agtv_array));
}
-/* PG wrapper function for agt_materialize_vle_path */
+/* PG wrapper function for age_materialize_vle_path */
PG_FUNCTION_INFO_V1(age_materialize_vle_path);
Datum age_materialize_vle_path(PG_FUNCTION_ARGS)
@@ -2283,3 +2419,102 @@ Datum _ag_enforce_edge_uniqueness(PG_FUNCTION_ARGS)
hash_destroy(exists_hash);
PG_RETURN_BOOL(true);
}
+
+/* PG wrapper function for age_vertex_degree */
+PG_FUNCTION_INFO_V1(age_vertex_stats);
+
+Datum age_vertex_stats(PG_FUNCTION_ARGS)
+{
+ GRAPH_global_context *ggctx = NULL;
+ vertex_entry *ve = NULL;
+ ListGraphId *edges = NULL;
+ agtype_value *agtv_vertex = NULL;
+ agtype_value *agtv_temp = NULL;
+ agtype_value agtv_integer;
+ agtype_in_state result;
+ char *graph_name = NULL;
+ Oid graph_oid = InvalidOid;
+ graphid vid = 0;
+ int64 self_loops = 0;
+ int64 degree = 0;
+
+ /* get the graph name (required) */
+ agtv_temp = get_agtype_value("vertex_stats", AG_GET_ARG_AGTYPE_P(0),
+ AGTV_STRING, true);
+
+ /* get the vertex (required) */
+ agtv_vertex = get_agtype_value("vertex_stats", AG_GET_ARG_AGTYPE_P(1),
+ AGTV_VERTEX, true);
+
+ graph_name = pnstrdup(agtv_temp->val.string.val,
+ agtv_temp->val.string.len);
+
+ /* get the graph oid */
+ graph_oid = get_graph_oid(graph_name);
+
+ /*
+ * Create or retrieve the GRAPH global context for this graph. This function
+ * will also purge off invalidated contexts.
+ */
+ ggctx = manage_GRAPH_global_contexts(graph_name, graph_oid);
+
+ /* get the id */
+ agtv_temp = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_vertex, "id");
+ vid = agtv_temp->val.int_value;
+
+ /* get the vertex entry */
+ ve = get_vertex_entry(ggctx, vid);
+
+ /* zero the state */
+ memset(&result, 0, sizeof(agtype_in_state));
+
+ /* start the object */
+ result.res = push_agtype_value(&result.parse_state, WAGT_BEGIN_OBJECT,
+ NULL);
+ /* store the id */
+ result.res = push_agtype_value(&result.parse_state, WAGT_KEY,
+ string_to_agtype_value("id"));
+ result.res = push_agtype_value(&result.parse_state, WAGT_VALUE, agtv_temp);
+
+ /* store the label */
+ agtv_temp = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv_vertex, "label");
+ result.res = push_agtype_value(&result.parse_state, WAGT_KEY,
+ string_to_agtype_value("label"));
+ result.res = push_agtype_value(&result.parse_state, WAGT_VALUE, agtv_temp);
+
+ /* set up an integer for returning values */
+ agtv_temp = &agtv_integer;
+ agtv_temp->type = AGTV_INTEGER;
+ agtv_temp->val.int_value = 0;
+
+ /* get and store the self_loops */
+ edges = get_vertex_entry_edges_self(ve);
+ self_loops = (edges != NULL) ? get_list_size(edges) : 0;
+ agtv_temp->val.int_value = self_loops;
+ result.res = push_agtype_value(&result.parse_state, WAGT_KEY,
+ string_to_agtype_value("self_loops"));
+ result.res = push_agtype_value(&result.parse_state, WAGT_VALUE, agtv_temp);
+
+ /* get and store the in_degree */
+ edges = get_vertex_entry_edges_in(ve);
+ degree = (edges != NULL) ? get_list_size(edges) : 0;
+ agtv_temp->val.int_value = degree + self_loops;
+ result.res = push_agtype_value(&result.parse_state, WAGT_KEY,
+ string_to_agtype_value("in_degree"));
+ result.res = push_agtype_value(&result.parse_state, WAGT_VALUE, agtv_temp);
+
+ /* get and store the out_degree */
+ edges = get_vertex_entry_edges_out(ve);
+ degree = (edges != NULL) ? get_list_size(edges) : 0;
+ agtv_temp->val.int_value = degree + self_loops;
+ result.res = push_agtype_value(&result.parse_state, WAGT_KEY,
+ string_to_agtype_value("out_degree"));
+ result.res = push_agtype_value(&result.parse_state, WAGT_VALUE, agtv_temp);
+
+ /* close the object */
+ result.res = push_agtype_value(&result.parse_state, WAGT_END_OBJECT, NULL);
+
+ result.res->type = AGTV_OBJECT;
+
+ PG_RETURN_POINTER(agtype_value_to_agtype(result.res));
+}
diff --git a/src/include/utils/age_global_graph.h b/src/include/utils/age_global_graph.h
index ec2cb05..ad6cd59 100644
--- a/src/include/utils/age_global_graph.h
+++ b/src/include/utils/age_global_graph.h
@@ -48,7 +48,9 @@ vertex_entry *get_vertex_entry(GRAPH_global_context *ggctx,
edge_entry *get_edge_entry(GRAPH_global_context *ggctx, graphid edge_id);
/* vertex entry accessor functions*/
graphid get_vertex_entry_id(vertex_entry *ve);
-ListGraphId *get_vertex_entry_edges(vertex_entry *ve);
+ListGraphId *get_vertex_entry_edges_in(vertex_entry *ve);
+ListGraphId *get_vertex_entry_edges_out(vertex_entry *ve);
+ListGraphId *get_vertex_entry_edges_self(vertex_entry *ve);
Oid get_vertex_entry_label_table_oid(vertex_entry *ve);
Datum get_vertex_entry_properties(vertex_entry *ve);
/* edge entry accessor functions */
diff --git a/src/include/utils/age_graphid_ds.h b/src/include/utils/age_graphid_ds.h
index d674e56..cfacfc1 100644
--- a/src/include/utils/age_graphid_ds.h
+++ b/src/include/utils/age_graphid_ds.h
@@ -65,5 +65,9 @@ int64 get_stack_size(ListGraphId *stack);
ListGraphId *append_graphid(ListGraphId *container, graphid id);
/* free a ListGraphId container */
void free_ListGraphId(ListGraphId *container);
+/* return a reference to the head entry of a list */
+GraphIdNode *get_list_head(ListGraphId *list);
+/* get the size of the passed list */
+int64 get_list_size(ListGraphId *list);
#endif