Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add support for linear range search #4979

Closed
mustafasrepo opened this issue Jan 19, 2023 · 1 comment · Fixed by #4989
Closed

Add support for linear range search #4979

mustafasrepo opened this issue Jan 19, 2023 · 1 comment · Fixed by #4989
Labels
enhancement New feature or request

Comments

@mustafasrepo
Copy link
Contributor

mustafasrepo commented Jan 19, 2023

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

@alamb
Copy link
Contributor

alamb commented Jan 20, 2023

Somewhat related to #4904

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants