TopDown optimizing approach exploring and implementation based on cascades/columbia
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
For modern advanced HTAP databases, the cascades-based optimizing approach will make the entire optimizing framework more flexible and extensible (modular, easy for adding/updating rules, making catalog and cost model more adaptive), eliminating the redundant searching space by group-pruning/low-bound admission branch check/equiv class classification, without completely do enumeration of each logical plan node from the bottom up.
## Details
### Infrastructure
* implement a stack mechanism https://github.com/pingcap/tidb/pull/51663
* Implement a serializing scheduling https://github.com/pingcap/tidb/pull/51866
* implement mutable and immutable fieldType https://github.com/pingcap/tidb/pull/51916
* make the task dir clean out of memo https://github.com/pingcap/tidb/pull/52083
* separate the pattern logic of the memo directory https://github.com/pingcap/tidb/pull/52117
#### HashEqual infra
* add base hasher and equaler for taking in primitive type https://github.com/pingcap/tidb/pull/55570
* regular the normal way to integrate HashEqual into base.LogicalPlan and expression.Expression https://github.com/pingcap/tidb/pull/55652
* introduce hashEquals to column/collationinfo/fieldType https://github.com/pingcap/tidb/pull/55691
* introduce hashEqual interface for datum https://github.com/pingcap/tidb/pull/55727
* introduce hashEquals interface for expression.Expression https://github.com/pingcap/tidb/pull/55793
### Refactoring
The current `plan/core` pkg is quite huge not as slim as we expected. The hybrid placement of logicalOp, physicalOp, property, task, logical-rewrite, build-phase, binder, cost, exhaustion, etc makes the hierarchy complicated. The boundary of them is also not as clear as we desired. I concluded that there is some reason for this phenomenon.
* One is if Golang's structure wants to implement member functions with itself as a receiver, including the interface implementation, which can only be defined in the same pkg where the structure is defined. (here clearly the pkg is `core`) [stackoverflow ref](https://stackoverflow.com/questions/41109708/cant-define-receiver-from-another-package-in-go)
+ eg: `LogicalSort` is defined in core pkg somewhere. If you want to implement (p *LogicalSort) buildKeyInfo for the sake of interface implementation or just member function of them, this implementation **can only be done in the same `core` pkg**, because Golang only allows local type as a receiver. Given buildKeyInfo is logical-rewrite-related code, it should be put into another part/component/pkg of core logic for clarity, that calls for the interface simplification or elimination of self-receiver's function.
* Numerous utility and facility functions related to the core logic are defined and used in the `core` package. These include trace, hashcode, cost mode, selectivity, task, enumeration, and more. Moving or adding a new feature outside the `core` package may result in many internal structures or functions being exported out as well.
* The biggest block is the import cycle problem. Say we create a new pkg called core2 and we want to add a new feature inside. The new feature couldn't work well without the current core context support, so by some means (exported original `core` structure or interface, using function pointer or something), we got a dependency from `core2` -> `core`. However, this feature must also be called from `core`, cause `core` is a current unified portal for the entire optimization phase, so we got a dependency from `core` -> `core`. As a result, hops, golang's import cycle is formed. The final solution to the problem is **Back** to integrate them all. Eventually, the core pkg becomes larger and larger.
* move logical optimizing trace logic out of core pkg https://github.com/pingcap/tidb/pull/52161
* planner: refine cop task as a capital one for latter pkg move https://github.com/pingcap/tidb/pull/52506
* planner: refine mppTask as capital one for latter pkg move https://github.com/pingcap/tidb/pull/52491
* planner: move physical opt and cost misc to util and split plan interface https://github.com/pingcap/tidb/pull/52224
* planner: move base plan related output of core pkg and make it well-packaged https://github.com/pingcap/tidb/pull/52529
* planner: remove internal pkg and move base code to certain place https://github.com/pingcap/tidb/pull/52620
* planner: rename base plan implemention's pkg from base to baseImpl https://github.com/pingcap/tidb/pull/52659
* planner: move debugtracer logic and handle col definition to util pkg https://github.com/pingcap/tidb/pull/52681
Contributor guide
Assessment
This issue has not been assessed yet.