Skip to content

Add support for linear range search #4979

Closed

Description

@mustafasrepo

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

During range calculation for window frames, we can use linear search instead of bisect. Since we know that table, is already sorted and we would progress only in one direction; linear search is amortized constant (When window frame boundaries are static e.g in the form RANGE BETWEEN 3 PRECEDING AND 5 FOLLOWING). Hence this version is more optimal than current bisect implementation (where search complexity is log(n)). This change decreases overall window range calculation complexity from O(n*log(n)) to O(n).
This reasoning is explained more thoroughly in the following paper.
https://dl.acm.org/doi/10.14778/2794367.2794375
p1058-leis.pdf

Describe the solution you'd like
Range calculation can use linear search instead of bisect. This will possibly improve performance.

Describe alternatives you've considered
N.A

Additional context
N.A

Activity

  1. alamb commented on Jan 20, 2023

    @alamb
    Contributor

    Somewhat related to #4904

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

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions