Optimization: Large `CASE WHEN` with unreachable branches causes severe execution-time slowdown

[Mrhs121]

Description

Summary

LadybugDB currently shows a severe performance gap for semantically equivalent queries when a WHERE predicate is expressed as a large CASE WHEN chain containing many unreachable branches.

The problematic pattern is a searched CASE WHEN expression with many branches whose WHEN condition is always false, followed by a branch whose WHEN condition is always true. Although the whole expression is equivalent to either true or a simple predicate such as n.id >= 0, execution time grows roughly linearly with the number of unreachable CASE WHEN branches.

This is similar to conditional simplification issues seen in other query engines: constant boolean branches inside CASE WHEN should be pruned during optimization/binding instead of being evaluated for every row.

This kind of branch pruning is common in OLAP query engines. For example, Spark Catalyst has a dedicated SimplifyConditionals optimizer rule for simplifying conditional expressions. A generated analytical query may contain expressions such as CASE WHEN false AND expensive_predicate THEN ... WHEN true OR other_predicate THEN ... END after predicate expansion, query templating, or rule-based rewrites. Engines typically simplify the constant false / true conditions and remove unreachable branches before execution, so the scan does not evaluate dead conditional logic for every input row.

Env

• Ladybug version: latest code
• Platform: macOS arm64

Reproduction dataset

CREATE NODE TABLE LargeCaseNode(
  id INT64,
  grp INT64,
  payload STRING,
  PRIMARY KEY(id)
);

UNWIND RANGE(1, 100000) AS i
CREATE (:LargeCaseNode {
  id: i,
  grp: i % 10,
  payload: 'payload-' + CAST(i AS STRING)
});

All generated nodes satisfy:

n.id >= 0

Baseline query 1: full scan

PROFILE
MATCH (n:LargeCaseNode)
RETURN COUNT(*) AS cnt;

Equivalent large CASE WHEN query 1

The following query is logically equivalent to the full-scan baseline above, because every initial WHEN condition is always false, and the final WHEN condition is always true.

PROFILE
MATCH (n:LargeCaseNode)
WHERE CASE
  WHEN NOT(NOT(false AND coalesce(n.id = n.id, true))) THEN false
  -- repeated 1000 times
  WHEN NOT(NOT(true OR coalesce(n.id = n.id, true))) THEN true
  ELSE false
END
RETURN COUNT(*) AS cnt;

Semantically, this should simplify to:

PROFILE
MATCH (n:LargeCaseNode)
WHERE true
RETURN COUNT(*) AS cnt;

or simply:

PROFILE
MATCH (n:LargeCaseNode)
RETURN COUNT(*) AS cnt;

Baseline query 2: simple predicate

PROFILE
MATCH (n:LargeCaseNode)
WHERE n.id >= 0
RETURN COUNT(*) AS cnt;

Equivalent large CASE WHEN query 2

This query is logically equivalent to the simple-predicate baseline above.

PROFILE
MATCH (n:LargeCaseNode)
WHERE CASE
  WHEN NOT(NOT(false AND coalesce(n.id = n.id, true))) THEN false
  -- repeated 1000 times
  WHEN NOT(NOT(true OR coalesce(n.id = n.id, true))) THEN n.id >= 0
  ELSE false
END
RETURN COUNT(*) AS cnt;

Semantically, this should simplify to:

PROFILE
MATCH (n:LargeCaseNode)
WHERE n.id >= 0
RETURN COUNT(*) AS cnt;

Observed results before optimization

Using the Python API and taking the median over 5 runs:

Query	Branches	Median compile time	Median execution time	Median wall time
baseline_scan.cypher	0	0.071 ms	0.286 ms	0.387 ms
large_case_when_true_10.cypher	10	1.240 ms	17.305 ms	18.516 ms
large_case_when_true_100.cypher	100	8.541 ms	148.373 ms	157.233 ms
large_case_when_true_500.cypher	500	41.451 ms	747.800 ms	790.674 ms
large_case_when_true_1000.cypher	1000	82.802 ms	1545.152 ms	1629.710 ms
baseline_predicate.cypher	0	0.149 ms	0.514 ms	0.690 ms
large_case_when_predicate_10.cypher	10	1.128 ms	17.423 ms	18.643 ms
large_case_when_predicate_100.cypher	100	8.242 ms	149.192 ms	158.080 ms
large_case_when_predicate_500.cypher	500	42.044 ms	753.650 ms	797.064 ms
large_case_when_predicate_1000.cypher	1000	84.227 ms	1553.363 ms	1640.631 ms

Key slowdowns:

• large_case_when_true_1000 vs baseline_scan:
  • 1545.152 ms / 0.286 ms ≈ 5402x slower in execution time
• large_case_when_predicate_1000 vs baseline_predicate:
  • 1553.363 ms / 0.514 ms ≈ 3022x slower in execution time

The execution time grows roughly linearly with the number of unreachable CASE WHEN branches.

Expected behavior

The optimizer/binder should simplify constant boolean conditions inside CASE WHEN before execution.

Safe simplifications include:

false AND x -> false
true OR x   -> true
NOT(NOT x)  -> x

For searched CASE WHEN, the following transformations are also safe:

WHEN false THEN ...  -> remove branch
WHEN NULL THEN ...   -> remove branch, because NULL does not match searched CASE
WHEN true THEN expr  -> replace the CASE with expr and discard later branches

After simplification, the large CASE WHEN examples above should be equivalent to their simple baselines at execution time.

Validation after implementing binder-side simplification

After adding a binder-side simplification pass for safe boolean identities and searched CASE WHEN branch pruning, the same benchmark produced:

Query	Branches	Median compile time	Median execution time	Median wall time
baseline_scan.cypher	0	0.063 ms	0.309 ms	0.387 ms
large_case_when_true_10.cypher	10	0.966 ms	0.272 ms	1.252 ms
large_case_when_true_100.cypher	100	7.897 ms	0.347 ms	8.353 ms
large_case_when_true_500.cypher	500	39.542 ms	0.397 ms	40.216 ms
large_case_when_true_1000.cypher	1000	82.269 ms	0.349 ms	83.261 ms
baseline_predicate.cypher	0	0.088 ms	0.437 ms	0.553 ms
large_case_when_predicate_10.cypher	10	1.008 ms	0.447 ms	1.471 ms
large_case_when_predicate_100.cypher	100	8.097 ms	0.518 ms	8.694 ms
large_case_when_predicate_500.cypher	500	39.999 ms	0.523 ms	40.785 ms
large_case_when_predicate_1000.cypher	1000	80.475 ms	0.494 ms	81.487 ms

The execution-time cost is effectively eliminated:

• large_case_when_true_1000:
  • before: 1545.152 ms
  • after: 0.349 ms
  • speedup: ≈ 4427x
• large_case_when_predicate_1000:
  • before: 1553.363 ms
  • after: 0.494 ms
  • speedup: ≈ 3144x

The remaining wall-clock growth is almost entirely compile-time cost from parsing/binding a large expression, which is expected. The execution time is now close to the simple equivalent baselines.

Proposal

Add a targeted binder-side expression simplification pass. The pass will run after expression binding and before the existing full constant-folding step.

The goal is not to introduce a broad algebraic optimizer, but to handle the high-impact conditional simplifications that are safe under Cypher's three-valued boolean semantics.

The proposed implementation will:

1. Apply three-valued-logic-safe boolean identities:

   • false AND x -> false
   • x AND false -> false
   • true AND x -> x
   • x AND true -> x
   • true OR x -> true
   • x OR true -> true
   • false OR x -> x
   • x OR false -> x
   • NOT true -> false
   • NOT false -> true
   • NOT NOT x -> x

2. Simplify searched CASE WHEN expressions:

   • remove WHEN false branches
   • remove WHEN NULL branches, because NULL does not match in searched CASE WHEN
   • replace the whole CASE with the THEN expression on the first WHEN true
   • return the ELSE expression if all branches are removed

3. Preserve SQL/Cypher three-valued logic by intentionally avoiding unsafe rewrites:

   • do not rewrite NULL AND x -> NULL
   • do not rewrite NULL OR x -> NULL
   • do not rewrite x OR NOT x -> true
   • do not rewrite x AND NOT x -> false

Why this is safe

For searched CASE WHEN, only TRUE matches. Both FALSE and NULL fall through to later branches or ELSE.

The boolean identities above are valid under three-valued logic. They also preserve short-circuit semantics: removing the right-hand side of false AND x or true OR x is safe because the result does not depend on x.

Impact

This optimization prevents large unreachable CASE WHEN branches from being evaluated per row. It significantly improves execution time for queries generated by tools or fuzzers that introduce redundant boolean expressions inside CASE WHEN, while preserving correctness under NULL semantics.

[hiSandog]

This is specific enough for a focused regression test around Optimization: Large CASE WHEN with unreachable branches causes severe execution-time slowdown. The test should set up the failing path, assert the intended behavior, and include the current error or bad output so the fix is not only verified manually. CASE WHEN is a useful concrete anchor because it is named directly in the report.