AryanVBW opened a new pull request, #2832: URL: https://github.com/apache/kvrocks/pull/2832
This pull request introduces significant additions to the e-graph data structure and its associated components for the KQIR optimizer. The changes include the implementation of the e-graph itself, equivalence classes, nodes, and rewrite rules, as well as a new equality saturation pass for query optimization. fix:https://github.com/apache/kvrocks/issues/2561 Key changes include: ### E-Graph Implementation: * Added `EGraph`, `EClass`, and `ENode` classes to represent the e-graph, equivalence classes, and nodes respectively. This includes methods for adding nodes, merging classes, and extracting the best query plan based on a cost model. (`src/search/passes/egraph.h`) ### Rewrite Rules: * Introduced several rewrite rules (`FilterPushDownRewrite`, `MergeFilterRewrite`, `SortPushDownRewrite`, `FilterMergeRewrite`, `CommonSubexpressionRewrite`) to transform the e-graph and optimize query plans. (`src/search/passes/egraph_saturation.h`) ### Equality Saturation Pass: * Added the `EGraphSaturation` class, which applies the rewrite rules to the e-graph until saturation is achieved and extracts the best query plan using a cost model. (`src/search/passes/egraph_saturation.h`) These changes collectively enhance the query optimization capabilities of the KQIR optimizer by leveraging e-graph-based equality saturation techniques. @git-hulk @aleksraiden @PragmaTwice -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
