gafiatulin opened a new issue, #25905: URL: https://github.com/apache/datafusion/issues/25905
### Describe the bug `restricted_column` added in https://github.com/apache/datafusion/pull/24520 counts the distinct values in an `IN list` using `Vec::contains` making `restricted_column` quadratic. `ScalarValue` already implements `Hash` and `Eq` so count can be performed via HashSet making `restricted_column` run linearly. \+ This happens even for tables without statistics since in `unique_match_limit` `restricted_column`is called before the check on whether the column's statistics say each value is unique. Adding another check on all columns can allow skipping counting altogether: ```rust fn unique_match_limit( predicate: &Arc<dyn PhysicalExpr>, statistics: &Statistics, ) -> Option<usize> { if !statistics .column_statistics .iter() .any(|column| holds_each_value_once(column, &statistics.num_rows)) { return None; } let mut limit: Option<usize> = None; ... ``` ### To Reproduce Plan with `IN list` of different sizes and observe quadratic runtime. ### Expected behavior Planning time grows linearly with the size of `IN-list`. ### Additional context _No response_ -- 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]
