You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@age.apache.org by GitBox <gi...@apache.org> on 2022/03/09 14:59:45 UTC
[GitHub] [incubator-age] Paxxxxxv-Dmitry opened a new issue #195: Variable Length Edges feature stucks
Paxxxxxv-Dmitry opened a new issue #195:
URL: https://github.com/apache/incubator-age/issues/195
Hello,
a database - 1.5 millions vertices and 1.2 millions edges.
Query runtime:
[*..4]. Total query runtime: 7 secs.
[*..5]. Total query runtime: 3 min 30 secs.
[*..6]. Total query runtime: ~7 min.
...
[*..10]. It is stuck forever.
It works very slowly. Do you have any idea how to debug this?
`SELECT * FROM cypher('graph', $$
MATCH (z:type1)-[*..4]->(b:type2 {id: 'CI02597329'})
RETURN z.id
$$) as (id agtype);
`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] pdpotter commented on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
pdpotter commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063820358
Some thoughts:
* The id attribute for node b is defined, depending on the relations in the graph, multiple z nodes could be returned for your query.
* You are currently including all relations types, can this be limited?
* Indexes are currently not supported by Apache AGE (see #45). I don't think your query would benefit a lot from using indices though, since it seems to be a scalability issue related to the number of relations.
* Running your query with `EXPLAIN` / `EXPLAIN ANALYZE` might provide more insight in how your query is executed. Please post the results below:
```
SELECT * FROM cypher('graph', $$ EXPLAIN MATCH (z:type1)-[*..4]->(b:type2 {id: 'CI02597329'}) RETURN z.id $$) as (id agtype);
```
```
SELECT * FROM cypher('graph', $$ EXPLAIN ANALYZE MATCH (z:type1)-[*..4]->(b:type2 {id: 'CI02597329'}) RETURN z.id $$) as (id agtype);
```
* Inversing the query should give the execution path and same performance, but it is easy to do, so maybe worth trying:
```
SELECT * FROM cypher('graph', $$ MATCH (b:type2 {id: 'CI02597329'})<-[*..4]-(z:type1) RETURN z.id $$) as (id agtype);
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1064846731
Thanks for the answer. I will search ways to limit queries. I'm glad to hear that you work on some performance improvements.
I have another one performance question about Variable Length Edges feature -
[*3] AND ()-[]->()-[]->()-[]->() are the same. Am I right?
[*3] query works much more faster than ()-[]->()-[]->()-[]->() and I don't understand why.
```
SELECT * FROM cypher('graph', $$
MATCH (z:type1)-[*3]->(b:type2 {ci_sm_id: 'CI02597329'})
RETURN z.ci_sm_id
$$) as (ci_sm_id agtype);
```
Total query runtime: 2 secs.
```
SELECT * FROM cypher('graph', $$
MATCH (z:type1)-[]->()-[]->()-[]->(b:type2 {ci_sm_id: 'CI02597329'})
RETURN z.ci_sm_id
$$) as (ci_sm_id agtype);
```
Total query runtime: 50 secs.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani edited a comment on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1064297992
I think I need to clear up some misconceptions first -
The VLE is a path finding algorithm, its speed is directly related to the size and connectedness of the graph and what it is looking for. Remember, this is a graph, not a tree, so nodes can be reused in paths but not edges. This means, the longer the path, the less qualified the edges are in a path, the more time it will take in very connected graphs. Btw, other than the start and terminal vertices, the algorithm doesn't care about the interior vertices; it only cares about the edges.
If we look at the following queries:
MATCH p=(u)-[*]-(v) RETURN p
MATCH (u)-[*]-(v) RETURN u
MATCH ()-[*]-() RETURN COUNT(1);
All of these queries will basically do the same thing - search for all paths of any length from all vertices to all vertices. This means that for a graph of 1 million nodes, this algorithm will be invoked up to 1 trillion times (the number of VxV combinations). Now, add that you are asking for all of the paths between each combination. So, each additional path length can add to the work done. This will always be the case for finding paths. Now the algorithm does do some things to help minimize this.
As you can see, the best way to deal with this is to limit what the algorithm has to do. This means restricting where it needs to look and how deeply it needs to look. Just remember, just because you restrict the input vertices doesn't mean that you restrict the interior vertices. The algorithm doesn't care about them, it only cares about interior edges. Additionally, due to other implementation factors (PostgreSQL being a big one) the algorithm generally generates all valid (within the selection window) paths from a start vertex and leaves the match against the terminal vertex to PG.
I will add this -
There are 2 patches coming out in the next release that will improve performance of some queries by up to 10%. I wouldn't expect their impact to be that great but, that depends on the graph and the query. This is across the board, btw, not just the VLE.
Additionally, I am currently working on a patch to the VLE that will negate some of the overhead due to how PG calls the VLE function. This has the potential of greatly increasing the speed of a large subset of queries. However, it is unlikely to be available as part of the next release. But, it should be available to pull down from the current master in about 1-2 weeks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] audiBookning edited a comment on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
audiBookning edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1072779272
I am not sure if i understand correctly the situation, but i will add my two cents dependent only on my limited knowledge. Corrections are welcome.
> I need first match and stop processing
I also am not aware of anything like this in OpenCypher or even Neo4j's Cypher implementation. From my understanding, that type of operation, although useful in certain cases, wouldn't make sense in the "semantics" of OpenCypher which is one of the main "inspiration" for AGE.
I will expand a little bit on the meaning of what i have just written.
OpenCypher, as a language, focuses on patterns to describe and traverse graphs. It is, in my opinion, one of its best qualities compared to others approach's. But with advantages comes disadvantages and, for example, one shouldn't easily confuse pattern matching with paths on the graph.
There is, at most, a relation of set (collection, list, ...) of paths to one pattern here. And that is, us, outside of the algorithm, trying to reason with it. But the fact is that we preferably shouldn't be concerned by its "internal" implementation (abstraction...).
All of this means that there really is not a syntax for an individual path in Cypher, only of patterns. And only in the final results, output, can you really "see" individual paths. So when modelling our "problem", one should try to describe it (and solve it) with patterns, not individual paths.
Cypher does have a shortest path function, but (not even considering the complexity of the problem) we enter in a very different area here.
There is also an old rule to indicates that one should never treat a collection as if was an item or vice versa. This avoids many weirds and unexpected behaviours in algorithms. I have seen many people subconsciously do it.
I think that changing this "pattern first semantic" (although not the only part of the language) would be basically going completely outside of Cypher. I am not part of AGE's dev group, but i imagine that it shouldn't be a decision to easily justify.
I have not enough info, but your specific use case may be considered as an anti-pattern. You might be able to do something similar in OpenCypher with User-defined functions (or not, i have not experimented with it...). In AGE the most similar thing to it may be creating you own extension to AGE.
A "cheaper" alternative could be using sql functions hooking on AGE, you would have to almost recreate the functionality of age in the worst case or, if using it as a kind of constraint (if the hooks exist, that is), it may be extremely expansive in terms of performance, jumping back and forth between your function and AGE's code.
If even with all of this, you still want to use Cypher (and think, as i do, that the alternatives "solutions" that i have given (or others) are not in any way satisfying) You might consider remodelling your graph models and queries to better conform to Cypher's approach and your business model.
Here is a very good inspiration for that (and possibly for the varied length issue discussed here):
[Video - Optimizing Cypher Queries in Neo4j](https://vimeo.com/84900121)
[Slides- Optimizing Cypher Queries in Neo4j](https://www.slideshare.net/neo4j/optimizing-cypher-32550605)
> Sometimes it is not the tool that is wrong for the problem, but the way we use it.
Random thoughts 😎.
This issue reminds me of wikipedia's great gif explaining Djikstra's Shortest Path algorithm [Dijkstra_Animation](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstra_Animation.gif) and also of the Traveling Salesman problem (if you solve it, you probably would be an automatic millionaire and remembered in history as an incomparable genius).
These last lines just to shows how much this issue can be complex and confusing...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1068544379
There will be a new release in a few days (hopefully) that will have some performance enhancements.
There will be a patch that didn't make it into the release that will have some significant (to major) performance enhancements for the VLE depending on the type of query. This patch should be available in a day or two, if you clone the repo and build it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani edited a comment on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
jrgemignani edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063158436
The time taken depends on a couple of factors: The size of the graph, how connected the graph is, how qualified the query is, and some PostgreSQL quirks. Without seeing some statistics (like the number of results returned) on the results from the previous queries I can only guess.
I would guess that each progressive query likely returns more results. PostgreSQL has an annoying habit of not returning anything until everything has been processed. So, while it is getting results (tuples), it won't display anything until it has received them all. If the resultant set is large, this will take a while.
If you can constrain the query, that may help. If you aren't using a variable, don't include it because it can slow the process down. You can use RETURN count(z) in place of RETURN z.id to see how large the set is and that usually runs faster as it is just counting.
Remember, *..x means all lengths from 1 to x will be included in the results.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1071112781
A query will always run to completion unless you use LIMIT -
```
psql-11.5-5432-pgsql=# SELECT * FROM cypher('agload_test_graph', $$ match (u)-[*1..1]->() return u limit 3 $$) AS (result agtype);
result
------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------
{"id": 1125899906842777, "label": "City", "properties": {"id": "153", "name": "Banaj", "__id__": 153, "latitude": "40.82492", "stat
e_id": "629", "longitude": "19.84074", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
{"id": 1125899906842778, "label": "City", "properties": {"id": "154", "name": "Bashkia Berat", "__id__": 154, "latitude": "40.69997
", "state_id": "629", "longitude": "19.94983", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
{"id": 1125899906842794, "label": "City", "properties": {"id": "170", "name": "Bashkia Kuçovë", "__id__": 170, "latitude": "40.8248
9", "state_id": "629", "longitude": "19.9535", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
(3 rows)
psql-11.5-5432-pgsql=#
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry edited a comment on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1070824804
Can criteria like stop at first compound level be added to the query?
[..4]. Total query runtime: 7 secs.
[..5]. Total query runtime: 3 min 30 secs.
But results are the same. I need first match and stop processing. I think the criteria maybe useful in my case.
Also can criteria like "allow self/non self intermediate relations" be added to the query?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] emotionbug commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
emotionbug commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1065026274
@Paxxxxxv-Dmitry
Two things go through a separate process.
First one, passed to VLE algorithm logic. but, second one uses `LEFT JOIN`.
I think it can be optimization in the later release.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1072649865
I am not aware of an openCypher [language specification] query or command that will allow what you asked (provided I understand what you are asking) to be done - other than using LIMIT to only output a specified number of results, but that has issues of its own -
Each vertex selected and processed by the VLE in a match query can have a different minimum length path based on the starting vertex, edge, and ending vertex criteria. And the returned matching paths, and path lengths, will vary in order by which path finding algorithm is used.
DFS, which is used here, starts by going down one side [say left] of the graph from the specified starting vertex, working its way across to the other side [say right]. It is possible, in a graph, that only the longer matching paths are on the left side of the graph and they might be found first. And this is from an arbitrary starting vertex. So, if you stop after the first matching path is found, you won't necessarily get the shortest path.
If BFS were used instead, the shortest matching paths would be found first, but the order would be from one side of the graph to the other, depending on the order of discovered edges. And, the minimum matching path length would be based on that arbitrary starting vertex. So, again, if you stop after the first one is found, you won't necessarily get the shortest path.
In either case, you would need to go through all vertices in order to find the matching paths with the shortest lengths. So, if that is what you are looking for, you can't just stop after the first one, you need to collect all of them.
Now, you can sort the results by the length of the path. You can also give a range [2..2] or [3..7] to look in.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1071112781
A query will always run to completion unless you use LIMIT -
```
psql-11.5-5432-pgsql=# SELECT * FROM cypher('agload_test_graph', $$ match (u)-[*1..1]->() return u limit 3 $$) AS (result agtype);
result
------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------
{"id": 1125899906842777, "label": "City", "properties": {"id": "153", "name": "Banaj", "__id__": 153, "latitude": "40.82492", "stat
e_id": "629", "longitude": "19.84074", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
{"id": 1125899906842778, "label": "City", "properties": {"id": "154", "name": "Bashkia Berat", "__id__": 154, "latitude": "40.69997
", "state_id": "629", "longitude": "19.94983", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
{"id": 1125899906842794, "label": "City", "properties": {"id": "170", "name": "Bashkia Kuçovë", "__id__": 170, "latitude": "40.8248
9", "state_id": "629", "longitude": "19.9535", "country_id": "3", "state_code": "BR", "country_code": "AL"}}::vertex
(3 rows)
psql-11.5-5432-pgsql=#
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063158436
The time taken depends on a couple of factors: The size of the graph, how connected the graph is, how qualified the query is, and some PostgreSQL quirks. Without seeing some statistics (like the number of results returned) on the results from the previous queries I can only guess.
I would guess that each progressive query likely returns more results. PostgreSQL has an annoying habit of not returning anything until everything has been processed. So, while it is getting results (tuples), it won't display anything until it has received them all. If the resultant set is large, this will take a while.
If you can constrain the query, that may help. If you aren't using a variable, don't include it because it can slow the process down. You can use RETURN count(z) to see how large the set is and that usually runs faster as it is just counting.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1070824804
Can criteria like stop at first compound level be added to the query?
[..4]. Total query runtime: 7 secs.
[..5]. Total query runtime: 3 min 30 secs.
But results are the same. I need first match and stop processing. I think the criteria maybe useful in my case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry commented on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063907268
**pdpotter**,
> You are currently including all relations types, can this be limited?
In production environment I have some relations types, but not in my sandbox. Search by all relations types is real production case.
> Indexes are currently not supported by Apache AGE (see https://github.com/apache/incubator-age/issues/45). I don't think your query would benefit a lot from using indices though, since it seems to be a scalability issue related to the number of relations.
Thank you for the link, I have used the workaround to fill my database with edges.
> Running your query with EXPLAIN / EXPLAIN ANALYZE might provide more insight in how your query is executed. Please post the results below.
At first want to let you know that I have changed {id: 'CI02597329'} to {ci_sm_id: 'CI02597329'}.
**SELECT * FROM cypher('graph', $$ EXPLAIN MATCH (z:type1)-[*..4]->(b:type2 {ci_sm_id: 'CI02597329'}) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
```
"Nested Loop (cost=0.01..2954396699.74 rows=43768343623 width=32)"
" Join Filter: age_match_vle_terminal_edge(graphid_to_agtype(z.id), graphid_to_agtype(b.id), _age_default_alias_0.edges)"
" -> Nested Loop (cost=0.01..24093.04 rows=1203000 width=136)"
" -> Seq Scan on type1 z (cost=0.00..33.03 rows=1203 width=104)"
" -> Function Scan on age_vle _age_default_alias_0 (cost=0.01..10.01 rows=1000 width=32)"
" -> Materialize (cost=0.00..9422.40 rows=109148 width=8)"
" -> Seq Scan on type2 b (cost=0.00..8876.66 rows=109148 width=8)"
" Filter: _property_constraint_check(properties, agtype_build_map('ci_sm_id'::text, '"CI02597329"'::agtype))"
```
**SELECT * FROM cypher('graph', $$ EXPLAIN ANALYZE MATCH (z:type1)-[*..4]->(b:type2 {ci_sm_id: 'CI02597329'}) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
```
"Nested Loop (cost=0.01..2954396699.74 rows=43768343623 width=32) (actual time=55343.648..79853.367 rows=1 loops=1)"
" Join Filter: age_match_vle_terminal_edge(graphid_to_agtype(z.id), graphid_to_agtype(b.id), _age_default_alias_0.edges)"
" Rows Removed by Join Filter: 1256960"
" -> Nested Loop (cost=0.01..24093.04 rows=1203000 width=136) (actual time=2.356..31450.736 rows=1256961 loops=1)"
" -> Seq Scan on type1 z (cost=0.00..33.03 rows=1203 width=104) (actual time=0.015..10.394 rows=1203 loops=1)"
" -> Function Scan on age_vle _age_default_alias_0 (cost=0.01..10.01 rows=1000 width=32) (actual time=3.065..10.841 rows=1045 loops=1203)"
" -> Materialize (cost=0.00..9422.40 rows=109148 width=8) (actual time=0.007..0.015 rows=1 loops=1256961)"
" -> Seq Scan on type2 b (cost=0.00..8876.66 rows=109148 width=8) (actual time=217.713..546.113 rows=1 loops=1)"
" Filter: _property_constraint_check(properties, agtype_build_map('ci_sm_id'::text, '"CI02597329"'::agtype))"
" Rows Removed by Filter: 327443"
"Planning Time: 0.106 ms"
"Execution Time: 79853.843 ms"
```
**SELECT * FROM cypher('graph', $$ MATCH (b:type2 {ci_sm_id: 'CI02597329'})<-[*..4]-(z:type1) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
Total query runtime: 661 msec. It works much more faster than before. Count: 1
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry commented on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063798981
**jrgemignani**,
I have done some tests with RETURN count(z):
[..4]. Count: 1. Total query runtime: 7 secs.
[..5]. Count: 1. Total query runtime: 3 min 30 secs.
[..6]. Count: 1. Total query runtime: ~7 min.
Nothing changed. Count equals 1 because Id attribute is unique in my database.
Maybe I can use postgres indexes or something else?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] audiBookning commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
audiBookning commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1072779272
I am not sure if understand correctly the situation, but i will add my two cents dependent only on my limited knowledge. Corrections are welcome.
> I need first match and stop processing
I also am not aware of anything like this in OpenCypher or even Neo4j's Cypher implementation. From my understanding that type of operation, although useful in certain cases, wouldn't make sense in the "semantics" of OpenCypher which is one of the main "inspiration" for AGE.
I will expand a little bit on the meaning of what i have just written.
OpenCypher, as a language, focuses on patterns to describe and traverse graphs. It is, in my opinion, one of one its best qualities compared to others approach's. But with advantages comes disadvantages and, in this particular case, one shouldn't easily confuse pattern matching with paths on the graph.
There is, at most, a relation of set/collection/list of paths to a pattern here. And that is us, outside of the algorithm, trying to reason with it. But we shouldn't be concerned by its "internal" implementation (abstraction...).
All of this means that there really is not a syntax for an individual path, only of patterns. And only in the final results, output, can you really "see" individual paths. So when modelling our "problem", one should try to describe it (and solve it) with patterns, not individual paths.
Cypher does have a shortest path function, but (not even considering the complexity of the problem) we enter in a very different area here.
There is also an old rule to indicates that one should never treat a collection as if was an item or vice versa. This avoids many weirds and unexpected behaviours in algorithms. I have seen many people subconsciously do it.
I think that changing this "pattern first semantic" (although not the only part of the language) would be basically going completely outside of Cypher. I am not part of AGE's dev group, but i imagine that it shouldn't be a decision to easily justify.
I have not enough info, but your specific use case may be considered as an anti-pattern. You might be able to do something similar in OpenCypher with User-defined functions (or not, i have not experimented with it...). In AGE the most similar thing to it may be creating you own extension to AGE.
A "cheaper" alternative could be using sql functions hooking on AGE, you would have to almost recreate the functionality of age in the worst case or, if using it as a kind of constraint (if the hooks exist, that is), it may be extremely expansive in terms of performance, jumping back and forth between your function and AGE's code.
If even with all of this, you still want to use Cypher (and think, as i do, that the alternatives "solutions" that i have given (or others) are not in any way satisfying) You might consider remodelling your graph models and queries to better conform to Cypher's approach and your business model.
Here is a very good inspiration for that (and possibly for the varied length issue discussed here):
[Video - Optimizing Cypher Queries in Neo4j](https://vimeo.com/84900121)
[Slides- Optimizing Cypher Queries in Neo4j](https://www.slideshare.net/neo4j/optimizing-cypher-32550605)
> Sometimes it is not the tool that is wrong for the problem, but the way we use it.
Random thoughts 😎.
This issue reminds me of wikipedia's great gif explaining Djikstra's Shortest Path algorithm [Dijkstra_Animation](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstra_Animation.gif) and also of the Traveling Salesman problem (if you solve it, you probably would be an automatic millionaire and remembered in history as an incomparable genius).
These last lines just to shows how much this issue can be complex and confusing...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry edited a comment on issue #195: Variable Length Edges feature stucks
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1063907268
**pdpotter**,
> You are currently including all relations types, can this be limited?
In production environment I have some relations types, but not in my sandbox. Search by all relations types is real production case.
> Indexes are currently not supported by Apache AGE (see https://github.com/apache/incubator-age/issues/45). I don't think your query would benefit a lot from using indices though, since it seems to be a scalability issue related to the number of relations.
Thank you for the link, I have used the workaround to fill my database with edges.
> Running your query with EXPLAIN / EXPLAIN ANALYZE might provide more insight in how your query is executed. Please post the results below.
At first want to let you know that I have changed {id: 'CI02597329'} to {ci_sm_id: 'CI02597329'}.
**SELECT * FROM cypher('graph', $$ EXPLAIN MATCH (z:type1)-[*..4]->(b:type2 {ci_sm_id: 'CI02597329'}) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
```
"Nested Loop (cost=0.01..2954396699.74 rows=43768343623 width=32)"
" Join Filter: age_match_vle_terminal_edge(graphid_to_agtype(z.id), graphid_to_agtype(b.id), _age_default_alias_0.edges)"
" -> Nested Loop (cost=0.01..24093.04 rows=1203000 width=136)"
" -> Seq Scan on type1 z (cost=0.00..33.03 rows=1203 width=104)"
" -> Function Scan on age_vle _age_default_alias_0 (cost=0.01..10.01 rows=1000 width=32)"
" -> Materialize (cost=0.00..9422.40 rows=109148 width=8)"
" -> Seq Scan on type2 b (cost=0.00..8876.66 rows=109148 width=8)"
" Filter: _property_constraint_check(properties, agtype_build_map('ci_sm_id'::text, '"CI02597329"'::agtype))"
```
**SELECT * FROM cypher('graph', $$ EXPLAIN ANALYZE MATCH (z:type1)-[*..4]->(b:type2 {ci_sm_id: 'CI02597329'}) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
```
"Nested Loop (cost=0.01..2954396699.74 rows=43768343623 width=32) (actual time=55343.648..79853.367 rows=1 loops=1)"
" Join Filter: age_match_vle_terminal_edge(graphid_to_agtype(z.id), graphid_to_agtype(b.id), _age_default_alias_0.edges)"
" Rows Removed by Join Filter: 1256960"
" -> Nested Loop (cost=0.01..24093.04 rows=1203000 width=136) (actual time=2.356..31450.736 rows=1256961 loops=1)"
" -> Seq Scan on type1 z (cost=0.00..33.03 rows=1203 width=104) (actual time=0.015..10.394 rows=1203 loops=1)"
" -> Function Scan on age_vle _age_default_alias_0 (cost=0.01..10.01 rows=1000 width=32) (actual time=3.065..10.841 rows=1045 loops=1203)"
" -> Materialize (cost=0.00..9422.40 rows=109148 width=8) (actual time=0.007..0.015 rows=1 loops=1256961)"
" -> Seq Scan on type2 b (cost=0.00..8876.66 rows=109148 width=8) (actual time=217.713..546.113 rows=1 loops=1)"
" Filter: _property_constraint_check(properties, agtype_build_map('ci_sm_id'::text, '"CI02597329"'::agtype))"
" Rows Removed by Filter: 327443"
"Planning Time: 0.106 ms"
"Execution Time: 79853.843 ms"
```
**SELECT * FROM cypher('graph', $$ MATCH (b:type2 {ci_sm_id: 'CI02597329'})<-[*..4]-(z:type1) RETURN z.ci_sm_id $$) as (ci_sm_id agtype);**
Total query runtime: 661 msec. It works much more faster than before. Count: 1
[*..10] - Total query runtime: 6 secs.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] jrgemignani commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
jrgemignani commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1064297992
I think I need to clear up some misconceptions first -
The VLE is a path finding algorithm, its speed is directly related to the size and connectedness of the graph and what it is looking for. Remember, this is a graph, not a tree, so nodes can be reused in paths but not edges. This means, the longer the path, the less qualified the edges are in a path, the more time it will take in very connected graphs. Btw, other than the start and terminal vertices, the algorithm doesn't care about the interior vertices; it only cares about the edges.
If we look at the following queries:
MATCH p=(u)-[*]-(v) RETURN p
MATCH (u)-[*]-(v) RETURN u
MATCH ()-[*]-() RETURN COUNT(1);
All of these queries will basically do the same thing - search for all paths of any length from all vertices to all vertices. This means that for a graph of 1 million nodes, this algorithm will be invoked up to 1 trillion times (the number of VxV combinations). Now, add that you are asking for all of the paths between each combination. So, each additional path length can add to the work done. This will always be the case for finding paths.
As you can see, the best way to deal with this is to limit what the algorithm has to do. This means restricting where it needs to look and how deeply it needs to look. Just remember, just because you restrict the input vertices doesn't mean that you restrict the interior vertices. The algorithm doesn't care about them, it only cares about interior edges. Additionally, due to other implementation factors (PostgreSQL being a big one) the algorithm generally generates all valid (within the selection window) paths from a start vertex and leaves the match against the terminal vertex to PG.
I will add this -
There are 2 patches coming out in the next release that will improve performance of some queries by up to 10%. I wouldn't expect their impact to be that great but, that depends on the graph and the query. This is across the board, btw, not just the VLE.
Additionally, I am currently working on a patch to the VLE that will negate some of the overhead due to how PG calls the VLE function. This has the potential of greatly increasing the speed of a large subset of queries. However, it is unlikely to be available as part of the next release. But, it should be available to pull down from the current master in about 1-2 weeks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry edited a comment on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry edited a comment on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1070824804
Can criteria like stop at first compound level be added to the query?
[..4]. Total query runtime: 7 secs.
[..5]. Total query runtime: 3 min 30 secs.
But results are the same. I need first match and stop processing. I think the criteria maybe useful in my case.
Also can criteria like "allow self/non self intermediate relations" be added to the query?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-age] Paxxxxxv-Dmitry commented on issue #195: Variable Length Edges feature does not scale well with the length of the path
Posted by GitBox <gi...@apache.org>.
Paxxxxxv-Dmitry commented on issue #195:
URL: https://github.com/apache/incubator-age/issues/195#issuecomment-1070824804
Can criteria like stop at first compound level be added to the query?
[..4]. Total query runtime: 7 secs.
[..5]. Total query runtime: 3 min 30 secs.
But results are the same. I need first match and stop processing. I think the criteria maybe useful in my case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@age.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org