TableFunction's cardinality also returns post-filter estimates - #28099

Ok, there's something strange going with Parquet (it never pushes any filters), I'll investigate

Ok, it's hive partitioning. MultiFileReader does remove the filters on virtual columns yet doesn't account it on cardinality. Ideally pushdown_complex_filter should return enum with option "remove but account me in cardinality" and "remove and don't account in cardinality".

I think this is a better solution - let implementations choose whether filters they've pushed are evaluated before the scan (and so cardinality already accounts for them) or after the scan (and so cardinality needs to be adjusted). To avoid breaking the API it's not a return type of pushdown_complex_filter but an output parameter on LogicalGet.

Thanks - but this seems like the wrong shape. Can't this be solved in the table function? The table function (1) is the one reporting its cardinality, and (2) is the one taking in the filters that are pushed down. Can't the table function itself take these filters into account when reporting the cardinality?

I let Codex look into this and it suggested that this can be fixed vortex-side:

diff --git a/vortex-duckdb/cpp/table_function.cpp b/vortex-duckdb/cpp/table_function.cpp
index 295d402..8c8590b 100644
--- a/vortex-duckdb/cpp/table_function.cpp
+++ b/vortex-duckdb/cpp/table_function.cpp
@@ -210,9 +210,6 @@ duckdb_state register_table_function(DatabaseInstance &db, LogicalType parameter
     fn.pushdown_expression = [](auto &, const auto &, Expression &expression) {
         return duckdb_table_function_pushdown_expression(reinterpret_cast<duckdb_vx_expr>(&expression));
     };
-    fn.pushdown_complex_filter = [](auto &, auto &, FunctionData *bind_data, FilterVec &filters) {
-        pushdown_complex_filter(*bind_data, filters);
-    };
     fn.projection_expression_pushdown = projection_expression_pushdown;
     fn.to_string = to_string;
 
diff --git a/vortex-duckdb/src/table_function.rs b/vortex-duckdb/src/table_function.rs
index ed751b1..0fb95c6 100644
--- a/vortex-duckdb/src/table_function.rs
+++ b/vortex-duckdb/src/table_function.rs
@@ -576,34 +576,19 @@ fn try_push_projection_aggregate(
     }))
 }
 
-/// Duckdb requires post-filter cardinality estimates, otherwise join planner
-/// may flip join sides which is a huge regression for some queries i.e. 1000x
-/// for tpcds 85.
-///
-/// See duckdb/src/optimizer/join_order/relation_statistics_helper.cpp
-///
-/// As we don't report distinct values (same as Parquet), the only heuristic
-/// duckdb uses is a 0.2 filter if there is any non-optional filter. We mimic it
-/// here.
-const DEFAULT_SELECTIVITY: f64 = 0.2;
+/// Estimate source rows; DuckDB estimates the selectivity of filters retained in the plan.
 pub fn cardinality(bind_data: &BindState, file_count: u64) -> Cardinality {
     // If we're doing an aggregate scan, we don't change output cardinality to
     // 1 as we want duckdb to do our aggregation in parallel. That may look
     // counterintuitive in the plan, though.
-    let has_non_optional_filter = bind_data.has_non_optional_filter.load(Ordering::Relaxed);
     let total = bind_data
         .first_file_row_count
         .saturating_mul(max(file_count, 1));
-    if !has_non_optional_filter {
-        return if file_count <= 1 {
-            Cardinality::Exact(total)
-        } else {
-            Cardinality::Estimate(total)
-        };
+    if file_count <= 1 {
+        Cardinality::Exact(total)
+    } else {
+        Cardinality::Estimate(total)
     }
-    let post_cardinality = total as f64 * DEFAULT_SELECTIVITY;
-    let post_cardinality: u64 = post_cardinality.as_();
-    Cardinality::Estimate(max(1, post_cardinality))
 }
 
 pub fn to_string(bind_data: &BindState, map: &mut DuckdbStringMapRef) {

@Mytherin

Can't this be solved in the table function?

No, because the issue is not in the cardinality estimation of the table function alone, but in the estimation in the join planner. You can push down a filter and then account for it in cardinality(). That's what we currently do, see Laurens's excerpt from our code.

However, when we're estimating cardinality for a join, cardinality()'s output becomes both base_table_cardinality and cardinality_after_filter, total_domain = base_table_cardinality.
For a join, resulting cardinality is the multiplication of sides cardinalities divided by the minimum of side' total_domains.

For an example join where left side has N rows, right has M rows, N > M,
each table function over a table has one filter

• the default case (nothing is pushed), domain is M, multipler is 0.2 * 0.2 * N * M (each filter for both sides gives a flat 0.2 multiplier), output is 0.04 * N.
• if you push a filter and multiply cardinality() with 0.2 inside (our current solution), multiplier is 0.2 * 0.2 * N * M (same as in first case), but domain (total_cardinality) is now 0.2 * M (since we return a smaller cardinality with accounted filter), output is 0.2 * N (5 times higher).
• if you push a filter and use my solution, it's the same case as (1)

So the issue is in the join estimator, maybe I should've been more clear about this.

@lnkuiper Not pushing down table filters will result in 10-100x regressions since we won't be able to discard unused data. The issue I'm describing is not specific to Vortex. Every table function which can push down filters and reports cardinality is subject to this bug.

Maybe as a work-around we can just leave in a cheap filter?

We don't know whether the filter is cheap or not without evaluating it. We may use heuristics like "if this is an equality over some column, this is cheap" but nothing guarantees it's cheap indeed. For this to be implemented, a TableFunction implementer like Vortex would also need to know/use DuckDB's heuristics for determining a filter's cost which shouldn't be the custody of the TableFunction.

This solution has yet another flaw if all filters are expensive by this heuristic, yet all can be pushed down (which we have also discovered in our tests). In this case you ultimately regress, either by making DuckDB reapply a filter or by having incorrect join estimates.

I agree it's not ideal. The ideal fix imo is to expand the statistics callback to allow it to give back both the pre and post filter statistics. Could we go down that path instead?

Of course that's an API change so that will only land in v2.1, as a work-around for v2.0.X leaving in the cheap filters could be done.

Could we go down that path instead?

No, because for multi-file scans statistics is not provided (i.e. by MultiFileReader, which is a resonable choice) yet we want to estimate number of rows for a multi-file scan. cardinality() is a good distinct feature for this purpose. Maybe cardinality() itself should return multiple estimates.

Yes, that's what I meant, we need to change / extend the API around what cardinality estimates table functions can provide

Ok, let's repurpose this PR to change cardinality() to return both pre- and post- estimates to 2.1, and we'll hack the implementation on our side in 2.0.

@Mytherin I think a new function is better for backwards compatibility, but let me know what you think.

I would prefer to change the existing callback, while we're at it we can also shape it more like the other newer callbacks (i.e. introduce a TableFunctionCardinalityInput struct)

I would prefer to change the existing callback

The issue with existing callback is that it already reports two cardinalities (estimate and max), it's unclear whether post-filter should be another field in it or another entry unique_ptr<NodeStatistics> in cardinality's output.

I'm off for a while, when I get back, I'll update the solution for cardinality