This module has been heavily developed by using a mix of LLMs with the goal of starting from the OpenCypher specification (ANTL grammar available as Apache 2 license) with the goal to have something native that runs on top of ArcadeDB API, without involving Gremlin or SQL. This engine "opencypher" will be available next to the legacy "cypher", so you can switch between them for testing in this first phase.

The results are incredible, the microbenchmark CypherEngineComparisonBenchmark shows impressive results since version 1.0:

  Benchmark 1: Index Seek (Selective Query)
  - Legacy: 5,584 μs
  - Native: 180 μs
  - Speedup: 30.98x FASTER 🚀

  Benchmark 2: Full Scan (Non-Selective Query)
  - Legacy: 12,395 μs
  - Native: 1,876 μs
  - Speedup: 6.61x FASTER

  Benchmark 3: Relationship Traversal
  - Legacy: 4,255 μs
  - Native: 167 μs
  - Speedup: 25.46x FASTER 🚀

  Benchmark 4: Multi-Hop Pattern (2-hop traversal)
  - Legacy: 15,246 μs
  - Native: 886 μs
  - Speedup: 17.21x FASTER 🚀

  Benchmark 5: Cross-Type Relationship (Person->Company)
  - Legacy: 5,000 μs
  - Native: 201 μs
  - Speedup: 24.85x FASTER 🚀

  Benchmark 6: Join Ordering (Start from selective Company filter)
  - Legacy: 29,921 μs
  - Native: 1,342 μs
  - Speedup: 22.28x FASTER 🚀

OpenCypher Implementation Status

Last Updated: 2026-01-13
Implementation Version: Native ANTLR4-based Parser (Phase 8 + Functions + GROUP BY + Pattern Predicates + COLLECT + UNWIND + Optimizer Phase 4 Complete + All Tests Fixed)
Test Coverage: 273/273 tests passing (100% - All tests passing! 🎉✅)

📊 Overall Status

Legend: ✅ Complete | 🟡 Partial | 🔴 Minimal | ❌ Not Implemented

✅ Working Features (Fully Implemented & Tested)

MATCH Clause

// ✅ Simple node patterns with labels
MATCH (n:Person) RETURN n

// ✅ Node patterns with property filters
MATCH (n:Person {name: 'Alice', age: 30}) RETURN n

// ✅ Comma-separated patterns (Cartesian product)
MATCH (a:Person), (b:Company) RETURN a, b

// ✅ Relationship patterns (single-hop)
MATCH (a:Person)-[r:KNOWS]->(b:Person) RETURN a, r, b

// ✅ Relationship patterns (multi-hop)
MATCH (a)-[:KNOWS]->(b)-[:WORKS_AT]->(c) RETURN a, b, c

// ✅ Variable-length relationships
MATCH (a)-[r:KNOWS*1..3]->(b) RETURN a, b

// ✅ Bidirectional relationships
MATCH (a)-[r]-(b) RETURN a, b

// ✅ Relationship with properties
MATCH (a)-[r:WORKS_AT {since: 2020}]->(b) RETURN r

// ✅ Multiple MATCH clauses (Cartesian product or chained)
MATCH (a:Person {name: 'Alice'})
MATCH (b:Person {name: 'Bob'})
RETURN a, b

// ✅ Pattern without labels (matches all vertices)
MATCH (n) RETURN n
MATCH (n) WHERE n.age > 25 RETURN n

// ✅ Named paths for single edges
MATCH p = (a:Person)-[r:KNOWS]->(b:Person) RETURN p

// ✅ Named paths for variable-length relationships
MATCH p = (a:Person)-[:KNOWS*1..3]->(b:Person) RETURN p

// ✅ OPTIONAL MATCH (LEFT OUTER JOIN semantics)
MATCH (a:Person)
OPTIONAL MATCH (a)-[r:KNOWS]->(b:Person)
RETURN a.name, b.name

// ✅ OPTIONAL MATCH with scoped WHERE clause
MATCH (a:Person)
OPTIONAL MATCH (a)-[r:KNOWS]->(b:Person)
WHERE b.age > 20
RETURN a.name, b.name

Limitations:

• ⚠️ Variable-length path queries return duplicate results (pre-existing bug, not related to named path implementation)

WHERE Clause

// ✅ Simple property comparisons
MATCH (n:Person) WHERE n.age > 30 RETURN n
MATCH (n:Person) WHERE n.name = 'Alice' RETURN n

// ✅ All comparison operators: =, !=, <, >, <=, >=
MATCH (n:Person) WHERE n.age >= 25 AND n.age <= 40 RETURN n

// ✅ Logical operators: AND, OR, NOT
MATCH (n:Person) WHERE n.age > 25 AND n.city = 'NYC' RETURN n
MATCH (n:Person) WHERE n.age < 20 OR n.age > 60 RETURN n
MATCH (n:Person) WHERE NOT n.retired = true RETURN n

// ✅ IS NULL / IS NOT NULL
MATCH (n:Person) WHERE n.email IS NULL RETURN n
MATCH (n:Person) WHERE n.phone IS NOT NULL RETURN n

// ✅ IN operator with lists
MATCH (n:Person) WHERE n.name IN ['Alice', 'Bob', 'Charlie'] RETURN n
MATCH (n:Person) WHERE n.age IN [25, 30, 35] RETURN n

// ✅ Regular expression matching (=~)
MATCH (n:Person) WHERE n.name =~ 'A.*' RETURN n
MATCH (n:Person) WHERE n.email =~ '.*@example.com' RETURN n

// ✅ String matching operators
MATCH (n:Person) WHERE n.name STARTS WITH 'A' RETURN n
MATCH (n:Person) WHERE n.email ENDS WITH '@example.com' RETURN n
MATCH (n:Person) WHERE n.name CONTAINS 'li' RETURN n

// ✅ Complex boolean expressions with combinations
MATCH (n:Person) WHERE n.age > 25 AND n.age < 35 AND n.email IS NOT NULL RETURN n
MATCH (n:Person) WHERE n.name IN ['Alice', 'Bob'] AND n.age > 28 RETURN n
MATCH (n:Person) WHERE n.name =~ 'A.*' AND n.age = 30 RETURN n

// ✅ Parenthesized expressions for operator precedence
MATCH (n:Person) WHERE (n.age < 26 OR n.age > 35) AND n.email IS NOT NULL RETURN n
MATCH (n:Person) WHERE ((n.age < 28 OR n.age > 35) AND n.email IS NOT NULL) OR (n.name CONTAINS 'li' AND n.age = 35) RETURN n

// ✅ Pattern predicates - existence checks
MATCH (n:Person) WHERE (n)-[:KNOWS]->() RETURN n // n has outgoing KNOWS relationship
MATCH (n:Person) WHERE (n)<-[:KNOWS]-() RETURN n // n has incoming KNOWS relationship
MATCH (n:Person) WHERE (n)-[:KNOWS]-() RETURN n // n has any KNOWS relationship (bidirectional)
MATCH (n:Person) WHERE NOT (n)-[:KNOWS]->() RETURN n // n doesn't know anyone

// ✅ Pattern predicates with specific endpoints
MATCH (alice:Person {name: 'Alice'}), (bob:Person {name: 'Bob'})
WHERE (alice)-[:KNOWS]->(bob)
RETURN alice, bob

// ✅ Pattern predicates with multiple relationship types
MATCH (n:Person) WHERE (n)-[:KNOWS|LIKES]->() RETURN n

// ✅ Pattern predicates combined with property filters
MATCH (n:Person) WHERE n.name STARTS WITH 'A' AND (n)-[:KNOWS]->() RETURN n

UNWIND Clause

// ✅ Unwind literal list
UNWIND [1, 2, 3] AS x RETURN x

// ✅ Unwind string list
UNWIND ['a', 'b', 'c'] AS letter RETURN letter

// ✅ Unwind with range function
UNWIND range(1, 10) AS num RETURN num

// ✅ Unwind null (produces no rows)
UNWIND null AS x RETURN x

// ✅ Unwind empty list (produces no rows)
UNWIND [] AS x RETURN x

// ✅ Combine with MATCH
MATCH (n:Person) UNWIND [1, 2, 3] AS x RETURN n.name, x

// ✅ Unwind property arrays (arrays stored as node properties)
MATCH (n:Person) WHERE n.name = 'Alice'
UNWIND n.hobbies AS hobby
RETURN n.name, hobby

// ✅ Unwind across multiple nodes
MATCH (n:Person)
UNWIND n.hobbies AS hobby
RETURN n.name, hobby
ORDER BY n.name, hobby

// ✅ Multiple UNWIND clauses (chained unwinding)
UNWIND [[1, 2], [3, 4]] AS innerList
UNWIND innerList AS num
RETURN num
// Returns: 1, 2, 3, 4

Limitations:

• ❌ UNWIND with WITH clause (WITH clause not implemented yet)

CREATE Clause

// ✅ Create single vertex with properties
CREATE (n:Person {name: 'Alice', age: 30})

// ✅ Create multiple vertices
CREATE (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'})

// ✅ Create vertex without label (defaults to "Vertex")
CREATE (n {name: 'Test'})

// ✅ Create relationship between new vertices
CREATE (a:Person {name: 'Alice'})-[r:KNOWS]->(b:Person {name: 'Bob'})

// ✅ Create relationship with properties
CREATE (a)-[r:WORKS_AT {since: 2020}]->(c:Company {name: 'ArcadeDB'})

// ✅ Create chained paths
CREATE (a)-[:KNOWS]->(b)-[:KNOWS]->(c)

// ✅ MATCH + CREATE (create with context)
MATCH (a:Person {name: 'Alice'})
CREATE (a)-[r:KNOWS]->(b:Person {name: 'Bob'})

// ✅ CREATE without RETURN (returns created elements)
CREATE (n:Person {name: 'Alice'})

Limitations:

• ❌ CREATE with variable-length patterns

RETURN Clause

// ✅ Return variables
MATCH (n:Person) RETURN n

// ✅ Return multiple variables
MATCH (a)-[r]->(b) RETURN a, r, b

// ✅ Return property projections
MATCH (n:Person) RETURN n.name, n.age

// ✅ Return with aliases
MATCH (n:Person) RETURN n.name AS personName

// ✅ Return all: RETURN *
MATCH (n:Person) RETURN *

// ✅ Return expressions with functions
MATCH (n:Person) RETURN abs(n.age), sqrt(n.value)

// ✅ Return aggregation functions
MATCH (n:Person) RETURN count(n), sum(n.age), avg(n.age), min(n.age), max(n.age)

// ✅ Return count(*)
MATCH (n:Person) RETURN count(*)

// ✅ Return collect() aggregation
MATCH (n:Person) RETURN collect(n.name) AS names

// ✅ Return Cypher-specific functions
MATCH (n:Person) RETURN id(n), labels(n), keys(n)
MATCH (a)-[r]->(b) RETURN type(r), startNode(r), endNode(r)

// ✅ Standalone expressions (without MATCH)
RETURN abs(-42), sqrt(16)

Limitations:

• ❌ DISTINCT: RETURN DISTINCT n.name
• ❌ Map projections: RETURN n{.name, .age}
• ❌ List comprehensions: RETURN [x IN list | x.name]
• ❌ CASE expressions
• ❌ Arithmetic expressions: RETURN n.age * 2

COLLECT Aggregation

// ✅ Collect values into a list
MATCH (n:Person) RETURN collect(n.name) AS names

// ✅ Collect with implicit GROUP BY
MATCH (p:Person)-[:LIVES_IN]->(c:City)
RETURN c.name AS city, collect(p.name) AS residents
ORDER BY city

// ✅ Collect numbers
MATCH (n:Person) RETURN collect(n.age) AS ages

// ✅ Collect from empty results (returns empty list)
MATCH (n:Person) WHERE n.name = 'DoesNotExist'
RETURN collect(n.name) AS names
// Returns: []

// ✅ Multiple aggregations
MATCH (n:Person)
RETURN count(n) AS total, collect(n.name) AS allNames, avg(n.age) AS avgAge

Status: ✅ Fully Implemented - COLLECT aggregation with implicit GROUP BY support
Test Coverage: 4 tests in OpenCypherCollectUnwindTest.java

ORDER BY, SKIP, LIMIT

// ✅ ORDER BY single property
MATCH (n:Person) RETURN n ORDER BY n.age

// ✅ ORDER BY ascending (default)
MATCH (n:Person) RETURN n ORDER BY n.name ASC

// ✅ ORDER BY descending
MATCH (n:Person) RETURN n ORDER BY n.age DESC

// ✅ ORDER BY multiple properties
MATCH (n:Person) RETURN n ORDER BY n.age DESC, n.name ASC

// ✅ SKIP results
MATCH (n:Person) RETURN n SKIP 5

// ✅ LIMIT results
MATCH (n:Person) RETURN n LIMIT 10

// ✅ Combined: ORDER BY + SKIP + LIMIT (pagination)
MATCH (n:Person) RETURN n ORDER BY n.age SKIP 10 LIMIT 5

// ✅ With WHERE clause
MATCH (n:Person) WHERE n.age > 28
RETURN n.name ORDER BY n.age DESC

✅ Write Operations (Fully Implemented)

All write operations are fully implemented with automatic transaction handling:

SET Clause

// ✅ Set single property
MATCH (n:Person {name: 'Alice'}) SET n.age = 31

// ✅ Set multiple properties
MATCH (n:Person) WHERE n.name = 'Alice' SET n.age = 31, n.city = 'NYC'

// ✅ Set property to expression result
MATCH (n:Person) SET n.updated = true

// ✅ Automatic transaction handling
// - Creates transaction if none exists
// - Reuses existing transaction when already active
// - Auto-commits when command completes (if transaction was created)

Status: ✅ Fully Implemented - SetStep with automatic transaction handling
Test Coverage: 11 tests in OpenCypherSetTest.java

DELETE Clause

// ✅ Delete vertices
MATCH (n:Person {name: 'Alice'}) DELETE n

// ✅ DETACH DELETE (delete node and its relationships first)
MATCH (n:Person {name: 'Alice'}) DETACH DELETE n

// ✅ Delete relationships
MATCH (a)-[r:KNOWS]->(b) DELETE r

// ✅ Delete multiple elements
MATCH (a:Person)-[r]->(b:Company) DELETE a, r, b

// ✅ Automatic transaction handling
// - Creates transaction if none exists
// - Reuses existing transaction when already active
// - Auto-commits when command completes (if transaction was created)

Status: ✅ Fully Implemented - DeleteStep with automatic transaction handling
Test Coverage: 9 tests in OpenCypherDeleteTest.java

MERGE Clause

// ✅ MERGE single node (find or create)
MERGE (n:Person {name: 'Alice'})

// ✅ MERGE with relationship patterns
MERGE (a:Person {name: 'Alice'})-[r:KNOWS]->(b:Person {name: 'Bob'})

// ✅ MERGE complex patterns
MERGE (a)-[r:WORKS_AT]->(c:Company {name: 'ArcadeDB'})

// ✅ Chained MERGE after MATCH (uses bound variables)
MATCH (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'})
MERGE (a)-[r:KNOWS]->(b)

// ✅ ON CREATE SET - executed when creating new elements
MERGE (n:Person {name: 'Charlie'})
ON CREATE SET n.created = true, n.timestamp = 1234567890

// ✅ ON MATCH SET - executed when matching existing elements
MERGE (n:Person {name: 'Alice'})
ON MATCH SET n.lastSeen = 1234567890, n.visits = 5

// ✅ ON CREATE SET and ON MATCH SET combined
MERGE (n:Person {name: 'David'})
ON CREATE SET n.created = true, n.count = 1
ON MATCH SET n.count = 2, n.updated = true

// ✅ ON CREATE/MATCH SET with property references
MATCH (existing:Person {name: 'Alice'})
MERGE (n:Person {name: 'Bob'})
ON CREATE SET n.age = existing.age

// ✅ ON CREATE/MATCH SET on relationships
MATCH (a:Person), (b:Company)
MERGE (a)-[r:WORKS_AT]->(b)
ON CREATE SET r.since = 2020, r.role = 'Engineer'
ON MATCH SET r.promoted = true

// ✅ Automatic transaction handling
// - Creates transaction if none exists
// - Reuses existing transaction when already active
// - Auto-commits when command completes (if transaction was created)

Status: ✅ Fully Implemented - MergeStep with automatic transaction handling and ON CREATE/MATCH SET support
Test Coverage: 14 tests (5 in OpenCypherMergeTest.java, 9 in OpenCypherMergeActionsTest.java)
Expression Evaluation: Supports literals (string, number, boolean, null), variable references, and property access (e.g., existing.age)

❌ Not Implemented

Query Composition

Aggregation Functions

Note: Core aggregation functions (count, sum, avg, min, max, collect) fully implemented and tested. Bridge to SQL aggregation functions complete. ✅ Implicit GROUP BY fully implemented - non-aggregated expressions in RETURN automatically become grouping keys.

String Functions

Note: All string functions implemented and tested. Functions with "Bridge Available" use SQL function bridge.

Math Functions

Note: All math functions available through SQL function bridge. Tested: abs(), sqrt().

Node/Relationship Functions

Path Functions

Note: Path extraction functions (nodes, relationships, length) fully implemented. Requires path matching to be fully functional.

List Functions

Note: All list functions fully implemented and tested. List literals ([1,2,3]) are supported.

Type Conversion Functions

Note: All type conversion functions fully implemented. toBoolean() supports numbers (0=false, non-zero=true), strings ("true"/"false"), and booleans.

Date/Time Functions

WHERE Enhancements

Expression Features

Note: List literals and type conversion functions are fully implemented and tested.

✅ GROUP BY (Implicit Grouping) - Fully Implemented

OpenCypher uses implicit GROUP BY semantics: when a RETURN clause contains both aggregation functions and non-aggregated expressions, the non-aggregated expressions automatically become grouping keys.

Examples

// ✅ Group by city and count people
MATCH (n:Person)
RETURN n.city, count(n)
// Groups by n.city, counts people in each group

// ✅ Group by multiple keys
MATCH (n:Person)
RETURN n.city, n.department, count(n), avg(n.age)
// Groups by (city, department) combination

// ✅ Multiple aggregations per group
MATCH (n:Person)
RETURN n.city, count(n) AS total, avg(n.age) AS avgAge,
       min(n.age) AS minAge, max(n.age) AS maxAge
// Groups by city with multiple aggregations

// ✅ Pure aggregation (no grouping)
MATCH (n:Person)
RETURN count(n), avg(n.age)
// Single aggregated result across all rows

Implementation Details

• GroupByAggregationStep: Efficient grouping with hash-based aggregation
• Supports all aggregation functions: count, count(*), sum, avg, min, max
• Multiple grouping keys: Can group by any combination of expressions
• Multiple aggregations: Can compute multiple aggregations per group
• Test Coverage: 5 comprehensive tests in OpenCypherGroupByTest.java

Status: ✅ Fully Implemented & Tested

Advanced Features

🗺️ Implementation Roadmap

Phase 4: Write Operations ✅ COMPLETED (2026-01-12)

Target: Q1 2026 → ✅ COMPLETED
Focus: Complete basic write operations

• ✅ Completed: SetStep for SET clause
• ✅ Completed: DeleteStep for DELETE/DETACH DELETE
• ✅ Completed: MergeStep for MERGE operations

Phase 6 (Current): WHERE Clause Enhancements ✅ COMPLETED (2026-01-12)

Target: Q1 2026 → ✅ COMPLETED
Focus: Enhance WHERE clause with logical operators, NULL checks, IN, and regex

• ✅ Completed: Boolean expression framework (BooleanExpression interface)
• ✅ Completed: Logical operators (AND, OR, NOT)
• ✅ Completed: IS NULL / IS NOT NULL support
• ✅ Completed: All comparison operators (=, !=, <, >, <=, >=)
• ✅ Completed: Complex boolean expressions with operator precedence
• ✅ Completed: FilterPropertiesStep integration
• ✅ Completed: IN operator with list literal parsing
• ✅ Completed: Regular expression matching (=~) with pattern compilation
• ✅ Completed: Comprehensive WHERE clause tests (15 tests)

Phase 5: Aggregation & Functions ✅ COMPLETED (2026-01-12)

Target: Q1 2026 → ✅ COMPLETED
Focus: Add aggregation support and common functions

• ✅ Completed: Expression evaluation framework
• ✅ Completed: Function executor interface & factory
• ✅ Completed: Bridge to all ArcadeDB SQL functions (100+ functions)
• ✅ Completed: Cypher-specific functions (id, labels, type, keys, properties, startNode, endNode)
• ✅ Completed: Parser integration for function invocations (including count(*) special handling)
• ✅ Completed: Execution pipeline integration
• ✅ Completed: Aggregation function special handling (AggregationStep)
• ✅ Completed: Core aggregation functions (count, count(*), sum, avg, min, max)
• ✅ Completed: Math functions (abs, sqrt) + bridge to all SQL math functions
• ✅ Completed: Relationship functions (startNode, endNode)
• ✅ Completed: Standalone expressions (RETURN without MATCH)
• ✅ Completed: All 14 function tests passing

Remaining for future phases:

• Add DISTINCT in RETURN
• ✅ Completed: GROUP BY aggregation grouping (Phase 8)
• Support for nested function calls
• Arithmetic expressions (n.age * 2)

Phase 6: Advanced Queries

Target: Q3 2026
Focus: Query composition and advanced features

• Implement WITH clause (query chaining)
• ✅ Completed: MERGE with ON CREATE/ON MATCH SET (Phase 7)
• ✅ Completed: OPTIONAL MATCH (Phase 7)
• ✅ Completed: String matching (STARTS WITH, ENDS WITH, CONTAINS) (Phase 7)
• ✅ Completed: UNWIND clause (2026-01-12)
• ✅ Completed: COLLECT aggregation function (2026-01-12)

Phase 7: Optimization & Performance

Target: Q1-Q4 2026
Focus: Cost-Based Query Optimizer inspired to the most advanced Cypher implementations

Status: ✅ Phase 4 Complete (Integration & Testing - 2026-01-13)

• ✅ Phase 1: Infrastructure (2026-01-13)
  • Statistics collection (TypeStatistics, IndexStatistics, StatisticsProvider)
  • Cost model with selectivity heuristics
  • Logical plan extraction from AST
  • Physical plan representation
  • 24 unit tests passing
• ✅ Phase 2: Physical Operators (2026-01-13)
  • NodeByLabelScan, NodeIndexSeek, ExpandAll, ExpandInto operators implemented
  • FilterOperator for WHERE clause evaluation
  • Abstract base classes for operator tree structure
  • All operators support cost/cardinality estimation
• ✅ Phase 3: Optimization Rules (2026-01-13)
  • AnchorSelector: Intelligent anchor node selection (index vs scan)
  • IndexSelectionRule: Decides between index seek and full scan (10% selectivity threshold)
  • FilterPushdownRule: Analyzes filter placement for optimal execution
  • JoinOrderRule: Reorders relationship expansions by estimated cardinality
  • ExpandIntoRule: ⭐ KEY OPTIMIZATION - Detects bounded patterns for 5-10x speedup
  • CypherOptimizer: Main orchestrator coordinating all optimization
  • 40 optimizer tests passing (7 integration + 33 unit tests)
• ✅ Phase 4: Integration & Testing (2026-01-13)
  • Wired CypherOptimizer into CypherExecutionPlanner
  • Hybrid execution model: Physical operators for MATCH, execution steps for RETURN/ORDER BY
  • Conservative rollout with comprehensive guard conditions (shouldUseOptimizer)
  • Bug Fixes: RID dereferencing, NodeHashJoin null values, index creation timing, cross-type relationship direction handling 🎉
  • Test Results: 273/273 passing (100% ✅), all tests passing!
  • Improvement: +23 tests fixed total (8 schema errors, 2 multiple MATCH, 3 named paths, 8 property constraints, 1 aggregation, 1 cross-type relationship)

Impact Achieved:

• 10-100x speedup expected on complex queries with indexes
• Optimizer enabled for simple read-only MATCH queries with labeled nodes
• Graceful fallback to traditional execution for unsupported patterns

Phase 4 Achievements:

• ✅ Seamless integration with existing execution pipeline
• ✅ Backward compatible (4-parameter constructor maintained)
• ✅ Fixed critical RID dereferencing bug in physical operators
• ✅ Conservative guard conditions prevent optimizer use on unsupported patterns:
  • Multiple MATCH clauses (Cartesian products)
  • Unlabeled nodes
  • Named path variables
  • Property constraints (pattern inline properties like {name: 'Alice'})
  • Aggregation functions (count, sum, avg, min, max, collect)
  • OPTIONAL MATCH
  • Write operations (CREATE, MERGE, DELETE, SET)
• ✅ All physical operator tests passing (8/8)
• ✅ 100% test pass rate (273/273) 🎉
• ✅ Fixed cross-type relationship direction handling in ExpandAll operator
• ✅ Comprehensive documentation (PHASE_4_COMPLETION.md)

Phase 5: Optimizer Coverage Expansion (Planned)

Target: Q1-Q2 2026
Focus: Expand optimizer to handle more query patterns

Planned Features:

• Multiple MATCH clause support (Cartesian products with NodeHashJoin)
• Named path variable support in optimizer
• OPTIONAL MATCH optimizer integration
• Write operation optimizer support (CREATE/MERGE after MATCH)
• Pattern predicate optimization
• EXPLAIN command for query plan visualization
• Performance benchmarks and validation
• Query plan caching

Future Phases

• UNION/UNION ALL
• Shortest path algorithms
• CALL procedures
• Subqueries
• Full function library

All Tests Fixed! 🎉

Note: All 23 pre-existing issues from Phase 3 have been successfully fixed in Phase 4!

Fixed in Phase 4 (10 tests):

• ✅ 8 tests with property constraints (excluded from optimizer)
• ✅ 1 test with aggregation (excluded from optimizer)
• ✅ 1 test with cross-type relationship (fixed ExpandAll direction handling)

Note: All 273 tests now pass! The optimizer handles simple read-only MATCH queries, while complex queries use the traditional execution path.

🧪 Test Coverage

Overall: 273/273 tests passing (100%) 🎉 - All tests passing!

Phase 4 Improvements:

• +23 tests fixed (8 schema errors, 2 multiple MATCH, 3 named paths, 8 property constraints, 1 aggregation, 1 cross-type relationship)
• From 250/273 (91.6%) → 273/273 (100%) 🎉
  Result: All tests passing!

Test Files

opencypher/src/test/java/com/arcadedb/opencypher/
├── OpenCypherBasicTest.java                 # Engine registration, basic queries
├── OpenCypherCreateTest.java                # CREATE clause tests
├── OpenCypherRelationshipTest.java          # Relationship pattern tests
├── OpenCypherTraversalTest.java             # Path traversal tests
├── OpenCypherOrderBySkipLimitTest.java      # ORDER BY, SKIP, LIMIT
├── OpenCypherExecutionTest.java             # Query execution tests
├── OpenCypherSetTest.java                   # SET clause tests
├── OpenCypherDeleteTest.java                # DELETE clause tests
├── OpenCypherMergeTest.java                 # MERGE clause tests (basic)
├── OpenCypherMergeActionsTest.java          # MERGE with ON CREATE/MATCH SET (NEW)
├── OpenCypherFunctionTest.java              # Function & aggregation tests
├── OpenCypherWhereClauseTest.java           # WHERE clause logical operators
├── OpenCypherOptionalMatchTest.java         # OPTIONAL MATCH with WHERE scoping
├── OpenCypherMatchEnhancementsTest.java     # Multiple MATCH, unlabeled patterns, named paths
├── OpenCypherVariableLengthPathTest.java    # Named paths for variable-length relationships
├── OpenCypherTransactionTest.java           # Automatic transaction handling
├── OpenCypherPatternPredicateTest.java      # Pattern predicates in WHERE
├── OpenCypherGroupByTest.java               # Implicit GROUP BY with aggregations
├── OpenCypherCollectUnwindTest.java         # COLLECT aggregation and UNWIND clause (NEW)
├── OrderByDebugTest.java                    # Debug tests
├── ParserDebugTest.java                     # Parser tests
└── optimizer/
    ├── CypherOptimizerIntegrationTest.java  # Optimizer integration tests (NEW)
    ├── AnchorSelectorTest.java              # Anchor selection tests (NEW)
    └── rules/
        ├── IndexSelectionRuleTest.java      # Index selection tests (NEW)
        └── ExpandIntoRuleTest.java          # ExpandInto tests (NEW)

🏗️ Architecture

Parser (ANTLR4-based)

Query String → Cypher25Lexer → Cypher25Parser → Parse Tree
                                                     ↓
                                            CypherASTBuilder (Visitor)
                                                     ↓
                                              CypherStatement (AST)

Files:

• Cypher25Lexer.g4 - Lexical grammar (official Cypher 2.5)
• Cypher25Parser.g4 - Parser grammar (official Cypher 2.5)
• Cypher25AntlrParser.java - Parser wrapper
• CypherASTBuilder.java - ANTLR visitor → AST transformer
• CypherErrorListener.java - Error handling

Execution Engine (Step-based)

CypherStatement → CypherExecutionPlanner → Execution Plan (Step Chain)
                                                     ↓
                                          CypherExecutionPlan.execute()
                                                     ↓
                                              ResultSet (lazy)

Execution Steps:

• MatchNodeStep - Fetch nodes by type/label
• MatchRelationshipStep - Traverse relationships
• ExpandPathStep - Variable-length path expansion
• FilterPropertiesStep - WHERE clause filtering
• CreateStep - CREATE vertices/edges
• SetStep - SET clause (update properties) ✅
• DeleteStep - DELETE clause (remove nodes/edges) ✅
• MergeStep - MERGE clause (upsert) ✅
• AggregationStep - Aggregation functions ✅ NEW
• ProjectReturnStep - RETURN projection (with expression evaluation) ✅
• UnwindStep - UNWIND clause (list expansion) ✅ NEW
• OrderByStep - Result sorting
• SkipStep - Skip N results
• LimitStep - Limit N results

Missing Steps:

• WithStep - WITH clause (query chaining)
• OptionalMatchStep - OPTIONAL MATCH
• GroupByStep - GROUP BY aggregation grouping

🚀 Phase 7 Implementation (January 2026)

New Features Added

This phase focused on enhancing MATCH clause capabilities and WHERE scoping:

1. ✅ Multiple MATCH Clauses

   • Support for multiple MATCH clauses in a single query
   • Cartesian product or chained matching
   • Example: MATCH (a:Person) MATCH (b:Company) RETURN a, b

2. ✅ Patterns Without Labels

   • Support for unlabeled patterns that match all vertices
   • Uses ChainedIterator to iterate all vertex types
   • Example: MATCH (n) WHERE n.age > 25 RETURN n

3. ✅ Named Paths (Single and Variable-Length)

   • Store path as TraversalPath object for both single and variable-length patterns
   • Access path properties: length(), getVertices(), getEdges(), getStartVertex(), getEndVertex()
   • Single edge: MATCH p = (a)-[r:KNOWS]->(b) RETURN p
   • Variable-length: MATCH p = (a)-[:KNOWS*1..3]->(b) RETURN p
   • Note: Variable-length queries have a duplication bug (pre-existing, unrelated to path implementation)

4. ✅ OPTIONAL MATCH

   • Implements LEFT OUTER JOIN semantics
   • Returns NULL for unmatched patterns
   • Uses SingleRowInputStep for proper data flow
   • Example: MATCH (a:Person) OPTIONAL MATCH (a)-[r]->(b) RETURN a, b

5. ✅ WHERE Clause Scoping for OPTIONAL MATCH

   • WHERE clauses are now properly scoped to their containing MATCH clause
   • For OPTIONAL MATCH, WHERE filters the optional match results but preserves rows where the match failed (with NULL values)
   • Example: MATCH (a:Person) OPTIONAL MATCH (a)-[r]->(b) WHERE b.age > 20 RETURN a, b
   • All people are returned; only matches passing the filter show b values, others get NULL

6. ✅ String Matching Operators

   • Implemented STARTS WITH, ENDS WITH, and CONTAINS operators
   • Native string matching without regex overhead
   • Example: MATCH (n:Person) WHERE n.name STARTS WITH 'A' RETURN n
   • Example: MATCH (n:Person) WHERE n.email ENDS WITH '@example.com' RETURN n
   • Example: MATCH (n:Person) WHERE n.name CONTAINS 'li' RETURN n

7. ✅ Parenthesized Boolean Expressions

   • Support for complex nested parentheses with proper operator precedence
   • Enables explicit control over AND/OR evaluation order
   • Example: MATCH (n) WHERE (n.age < 26 OR n.age > 35) AND n.email IS NOT NULL RETURN n
   • Example: MATCH (n) WHERE ((n.age < 28 OR n.age > 35) AND n.email IS NOT NULL) OR (n.name CONTAINS 'li' AND n.age = 35) RETURN n

8. ✅ Automatic Transaction Handling

   • All write operations (CREATE, SET, DELETE, MERGE) now handle transactions automatically
   • If no transaction is active, operations create, execute, and commit their own transaction
   • If a transaction is already active, operations reuse it (don't commit)
   • Proper rollback on errors for self-managed transactions
   • Example: CREATE (n:Person {name: 'Alice'}) - automatically creates and commits transaction
   • Example: Within database.transaction(() -> { CREATE...; SET...; }) - reuses existing transaction

Architecture Changes

• OptionalMatchStep: New execution step implementing optional matching with NULL emission
• CypherExecutionPlan: Enhanced to handle multiple MATCH clauses, source variable binding, and scoped WHERE application
• MatchNodeStep: Added ChainedIterator for unlabeled pattern support
• CypherASTBuilder:
  • Fixed path variable extraction in visitPattern() and scoped WHERE extraction in visitMatchClause()
  • Added findParenthesizedExpression() to recursively parse parenthesized boolean expressions
  • Implemented string matching operators (STARTS WITH, ENDS WITH, CONTAINS)
• MatchClause: Added whereClause field to store WHERE clauses scoped to each MATCH
• ExpandPathStep: Fixed to use pathVariable instead of relVar for named variable-length paths
• StringMatchExpression: New expression class for string matching operations
• CreateStep: Added automatic transaction handling - detects active transactions, creates/commits as needed
• SetStep: Added automatic transaction handling with proper rollback on errors
• DeleteStep: Added automatic transaction handling for deletions
• MergeStep: Added automatic transaction handling for upsert operations

Test Coverage

• Added 32 new tests (107 → 139 tests)
• OpenCypherOptionalMatchTest: 6 tests for OPTIONAL MATCH with WHERE scoping
• OpenCypherMatchEnhancementsTest: 7 tests for multiple MATCH and unlabeled patterns
• OpenCypherVariableLengthPathTest: 2 tests for named paths with variable-length relationships
• OpenCypherWhereClauseTest: Enhanced with 8 new tests for string matching and parenthesized expressions
• OpenCypherTransactionTest: 9 new tests for automatic transaction handling
• All 139 tests passing

🐛 Known Issues

1. Variable-length path queries return duplicates - Pre-existing bug unrelated to named path implementation

   • Status: Variable-length traversal (-[*1..3]->) returns duplicate results
   • Example: MATCH (a)-[:KNOWS*2]->(b) may return the same path multiple times
   • Named path variable storage works correctly (path object is not null)
   • Workaround: Use LIMIT or deduplicate results in application logic
   • Note: Single-hop relationships do not have this issue

2. Arithmetic expressions not yet supported - RETURN n.age * 2 not working

   • Status: Function expressions working, arithmetic operators need parser support
   • Workaround: Use SQL functions or pre-compute values

📝 How to Report Issues

If you encounter issues with the OpenCypher implementation:

1. Check this status document to see if the feature is implemented
2. Create an issue at: https://github.com/arcadedata/arcadedb/issues
3. Include:
   • Your Cypher query
   • Expected behavior
   • Actual behavior (error message or incorrect results)
   • ArcadeDB version
   • Label with cypher tag

🤝 Contributing

We welcome contributions to the OpenCypher implementation!

High-Priority Contributions Needed:

1. ✅ SetStep implementation - COMPLETED
2. ✅ DeleteStep implementation - COMPLETED
3. ✅ Expression evaluator - COMPLETED (functions bridge)
4. ✅ Aggregation functions - COMPLETED (count, sum, avg, min, max)
5. ✅ Function expression parsing - COMPLETED (with count(*) support)
6. ✅ Logical operators in WHERE - COMPLETED (AND, OR, NOT)
7. ✅ IS NULL / IS NOT NULL in WHERE - COMPLETED
8. ✅ IN operator - COMPLETED (with list literal parsing)
9. ✅ Regular expression matching - COMPLETED (=~ operator with patterns)
10. ✅ String matching operators - COMPLETED (STARTS WITH, ENDS WITH, CONTAINS)
11. ✅ Parenthesized boolean expressions - COMPLETED (complex nested expressions)
12. ✅ GROUP BY aggregation grouping - COMPLETED (implicit grouping)
13. Arithmetic expressions - Support n.age * 2, n.value + 10, etc.
14. Nested function support - Enable function composition
15. DISTINCT in RETURN - Remove duplicate results

Getting Started:

1. Review CypherASTBuilder.java - See what's parsed
2. Check CypherExecutionPlan.java - See execution flow
3. Look at existing steps in executor/steps/ - Follow patterns
4. Write tests first in test/java/com/arcadedb/opencypher/
5. Implement execution step
6. Update this status document

Coding Standards:

• Use Low-Level Java optimizations
• Minimize garbage collection pressure
• All tests must pass (120/120)
• Add tests for new features

📚 References

• Cypher Query Language: https://opencypher.org/
• Cypher 2.5 Grammar: Used by this implementation
• ArcadeDB Documentation: https://docs.arcadedb.com/