GraphBench q5/q6/q7@100k: two-star star-join loses to Memgraph; array-side seeded traversal is the lever (0.725 ms floor vs 6.5 ms today)

Aperta
  • Qualcosa non va?
#2,101 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
pandas, python
Ambito
data, performance

Direzione di ricerca

Start by reading _connected_join_two_star_fast_grouped_count and _connected_join_two_star_fused_polars, then inspect _resident_seed_indexes and the existing CSR/array-level traversal paths. The issue calls for a full array-side two-star specialization across pandas, polars, and polars-gpu, with admission and decline paths and behavior-boundary plus route-off tests. Validate correctness and measure the full benchmark board; done means the specialization is safe and improves the target queries without regressing neighboring cells.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

The gap

On the shipped board (f283a305e, 100k), GFQL's best engine loses to Memgraph on three cells of the same shape, and to Kuzu on q8:

q GFQL best Kuzu Memgraph Neo4j
q5 7.57 12.65 3.95 8.96
q6 8.65 16.07 5.14 22.94
q7 5.62 8.18 3.74 140.18
q8 13.10 9.03 7316 3767

q5/q6/q7 are one shape: a two-pattern star join on p (HAS_INTEREST + LIVES_IN) with predicates and a grouped count. Route: _connected_join_two_star_fast_grouped_count → _connected_join_two_star_fused_polars.

Where the time goes (dgx, pinned 5-9,15-19, POLARS_MAX_THREADS=20)

component q5 q6 q7
wall 6.64 7.59 4.90
polars collect 5.76 6.85 4.47
Python dispatch 1.43 1.43 1.56

Even at zero dispatch, q5 is 5.76 vs Memgraph 3.95 — dispatch alone cannot close it.

The lever, measured

Memgraph drives from the selective seed (Interest has 41 rows; interest = 'fine dining' reaches ~6k persons by index). Our plan joins 250,067 HAS_INTEREST edges against a 50,000-row person set.

measurement ms
seed-driven floor (hand numpy, whole q5, answer 48) 0.725
product's own AdjacencyIndex lookup, one hop 0.111
product's Plottable-level hop around that same index 3.982

The CSR index is excellent; the g.hop() wrapper carries ~3.9 ms that eats the entire prize. So this is not "the index is missing" — it's that this shape never consults it at array level. Related: the standing selective-traversal gap (CSR engages via g.hop(), not through chain/Cypher).

Two attempts that FAILED — please read before retrying

Both were correct (answers byte-identical, verified by sha256 across all five queries on indexed graphs with engagement counted) and both were slower:

attempt result
reorder the right arm's semi-joins by selectivity (leaf before shared domain) q6 +9.5% vs a +0.1% A/A control
narrow the shared alias to adjacency-derived candidates before its predicates q5 +8%

Two implementation traps found on the way, worth keeping:

  • edges[col].to_numpy() converts a 2.77M-row string column per query → 6.5 → 126 ms. Gather only the candidate rows.
  • pl.col(x).is_in(<6k array>) is not the cost (a semi-join rewrite measured identical); the whole-column conversion was.

Lesson: partial integration into the existing polars plan captures none of the prize. Polars already pushes those semi-joins down, so the added lookup/join costs more than the scan it saves. The 0.725 ms floor comes from computing the whole query array-side.

What would actually be needed

A full array-side two-star specialization: leaf lookups on both arms via the CSR, intersection, shared predicates evaluated on the gathered candidate rows, then the count. Reuse _resident_seed_indexes (already validates fingerprint + identity and returns None when stale/absent, so results can never change — only speed).

Scope honestly:

  • ~150–250 lines plus admission and decline paths
  • ×3 engines: the fused path is polars-only; the board publishes pandas, polars and polars-gpu, and the sibling-specialization rule requires all of them
  • behaviour-boundary tests + route-off coverage
  • a full board re-measure, because two correct changes already regressed neighbouring cells

Unproven risk: the floor is real, but no integration has yet landed near it. Both attempts had overhead consume the theoretical win. A third could too, and that only becomes visible once the whole route exists.

Estimated payoff if it lands: q5/q6/q7 at roughly 2 ms (0.7 array + 1.4 dispatch) against Memgraph's 3.95 — loss → win, with q8 plausibly following.

Deferred deliberately: the 0.60 performance release is shipping and this is not a regression, it is an unrealised win.

🤖 Generated with Claude Code

https://claude.ai/code/session_012Me1E7ZdDuGqJGu3mMEzhp

Lingua principale
Python
Stelle
2.6k
Fork
229
Merge medio
1g 5h
PR unite (30g)
99

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di graphistry/pygraphistry

Tutte le issue di graphistry/pygraphistry

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.