alibaba / alibaba/GraphScope

Design equivalence rules for GIE RBO optimizer

Open
#2,651 0 comments 0 reactions 0 assignees View on GitHub
enhancement summer-of-code
Dominant language
C++
Stars
3.6k
Forks
468
Avg merge
29m
Merged PRs (30d)
1

Description

**Is your feature request related to a problem? Please describe.**

The query optimizer is the core module of traditional SQL, which refers to a series of logical deductions based on relational algebra expressions that can help generate more efficient execution plans without changing the execution results. GraphScope Interactive Engine (GIE) is a graph interactive query system based on GraphScope. Currently, GIE defines a set of Graph Relational operators based on Calcite and an RBO optimization framework based on these operators. This RBO framework allows different optimization rules to be registered per query, thereby generating optimized logical plans. However, we still lack a complete set of equivalence rules. We hope to further investigate the SQL rules already available in Calcite, starting from the real scenarios of GIE (i.e., bi), and summarize a set of equivalence rules for GIE as the basis for our subsequent RBO/CBO.

References:
- Calcite Rules:
https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/rules/package-summary.html
- LDBC BI:
https://github.com/ldbc/ldbc_snb_bi

Tasks:
- Summarize a set of equivalence rules based on real scenarios, and document the technical details.
- Implement the equivalence rules and validate the performance improvement through benchmarking tools.

Contributor guide

Open the contributing guide

Research direction

Start with the Calcite Rules reference and LDBC BI scenarios named in the issue, then inspect GIE's existing Graph Relational operators and RBO framework. Done means a documented set of equivalence rules grounded in BI scenarios, implemented rules, and benchmark validation showing their performance impact.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.