Repository navigation
perf(ldbc): close performance gap vs lance-csr on IC5/IC7/IC13 #1457
Description
Benchmarking LDBC SNB complex reads shows lance-csr ahead of ladybug on 3 queries (IC5, IC7, IC13), with IC7 at ~11x. Full comparison and plans below — looking for ladybug-side optimizer/runtime improvements to close the gap.
Complex queries where lance-csr dominates ladybug
Comparison of lance_csr/0.2.0.txt vs ladybugdb/0.22.1.txt
(median ms, lower is better):
| query | lance_csr 0.2.0 | ladybug 0.22.1 | winner | speedup |
|---|---|---|---|---|
| IC7 | 53.39 | 608.66 | lance | 11.40x |
| IC13 | 11.40 | 51.54 | lance | 4.52x |
| IC5 | 154.50 | 446.91 | lance | 2.89x |
Full 14-query totals: lance_csr/0.2.0.txt 22.05s vs ladybugdb/0.22.1.txt 17.18s
wall time; sum of medians ~1502ms vs ~1836ms.
Plans via uv run:
- lance:
CypherEngine.explain(q,params)->graph_logical_plan - ladybug:
LBUG_DUMP_LOGICAL=1 uv run python->LOGICAL PLAN (before/after optimization)
Sources: lance_csr/query.py vs ladybugdb/query.py (run_query5/7/13).
1. IC5 — New groups (2.9x): looks identical, 5 subtle lines differ
| # | lance lance_csr/query.py:run_query5 |
ladybug ladybugdb/query.py:run_query5 |
|---|---|---|
| 1 | MATCH (person:Person {ID: $personId})-[:knows*1..2]-(friend) |
MATCH (person:Person {ID: $personId})-[:knows*1..2]-(friend:Person) |
| 2 | WHERE NOT person = friend |
WHERE person.ID <> friend.ID |
| 3 | WITH DISTINCT friend |
WITH DISTINCT friend |
| 4 | MATCH (friend)<-[membership:hasMember]-(forum) |
MATCH (friend)<-[membership:hasMember]-(forum:Forum) |
| 5 | WHERE membership.joinDate > $minDate |
WHERE membership.joinDate > $minDate |
| 6 | WITH forum, collect(friend) AS friends |
WITH forum, collect(friend.ID) AS friends |
| 7 | OPTIONAL MATCH (friend)<-[:postHasCreator]-(post)<-[:containerOf]-(forum) |
OPTIONAL MATCH (friend:Person)<-[:postHasCreator]-(post:Post)<-[:containerOf]-(forum) |
| 8 | WHERE friend IN friends |
WHERE friend.ID IN friends |
| 9-12 | WITH forum, count(post)... RETURN... ORDER BY... LIMIT 20 |
WITH forum, count(post)... RETURN... ORDER BY... LIMIT 20 |
Why: per ladybugdb/query.py header — lists hold one type so collect(friend.ID),
nodes compared by ID (person.ID <> friend.ID), messages/rel targets need
:Post/:Forum/:Person labels. Logic is the same.
// lance graph_logical_plan:
Limit->Sort->Project->Project->OptionalMatch -> Project->Filter->Expand[hasMember]
-> Distinct->Project->Filter->VariableLengthExpand[knows 1..2]->ScanByLabel(person)
// ladybug logical (after opt):
PROJECTION->ORDER_BY->AGGREGATE[postCount]->HASH_JOIN[LEFT forum._ID]
-> AGGREGATE[friends]->HASH_JOIN[friend._ID]
-> DISTINCT -> FILTER[person<>friend] -> HASH_JOIN -> SCAN[Person]
-> SEMI_MASKER -> RECURSIVE_EXTEND[VAR_LEN_JOINS]+PATH_PROPERTY_PROBE -> PK_SCAN(person)
-> HASH_JOIN -> SCAN[Forum] -> FILTER[joinDate] -> EXTEND[hasMember]
-> FILTER[LIST_CONTAINS(friends,friend.ID)] -> HASH_JOIN -> EXTEND[postHasCreator]
-> EXTEND[containerOf] -> EXPRESSIONS_SCAN/DISTINCT[friends,forum]
Same logic, different runtime — lance lowers to DataFusion over Arrow/Lance CSR;
ladybug stays volcano-style RECURSIVE_EXTEND+FLATTEN+HASH_JOIN+SEMI_MASKER+ACCUMULATE
plus LIST_CONTAINS+EXPRESSIONS_SCAN for the OPTIONAL side.
2. IC7 — Recent likers (11.4x): 1 MATCH vs 3 MATCHes
| lance (14 lines, 1 traversal) | ladybug (18 lines, 3 traversals) |
|---|---|
MATCH (person:Person {ID:$personId})<-[:postHasCreator|commentHasCreator]-(message)<-[like:likePost|likeComment]-(liker:Person) |
MATCH (person:Person {ID:$personId})<-[:postHasCreator|:commentHasCreator]-(message:Post:Comment)<-[like:likePost|:likeComment]-(liker:Person) |
WITH liker, message, like.creationDate AS likeTime, person |
WITH person, liker, max(like.creationDate) AS likeTime |
ORDER BY likeTime DESC, message.ID ASC |
MATCH (person)<-[:postHasCreator|:commentHasCreator]-(likedMessage:Post:Comment)<-[latestLike:likePost|:likeComment]-(liker) |
WITH liker, head(collect({msg:message, likeTime:likeTime})) AS latestLike, person |
WHERE latestLike.creationDate = likeTime |
RETURN liker.ID ... latestLike.likeTime ... latestLike.msg.ID ... |
WITH person, liker, likeTime, min(likedMessage.ID) AS latestMessageId |
coalesce(latestLike.msg.content, latestLike.msg.imageFile) |
MATCH (person)<-[:postHasCreator|:commentHasCreator]-(message:Post:Comment) WHERE message.ID=latestMessageId |
toInteger(duration.inSeconds(datetime(msg.creationDate), datetime(likeTime)).seconds/60.0) |
WITH ... to_epoch_ms(message.creationDate) AS messageTime, to_epoch_ms(likeTime) AS likeTimeMs |
NOT ((liker)-[:knows]-(person)) AS isNew |
NOT EXISTS {MATCH (liker)-[:knows]-(person)} AS isNew |
Key rewrites forced by ladybug/Kuzu (ladybugdb/query.py header):
ORDER BY inside WITH needs LIMIT, so IC7 finds each liker's latest like with max()
- tie-break with
min(ID)+ re-match message;to_epoch_msinstead of
duration.inSeconds;EXISTS{}instead of pattern predicate.
// lance:
Limit -> Sort -> Project -> OptionalMatch[isNew]
-> Project -> Sort -> Project -> Union[Post|Comment x likePost|likeComment]
-> Expand -> Expand -> ScanByLabel(person)
// ladybug (after opt):
LIMIT -> MULTIPLICITY_REDUCER -> CROSS_PRODUCT
-> ORDER_BY -> HASH_JOIN[MARK EXISTS{knows}]
-> FILTER -> HASH_JOIN
-> AGGREGATE[likeTime=max] -> QUERY_PRIMARY_KEY_LOOKUP -> EXTEND[like] -> EXTEND[creator]
-> AGGREGATE[latestMessageId=min] -> HASH_JOIN -> SCAN[Comment|Post] -> EXTEND x2
-> HASH_JOIN -> SCAN[Comment|Post] -> EXTEND[creator]
Single traversal + Sort+head(collect) vs re-probing Comment|Post 3x.
3. IC13 — Single shortest path (4.5x): shortestPath() vs * SHORTEST
| lance | ladybug |
|---|---|
MATCH |
MATCH (person1:Person {ID:$person1Id}), (person2:Person {ID:$person2Id}) |
(person1:Person {ID:$person1Id}), |
OPTIONAL MATCH path=(person1)-[:knows* SHORTEST 1..30]-(person2) |
(person2:Person {ID:$person2Id}), |
RETURN CASE WHEN path IS NULL THEN -1 ELSE length(path) END AS shortestPathLength |
path = shortestPath((person1)-[:knows*]-(person2)) |
|
RETURN CASE path IS NULL WHEN true THEN -1 ELSE length(path) END AS shortestPathLength |
Why: ladybug/Kuzu has no shortestPath()/allShortestPaths() — uses
* SHORTEST/* ALL SHORTEST with finite upper bound (30 max). OPTIONAL MATCH
for -1 null case.
// lance:
Project -> ShortestPath{min:1,max:4294967295,all:false,dir:Undirected,rel:knows}
-> Join[Cross] -> ScanByLabel(person1 ID=1131) + ScanByLabel(person2 ID=1979...)
// ladybug (after opt):
PROJECTION -> HASH_JOIN[LEFT]
-> CROSS_PRODUCT -> PK_SCAN(person1) + PK_SCAN(person2)
-> HASH_JOIN -> PATH_PROPERTY_PROBE -> SEMI_MASKER -> RECURSIVE_EXTEND[SINGLE_SP_PATHS]
-> SEMI_MASKER -> DISTINCT -> EXPRESSIONS_SCAN[person1._ID,person2._ID]
Native ShortestPath on CSR vs RECURSIVE_EXTEND+PATH_PROPERTY_PROBE+LEFT_JOIN scaffolding.
Activity
[-]Close performance gap vs lance-csr on IC5/IC7/IC13[/-][+]perf(ldbc): close performance gap vs lance-csr on IC5/IC7/IC13[/+]zahariash commentedon Nov 2, 2026
On IC13, almost all of the time is the BFS: in
PROFILE,RECURSIVE_EXTENDtakes 40.4 of 48.8 ms, while theOPTIONAL MATCH,PATH_PROPERTY_PROBEand LEFT hash join take under 1 ms together. The BFS is slow for two reasons.Per-neighbor visibility check. Since #459,
OnDiskGraphNbrScanState::InnerIterator::nextcallsNodeTable::isVisible()for every neighbor it returns. Each call takes three mutexes:getNumNodeGroups(),getNodeGroup(), then the node group'schunkedGroupslock. IC13 reads about 361k adjacency entries, so that's ~1.1M lock/unlock pairs per query. All persons sit in one node group, so every worker thread contends for the same mutexes, and IC13 gets slower as threads are added. SF1 on a 16-core x86 box, builds ofmainat f90add1, median ms:mainBoth variants return the same results as
main, including around deleted and uncommitted nodes, but they are only experiments. The check guards against #456 and has to stay, and taking the locks once per chunk isn't enough, since every chunk still takes the same mutex.One-sided search. Person 2 is 4 hops from person 1, and by depth 3 a search from person 1 alone has read every person's adjacency list. lance-csr 0.2.0, the 11.4 ms above, also searched from one end. lance-csr added bidirectional search in 0.3.0 (lance-csr#54) and is at 1.1 ms in the current results (0.5.1); Neo4j's
shortestPathis bidirectional too. From both ends, this pair needs about 5.6k adjacency entries before the two depth-2 frontiers meet. Matching that needs a bidirectional single-pair* SHORTEST/* ALL SHORTESTinfunction/gds.A smaller cost: with
OPTIONAL MATCH ... path IS NULL, the planner keepsSINGLE_SP_PATHS, which records parents for the path, while the non-optionallength(path)form getsSINGLE_SP_DESTINATIONS. That's about 4 ms of IC13's 30 at 1 thread.