Skip to content

Result-equivalent queries show a 16.2x runtime gap across pattern-order variants #5116

Description

@YaeSakuraQ

Result-equivalent queries show a 16.2x runtime gap across pattern-order variants

I found two result-equivalent ArcadeDB query formulations whose measured runtime differs substantially on the attached graph. The intended difference between the formulations is a pattern-order variant.

I am reporting the observed runtime/profile difference without assigning it to a specific ArcadeDB component.

ArcadeDB Version: Docker image arcadedata/arcadedb:latest
Operating System: Linux Docker container
Installation Method: Docker image arcadedata/arcadedb:latest
API/Driver: ArcadeDB HTTP OpenCypher endpoint

Steps to reproduce

  1. Load the attached graph setup file into an empty disposable ArcadeDB database:

reproducer_graph.cypher.txt

while IFS= read -r stmt; do
  curl -sS -u root:password \
    -H 'Content-Type: application/json' \
    -d "{\"language\":\"opencypher\",\"command\":\"${stmt//\"/\\\"}\"}" \
    http://localhost:2480/api/v1/command/graph
done < reproducer_graph.cypher.txt
  1. Verify the graph size:
MATCH (n) RETURN count(n) AS nodes;
-- nodes: 128

MATCH ()-[r]->() RETURN count(r) AS relationships;
-- relationships: 113
  1. Run the fast query:
PROFILE
MATCH (n0 :L1 :L5), (n0), (n1)
WHERE ((n0.k9) OR (n0.k8))
OPTIONAL MATCH (n2 :L5)-[r0 :T1]->(n3 :L3 :L0), (n1)
WHERE ('b' ENDS WITH '0ZIeb')
OPTIONAL MATCH (n1)
RETURN max('h') AS a0, (n0.k36) AS a1, (r0.k52) AS a2;
  1. Run the slow query:
PROFILE
MATCH (n1), (n0), (n0 :L1 :L5)
WHERE ((n0.k9) OR (n0.k8))
OPTIONAL MATCH (n2 :L5)-[r0 :T1]->(n3 :L3 :L0), (n1)
WHERE ('b' ENDS WITH '0ZIeb')
OPTIONAL MATCH (n1)
RETURN max('h') AS a0, (n0.k36) AS a1, (r0.k52) AS a2;

Expected behavior

The two queries are intended to be result-equivalent. On the same graph, I would expect comparable execution time, or at least not an order-of-magnitude runtime gap, between these two formulations.

Actual behavior

Repeated replay confirmed that the two queries returned the same result rows and reported a large runtime gap.

Metric Fast query Slow query
Query form one result-equivalent pattern-order formulation reordered result-equivalent pattern-order formulation
Median runtime 2.925 ms 47.497 ms
Runtime ratio 1.000x 16.238x
Runtime delta n/a 44.572 ms

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

Fields

No fields configured for Bug.

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions