YimingQiao commented on PR #24575: URL: https://github.com/apache/datafusion/pull/24575#issuecomment-5384532004
Hi, @2010YOUY01 In short, I think RPT makes the join reordering problem less important. Specifically, it reduces the impact of bad join ordering from potentially exponential, e.g., 10×, 100×, or even 1000× worse than the optimal plan, to something much closer to linear, e.g., 1–10× worse than the optimal plan, by introducing a relatively small fixed overhead. This is why it is called “robust.” I have recently written three extensions for DataFusion, DuckDB, and Postgres. Most people would view Bloom as a data-reduction layer over the input tables, i.e., it uses runtime filters to reduce the amount of input data and provide speedups. SQL Server, whose query optimizer is generally considered very mature, has used runtime filtering techniques for a long time. A recent CIDR paper, *“I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server”* (Zhao et al., CIDR 2026), shows that bitmap filters, pull-based execution, and the Cascades optimizer together can achieve surprisingly strong Yannakakis-like behavior. An interesting side effect they highlight is that runtime filtering also mitigates the impact of poor join ordering. Previous work has mostly tried to add runtime filtering techniques to an already mature Cascades-style optimizer/CBO. I think another promising solution is to build a Cascades-style optimizer around runtime filters. For example, after the transfer phase, we can obtain the actual cardinalities of the reduced tables without having to estimate all predicate selectivities beforehand. This makes the optimizer's job easier. One of the most challenging parts of a Cascades-style optimizer is obtaining reliable statistics for cardinality estimation. In the future, database systems may increasingly operate over external data, such as data lakes, rather than managing all of the data themselves. In such cases, we may have much less opportunity to maintain rich statistics than before. For this reason, I think sampling is a robust solution, and a lightweight but sufficiently accurate runtime sampling method is promising. One observation from RPT/Bloom is that we do not require extremely precise sampling: we care whether the filter selectivity is 10% or 60%, but we usually do not care whether it is 10% or 11%. Currently, many database systems already use a mixture of optimization techniques: 1. heuristics for predicate pushdown and rewriting sort + limit into TopN; 2. CBO for join ordering; and 3. runtime adaptivity for decisions such as filter reordering for table scan. I do not think a traditional Cascades structure can necessarily handle all of these mechanisms naturally. For join ordering, if we have sufficiently good statistics, CBO would probably be better; if not, I think its decisions can become unreliable. I have to admit that Bloom introduces some overhead because it needs to scan all input tables one extra time, and it also needs to temporarily materialize the reduced tables in memory. We still do not have a clear plan for how to efficiently extend it to a distributed database. Overall, though, I feel that it points toward a promising direction. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
