Window Function Optimization: Co-Evaluation and Other Techniques

Alberto Lerner; Daniel Lindner; Felix Naumann

REVIEW 4 major objections 4 minor 49 references

Window Function Optimization: Co-Evaluation and Other Techniques

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper argues that the limits of window-function optimization are not fundamental: a phase-based formal model makes them algebraic, so predicates that depend on a window's result can be evaluated early without changing the query result.

desk verdict Real contribution: phase-based equivalence framework plus DuckDB implementation; the tie-handling gap in partition pruning needs clarification before I'd trust the Q3 numbers. read the letter →

arxiv 2608.06043 v1 pith:7TZGTEY4 submitted 2026-08-06 cs.DB

Daniel Lindner , Felix Naumann , Alberto Lerner This is my paper · ORCID

classification cs.DB

keywords windowfunctionsqueryoptimizationalgebraicequivalencespredicatepush-downco-evaluationMODpredicatestop-kpruningoperatorphases

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Modern SQL relies heavily on window functions for ranking, moving aggregates, and top-k analytics, yet optimizers have few reliable rules for rewriting them. This paper argues that the missing piece is a formal, phase-based model of the window operator, and it supplies one by decomposing the operator into partitioning, sorting, framing, aggregating, emitting, and collecting. On top of that model it derives a table of algebraic equivalences, including new techniques called Frame Analysis, Partition Analysis, and Co-Evaluation. The claim is that predicates that depend on a window's result, previously thought unpushable, can be co-evaluated inside the operator and used to prune rows before or during the sort. In an open-source engine the rewrites never slowed any tested query and made some queries up to 40.7 times faster, with larger tables showing larger gains.

What carries the argument

The load-bearing object is the phase-based formal definition of the window operator and the equivalence table built on it. The operator is decomposed into partition, sort, frame, aggregate, emit, and collect phases, and this decomposition is what allows intermediate execution states to be reasoned about. The key concept for push-downs is partition integrity: a predicate or join can cross the window only if it removes whole partitions or leaves them intact, and functional and order dependencies certify when that holds. The key concept for Co-Evaluation is the monotonic order-dependent (MOD) predicate, one that, once false, stays false for the rest of the sorted partition; for such predicates Equivalence 14 justifies a WF+ operator whose pruning points are partition pruning with per-partition heaps of size $k$, merge pruning that stops reading sorted runs beyond the rank-$k$ element, and early stop during framing and aggregation. An adaptive guard uses a HyperLogLog sketch to estimate the number of partitions and switches partition pruning on or off per chunk, so the cost-dependent optimization is decided at runtime rather than by a static cost model.

What would settle it

Run a query of the Q3 shape on a table where one department has, say, five employees tied at the same salary and k=3 with rank() under standard SQL semantics: any implementation that keeps only a heap of size 3 per partition will drop two tied rows even though all five have rank 3 and should satisfy rnk <= 3. Comparing WF+ output against a native window operator on that input settles whether Equivalence 14 is semantics-preserving for tied data.

Watch

Extended reading notes

Core claim

The central discovery is a semantics-preserving decomposition of the window function operator into six phases, which turns window-function optimization into ordinary algebraic reasoning. Each SQL OVER() construct maps to four parameters: partition attributes $P$, order attributes $O$, a frame function $w$, and an aggregate $f$, written as $\boxplus_{P,O,w,f}(r)$. The decomposition yields a table of equivalences: reductions remove redundant partition or sort attributes when functional dependencies hold; substitutions replace singleton or whole-partition frames with projections or group-by joins; push-downs move predicates and joins through the window when partition integrity is preserved; and limit-like rules rewrite predicates on ranking functions into top-k pruning. The capstone is Equivalence 14, $\sigma_C(\boxplus_{P,\ldots}(r)) \equiv \boxplus^+_{P,\ldots,C}(r)$, for monotonic order-dependent (MOD) predicates such as rnk <= 3: the predicate is fused into a modified operator WF+ that prunes rows at partition time, during merge, and at aggregation. The paper reports that in every tested case the optimized plan matched or beat native execution, with speedups up to 40.7 times.

Load-bearing premise

The load-bearing premise is that per-partition pruning to top-k rows preserves SQL rank semantics, which holds only when tied rows at the rank boundary are kept or the ordering attributes are unique, as the paper itself notes in Section 6.3.

Editorial extensions

If this is right

Reductions, projection substitution, group-by substitution, and limit elimination are unconditional: an optimizer can apply them during normalization without costing them against alternatives.
Predicate and join push-downs become safe whenever a functional dependency certifies partition integrity, extending earlier push-down techniques to queries where the predicate and partition expression do not match exactly.
Co-Evaluation changes the optimizer's contract: predicates that depend on a window result can be fused into the operator, so top-k rank filters no longer force a full sort and a post-window evaluation.
The reported speedups are tied to table size: the 40.7x gain comes from removing a singleton-frame window entirely, while the top-k rank query runs up to about 5x faster and the gains grow as sorting becomes more expensive.
The techniques never hurt performance in the tested matrix, with adaptive partition pruning preventing the worst-case overhead of heap maintenance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next test, not in the paper, is whether Co-Evaluation generalizes to other MOD predicates such as cumulative sums over non-negative values or time-since-event computations; the monotonicity condition suggests the same early-stop argument applies.
The phase-based decomposition could serve as a template for optimizing other order-sensitive operators, such as pattern matching, array or string folding, and streaming windows, by identifying the phase where a predicate can be injected.
The adaptive partition-pruning guard combines a HyperLogLog estimate, $k$, and a threshold $\delta=5$; one could test whether that threshold transfers to other engines, data distributions, and values of $k$, or whether it needs to be made cost-aware.
Because tie handling is the boundary condition for rank and dense_rank, an independent test with duplicate ordering values at the rank boundary is the cheapest way to check whether the heap-based WF+ implementation matches SQL rank semantics.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing you should know: this is a genuine contribution to window-function optimization. The phase decomposition (partition, sort, frame, aggregate) is simple but actually usable, the equivalence table in Table 3 goes beyond anything in the cited Cao, Bellamkonda, or Leis work, and they implemented the optimizations in DuckDB with plausible speedups—up to 40.7x for frame collapse and 2-5x for co-evaluation on top-k queries. The code is on GitHub, which makes the results checkable. I'd send this to review.

The main soft spot the stress-test hits is tie-handling in partition pruning. Section 6.3 correctly says that for rank() and dense_rank(), you need queues of size k' >= k unless the order attributes are unique. Section 7.1 then casually describes 'heaps of size k' and Figure 2 shows 'top 2 salary'. If that description is taken literally, the pruning drops boundary ties and returns wrong answers for Q3. I think the authors know this—they stated the condition explicitly in 6.3—so the fix is to make the implementation description and the figure match the stated condition. But it needs to be explicit, because a reader implementing from the paper could easily get it wrong, and the experiments should state whether the data has duplicate salaries. This is an exposition gap, not necessarily a fatal flaw, but it is the first thing a referee should check against the artifact.

The other soft spots are real but smaller. Most of Table 3 is asserted without proof; only Equivalences 5 and 13 get sketches. Some of these are new, so they deserve either full proofs or at least a clear proof strategy. Equivalence 8's precondition in the table says FD{b}->p, but the text's range-predicate derivation relies on an order dependency [b] -> [e(b)]. That mismatch needs fixing. And delta=5 for adaptive pruning is tuned on the same workloads used for the headline speedups, so the 'never hurt performance' claim is weaker than it looks; an external benchmark or held-out workload would strengthen it.

Who this is for: database system researchers and anyone building a query optimizer that handles window functions. The formal framework and the table are the lasting parts. It deserves serious peer review; the revisions should focus on the tie-handling description, the proof sketches, and the delta tuning.

Referee Report

4 major / 4 minor

Summary. The paper proposes a phase-based formalization of SQL window functions, breaking execution into partitioning, sorting, framing, aggregating, emitting, and collecting. On top of this formalization it derives a table of algebraic equivalences, grouped into reductions, operator substitutions, push-downs, and limit-like optimizations, and it introduces three techniques: Frame Analysis, Partition Analysis, and Co-Evaluation. Co-Evaluation is realized in a modified DuckDB operator called WF+, which prunes rows before and during sorting based on monotonic-order-dependent predicates such as RANK() <= k. The experimental section reports speedups up to 40.7x for frame collapse and up to about 5x for the Q3 top-k-per-partition query, and claims the optimizations never hurt performance.

Significance. The phase-based formalization is a genuinely useful way to reason about window-function optimizations, and the paper is, to my knowledge, the first to present a broad table of algebraic equivalences for window functions. The distinction between partition integrity and monotonic-order-dependent predicates is insightful, and the open-source artifact in DuckDB makes the empirical claims reproducible. The reported speedups, particularly for frame collapse and partition pruning on large tables, are substantial if they hold. However, the central correctness claim for Co-Evaluation is undermined by an internal contradiction in tie handling, and one push-down equivalence is stated with an insufficient precondition. These issues are load-bearing and need to be fixed before the paper can be accepted.

major comments (4)

[Sections 6.3, 7.1, Table 3 Equivalence 14, Figure 2] There is an internal contradiction in tie handling. Section 6.3 states that for rank() and dense_rank() the pruning queues must handle duplicates and have size k' >= k unless a UCC on the ordering attributes ensures no ties occur. Section 7.1, however, describes partition pruning as dynamically creating 'heaps of size k' per partition, and Figure 2 illustrates 'top 2 salary' without any uniqueness check. On a partition with more than k tuples tied at the k-th distinct ordering value, a k-sized heap will discard some tuples whose RANK() is <= k, changing the query result. Since later phases cannot restore discarded tuples, Equivalence 14 and the Q3 speedups in Section 8.2 are not semantics-preserving for tied data. The implementation must either retain all boundary ties (k' >= k), require and verify a UCC on the ordering attributes, or disable partition pruning when ties are possible.
[Table 3, Equivalence 8; Section 5.3] Equivalence 8 is stated with the precondition FD {b} -> p, with p in P, but that functional dependency is insufficient for the derived-predicate push-down for range predicates. An FD only says that equal b implies equal p; it does not imply that b >= c entails p >= c' or any other comparison p theta c'. The derivation in Section 5.3 explicitly relies on order-preservation for range predicates (approach (iii), using order dependencies [b] -> [e(b)]), but the table does not list that requirement and allows arbitrary theta. For example, with b = sold_date and p = EXTRACT(MONTH FROM sold_date), the FD holds but b >= '2020-02-15' does not imply any p >= c'. The precondition in Table 3 must be strengthened to require an order dependency or a monotonic mapping, and the scope of theta must be restricted accordingly.
[Section 7 and Table 3, Equivalence 14] The paper uses the operator symbol boxplus+ and Equivalence 14 for WF+ but never gives a formal definition of this operator, nor a correctness proof that the pruning performed in the three pruning points preserves the window function result for all inputs. The prose in Section 7 says pruning 'reduces the data volume' and that every phase still runs, but this is not a formal argument, and the tie issue in my first comment shows why such an argument is needed. Since Equivalence 14 is the basis for the headline Q3 results, the paper should define WF+ precisely, state its semantics relative to the phase decomposition of Section 2, and prove that it returns the same relation as the unoptimized window operator under the stated preconditions.
[Section 8.2, 8.4, and Abstract] The experimental validation of the 'never hurt performance' claim is partially circular. Section 8.4 selects delta = 5 by averaging over all configurations from Section 8.2, and Section 8.2 then reports WF+ results using that same delta on the same configurations. This tuning-on-the-test-set procedure does not support the abstract's unconditional claim that the optimizations 'never hurt performance.' Figure 4 also shows that partition pruning alone can time out at 3x the baseline runtime, so the no-harm property holds only for the combined adaptive operator with a tuned threshold. The authors should evaluate delta on a held-out configuration set, or at least report the sensitivity separately, and the no-harm claim should be scoped to the combined WF+ operator.

minor comments (4)

[Figure 3 and Section 8.1] The caption says 'Each column corresponds to one equivalence class from Table 3,' but the figure labels show only Equivalences 1, 2, 4, 6, 8, 9, and 13; Equivalences 3, 5, 7, 10, 11, 12, and 14 are not plotted. The text in Section 8.1 says the experiment covers 'the full equivalence table,' which is inconsistent with the figure.
[Section 8.2] The sentence 'This is the case for the right-most data point in the MT plots above 100 000 rows' is unclear, because the x-axis of each plot is the number of partitions, not the number of rows; it should say the right-most data point in the '100 000 Rows' plot.
[Figure 2] The label 'predc' in the top pipeline appears to be a truncated or corrupted word; it should probably be 'predicate' or 'co-evaluation predicate.'
[Section 4.2, Table 4] The condition numbering in Table 4 refers to conditions (i)-(iv) from Section 4.1, which is fine, but the table would be easier to read if the conditions were restated or explicitly listed in the caption.

Circularity Check

2 steps flagged · score 4.0 of 10

Core algebraic framework is self-contained, but the 'never hurt' claim is validated on the same configurations used to tune δ, and Equivalence 14's tie handling is internally inconsistent.

fitted input called prediction [Section 7.2, Section 8.2 (Figure 4), Section 8.4 (Figure 6)]
"We have determined experimentally that δ should be 5 (see Section 8.4). ... we execute all configurations from Section 8.2 with Adaptive Partition Pruning and δ between 1 and 10. Then, we calculate the average runtime across all configurations ... In our experiments, δ=5 is the optimal value."

Adaptive Partition Pruning's threshold δ is selected by minimizing the average runtime over exactly the configurations shown in Figure 4, and Figure 4 (with δ=5) is then reported as evidence that the combined WF+ implementation 'never hurt performance'. The performance conclusion is therefore a fitted result: the parameter was tuned on the same benchmark used to demonstrate robustness, so the claim is not an independent prediction. This does not affect the algebraic equivalences, but it weakens the experimental claim that the optimizations are universally safe.
self definitional [Section 6.3 vs Section 7.1, Equivalence 14 in Table 3]
"For rank() and dense_rank(), the queues must handle duplicates and have a size k′≥k, unless a UCC on the ordering attributes ensures no ties occur. ... we dynamically create heaps of size k for each partition per worker. When a tuple gets assigned to a bucket, we identify its partition. If the ordering value is larger than the respective heap's maximum value, we disregard the tuple."

Equivalence 14 asserts that σ_C(⊞_{P,...}(r)) ≡ ⊞^+_{P,...,C}(r) for 'C is any predicate'. The paper's own correctness condition for rank()/dense_rank() requires retaining boundary ties (k′≥k) unless the ordering attributes are unique, but the implemented partition pruning keeps only k values per partition. On tied data, rows whose rank is still ≤ k can be discarded before the sort, so the right-hand side returns fewer rows than the SQL query. The equivalence is thus not derived from the stated semantics; it holds only if ties are assumed away, i.e., the claimed result is true by construction only under an extra precondition that the implementation does not enforce.

full rationale

The phase-based formalization and the algebraic equivalences in Table 3 are self-contained derivations from the operator definition in Section 2; Equivalences 1-13 follow from FD/OD preconditions and the phase semantics, and they are not fitted to experimental data. The paper's self-citation of [26] in Section 9 is a pointer to related ongoing work by the authors, not load-bearing for the main results, and no uniqueness theorem is imported from prior work. The main circularity is experimental: δ=5 is tuned on the very configurations used to demonstrate 'never hurt performance', so the robustness claim is partially an artifact of the tuning set. Separately, the rank-tie inconsistency between Section 6.3 (k′≥k) and Section 7.1 (heaps of size k) means Equivalence 14 lacks support for tied orderings; this is a correctness gap rather than a derivation-level circularity, but it should be flagged because it undermines the Q3 speedup evidence on real-world duplicate data. Overall, the central framework is independent, so the score is moderate, reflecting the validation loop and the unsupported tie assumption.

Assumptions & free parameters 1 free parameters · 4 assumptions · 1 invented entities

Central claims rest on SQL NULL and order semantics, dependency availability in the optimizer, MOD predicate classification, and order dependencies for derived predicates. The only numeric parameter fitted to data is delta=5. No new physical entities are postulated beyond the WF+ operator, which is implemented and externally testable.

free parameters (1)

delta (adaptive pruning threshold) = 5
Threshold for enabling adaptive partition pruning in Section 8.4, chosen by sweeping 1..10 across the same workload configurations used for the speedup claims in Section 8.2; it is a tuning parameter, not a theoretical constant.

assumptions (4)

domain assumption SQL's syntactic equality semantics for NULLs in partitioning, grouping, and frame peer determination.
Section 2.1 states NULL=NULL is true in these contexts, matching the SQL standard [18,25]; the equivalences inherit this semantics.
domain assumption Optimizers can discover functional and order dependencies for partition and order expressions at optimization time.
Section 5.2 admits the general check is undecidable, and relies on tractable patterns (i)-(iii) plus implementation notes in Sections 3.2 and 5.3.
ad hoc to paper MOD predicates are identified and classified for ranking functions and cumulative frames over non-negative values without a general proof for all window functions.
Section 6.2 defines the MOD property and gives examples; Equivalence 14 assumes co-evaluation of any predicate, with only MOD predicates benefiting.
domain assumption Order dependencies such as [date] -> [year] are available to justify derived predicates for range comparisons.
Section 5.3 case (iii) needs this monotonic order dependency; without it the derived predicate in Equivalence 8 can change results for range predicates.

invented entities (1)

WF+ operator independent evidence
purpose: Extends DuckDB's window operator with co-evaluation, merge pruning, and partition pruning.
Implemented in the linked GitHub fork, so its behavior can be tested externally; correctness depends on the MOD classification and on tie handling during pruning.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Window Function Optimization: Co-Evaluation and Other Techniques." pith.science (2026). https://pith.science/paper/7TZGTEY4

@misc{pith2026260806043,
  author       = {Pith},
  title        = {Pith review of: Window Function Optimization: Co-Evaluation and Other Techniques},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7TZGTEY4}},
  note         = {Machine review of arXiv:2608.06043}
}

read the original abstract

Window functions are among the most expressive features of modern SQL. Surprisingly, relatively little has been written about their optimization. Some techniques exist, such as pushing predicates through a window under ideal conditions, but known optimizations no longer apply when those conditions are even slightly unmet. We show that these limitations are not fundamental, but persist because a reasoning framework for window function optimization has been missing. We provide such a framework, introducing techniques we call Frame Analysis, Partition Analysis, and a new execution strategy called Co-Evaluation. These clarify when and how optimizations can be applied. Co-Evaluation, in particular, allows early evaluation of predicates even when they depend on the window function's result. We present each technique and organize the results as a table of algebraic equivalences for window functions. We test these optimizations in an open-source engine, where they never hurt performance and make certain common queries up to 40.7 times faster, with larger tables yielding larger gains.

Figures

Figures reproduced from arXiv: 2608.06043 by the authors.

**Figure 2.** DuckDB’s WF pipeline for Q3. We use rnk<=2 for the purpose of this illustration. Top: standard execution. Bottom: WF+ with pruning at different phases. The benefits of WF+ ’s pruning points are cumulative, as early pruning reduces the work of all subsequent phases. scale without sorting the entire relation at once, and (D) framing/aggregation computes the results, using a segment tree to share aggregation work acro… view at source ↗

**Figure 4.** Microbenchmarks for Co-Evaluation (Q3, 𝒌 = 3, 𝜹 = 5) using different optimizations for different relation sizes and numbers of WF partitions, multi- (MT) and single-threaded (ST). Asterisk ∗ depicts a time-out within three times of the Baseline. The combination of optimization techniques is almost always considerably faster than the baseline. 1 2 3 4 Skew Factor 𝛼 (MT) 0 20 40 Runtime [ms] 1 2 3 4 Skew Factor 𝛼 (ST)… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 40 canonical work pages

[1]

Serge Abiteboul and Seymour Ginsburg. 1986. Tuple sequences and lexicographic indexes.J. ACM33, 3 (1986), 409–422. https://doi.org/10.1145/5925.5926

work page arXiv 1986
[2]

Alibaba Cloud. 2025. Window Functions. PolarDB-X Documentation. https: //doc.polardbx.com/en/dev-guide/topics/window.html (accessed July 17, 2026)

work page 2025
[3]

Amazon Web Services. 2025. Window Functions. Amazon Redshift Documenta- tion. https://docs.aws.amazon.com/redshift/latest/dg/c_Window_functions.html (accessed July 17, 2026)

work page 2025
[4]

Auerbach, Martin Hirzel, Louis Mandel, Avraham Shinnar, and Jérôme Siméon

Joshua S. Auerbach, Martin Hirzel, Louis Mandel, Avraham Shinnar, and Jérôme Siméon. 2017. Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler. InProceedings of the International Conference on Management of Data (SIGMOD). 1555–1569. https://doi.org/10.1145/3035918.3035961

work page arXiv 2017
[5]

Radim Bača. 2024. Window Function Expression: Let the Self-Join Enter.Pro- ceeding of the VLDB Endowment (PVLDB)17, 9 (2024), 2162–2174. https: //doi.org/10.14778/3665844.3665848

arXiv 2024
[6]

Mior, and Daniel Lemire

Edmon Begoli, Jesús Camacho-Rodríguez, Julian Hyde, Michael J. Mior, and Daniel Lemire. 2018. Apache Calcite: A Foundational Framework for Opti- mized Query Processing Over Heterogeneous Data Sources. InProceedings of the International Conference on Management of Data (SIGMOD). 221–230. https://doi.org/10.1145/3183713.3190662

arXiv 2018
[7]

2000.Analytic Functions in Oracle 8i

Srikanth Bellamkonda, Tolga Bozkaya, Biswapriyo Ghosh, Abhinav Gupta, John Haydu, Sankar Subramanian, and Andrew Witkowski. 2000.Analytic Functions in Oracle 8i. Technical Report. Oracle Corporation. http://infolab.stanford.edu/ infoseminar/archive/SpringY2000/speakers/agupta/paper.pdf

work page 2000
[8]

Bin Cao and Antonio Badia. 2007. SQL query optimization through nested relational algebra.ACM Transactions on Database Systems (TODS)32, 3 (2007), 46 pages. https://doi.org/10.1145/1272743.1272748

work page arXiv 2007

Show all 49 references

[9]

Yu Cao, Chee-Yong Chan, Jie Li, and Kian-Lee Tan. 2012. Optimization of Analytic Window Functions.Proceeding of the VLDB Endowment (PVLDB)5, 11 (2012), 1244–1255. https://doi.org/10.14778/2350229.2350243

2012
[10]

CedarDB GmbH. 2026. Reference: Window Functions. CedarDB Documentation. https://cedardb.com/docs/references/queries/window/ (accessed July 17, 2026)

2026
[11]

ClickHouse Inc. 2025. Window Functions. ClickHouse Documentation. https: //clickhouse.com/docs/sql-reference/window-functions (accessed July 17, 2026)

2025
[12]

Cockroach Labs. 2025. Window Functions. CockroachDB Documentation. https://www.cockroachlabs.com/docs/stable/window-functions (accessed July 17, 2026)

2025
[13]

DuckDB Foundation. 2025. Window Functions. DuckDB Documentation. https: //duckdb.org/docs/sql/window_functions (accessed July 17, 2026)

2025
[14]

Ullman, and Jennifer Widom

Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. 2009.Database systems - the complete book(2 ed.). Pearson Education

2009
[15]

Google Cloud. 2025. Window Function Calls. BigQuery Documenta- tion. https://docs.cloud.google.com/bigquery/docs/reference/standard-sql/ window-function-calls (accessed July 17, 2026)

2025
[16]

Stefan Heule, Marc Nunkesser, and Alexander Hall. 2013. HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. InProceedings of the International Conference on Extending Database Technology (EDBT). 683–692. https://doi.org/10.1...

2013
[17]

IBM. 2025. OLAP Specification. Db2 Documentation. https://www.ibm.com/ docs/en/db2/11.5?topic=expressions-olap-specification (accessed July 17, 2026)

2025
[18]

2023.Information technology – Database languages SQL – Part 2: Foundation (SQL/Foundation)

International Organization for Standardization. 2023.Information technology – Database languages SQL – Part 2: Foundation (SQL/Foundation). Standard Specification ISO/IEC 9075-2:2023(E)

2023
[19]

Gerhard Jaeschke and Hans-Jörg Schek. 1982. Remarks on the Algebra of Non First Normal Form Relations. InProceedings of the Symposium on Principles of Database Systems (PODS). 124–138. https://doi.org/10.1145/588111.588133

1982
[20]

Jan Kossmann, Thorsten Papenbrock, and Felix Naumann. 2022. Data depen- dencies for query optimization: a survey.The VLDB Journal31, 1 (2022), 1–22. https://doi.org/10.1007/S00778-021-00676-3

2022 doi
[21]

Laurens Kuiper. 2025. Redesigning DuckDB’s Sort, Again. https://duckdb.org/ 2025/09/24/sorting-again (accessed July 17, 2026)

2025
[22]

Laurens Kuiper and Hannes Mühleisen. 2023. These Rows Are Made for Sorting and That’s Just What We’ll Do. InProceedings of the International Conference on Data Engineering (ICDE). IEEE, 2050–2062. https://doi.org/10.1109/ICDE55515. 2023.00159

2023
[23]

Viktor Leis, Kan Kundhikanjana, Alfons Kemper, and Thomas Neumann. 2015. Efficient Processing of Window Functions in Analytical SQL Queries.Proceeding of the VLDB Endowment (PVLDB)8, 10 (2015), 1058–1069. https://doi.org/10. 14778/2794367.2794375

2015
[24]

Ilyas, and Sumin Song

Chengkai Li, Kevin Chen-Chuan Chang, Ihab F. Ilyas, and Sumin Song. 2005. RankSQL: Query Algebra and Optimization for Relational Top-k Queries. In Proceedings of the International Conference on Management of Data (SIGMOD). 131–142. https://doi.org/10.1145/1066157.1066173

2005
[25]

Leonid Libkin and Liat Peterfreund. 2023. SQL Nulls and Two-Valued Logic. In Proceedings of the Symposium on Principles of Database Systems (PODS). 11–20. https://doi.org/10.1145/3584372.3588661

2023
[26]

Daniel Lindner, Daniel Ritter, and Felix Naumann. 2026. Unleashing Data Dependency-based Query Optimization. InProceedings of the International Con- ference on Extending Database Technology (EDBT). 516–529. https://doi.org/10. 48786/EDBT.2026.41

2026
[27]

Hong-Cheu Liu and Kotagiri Ramamohanarao. 1994. Algebraic Equivalences Among Nested Relational Expressions. InProceedings of the International Con- ference on Information and Knowledge Management (CIKM). 234–243. https: //doi.org/10.1145/191246.191287

1994
[28]

Hong-Cheu Liu and Jeffrey Xu Yu. 2005. Algebraic equivalences of nested relational operators.Information Systems (IS)30, 3 (2005), 167–204. https: //doi.org/10.1016/J.IS.2003.12.001

2005 doi
[29]

Akifumi Makinouchi. 1977. A Consideration on Normal Form of Not-Necessarily- Normalized Relation in the Relational Data Model. InProceedings of the Interna- tional Conference on Very Large Databases (VLDB). 447–453

1977
[30]

Microsoft Corporation. 2025. OVER Clause (Transact-SQL). Microsoft SQL Server Documentation. https://learn.microsoft.com/en-us/sql/t-sql/queries/select-over- clause-transact-sql (accessed July 17, 2026)

2025
[31]

OceanBase. 2025. Window Function. OceanBase Database Documentation. https: //en.oceanbase.com/docs/common-oceanbase-database-10000000001718113 (ac- cessed July 17, 2026)

2025
[32]

Oracle Corporation. 2025. Analytic Functions. Oracle Database SQL Language Reference. https://docs.oracle.com/en/database/oracle/oracle-database/23/sqlrf/ Analytic-Functions.html (accessed July 17, 2026)

2025
[33]

Oracle Corporation. 2025. Window Function Concepts and Syntax. MySQL Reference Manual. https://dev.mysql.com/doc/refman/8.0/en/window-functions. html (accessed July 17, 2026)

2025
[34]

PingCAP. 2025. Window Functions. TiDB Documentation. https://docs.pingcap. com/tidb/stable/window-functions/ (accessed July 17, 2026)

2025
[35]

PostgreSQL Global Development Group. 2025. Window Functions. PostgreSQL Documentation. https://www.postgresql.org/docs/current/tutorial-window. html (accessed July 17, 2026)

2025
[36]

Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: an Embeddable Analytical Database. InProceedings of the International Conference on Management of Data (SIGMOD). 1981–1984. https://doi.org/10.1145/3299869.3320212

2019
[37]

Roth, Henry F

Mark A. Roth, Henry F. Korth, and Abraham Silberschatz. 1988. Extended Algebra and Calculus for Nested Relational Databases.ACM Transactions on Database Systems (TODS)13, 4 (1988), 389–417. https://doi.org/10.1145/49346.49347

1988
[38]

Raghav Sethi, Martin Traverso, Dain Sundstrom, David Phillips, Wenlei Xie, Yutian Sun, Nezih Yegitbasi, Haozhun Jin, Eric Hwang, Nileema Shingte, and Christopher Berner. 2019. Presto: SQL on Everything. InProceedings of the International Conference on Data Engineering (ICDE). ...

2019
[39]

Simmen, Eugene J

David E. Simmen, Eugene J. Shekita, and Timothy Malkemus. 1996. Fundamental Techniques for Order Optimization. InProceedings of the International Conference on Management of Data (SIGMOD). 57–67. https://doi.org/10.1145/233269.233320

1996
[40]

SingleStore Inc. 2025. Window Functions. SingleStore Documentation. https: //docs.singlestore.com/cloud/reference/sql-reference/window-functions/ (ac- cessed July 17, 2026)

2025
[41]

1997.Introduction to the theory of computation

Michael Sipser. 1997.Introduction to the theory of computation. International Thomson Publishing

1997
[42]

Snowflake Inc. 2025. Window Functions. Snowflake Documentation. https: //docs.snowflake.com/en/sql-reference/functions-window (accessed July 17, 2026)

2025
[43]

Soliman, Lyublena Antova, Venkatesh Raghavan, Amr El-Helw, Zhongxian Gu, Entong Shen, George C

Mohamed A. Soliman, Lyublena Antova, Venkatesh Raghavan, Amr El-Helw, Zhongxian Gu, Entong Shen, George C. Caragea, Carlos Garcia-Alvarado, Foyzur Rahman, Michalis Petropoulos, Florian Waas, Sivaramakrishnan Narayanan, Konstantinos Krikellas, and Rhonda Baldwin. 2014. Orca: a ...

2014 doi
[44]

SQLite Consortium. 2025. Built-In Window Functions. SQLite Documentation. https://www.sqlite.org/windowfunctions.html (accessed July 17, 2026)

2025
[45]

Jan Vincent Szlang, Sebastian Breß, Sebastian Cattes, Jonathan Dees, Florian Funke, Max Heimel, Michel Oleynik, Ismail Oukid, and Tobias Maltenberger
[46]

Jaroslaw Szlichta, Parke Godfrey, Jarek Gryz, and Calisto Zuzarte. 2013. Expres- siveness and Complexity of Order Dependencies.Proceeding of the VLDB Endow- ment (PVLDB)6, 14 (2013), 1858–1869. https://doi.org/10.14778/2556549.2556568

2013
[47]

Jeffrey D. Ullman. 1988.Principles of Database and Knowledge-Base Systems, Volume I. Principles of computer science series, Vol. 14. Computer Science Press

1988
[48]

Wangda Zhang and Kenneth A. Ross. 2022. Exploiting Data Skew for Improved Query Performance.IEEE Transactions on Knowledge and Data Engineering (TKDE)34, 5 (2022), 2176–2189. https://doi.org/10.1109/TKDE.2020.3006446

2022
[2025]

https://doi.org/10.14778/3750601.3750632

Workload Insights From the Snowflake Data Cloud: What Do Production Analytic Queries Really Look Like?Proceeding of the VLDB Endowment (PVLDB) 18, 12 (2025), 5126–5138. https://doi.org/10.14778/3750601.3750632

2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Serge Abiteboul and Seymour Ginsburg. 1986. Tuple sequences and lexicographic indexes.J. ACM33, 3 (1986), 409–422. https://doi.org/10.1145/5925.5926

work page arXiv 1986

[2] [2]

Alibaba Cloud. 2025. Window Functions. PolarDB-X Documentation. https: //doc.polardbx.com/en/dev-guide/topics/window.html (accessed July 17, 2026)

work page 2025

[3] [3]

Amazon Web Services. 2025. Window Functions. Amazon Redshift Documenta- tion. https://docs.aws.amazon.com/redshift/latest/dg/c_Window_functions.html (accessed July 17, 2026)

work page 2025

[4] [4]

Auerbach, Martin Hirzel, Louis Mandel, Avraham Shinnar, and Jérôme Siméon

Joshua S. Auerbach, Martin Hirzel, Louis Mandel, Avraham Shinnar, and Jérôme Siméon. 2017. Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler. InProceedings of the International Conference on Management of Data (SIGMOD). 1555–1569. https://doi.org/10.1145/3035918.3035961

work page arXiv 2017

[5] [5]

Radim Bača. 2024. Window Function Expression: Let the Self-Join Enter.Pro- ceeding of the VLDB Endowment (PVLDB)17, 9 (2024), 2162–2174. https: //doi.org/10.14778/3665844.3665848

arXiv 2024

[6] [6]

Mior, and Daniel Lemire

Edmon Begoli, Jesús Camacho-Rodríguez, Julian Hyde, Michael J. Mior, and Daniel Lemire. 2018. Apache Calcite: A Foundational Framework for Opti- mized Query Processing Over Heterogeneous Data Sources. InProceedings of the International Conference on Management of Data (SIGMOD). 221–230. https://doi.org/10.1145/3183713.3190662

arXiv 2018

[7] [7]

2000.Analytic Functions in Oracle 8i

Srikanth Bellamkonda, Tolga Bozkaya, Biswapriyo Ghosh, Abhinav Gupta, John Haydu, Sankar Subramanian, and Andrew Witkowski. 2000.Analytic Functions in Oracle 8i. Technical Report. Oracle Corporation. http://infolab.stanford.edu/ infoseminar/archive/SpringY2000/speakers/agupta/paper.pdf

work page 2000

[8] [8]

Bin Cao and Antonio Badia. 2007. SQL query optimization through nested relational algebra.ACM Transactions on Database Systems (TODS)32, 3 (2007), 46 pages. https://doi.org/10.1145/1272743.1272748

work page arXiv 2007