All geek questions in one place

Neo4j / Cypher efficient pagination with a large subgraph order

I have the following simple link between nodes (:User).

(:User)-[:FOLLOWS {timestamp}]->(:User)

If I paginate followers in order FOLLOWS.timestamp, I run into performance issues when someone has millions of followers.

MATCH (u:User {Id:{id}})<-[f:FOLLOWS]-(follower)
WHERE f.timestamp <= {timestamp}
RETURN follower
ORDER BY f.timestamp DESC
LIMIT 100

What is the approach for breaking large datasets when ordering?

UPDATE

follower             timestamp
---------------------------------------
id(1000000)          1455967905
id(999999)           1455967875
id(999998)           1455967234
id(999997)           1455967123
id(999996)           1455965321
id(999995)           1455964123
id(999994)           1455963645
id(999993)           1455963512
id(999992)           1455961343
....
id(2)                1455909382
id(1)                1455908432

I want to cut this list down using the timestamp that is set in the relation :FOLLOWS. If I want to return batches of 4 followers, I first take the current timestamp and return the last 4, then 1455967123 and the last 4 and so on. To do this, the entire list must be ordered by timestamp, which leads to performance problems on millions of records.

+4
1

, .. , .

(2) 20

() , ( 1 , . (3)). , 230 , . (1)

, , 2M db- ​​ .

(1) /

PROFILE
> MATCH (u)<-[f:FOLLOWS]-(follower) WHERE id(u) = 0
> // skip ahead
> WITH f,follower SKIP 999000
> // do the actual check
> WITH f,follower WHERE f.ts < 500
> RETURN f, follower
> ORDER BY f.ts
> LIMIT 10;
+---------------------------------+
| f                  | follower   |
+---------------------------------+
| :FOLLOWS[0]{ts:1}  | Node[1]{}  |
...
+---------------------------------+
10 rows
243 ms

Compiler CYPHER 2.3 Planner COST Runtime INTERPRETED

+-----------------+----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| Operator        | Estimated Rows | Rows    | DB Hits | Identifiers                                                             | Other                                 |
+-----------------+----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +ProduceResults |              1 |      10 |       0 | f, follower                                                             | f, follower                           |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Projection     |              1 |      10 |       0 | anon[142], anon[155], anon[158], anon[178], f, follower, f, follower, u | anon[155]; anon[158]                  |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Top            |              1 |      10 |       0 | anon[142], anon[155], anon[158], anon[178], f, follower, u              | Literal(10);                          |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Projection     |              1 |     499 |     499 | anon[142], anon[155], anon[158], anon[178], f, follower, u              | anon[155]; anon[158]; anon[155].ts    |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Projection     |              1 |     499 |       0 | anon[142], anon[155], anon[158], f, follower, u                         | f; follower                           |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Filter         |              1 |     499 |       0 | anon[142], f, follower, u                                               | anon[142]                             |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Projection     |              1 |    1000 |    1000 | anon[142], f, follower, u                                               | f; follower; f.ts < {  AUTOINT2}      |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Skip           |              1 |    1000 |       0 | f, follower, u                                                          | {  AUTOINT1}                          |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +Expand(All)    |              1 | 1000000 | 1000001 | f, follower, u                                                          | (u)<-[  f@12:FOLLOWS]-(  follower@24) |
| |               +----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+
| +NodeByIdSeek   |              1 |       1 |       1 | u                                                                       |                                       |
+-----------------+----------------+---------+---------+-------------------------------------------------------------------------+---------------------------------------+

Total database accesses: 1001501

(2)

PROFILE
> MATCH (u)<-[f:FOLLOWS]-(follower) WHERE id(u) = 0
> AND f.ts > 999500
> RETURN f, follower
> LIMIT 10;
+----------------------------------------------+
| f                           | follower       |
+----------------------------------------------+
| :FOLLOWS[999839]{ts:999840} | Node[999840]{} |
...
+----------------------------------------------+
10 rows
23 ms

Compiler CYPHER 2.3 Planner COST Runtime INTERPRETED

+-----------------+----------------+-------+---------+----------------+---------------------------------------------------------------+
| Operator        | Estimated Rows | Rows  | DB Hits | Identifiers    | Other                                                         |
+-----------------+----------------+-------+---------+----------------+---------------------------------------------------------------+
| +ProduceResults |              1 |    10 |       0 | f, follower    | f, follower                                                   |
| |               +----------------+-------+---------+----------------+---------------------------------------------------------------+
| +Limit          |              1 |    10 |       0 | f, follower, u | Literal(10)                                                   |
| |               +----------------+-------+---------+----------------+---------------------------------------------------------------+
| +Filter         |              1 |    10 |   16394 | f, follower, u | AndedPropertyComparablePredicates(f,f.ts,f.ts > {  AUTOINT1}) |
| |               +----------------+-------+---------+----------------+---------------------------------------------------------------+
| +Expand(All)    |              1 | 16394 |   16395 | f, follower, u | (u)<-[f:FOLLOWS]-(follower)                                   |
| |               +----------------+-------+---------+----------------+---------------------------------------------------------------+
| +NodeByIdSeek   |              1 |     1 |       1 | u              |                                                               |
+-----------------+----------------+-------+---------+----------------+---------------------------------------------------------------+

Total database accesses: 32790

(3)

PROFILE
> MATCH (u)<-[f:FOLLOWS]-(follower) WHERE id(u) = 0
> AND f.ts < 500
> RETURN f, follower
> LIMIT 10;
+-------------------------------------+
| f                     | follower    |
+-------------------------------------+
...
| :FOLLOWS[491]{ts:492} | Node[492]{} |
+-------------------------------------+
10 rows
1008 ms

Compiler CYPHER 2.3 Planner COST Runtime INTERPRETED

+-----------------+----------------+--------+---------+----------------+---------------------------------------------------------------+
| Operator        | Estimated Rows | Rows   | DB Hits | Identifiers    | Other                                                         |
+-----------------+----------------+--------+---------+----------------+---------------------------------------------------------------+
| +ProduceResults |              1 |     10 |       0 | f, follower    | f, follower                                                   |
| |               +----------------+--------+---------+----------------+---------------------------------------------------------------+
| +Limit          |              1 |     10 |       0 | f, follower, u | Literal(10)                                                   |
| |               +----------------+--------+---------+----------------+---------------------------------------------------------------+
| +Filter         |              1 |     10 |  999498 | f, follower, u | AndedPropertyComparablePredicates(f,f.ts,f.ts < {  AUTOINT1}) |
| |               +----------------+--------+---------+----------------+---------------------------------------------------------------+
| +Expand(All)    |              1 | 999498 |  999499 | f, follower, u | (u)<-[f:FOLLOWS]-(follower)                                   |
| |               +----------------+--------+---------+----------------+---------------------------------------------------------------+
| +NodeByIdSeek   |              1 |      1 |       1 | u              |                                                               |
+-----------------+----------------+--------+---------+----------------+---------------------------------------------------------------+

Total database accesses: 1998998
+4

Source: https://habr.com/ru/post/1629597/

More articles:


All Articles