Self-pointing Cypher pattern causes lance-graph to hang indefinitely for high cardinality datasets

I've created a second benchmark to push lance-graph to its breaking point, and it breaks :)

This one uses the well-known LDBC SNB (SF1) dataset, and the query suite and results are here - should be quite easy to reproduce.

Issue

The query pattern that breaks is Q30 in the suite: "Are there comments replying to posts created by the same person?". Basically, a self-reference to a node variable in a query.

Attempt 1

Here's how it looks in Neo4j/Kuzu/Ladybug:

// Are there comments replying to posts created by the same person?
MATCH (c:Comment)-[:commentHasCreator]->(p:Person)<-[:postHasCreator]-(post:Post)<-[:replyOfPost]-(c)
RETURN COUNT(DISTINCT c.ID) > 0 AS has_self_reply;

The above pattern doesn't work in lance-graph, because of #108: COUNT(DISTINCT x.id) isn't yet supported in lance-graph.

Attempt 2

I then tried just returning the distinct IDs to take them to an external system (e.g., Polars) to aggregate. Not ideal from a performance standpoint, as this requires materializing a lot of results.

But this doesn't work either.
Trying:

MATCH (c:Comment)-[:commentHasCreator]->(p:Person)<-[:postHasCreator]-(post:Post)<-[:replyOfPost]-(c)
RETURN DISTINCT c.id AS id

Gives:

Traceback (most recent call last):
  File "/Users/prrao/code/graph-benchmark-ldbc-snb/lance_graph/query.py", line 685, in <module>
    main(selected_queries)
    ~~~~^^^^^^^^^^^^^^^^^^
  File "/Users/prrao/code/graph-benchmark-ldbc-snb/lance_graph/query.py", line 678, in main
    func(cfg, datasets)
    ~~~~^^^^^^^^^^^^^^^
  File "/Users/prrao/code/graph-benchmark-ldbc-snb/lance_graph/query.py", line 606, in run_query30
    return _execute_distinct_count(
        cfg,
    ...<5 lines>...
        as_bool=True,
    )
  File "/Users/prrao/code/graph-benchmark-ldbc-snb/lance_graph/query.py", line 135, in _execute_distinct_count
    result = execute_query(query, cfg, datasets)
  File "/Users/prrao/code/graph-benchmark-ldbc-snb/lance_graph/query.py", line 108, in execute_query
    result = cypher.with_config(cfg).execute(datasets)
ValueError: Query planning error: Failed to join source to relationship: Schema error: No field named posthascreator_1__dst. Valid fields are c__id, c__creationdate, c__locationip, c__browserused, c__content, c__length, comment.id, comment.creationdate, comment.locationip, comment.browserused, comment.content, comment.length.

Based on the error message, it seems that the query planner can't handle query patterns that point back to the same variable?

Attempt 3

Finally, I tried rewriting it another way, with an additional WHERE predicate that checks where c1 and c2, so as to force a different query plan.

// Are there comments replying to posts created by the same person?
MATCH (c1:Comment)-[:commentHasCreator]->(p:Person)<-[:postHasCreator]-(post:Post)<-[:replyOfPost]-(c2:Comment)
WHERE c1.id = c2.id
RETURN DISTINCT c1.id AS id

This doesn't work either: Due to extremely high cardinality in these intermediate paths, this query never returns (it just hangs).

As can be seen, this issue is multifold and has a more complex cause.

How to reproduce

The LDBC SNB SF1 dataset was used for this experiment. The dataset can be downloaded via the script provided here.

Once the dataset is downloaded locally, the code to build the graph in lance-graph and query it are available in the lance_graph directory of the project, here.

# Ingest dataset into in lance_graph
cd lance_graph
uv run build_graph.py

# Uncomment L649 of query.py and aim to run Q30 as follows
uv run query.py "30"

Looking

Yeah the concern is also that Ctrl + C in the terminal doesn't kill the running process to stop the query execution. Once it hangs, I have to open another terminal and use the kill -9 command to manually stop the Python process. Seems like a many-layered issue for sure.

explain on Q30 gave me

| logical_plan       | Distinct:                                                                                                                                                                                                                                                                                        |
|                    |   Projection: c1__id AS id                                                                                                                                                                                                                                                                       |
|                    |     Filter: c1__id = c2__id                                                                                                                                                                                                                                                                      |
|                    |       Inner Join: replyofpost_1__src = c2__id                                                                                                                                                                                                                                                    |
|                    |         Inner Join: post__id = replyofpost_1__dst                                                                                                                                                                                                                                                |
|                    |           Inner Join: posthascreator_1__src = post__id                                                                                                                                                                                                                                           |
|                    |             Inner Join: p__id = posthascreator_1__dst                                                                                                                                                                                                                                            |
|                    |               Inner Join: commenthascreator_1__dst = p__id                                                                                                                                                                                                                                       |
|                    |                 Inner Join: c1__id = commenthascreator_1__src                                                                                                                                                                                                                                    |
|                    |                   Projection: comment.id AS c1__id, comment.creationdate AS c1__creationdate, comment.locationip AS c1__locationip, comment.browserused AS c1__browserused, comment.content AS c1__content, comment.length AS c1__length                                                         |
|                    |                     TableScan: comment                                                                                                                                                                                                                                                           |
|                    |                   Projection: commenthascreator.src AS commenthascreator_1__src, commenthascreator.dst AS commenthascreator_1__dst                                                                                                                                                               |
|                    |                     TableScan: commenthascreator                                                                                                                                                                                                                                                 |
|                    |                 Projection: person.id AS p__id, person.firstname AS p__firstname, person.lastname AS p__lastname, person.gender AS p__gender, person.birthday AS p__birthday, person.creationdate AS p__creationdate, person.locationip AS p__locationip, person.browserused AS p__browserused   |
|                    |                   TableScan: person                                                                                                                                                                                                                                                              |
|                    |               Projection: posthascreator.src AS posthascreator_1__src, posthascreator.dst AS posthascreator_1__dst                                                                                                                                                                               |
|                    |                 TableScan: posthascreator                                                                                                                                                                                                                                                        |
|                    |             Projection: post.id AS post__id, post.imagefile AS post__imagefile, post.creationdate AS post__creationdate, post.locationip AS post__locationip, post.browserused AS post__browserused, post.language AS post__language, post.content AS post__content, post.length AS post__length |
|                    |               TableScan: post                                                                                                                                                                                                                                                                    |
|                    |           Projection: replyofpost.src AS replyofpost_1__src, replyofpost.dst AS replyofpost_1__dst                                                                                                                                                                                               |
|                    |             TableScan: replyofpost                                                                                                                                                                                                                                                               |
|                    |         Projection: comment.id AS c2__id, comment.creationdate AS c2__creationdate, comment.locationip AS c2__locationip, comment.browserused AS c2__browserused, comment.content AS c2__content, comment.length AS c2__length                                                                   |
|                    |           TableScan: comment                                                                                                                                                                                                                                                                     |
| physical_plan      | AggregateExec: mode=FinalPartitioned, gby=[id@0 as id], aggr=[]                                                                                                                                                                                                                                  |
|                    |   CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                                    |
|                    |     RepartitionExec: partitioning=Hash([id@0], 20), input_partitions=20                                                                                                                                                                                                                          |
|                    |       AggregateExec: mode=Partial, gby=[id@0 as id], aggr=[]                                                                                                                                                                                                                                     |
|                    |         ProjectionExec: expr=[c1__id@0 as id]                                                                                                                                                                                                                                                    |
|                    |           CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                            |
|                    |             HashJoinExec: mode=Partitioned, join_type=Inner, on=[(replyofpost_1__src@1, c2__id@0), (c1__id@0, c2__id@0)], projection=[c1__id@0]                                                                                                                                                  |
|                    |               CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                        |
|                    |                 RepartitionExec: partitioning=Hash([replyofpost_1__src@1, c1__id@0], 20), input_partitions=20                                                                                                                                                                                    |
|                    |                   CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                    |
|                    |                     HashJoinExec: mode=Partitioned, join_type=Inner, on=[(post__id@1, replyofpost_1__dst@1)], projection=[c1__id@0, replyofpost_1__src@2]                                                                                                                                        |
|                    |                       CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                |
|                    |                         HashJoinExec: mode=Partitioned, join_type=Inner, on=[(posthascreator_1__src@1, post__id@0)], projection=[c1__id@0, post__id@2]                                                                                                                                           |
|                    |                           CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                            |
|                    |                             RepartitionExec: partitioning=Hash([posthascreator_1__src@1], 20), input_partitions=20                                                                                                                                                                               |
|                    |                               CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                        |
|                    |                                 HashJoinExec: mode=Partitioned, join_type=Inner, on=[(p__id@1, posthascreator_1__dst@1)], projection=[c1__id@0, posthascreator_1__src@2]                                                                                                                         |
|                    |                                   CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                    |
|                    |                                     RepartitionExec: partitioning=Hash([p__id@1], 20), input_partitions=20                                                                                                                                                                                       |
|                    |                                       ProjectionExec: expr=[c1__id@1 as c1__id, p__id@0 as p__id]                                                                                                                                                                                                |
|                    |                                         CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                              |
|                    |                                           HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(p__id@0, commenthascreator_1__dst@1)], projection=[p__id@0, c1__id@1]                                                                                                                            |
|                    |                                             ProjectionExec: expr=[id@0 as p__id]                                                                                                                                                                                                                 |
|                    |                                               DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                                  |
|                    |                                             CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                          |
|                    |                                               HashJoinExec: mode=Partitioned, join_type=Inner, on=[(c1__id@0, commenthascreator_1__src@0)], projection=[c1__id@0, commenthascreator_1__dst@2]                                                                                                    |
|                    |                                                 CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                      |
|                    |                                                   RepartitionExec: partitioning=Hash([c1__id@0], 20), input_partitions=20                                                                                                                                                                        |
|                    |                                                     RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                        |
|                    |                                                       ProjectionExec: expr=[id@0 as c1__id]                                                                                                                                                                                                      |
|                    |                                                         DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                        |
|                    |                                                 CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                      |
|                    |                                                   RepartitionExec: partitioning=Hash([commenthascreator_1__src@0], 20), input_partitions=20                                                                                                                                                      |
|                    |                                                     RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                        |
|                    |                                                       ProjectionExec: expr=[src@0 as commenthascreator_1__src, dst@1 as commenthascreator_1__dst]                                                                                                                                                |
|                    |                                                         DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                        |
|                    |                                   CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                    |
|                    |                                     RepartitionExec: partitioning=Hash([posthascreator_1__dst@1], 20), input_partitions=20                                                                                                                                                                       |
|                    |                                       RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                                      |
|                    |                                         ProjectionExec: expr=[src@0 as posthascreator_1__src, dst@1 as posthascreator_1__dst]                                                                                                                                                                    |
|                    |                                           DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                                      |
|                    |                           CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                            |
|                    |                             RepartitionExec: partitioning=Hash([post__id@0], 20), input_partitions=20                                                                                                                                                                                            |
|                    |                               RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                                              |
|                    |                                 ProjectionExec: expr=[id@0 as post__id]                                                                                                                                                                                                                          |
|                    |                                   DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                                              |
|                    |                       CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                |
|                    |                         RepartitionExec: partitioning=Hash([replyofpost_1__dst@1], 20), input_partitions=20                                                                                                                                                                                      |
|                    |                           RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                                                  |
|                    |                             ProjectionExec: expr=[src@0 as replyofpost_1__src, dst@1 as replyofpost_1__dst]                                                                                                                                                                                      |
|                    |                               DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                                                  |
|                    |               CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                        |
|                    |                 RepartitionExec: partitioning=Hash([c2__id@0, c2__id@0], 20), input_partitions=20                                                                                                                                                                                                |
|                    |                   RepartitionExec: partitioning=RoundRobinBatch(20), input_partitions=1                                                                                                                                                                                                          |
|                    |                     ProjectionExec: expr=[id@0 as c2__id]                                                                                                                                                                                                                                        |
|                    |                       DataSourceExec: partitions=1, partition_sizes=[1]                                                                                                                                                                                                                          |

So, OOM can be attributed to inefficient HashJoins which could be fixed as part of LanceNative Execution strategy

kuzu/ladybug uses factorized vectors and ASP joins hence the low memory footprint

it seems that the query planner can't handle query patterns that point back to the same variable?

I will take a look at this

it seems that the query planner can't handle query patterns that point back to the same variable?

I will take a look at this

Sorry for the delay. Got occupied with something else. I am done with the changes with e2e/integration tests pending. Will make a PR by tmrw

@prrao87

@prrao87 Thanks for bringing up the issue.
@aheev Thanks for raising a PR to help fix it.

Let me think more about the issue and reply in this thread afterwards. At my first glance, the issue actually involves fundamental design options.

@prrao87

Hi @prrao87 @aheev , thanks for your patience. After investigation, let me share my thoughts in detail:

The target natural-language question in GraphRAG is:
“Are there comments replying to posts created by the same person?”

The question is actually a relational query in nature (checking whether two foreign keys are equal, comment.creator_id == post.creator_id), rather than a traversal-based graph query (finding a circular path). Since lance-graph is designed to target SQL execution engines and columnar storage optimizations in lance, we should prefer relational-type queries (but still in the Cypher format) over self-reference graph queries.

To put it in another way, we should reject traversal-heavy queries such as (your attempt 1)

MATCH (c:Comment)-[:commentHasCreator]->(p:Person)<-[:postHasCreator]-(post:Post)<-[:replyOfPost]-(c)
RETURN COUNT(DISTINCT c.ID) > 0 AS has_self_reply;

and instead favor JOIN-friendly queries like

MATCH (c:Comment)-[:commentHasCreator]->(creator:Person),
      (c)-[:replyOfPost]->(post:Post)-[:postHasCreator]->(creator)
RETURN COUNT(DISTINCT c.ID) AS has_self_reply;

Note that the two queries are semantically the same, but they would lead to very different query plans in lance-graph.

At this moment, the JOIN-friendly query also fails due to a duplicate-column issue (shared variables), which we need to resolve so we can run the query 30 in the LDBC benchmark.

@beinan: I think @prrao87 @aheev 's work also indicated that we may need a query rewriter component in the long-term planning, to help users convert queries into lance-graph-friendly queries (instead of rejecting the queries). What do you think?

@ChunxuTang

Thanks @ChunxuTang, makes sense. If the query rewriter is a longer term task, then in the interim, it's still better to outright reject (and inform the user) rather than have a generic error message that doesn't help the user rewrite it in a join-friendly way. Hope that makes sense.

@beinan

Note that the two queries are semantically the same, but they would lead to very different query plans in lance-graph

How exactly 🤔

@beinan: I think @prrao87 @aheev 's work also indicated that we may need a query rewritter component in the long-term planning, to help users convert queries into lance-graph-friendly queries (instead of rejecting the queries). What do you think?

+1 to this

Thanks @ChunxuTang, makes sense. If the query rewriter is a longer term task, then in the interim, it's still better to outright reject (and inform the user) rather than have a generic error message that doesn't help the user rewrite it in a join-friendly way. Hope that makes sense.

Yes, it makes sense to have a more user-friendly error for the self-reference graph queries. Let me create an issue to track that.

Note that the two queries are semantically the same, but they would lead to very different query plans in lance-graph

How exactly 🤔

The first query

MATCH (c:Comment)-[:commentHasCreator]->(p:Person)<-[:postHasCreator]-(post:Post)<-[:replyOfPost]-(c)
RETURN COUNT(DISTINCT c.ID) > 0 AS has_self_reply;

will generate a sequence of Expand operations based on the self-reference.

By contrast, the second query

MATCH (c:Comment)-[:commentHasCreator]->(creator:Person),
      (c)-[:replyOfPost]->(post:Post)-[:postHasCreator]->(creator)
RETURN COUNT(DISTINCT c.ID) AS has_self_reply;

will generate two Expand operations, then a JOIN operation on the comment id and creator id.

Navigation Menu

Repository navigation

Self-pointing Cypher pattern causes lance-graph to hang indefinitely for high cardinality datasets #111

Issue

Attempt 1

Attempt 2

Attempt 3

How to reproduce

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Self-pointing Cypher pattern causes lance-graph to hang indefinitely for high cardinality datasets #111

Description

Issue

Attempt 1

Attempt 2

Attempt 3

How to reproduce

Activity

aheev commented on Jan 29, 2026

prrao87 commented on Jan 29, 2026

aheev commented on Jan 31, 2026

aheev commented on Jan 31, 2026

aheev commented on Feb 3, 2026

ChunxuTang commented on Feb 6, 2026

ChunxuTang commented on Feb 7, 2026

prrao87 commented on Feb 7, 2026

aheev commented on Feb 7, 2026

ChunxuTang commented on Feb 8, 2026

ChunxuTang commented on Feb 8, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions