algo.mst builds three edge-sized arrays and an index sort with no working-memory reservation, the one dense algo path #6263 did not price

[lvca]

Raised in the review of PR #6298 (issues #6296 / #6289) and deliberately not folded into it: it is pre-existing, and that PR is about the result set and about churn, not about closing a new hole in the budget.

The gap

#6263 reserved the dense working set of every algo.* procedure that builds one against arcadedb.cypher.algoMaxWorkingMemory. algo.mst was not among them, and it builds a working set sized by the edge count:

final int[]    eu = new int[edgeCount];
final int[]    ev = new int[edgeCount];
final double[] ew = new double[edgeCount];
...
final int[] sortIdx = sortedIndexesByWeight(ew, ec);   // order + merge scratch: two more int[ec]

That is 16 bytes per edge in the three parallel arrays plus 8 in the sort, so 24 bytes per edge, none of it reserved. At 100M edges - a size ArcadeDB is built for - that is ~2.4 GB requested with no check and no error naming what asked for it, which is exactly the OutOfMemoryError shape #6065, #6216 and #6263 exist to replace with a client error.

AlgoMST also holds the List<Vertex> of every vertex and the Map<RID, Integer> index beside it, which is the OLTP loading path rather than anything the MST itself chose - worth pricing separately, or worth not doing at all (see below).

Why it was missed

The procedures #6263 priced are the ones whose working set is sized by a knob (an embedding dimension, a terminal list) or is quadratic in the node count (a distance, similarity or capacity matrix). algo.mst is neither: it is linear in the edge count, which reads like the graph paying for itself. But linear in the edge count is not small - it is the largest linear dimension a graph has, usually an order of magnitude above the node count - and "linear" is not the criterion the budget uses. The criterion is whether the allocation has a ceiling the caller can predict, and this one does not.

algo.minSpanningArborescence and any other Kruskal/Borůvka-shaped procedure should be checked in the same pass rather than fixed one at a time; the review that found this one only looked at the files PR #6298 touched.

Suggested fix, and a better alternative

The mechanical fix is one newMemoryBudget(db).reserve(...) before the pass-2 fill, pricing edgeCount x (2 * INT_BYTES + DOUBLE_BYTES) plus the 2 * INT_BYTES the index sort adds, with a detail string naming the edge count. That is consistent with every other procedure and is what the reviewer asked for.

Worth considering instead, or as well: algo.mst does not need the edge arrays to be dense in the first place. Kruskal's only ever reads the edges in weight order, and the sort is the only reason they are all resident. A Borůvka formulation over the CSR adjacency does the same job in O(nodeCount) working memory with no edge array at all, and parallelises per component, which is the shape the analytical view already offers. That would remove the allocation rather than bound it, and would make the reservation a formality rather than a limit users have to raise. It is a larger change than the budget line, which is why both are worth stating.

If the dense form is kept, the reservation should be made before the pass-1 count loop rather than between the passes: pass 1 already walks every edge, so a graph too large to serve should not first pay for a full traversal it will throw away. The same argument is why algo.steinerTree reserves before its adjacency build.

Related

#6263, PR #6285, PR #6298, #6296, #6289, #6216, #6065.