memgraph/customers/elliott/README_internal.md

DISCLAIMER: this is just an initial test, graph might not resemble
the graph in the use case at all and the data might be completely
irrelevant.

We tried generating a few sample graphs from the vague description
given in the use case doc. Then we tried writing queries that would
solve the problem of updating nodes when a leaf value changes,
assuming all the internal nodes compute only the sum function.

We start by creating an index on `id` property to improve initial lookup
performance:

    CREATE INDEX ON :Leaf(id)

Set values of all leafs to 1:

    MATCH (u:Leaf) SET u.value = 1

Now we initialize the values of all other nodes in the graph:

    MATCH (u) WHERE NOT u:Leaf SET u.value = 0

    MATCH (u) WITH u
    ORDER BY u.topological_index DESC
    MATCH (u)-->(v) SET u.value = u.value + v.value

Change the value of a leaf:

    MATCH (u:Leaf {id: "18"}) SET u.value = 10

We have to reset all the updated nodes to a neutral element:

    MATCH (u:Leaf {id: "18"})<-[* bfs]-(v)
    WHERE NOT v:Leaf SET v.value = 0

Finally, we recalculate their values in topological order:

    MATCH (u:Leaf {id: "18"})<-[* bfs]-(v)
    WITH v ORDER BY v.topological_index DESC
    MATCH (v)-->(w) SET v.value = v.value + w.value

There are a few assumptions made worth pointing out.

* We are able to efficiently maintain topological order
  of vertices in the graph.

* It is possible to accumulate the value of the function.  Formally: 
  $$f(x_1, x_2, ..., x_n) = g(...(g(g(x_1, x_2), x_3), ...), x_n)$$

* There is a neutral element for the operation. However, this
  assumption can be dropped by introducing an artificial neutral element.

Number of operations required is proportional to the sum of degrees of affected
nodes.

We generated graph with $10^5$ nodes ($20\ 000$ nodes in each layer),  varied the
degree distribution in node layers and measured time for the query to execute:

| # |  Root-Category-Group degree | Group-CustomGroup-Leaf degree |   Time    |
|:-:|:---------------------------:|:-----------------------------:|:---------:|
| 1 |            [1, 10]          |           [20, 40]            |   ~1.1s   |
| 2 |            [1, 10]          |          [50, 100]            |   ~2.5s   |
| 3 |           [10, 50]          |          [50, 100]            |   ~3.3s   |

Due to the structure of the graph, update of a leaf required update of almost
all the nodes in the graph so we don't show times required for initial graph
update and update after leaf change separately.

However, there is not enough info on the use case to make the test more
sophisticated.