Edge materialization from a mixed index scans the full adjacency when the edge label has a sort key (seek is defeated)

[batrived]

Summary

When a mixed-index query returns edges and those edges are materialized, JanusGraph resolves each result edge via RelationIdentifierUtils.findEdge. If the edge label has a user-defined sort key, this per-edge lookup cannot seek to the target edge and instead scans the source vertex's entire adjacency for that label/direction, filtering in memory. Retrieval degrades from the documented O(log k) (Technical Limitations) to O(k) in the adjacent vertex's degree — per result edge.

For a query returning N edges on a high-degree, sort-keyed label, this is an N × O(degree) cost that is invisible in .profile() (it is folded into the backend-query node).

Environment

• JanusGraph: 1.0.0
• Storage backend: any (the behavior is backend-independent)
• Index backend: Elasticsearch (mixed index)

Reproduction

1. Define an edge label E with a sort key on some property p.
2. Create many parallel E edges from a single source vertex (so that vertex has a high E out-degree).
3. Define a mixed (Elasticsearch) index over an edge property q.
4. Run and profile a mixed-index edge query:

   g.E().has("q", someValue).profile()

Observed: the Elasticsearch query itself is fast (verifiable by issuing the equivalent query directly to Elasticsearch), but the traversal is far slower. The excess time is spent materializing each result edge, and is hidden inside the backend-query metric node of the profile.

The total cost is multiplicative in two factors: total ≈ (number of matched results N) × (per-edge findEdge cost).

• N — number of results from the index. Each relation id returned by Elasticsearch triggers one findEdge, and these are executed sequentially as the SubqueryIterator stream is consumed (.map(edgeIDConversionFct), no batching). So even ignoring the per-edge scan, N sequential storage round-trips are paid, and latency grows linearly with N.
• Per-edge findEdge cost — O(out-degree). As described below, the sort key defeats the seek, so each findEdge scans the source vertex's full adjacency for that label/direction (plus incident-vertex loads).

Both factors compound: latency scales with the number of matched results and with the out-degree of the label on the matched vertices.

Root cause

The edge column key is ordered:

[relationType + direction][ sort key ][ ADJACENT_ID ][ JANUSGRAPHID (relationId) ]

findEdgeRelations builds a vertex-centric query pinning type, direction, adjacent(other), and has(JANUSGRAPHID, relationId) — but it has no value for the sort-key property, because the RelationIdentifier only carries outVertexId / typeId / relationId / inVertexId.

• RelationIdentifierUtils.findEdgeRelations — janusgraph-core/.../graphdb/relations/RelationIdentifierUtils.java:69-87
• EdgeSerializer.getQuery walks the extended sort key in order and breaks at the first unpinned position — janusgraph-core/.../graphdb/database/EdgeSerializer.java:~423-461, fallback at :487-503. The sort key sits at position 0, ahead of ADJACENT_ID and JANUSGRAPHID; because the query cannot pin it, the loop breaks immediately and the SliceQuery collapses to the [type+direction] prefix — the whole adjacency for that label/direction. This happens before any multiplicity- or consistency-dependent component is reached, so it is independent of the label's multiplicity and consistency.

Why the information to fix this is already available

The mixed index that produced the result already contains the sort-key field value whenever the sort-key property is one of the indexed fields (common — it is frequently the field being queried). Today IndexSerializer.query fetches only element ids (string2ElementId) and discards field values, so the sort-key value that would enable a seek is thrown away.

Proposal

When materializing edges from a mixed-index hit, carry the sort-key field value(s) from the index into findEdge, so the per-edge vertex-centric query can pin the sort key and perform a true single-column seek.

Sketch of touch points:

1. IndexSerializer.query — optionally retrieve the sort-key field(s) from the index and emit (RelationIdentifier, sortKeyValues) instead of bare ids. Gate: only when every component of type.getSortKey() is an indexed field of that mixed index.
2. StandardJanusGraphTx.edgeIDConversionFct — pass sortKeyValues into a new findEdge overload.
3. SubqueryIterator — propagate the richer carrier through the map chain.
4. RelationIdentifierUtils.findEdgeRelations — new overload that adds the sort-key values as constraints (query.has(sortKeyProp, value)) ahead of ADJACENT_ID/JANUSGRAPHID, restoring the seek. Existing (no-value) path preserved as fallback.

Correctness considerations / open questions

• Requires all sort-key components present and in order (a partial prefix still breaks the seek).
• Composite sort keys, DESC sort order, and the partitioned-vertex swap in findEdgeRelations must compose correctly.
• The getPreviousID() matching in findRelation and the FORK path (which deliberately omits the JANUSGRAPHID bound) need separate handling — a sort-key-only seek under FORK must not miss forked versions.
• Sort-key value round-tripping: the value returned by the index backend must encode to exactly the column representation the sort key expects, or the slice bounds are wrong. This is the highest-risk area and needs thorough tests.

Alternative / companion: auto-include sort-key fields in the mixed index

The proposal above is the "use the sort-key value at materialization" half. Its precondition — that the sort-key value is retrievable from the index hit — can be guaranteed at index-build time rather than left to chance: when a mixed index covers an edge label, automatically include that label's sort-key propertie(s) in the index, so every indexed edge document carries the value needed to seek.

Two variants, cheap → thorough:

1. Store-only (preferred). The sort key does not need to be searchable to enable the seek — only readable back. Store the sort-key value as a retrieval-only field (e.g. a stored field / doc value, not analyzed/indexed). Minimal mapping overhead, no change to query semantics.
2. Fully indexed. Add the sort-key key as a normal indexed field. Heavier, but also makes it queryable. Overkill if the only goal is enabling the seek.

This turns the fix from "opportunistic — works only if the user happened to index the sort key" into "the framework ensures the value is present," making it automatic.

Caveats specific to this approach:

• Mixed indexes are not strictly label-scoped. A graph index over a property may cover multiple edge labels (unless indexOnly(label) is used), each with its own (or no) sort key. The auto-added set is therefore the union of sort-key properties across all labels the index covers, computed from those labels rather than a single label.
• Existing indexes require a reindex to backfill the added field(s); the improvement applies immediately only to newly created indexes.
• Storage / write overhead: each indexed edge document gains extra field(s). Store-only (variant 1) minimizes this.
• Same all-components + exact-encoding requirement as the query-side change: every sort-key component must be present and must round-trip to the column-key representation.
• The sort-key property must be representable in the index backend (true for scalar keys; exotic datatypes may be edge cases).

Combined, the index side (ensure sort-key values are stored) and the query side (pin them at materialization to seek) make the optimization automatic and always-available.

[batrived]

@porunov @li-boxuan Please take a look.