mustafasrepo opened a new issue, #4979: URL: https://github.com/apache/arrow-datafusion/issues/4979
**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](https://github.com/apache/arrow-datafusion/files/10417023/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** A clear and concise description of any alternative solutions or features you've considered. **Additional context** Add any other context or screenshots about the feature request here. -- 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]
