3 ms·

Thanks for your comment. I'm the author of this post. I have been thinking about sharing something about database internals for a long time, but none of my wri

Thanks for your comment. I'm the author of this post. I have been thinking about sharing something about database internals for a long time, but none of my writing ideas was out of cliché then(e.g. introduce some algorithms, summarize some papers). But I just realized that it maybe an interesting thing to talk about "how" and "why" instead of "what". The rest posts are coming soon, hope you can see them on hacker news again.

Sesse__ 3y ago
An honest question, since you're there: Why do you consider MySQL 8.0's optimizer to be based on relational algebra? It's true that the new executor introduced in 8.0 is Volcano-style, but the optimizer is pretty much ad-hoc as I see it.
- leiysky 3y ago
  I agreed with you on the ad-hoc part. The thing is Oracle guys have made significant improvement in MySQL 8.0, including the Volcano-style executor. They also implemented DPhyp join reorder algorithm but with an ad-hoc IR. The join optimizer IR(they call it RelationalExpression) is based on relational algebra. I think this is a good start. But it’s not easy to migrate a project lived for decades, especially one with poor design.
  - Sesse__ 3y ago
    Yeah, I know, I wrote the new executor and the hypergraph join optimizer (the one based on DPhyp), that's why I wondered :-) It's true that if you are using the hypergraph optimizer, you will get a rewrite from the array of tables into RelationalExpression. But I find it hard to call that relational algebra; in particular, it only supports joins and tables as operations. Filters are pushed down ad-hoc, and things like grouping or windowing operators are simply not representable in this structure at all. Columns are not dealt with at all either (projection is unavailable). And perhaps more importantly; RelationalExpression is hardly used. Most of the optimizer works on the old array-of-tables structure, then it briefly becomes RelationalExpression for condition pushdown, then the hypergraph is created and RelationalExpression is never to be seen again. The entire hypergraph optimizer works by inducing subgraphs of a hypergraph; it does not use relational algebra. Also, notably, MySQL 8.0 does not actually _use_ the hypergraph optimizer by default. You need to explicitly compile it in (it's off in release builds), and then enable it using an optimizer switch. So unless you go to fairly great lengths to enable it yourself, RelationalExpression and friends is never used. I agree that using a relational algebra IR would be a good idea; it's a better structure than what's in there right now (which comes all the way from MySQL 3.x, and is extremely unflexible to work with). It's just that I don't think MySQL 8.0 does it. :-) (I obviously don't speak for Oracle, not the least because I haven't worked there in a while)

Sesse__ 3y ago

An honest question, since you're there: Why do you consider MySQL 8.0's optimizer to be based on relational algebra? It's true that the new executor introduced in 8.0 is Volcano-style, but the optimizer is pretty much ad-hoc as I see it.

leiysky 3y ago
I agreed with you on the ad-hoc part. The thing is Oracle guys have made significant improvement in MySQL 8.0, including the Volcano-style executor. They also implemented DPhyp join reorder algorithm but with an ad-hoc IR. The join optimizer IR(they call it RelationalExpression) is based on relational algebra. I think this is a good start. But it’s not easy to migrate a project lived for decades, especially one with poor design.
- Sesse__ 3y ago
  Yeah, I know, I wrote the new executor and the hypergraph join optimizer (the one based on DPhyp), that's why I wondered :-) It's true that if you are using the hypergraph optimizer, you will get a rewrite from the array of tables into RelationalExpression. But I find it hard to call that relational algebra; in particular, it only supports joins and tables as operations. Filters are pushed down ad-hoc, and things like grouping or windowing operators are simply not representable in this structure at all. Columns are not dealt with at all either (projection is unavailable). And perhaps more importantly; RelationalExpression is hardly used. Most of the optimizer works on the old array-of-tables structure, then it briefly becomes RelationalExpression for condition pushdown, then the hypergraph is created and RelationalExpression is never to be seen again. The entire hypergraph optimizer works by inducing subgraphs of a hypergraph; it does not use relational algebra. Also, notably, MySQL 8.0 does not actually _use_ the hypergraph optimizer by default. You need to explicitly compile it in (it's off in release builds), and then enable it using an optimizer switch. So unless you go to fairly great lengths to enable it yourself, RelationalExpression and friends is never used. I agree that using a relational algebra IR would be a good idea; it's a better structure than what's in there right now (which comes all the way from MySQL 3.x, and is extremely unflexible to work with). It's just that I don't think MySQL 8.0 does it. :-) (I obviously don't speak for Oracle, not the least because I haven't worked there in a while)