fix: Reduce number of DB queries needed in ReverseExpand #2567

justincoh · 2025-07-16T16:49:13Z

Description

What problem is being solved?

In the weighted reverse_expand, each individual leaf node kicks off its own independent chain of queries. Each query chain attempts to deduplicate its own work, but for some models these query chains can start to overlap as they move up the graph because they have common ancestors. This model for example, has 3 leaf nodes which all share a common ancestor in document#viewer:

type user
type document
	relations
		define commenter: [user]
		define editor: [user]
		define writer: [user]
		define viewer: writer or editor or commenter
		define owner: [document#viewer]

You can clearly see the common ancestor document#viewer in the graph:

If a user is related to document:a via #commenter, #editor, and #writer, all 3 of those independent branches will attempt to read from the DB to find the common ancestor document#owner@document:a#viewer. That means this query will run 3 times instead of 1.

How is it being solved?

We have an existing jobDedupeMap, but it is scoped within each query chain. So multiple query chains which lead to the same tuples will do duplicate work.

What changes are made to solve it?

Add queryDedupeMap to the ReverseExpandQuery object itself, so all querying routines will be aware of all duplicate work.

References

Review Checklist

I have clicked on "allow edits by maintainers".
I have added documentation for new/changed functionality in this PR or in a PR to openfga.dev [Provide a link to any relevant PRs in the references section above]
The correct base branch is being used, if not main
I have added tests to validate that the change in functionality is working as expected

Summary by CodeRabbit

Refactor
- Improved internal handling of duplicate queries to optimize performance and efficiency. Query deduplication is now managed centrally within the query process, reducing redundant operations during exploration. No changes to user-facing behavior.

coderabbitai · 2025-07-16T16:49:20Z

Important

Review skipped

Auto incremental reviews are disabled on this repository.

Please check the settings in the CodeRabbit UI or the .coderabbit.yaml file in this repository. To trigger a single review, invoke the @coderabbitai review command.

You can disable this status message by setting the reviews.review_status to false in the CodeRabbit configuration file.

Walkthrough

A new queryDedupeMap field was added to the ReverseExpandQuery struct to centralize deduplication logic for queries. The deduplication logic, previously handled by passing a local map through recursive calls, is now managed via this struct-level field and accessed through a receiver method, simplifying function signatures and state management.

Changes

File(s)	Change Summary
pkg/server/commands/reverseexpand/reverse_expand.go	Added `queryDedupeMap *sync.Map` field to `ReverseExpandQuery` struct; initialized in constructor.
pkg/server/commands/reverseexpand/reverse_expand_weighted.go	Refactored deduplication logic: removed local dedupe map, updated method signatures, and converted dedupe check to use struct field.

Sequence Diagram(s)

sequenceDiagram
    participant Caller
    participant ReverseExpandQuery
    participant queryDedupeMap

    Caller->>ReverseExpandQuery: queryForTuples(...)
    ReverseExpandQuery->>ReverseExpandQuery: isDuplicateQuery(...)
    ReverseExpandQuery->>queryDedupeMap: Check/Update dedupe state
    alt Not duplicate
        ReverseExpandQuery->>ReverseExpandQuery: executeQueryJob(...)
    end

Suggested reviewers

cikasfm
adriantam
Vic-Dev

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

🪧 Tips

Chat

There are 3 ways to chat with CodeRabbit:

Review comments: Directly reply to a review comment made by CodeRabbit. Example:
- I pushed a fix in commit <commit_id>, please review it.
- Explain this complex logic.
- Open a follow-up GitHub issue for this discussion.
Files and specific lines of code (under the "Files changed" tab): Tag @coderabbitai in a new review comment at the desired location with your query. Examples:
- @coderabbitai explain this code block.
- @coderabbitai modularize this function.
PR comments: Tag @coderabbitai in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
- @coderabbitai gather interesting stats about this repository and render them as a table. Additionally, render a pie chart showing the language distribution in the codebase.
- @coderabbitai read src/utils.ts and explain its main purpose.
- @coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.
- @coderabbitai help me debug CodeRabbit configuration file.

Support

Need help? Create a ticket on our support page for assistance with any issues or questions.

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

CodeRabbit Commands (Invoked using PR comments)

@coderabbitai pause to pause the reviews on a PR.
@coderabbitai resume to resume the paused reviews.
@coderabbitai review to trigger an incremental review. This is useful when automatic reviews are disabled for the repository.
@coderabbitai full review to do a full review from scratch and review all the files again.
@coderabbitai summary to regenerate the summary of the PR.
@coderabbitai generate docstrings to generate docstrings for this PR.
@coderabbitai generate sequence diagram to generate a sequence diagram of the changes in this PR.
@coderabbitai resolve resolve all the CodeRabbit review comments.
@coderabbitai configuration to show the current CodeRabbit configuration for the repository.
@coderabbitai help to get help.

Other keywords and placeholders

Add @coderabbitai ignore anywhere in the PR description to prevent this PR from being reviewed.
Add @coderabbitai summary to generate the high-level summary at a specific location in the PR description.
Add @coderabbitai anywhere in the PR title to generate the title automatically.

CodeRabbit Configuration File (`.coderabbit.yaml`)

You can programmatically configure CodeRabbit by adding a .coderabbit.yaml file to the root of your repository.
Please see the configuration documentation for more information.
If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: # yaml-language-server: $schema=https://coderabbit.ai/integrations/schema.v2.json

Documentation and Community

Visit our Documentation for detailed information on how to use CodeRabbit.
Join our Discord Community to get help, request features, and share feedback.
Follow us on X/Twitter for updates and announcements.

codecov · 2025-07-16T20:00:01Z

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 90.33%. Comparing base (e383258) to head (4cede70).
Report is 1 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #2567      +/-   ##
==========================================
- Coverage   90.35%   90.33%   -0.02%     
==========================================
  Files         140      140              
  Lines       19583    19589       +6     
==========================================
  Hits        17693    17693              
- Misses       1440     1444       +4     
- Partials      450      452       +2

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

pkg/server/commands/reverseexpand/reverse_expand_weighted.go

cikasfm

You could achieve similar results by using golang.org/x/sync/singleflight; see

openfga/pkg/typesystem/resolver.go

Line 35 in e147e4b

lookupGroup := singleflight.Group{}

pkg/server/commands/reverseexpand/reverse_expand_weighted.go

justincoh requested a review from a team as a code owner July 16, 2025 16:49

justincoh requested review from adriantam and Vic-Dev July 16, 2025 16:50

move ReverseExpand query dedupe map to request object

85d91ce

justincoh force-pushed the feat/reduce-query-count-in-reverse-expand branch from 9d5b4e2 to 85d91ce Compare July 16, 2025 16:51

justincoh added 2 commits July 16, 2025 15:47

consider a query's stack in dedupe logic

241ca00

cleanup

1250092

justincoh commented Jul 16, 2025

View reviewed changes

pkg/server/commands/reverseexpand/reverse_expand_weighted.go Show resolved Hide resolved

Merge branch 'main' into feat/reduce-query-count-in-reverse-expand

95b34e5

elbuo8 reviewed Jul 17, 2025

View reviewed changes

pkg/server/commands/reverseexpand/reverse_expand_weighted.go Outdated Show resolved Hide resolved

cikasfm reviewed Jul 17, 2025

View reviewed changes

pkg/server/commands/reverseexpand/reverse_expand_weighted.go Outdated Show resolved Hide resolved

justincoh and others added 2 commits July 17, 2025 14:09

remove debug log

b8ddbac

Merge branch 'main' into feat/reduce-query-count-in-reverse-expand

4cede70

adriantam reviewed Jul 17, 2025

View reviewed changes

pkg/server/commands/reverseexpand/reverse_expand_weighted.go Show resolved Hide resolved

adriantam approved these changes Jul 17, 2025

View reviewed changes

justincoh merged commit 5478807 into main Jul 17, 2025
27 of 28 checks passed

justincoh deleted the feat/reduce-query-count-in-reverse-expand branch July 17, 2025 23:35

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

fix: Reduce number of DB queries needed in ReverseExpand #2567

fix: Reduce number of DB queries needed in ReverseExpand #2567

Uh oh!

justincoh commented Jul 16, 2025 •

edited by coderabbitai bot

Loading

Uh oh!

coderabbitai bot commented Jul 16, 2025 •

edited

Loading

Review skipped

Chat

Support

CodeRabbit Commands (Invoked using PR comments)

Other keywords and placeholders

CodeRabbit Configuration File (`.coderabbit.yaml`)

Documentation and Community

Uh oh!

codecov bot commented Jul 16, 2025 •

edited

Loading

Uh oh!

Uh oh!

Uh oh!

cikasfm left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

fix: Reduce number of DB queries needed in ReverseExpand #2567

fix: Reduce number of DB queries needed in ReverseExpand #2567

Uh oh!

Conversation

justincoh commented Jul 16, 2025 • edited by coderabbitai bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

What problem is being solved?

How is it being solved?

What changes are made to solve it?

References

Review Checklist

Summary by CodeRabbit

Uh oh!

coderabbitai bot commented Jul 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Review skipped

Walkthrough

Changes

Sequence Diagram(s)

Suggested reviewers

Chat

Support

CodeRabbit Commands (Invoked using PR comments)

Other keywords and placeholders

CodeRabbit Configuration File (.coderabbit.yaml)

Documentation and Community

Uh oh!

codecov bot commented Jul 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

Uh oh!

cikasfm left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

justincoh commented Jul 16, 2025 •

edited by coderabbitai bot

Loading

coderabbitai bot commented Jul 16, 2025 •

edited

Loading

CodeRabbit Configuration File (`.coderabbit.yaml`)

codecov bot commented Jul 16, 2025 •

edited

Loading