UNDF: UNDF-2026-000000430

janusgraph-0001: MultiCondition extends ArrayList — O(C²) condition deduplication in query builder

Severity

MEDIUM

Location

janusgraph-core/src/main/java/org/janusgraph/graphdb/query/condition/MultiCondition.java Line 29 — class declaration

janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java Line 339 — call site

Description

MultiCondition<E> is the base class for both And and Or condition nodes in JanusGraph's query tree. It extends ArrayList<Condition<E>>, inheriting ArrayList.contains() which is an O(N) linear scan.

QueryUtil.addConstraint() (line 339) calls conditions.contains(pc) before adding a new PredicateCondition to guard against duplicates. This method is called once per predicate being added to a query's condition tree.

For a query with C conditions, building the tree costs O(1 + 2 + … + C) = O(C²) comparisons. Since JanusGraph queries often carry dozens of predicate conditions (property filters, label constraints, range queries), this is a realistic quadratic bottleneck in the query planning path.

Defective Code

// MultiCondition.java:29
public abstract class MultiCondition<E extends JanusGraphElement>
        extends ArrayList<Condition<E>> implements Condition<E> {
    // inherits O(N) contains() from ArrayList
}

// QueryUtil.java:339 — called once per predicate addition
if (!conditions.contains(pc)) conditions.add(pc);

Root Cause

Extending ArrayList for a semantic "set of conditions" conflates ordered list storage with membership testing. The design choice to back conditions with a List means every duplicate-check is O(C).

Fix

Change MultiCondition to maintain a parallel HashSet for O(1) membership testing:

public abstract class MultiCondition<E extends JanusGraphElement>
        extends ArrayList<Condition<E>> implements Condition<E> {

    private final Set<Condition<E>> conditionSet = new HashSet<>();

    @Override
    public boolean add(Condition<E> condition) {
        assert condition != null;
        if (conditionSet.add(condition)) {
            return super.add(condition);
        }
        return false;
    }

    @Override
    public boolean contains(Object o) {
        return conditionSet.contains(o);
    }
}

This keeps insertion order (for any callers that iterate conditions in order) while making contains() O(1). The QueryUtil.addConstraint() call site requires no change.

Alternatively, replace the backing structure with LinkedHashSet entirely and change the getChildren() return type — but that is a larger API change.

Complexity

Operation	Before	After
`conditions.contains(pc)` per call	O(C)	O(1)
Build C-condition query tree	O(C²)	O(C)

2.8 KiB Raw Permalink Blame History