Julian,
many thanks for the insights. I'm obiously not able to know/find out
where in the code those aggregate/combiner functions for RelSubsets are
located. AFAIK there are no metadata handler methods inside the metadata
handler implementations (in the form of `RelMdXXX implements
MetadataHandler<BuiltInMetadata.XXX>`) which address RelSubsets.
So I guess they are defined $somewhere else?
FYI: I currently do implement my own version of RelMdSelectivity by
extending this class and writing a handler method for RelSubSets.
Hovever, my implementation isn't responsible for the Calcite behavior
since I disabled my MetadataProvider.
You’re asking about how the Volcano algorithm computes metadata for equivalence
classes (what Calcite calls subsets) and to my knowledge it’s not been spelled
out explicitly (either in the Volcano/Cascades papers or in Calcite
discussions).
I guess with *the papers* you refer to [1] and [2]?
[1]: https://ieeexplore.ieee.org/abstract/document/344061
[2]:
https://liuyehcf.github.io/resources/paper/The-Cascades-Framework-For-Query-Optimization.pdf
Best regards,
Tony
Am 16.01.24 um 23:17 schrieb Julian Hyde:
Tony,
You’re asking about how the Volcano algorithm computes metadata for equivalence
classes (what Calcite calls subsets) and to my knowledge it’s not been spelled
out explicitly (either in the Volcano/Cascades papers or in Calcite
discussions).
Calcite needs various kinds of metadata, such as estimated row count, whether a
set of columns form a unique key, cpu cost. And since (when the planner is
using the Volcano algorithm) an equivalence class is a RelNode, we need to
compute those metadata for an equivalence class. The only practical choice is
to combine the metadata from the RelNodes in that equivalence class using some
kind of aggregate function (sum, min, max, average).
For keys, we use union. If equivalence class C contains R1 and R2, and R1 has
key (a, b), and R2 has key (b, c), then C has keys {(a, b), (b, c)}. This makes
sense because R1 and R2 return the same rows, and therefore if (a, b) is a key
for R1 then it is also a key for R2 (even though R2 doesn’t know it).
For predicates, union also makes sense. E.g. if we have deduced that a > 10 in
R1, it must hold for R2 also, and therefore for C.
For minimum row count, we take the maximum. If R1 produces no fewer than 10
rows, and R2 produces no fewer than 1 row, then C produces no fewer than 10
rows.
For cost (cpu cost, or some combination of cpu, io and row count) we should
take the minimum, because we are going to choose the RelNode with the minimum.
For expected row count, it’s tricky. Ideally we take the average, but give more
weight to estimates that are more certain. But in practice I think we take the
minimum. Joins with high uncertainty tend to skew high. Materialized views
(summary tables) that have actually been materialized have actual row counts,
so have high certainty, and tend to have lower numbers.
And so forth, for other kinds of metadata.
It’s probably possible to change these combiner (aggregate) functions by
writing your own RelMetadataProvider. If anyone has experimented with with
different combiner functions I would love to hear what you found.
Julian
On Jan 16, 2024, at 8:49 AM, Thomas Rebele <thomas.reb...@cloud.com.INVALID>
wrote:
Hello,
The RuleMatchVisualizer uses the planner to get the cost [1], and the
Volcano planner uses the bestCost attribute for RelSubset [2].
The color depends on the steps:
* For intermediate steps, the purple color shows which nodes have been
matched by the rule. Light blue shows added nodes.
* For the final step, the purple and light blue colors show the chosen
nodes of the final plan. Light blue for the RelSubset nodes.
If I remember correctly, the cost for a subset shown at a step should be
the same as the best cost of all children for that particular step.
It would be helpful to share at least the generated files (especially the
.js), to understand what's going on.
[1]
https://github.com/apache/calcite/blob/c4042a34ef054b89cec1c47fefcbc8689bad55be/core/src/main/java/org/apache/calcite/plan/visualizer/RuleMatchVisualizer.java#L300C34-L300C34
[2]
https://github.com/apache/calcite/blob/c4042a34ef054b89cec1c47fefcbc8689bad55be/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java#L722
Cordialement / Best Regards,
*Dr. Thomas Rebele* | R&D Developer | Germany | *E* *treb...@tibco.com
<treb...@tibco.com>* | *W* *www.cloud.com <http://www.cloud.com/>*
*Cloud SG Germany GmbH* | ℅ Citrix Systems GmbH, Erika-Mann-Straße 67-69,
80636 München Deutschland | Registergericht: Amtsgericht München, HRB
123355 | Geschäftsführer: Antonio Gomes, Alexander E. Kolar, Ganesh
Vaidyanathan, Brian Lee Shytle
On Fri, Jan 12, 2024 at 11:35 PM Tony Fiedler <
tony.fied...@mailbox.tu-dresden.de> wrote:
Dear Calcite devs,
First of all I really appreciate having a mature framework like Calcite.
Please continue your great work on this project!
My use case is feeding Calcite (v1.35.0) with an SQL query and doing
some optimizations by providing metadata and selected planner rules. I
initialize the Volcano planner and convert the logical plan resulting
from the sql to a physical plan (using bindable convention).
After the optimization, I convert the physical plan back to sql --
hoping its execution time is faster (running the query by a PostgreSQL
server) than the original query.
There are some aspects I don't understand regarding both the cost
calculation and cost propagation of (Rel) Subsets in the tree-based plan
representation generated by RuleMatchVisualizer.
AFAIK Subsets don't have any costs [1], so I'm really confused why
(cumulative) `cpu` is higher in the subset than it is in its child
elements (BindableJoin and BindableFilter), see [2]. In addition to that
the cost metric `rows` is smaller(!) than the values provided by the
children.
What I expect is that Subset has exactly the same `rows`, `cpu` (and
`io`) of the selected (purple) child element.
Having a look at this sub tree [3] the cost propagation works like
expected.
Besides that I already noticed that Calcite costs seem to have an upper
bound (9.223372036854775807E18) where costs can't get any higher in sub
trees where this value is reached in an (physical operator) element.
I know it's hard to tell what Calcite actually does just using
screenshots. Please let me know if I should provide e.g., my code for
giving better insights.
Thank you in advance for your reply!
[1]:
https://github.com/apache/calcite/blob/c4042a34ef054b89cec1c47fefcbc8689bad55be/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java#L254
[2]: https://ibb.co/7jtXKH3
[3]: https://ibb.co/5BZZyLz
Best regards,
Tony
