Skip to content

Planning time grows quadratically with IN-list size on main #25905

Description

@gafiatulin

Describe the bug

restricted_column added in #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_columnis 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:

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

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions