Window functions with ORDER BY are up to 1.8 times slower than in 3.0, because the frame is evaluated for every row, also for functions that do not use it (4.0, 5.0, master)

[tomaszdubiel18]

Below are the results of analysis performed by AI.

Title: Window functions with ORDER BY are up to 1.8 times slower than in 3.0, because the frame is evaluated for every row, also for functions that do not use it (4.0, 5.0, master)

Summary

Since 4.0, window functions with ORDER BY in the window (ROW_NUMBER, RANK, DENSE_RANK, LAG, running SUM/COUNT, ...) are slower than in 3.0.
The test case below shows 1.28–1.40 times slower execution when the window buffer fits in memory, and 1.74 times slower execution when it is spilled to the temporary file.
The sort that feeds the window is not slower, and windows without ORDER BY are affected only marginally.

The cause is in WindowedStream::WindowStream::internalGetRecord(), which reads every row from the window buffer about 7 times instead of once.
A patch for v5.0-release is included below.
It does not change any results, makes ROW_NUMBER faster than in 3.0, and reduces the time of RANK and running SUM by about a quarter.

Environment

• Firebird 3.0.14.33856, 4.0.8.3328 (97f2656) and 5.0.5.1903 (snapshot, 14bfcdf): official Linux x64 packages.
• Two own builds of v5.0-release at the same commit 14bfcdf (gcc 13.3, release build): one unchanged and one with the patch below. The unchanged own build and the official 5.0.5.1903 package differ by at most about 8%.
• SuperServer, DefaultDbCachePages = 32768, all other settings default (TempCacheLimit 64 MB), page size 16 KB, 2 vCPU.
• isql over TCP; times are "Elapsed time" from SET STATS ON, median of 5 runs on a warm cache.

Test case

-- 1,000,000 rows, 10,000 partitions of 100 rows (column k), unique sort key (d, id)
create table t (
  id integer not null primary key,
  k integer,
  d date,
  v numeric(15,2)
);
commit;
set term ^;
execute block as
  declare i integer = 1;
begin
  while (i <= 1000000) do
  begin
    insert into t (id, k, d, v)
    values (:i, mod(:i * 7919, 10000), dateadd(mod(:i * 31, 2000) day to date '2020-01-01'),
            mod(:i * 13, 100000) / 100.00);
    i = i + 1;
  end
end^
set term ;^
commit;
-- 150,000 rows, 1,500 partitions of 100 rows (the window buffer fits into the default TempCacheLimit)
create table t2 (
  id integer not null primary key,
  k integer,
  d date,
  v numeric(15,2)
);
commit;
insert into t2 select * from t where k < 1500;
commit;
 
set stats on;
-- Q1: the same sort without a window (reference)
select count(*), sum(x.id) from (select first 2000000 id from t2 order by k, d, id) x;
-- Q2: ROW_NUMBER with ORDER BY
select count(*), sum(x.w) from (select row_number() over (partition by k order by d, id) w from t2) x;
-- Q3: ROW_NUMBER without ORDER BY
select count(*), sum(x.w) from (select row_number() over (partition by k) w from t2) x;
-- Q4: RANK
select count(*), sum(x.w) from (select rank() over (partition by k order by d, id) w from t2) x;
-- Q5: running SUM, default frame (RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
select count(*), sum(x.w) from (select sum(v) over (partition by k order by d, id) w from t2) x;
-- Q6: ROW_NUMBER with ORDER BY, 1,000,000 rows (the window buffer is spilled to the temporary file)
select count(*), sum(x.w) from (select row_number() over (partition by k order by d, id) w from t) x;
-- Q7 (4.0+): running SUM with an explicit ROWS frame
select count(*), sum(x.w) from (select sum(v) over (partition by k order by d, id rows between unbounded preceding and current row) w from t2) x;

Results

All versions return the same results.

Query	3.0.14	4.0.8	5.0.5	5.0.5 / 3.0.14	5.0 own build	5.0 own build + patch
Q1 sort without window	0.119 s	0.117 s	0.116 s	0.97	0.117 s	0.106 s
Q2 ROW_NUMBER, ORDER BY	0.246 s	0.317 s	0.314 s	1.28	0.325 s	0.209 s
Q3 ROW_NUMBER, no ORDER BY	0.147 s	0.152 s	0.152 s	1.03	0.154 s	0.148 s
Q4 RANK	0.237 s	0.309 s	0.312 s	1.32	0.330 s	0.251 s
Q5 running SUM (RANGE)	0.256 s	0.345 s	0.358 s	1.40	0.376 s	0.282 s
Q6 ROW_NUMBER, 1,000,000 rows	3.336 s	5.777 s	5.816 s	1.74	6.026 s	2.675 s
Q7 running SUM (ROWS)	–	0.290 s	0.291 s	–	0.315 s	0.234 s

4.0 and 5.0 behave the same, so the slowdown came with the 4.0 rework of window functions (frame support).
A wider set of measurements on the same data (Python client, 3–7 runs) gives the same picture.
With 1,000,000 rows, ROW_NUMBER, RANK, DENSE_RANK, running SUM and running COUNT are 1.7–1.8 times slower than in 3.0, and LAG is 1.36 times slower.
With TempCacheLimit = 1G, Q6 takes 1.66 s in 3.0.14 and 2.11 s in 5.0.5.

With the patch:

• ROW_NUMBER is 36% faster in memory and 56% faster with the temporary file, which makes it faster than in 3.0.
• RANK and running SUM are 24–26% faster in memory and about 35% faster with the temporary file, but still 6–21% slower than in 3.0.
• Queries without ORDER BY in the window are not affected.

Cause (based on reading the source code)

Functions that do not respect the frame (ROW_NUMBER, RANK, DENSE_RANK, PERCENT_RANK, CUME_DIST, NTILE, LAG, LEAD) always get the default frame RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW (ExprNodes.cpp).
For this frame, WindowStream::internalGetRecord() does the following for each row:

1. To find the window end (L713-L739), it reads the following rows until the order key changes, then moves back with locate() and reads the current row again.
2. To compute rangePending (L759-L783), it repeats the same peer-group scan with the same result, then moves back and reads the current row again.
3. In the aggregation block (L785-L853), it extends the previous window by the new row: it calls locate(), reads the row, calls aggPass(), then calls locate() and reads the current row once more. This is done even when the window has no aggregate functions; the code says so in a comment: //// TODO: There is no need to pass record by record when m_aggSources.isEmpty().
   ROW_NUMBER, LAG, LEAD and NTILE use neither the frame nor the aggregation; they need only the partition boundaries and the row position.
   With a unique order key, every row is thus read from the window buffer about 7 times.
   Each BufferedStream::internalGetRecord() copies all fields of the record, and when the buffer is in the temporary file, each read is also a read() + lseek() system call, which explains the larger slowdown of Q6.

Callgrind measurement on 20,000 rows (200 partitions of 100), own builds; the window part is the query minus Q1 on the same data:

Query	build	BufferedStream::getRecord calls	BufferedStream::locate calls	instructions, window part
Q3 ROW_NUMBER, no ORDER BY	unchanged	120,503	20,801	96 M
Q2 ROW_NUMBER, ORDER BY	unchanged	219,703	100,201	380 M
Q2 ROW_NUMBER, ORDER BY	patched	100,103	20,201	166 M
Q4 RANK	unchanged → patched	219,703 → 140,303	100,201 → 40,601	383 M → 249 M
Q5 running SUM	unchanged → patched	219,703 → 140,303	100,201 → 40,601	459 M → 304 M

The call counts include filling the buffers.
The same code is in master (e1e14ac), extended with GROUPS and EXCLUDE; master was not measured.

Proposed change

The patch for v5.0-release (below) changes WindowedStream.cpp and RecordSource.h:

1. If a window has no aggregate functions and its other functions are only ROW_NUMBER, LAG, LEAD and NTILE, the frame and the aggregation are not evaluated. aggInit() is still called on the first row of each partition, where the original code called it. The flag is computed once, in the WindowStream constructor.
2. The peer group is scanned once; the result is used both for the window end and for rangePending (new helper findPeerGroupEnd()).
3. The stream is moved back to the current row only if it was actually moved.
4. When the frame grows by exactly the current row (same start, previous end position - 1, new end position), the current record, which is already fetched, is passed to aggPass() directly. This covers running aggregates with a ROWS frame and with a RANGE frame over a unique order key.
   RANK, DENSE_RANK, PERCENT_RANK, CUME_DIST, FIRST_VALUE, LAST_VALUE, NTH_VALUE and the aggregate functions keep the frame evaluation and benefit only from changes 2–4.

Notes:

• Frame-independent functions are recognized by aggInfo.name, because the engine is built without RTTI. A cleaner way would be a new capability flag in AggNode, next to CAP_SUPPORTS_WINDOW_FRAME and CAP_RESPECTS_WINDOW_FRAME; it was not added, to avoid changing Nodes.h. An unrecognized function simply stays on the original path.
• For master, the patch needs to be adapted to GROUPS and EXCLUDE. For example, change 4 must apply only when m_exclusion == Exclusion::NO_OTHERS.

Verification of the patch

The patched build was compared with the official 5.0.5.1903 on 70 queries, and all results were identical:

• 41 queries over a 20,000-row table with ties and NULLs in the order key and NULLs in the arguments: all window functions, windows with and without PARTITION BY / ORDER BY, ROWS and RANGE frames with offsets, DESC and NULLS FIRST/LAST, several functions in one window, empty and one-row input;
• 20 queries with less common usage: correlated subqueries with windows, a selectable procedure with windows called for each outer row, a view with windows read with FIRST/SKIP, windows over GROUP BY (including SUM(SUM(...)) OVER), different windows in one query, one-row partitions, peers defined by a case-insensitive collation, an invalid NTILE argument (the same error is raised);
• 9 checksum queries over 1,000,000 rows with the window buffer in the temporary file.
  The firebird-qa test files containing OVER ( (183 files) give identical results on the unchanged and the patched build: 147 passed, 4 skipped, 27 deselected.
  7 of them fail on both builds and also on the official 5.0.5.1903, for reasons unrelated to window functions (environment, plan expectations).

The only other observable difference is in the profiler statistics: the record source under Window Partition is fetched fewer times (for Q2 on 20,000 rows, FETCH_COUNTER of that Record Buffer drops from 179,424 to 59,498).

Expected behaviour

ROW_NUMBER, LAG, LEAD and NTILE with ORDER BY in the window cost the same as without it, apart from the sort.
For the other window functions, each row is read from the window buffer only as many times as the frame actually requires.

[tomaszdubiel18]

window_frame_5_0.patch

[hvlad]

Please remove duplicated part of description

[tomaszdubiel18]

Sorry. The ticket is already corrected.

[asfernandes]

Please test #9195

[tomaszdubiel18]

Below are the results of analysis performed by AI.

The fix was tested with the CI artifact firebird-linux-x64 of this PR (6.0.0.2199), Linux x64, SuperServer, 2 vCPU, DefaultDbCachePages = 32768, page size 16384, default TempCacheLimit.
Baseline without the fix: the CI artifact of #9194 (6.0.0.2199), built on the same master commit 474cb87; that PR changes only the time zone code.
Snapshot 6.0.0.2197 (e1e14ac) was used as a second reference for correctness.
No differences in results and no performance regressions were found.

Correctness

The output of every query was compared (md5 of the full isql output) between the PR build, the baseline and 6.0.0.2197.

1. The 41 queries used for the 5.0 patch from the issue: all window functions, ties and NULLs in the sort key, ROWS/RANGE frames with offsets, several functions in one window, empty input.
2. 21 edge cases: correlated subqueries with windows (the stream is reopened many times), a selectable procedure with windows called per row, a view with a window and FIRST/SKIP, windows over GROUP BY including SUM(SUM()) OVER, RANGE frames with DESC/NULLS FIRST/LAST and offsets (also 2 PRECEDING AND 2 PRECEDING, 0 PRECEDING AND 0 FOLLOWING), ties from UNICODE_CI, 1-row partitions, NTILE(0) error.
3. 42 queries for the code paths that exist only in master (2 of them, with DISTINCT in an ordered window, are rejected with the same error by all builds):

• GROUPS frames with all kinds of bounds (1 PRECEDING AND CURRENT ROW, CURRENT ROW AND 1 FOLLOWING, 2 PRECEDING AND 1 PRECEDING, 1 FOLLOWING AND 2 FOLLOWING, unbounded), also with DESC, NULLs and UNICODE_CI,
• EXCLUDE CURRENT ROW / GROUP / TIES / NO OTHERS with ROWS, RANGE and GROUPS frames, for aggregates and for FIRST_VALUE, LAST_VALUE, NTH_VALUE, MIN, MAX,
• CUME_DIST together with ROW_NUMBER in the same window (CAP_USES_WINDOW_FRAME),
• ROW_NUMBER, NTILE, LAG, LEAD in a window with an explicit frame and EXCLUDE (the path where the frame is skipped),
• frames entirely before or after the current row (3 FOLLOWING AND 5 FOLLOWING, 5 PRECEDING AND 2 PRECEDING, also RANGE), UNBOUNDED PRECEDING AND 2 FOLLOWING,
• a ROWS frame with a per-row offset (mod(id, 3) PRECEDING).

4. Checksums over 1 million rows (window buffer in a temporary file): 9 queries from the issue plus 5 with GROUPS, EXCLUDE and CUME_DIST.
   All results identical.

firebird-qa (current master), the 183 test files that contain OVER (: identical outcome for every test on the PR build and the baseline (164 passed, 13 failed, 5 skipped, 1 error).
The failures are the same on both builds and are caused by the local environment (expected plans, parallel workers, external connection pool, replication, trace) or by expected output; gh_8946_test fails also on 6.0.0.2197 because of trailing zeros of NUMERIC values in the expected output.

Performance

Seconds, median of 5 interleaved runs (11 runs for the 150k rows queries marked with *).
Table t: 1,000,000 rows, 10,000 partitions of 100 rows, unique sort key (d, id); table t2: 150,000 rows of t (fits into the default TempCacheLimit).
Query shape: select count(*), sum(x.w) from (select <window function> as w from t) x.

Query	rows	3.0.14	5.0.5.1903	master	PR	PR / master
sort only, no window	150k	0.101	0.090	0.106	0.101	0.95
ROW_NUMBER() OVER (PARTITION BY k ORDER BY d, id)	150k	0.213	0.313	0.321	0.200	0.62
ROW_NUMBER() OVER (PARTITION BY k) *	150k	0.141	0.144	0.151	0.148	0.98
RANK()	150k	0.200	0.261	0.303	0.231	0.76
LAG(id)	150k	0.262	0.294	0.322	0.239	0.74
NTILE(4)	150k		0.270	0.298	0.194	0.65
CUME_DIST()	150k		0.286	0.318	0.243	0.76
SUM(v), default frame (RANGE)	150k	0.242	0.311	0.345	0.280	0.81
SUM(v) ... ROWS UNBOUNDED PRECEDING	150k		0.251	0.293	0.240	0.82
SUM(v) ... ROWS BETWEEN 2 PRECEDING AND 2 FOLLOWING *	150k		0.335	0.382	0.361	0.94
SUM(v) OVER (PARTITION BY k ORDER BY d GROUPS BETWEEN 1 PRECEDING AND CURRENT ROW) *	150k			0.257	0.264	1.03
SUM(v) ... ROWS BETWEEN 2 PRECEDING AND 2 FOLLOWING EXCLUDE CURRENT ROW *	150k			0.385	0.366	0.95
sort only, no window	1M	0.682	0.663	0.708	0.724	1.02
ROW_NUMBER() OVER (PARTITION BY k ORDER BY d, id)	1M	3.093	5.657	5.768	2.627	0.46
ROW_NUMBER() OVER (PARTITION BY k)	1M	1.840	2.134	2.259	2.039	0.90
RANK()	1M	3.125	5.728	5.943	3.864	0.65
LAG(id)	1M	4.993	6.664	7.098	3.519	0.50
NTILE(4)	1M		5.707	5.984	2.748	0.46
CUME_DIST()	1M		5.662	5.933	3.768	0.64
SUM(v), default frame (RANGE)	1M	3.132	5.770	5.931	3.724	0.63
SUM(v) ... ROWS UNBOUNDED PRECEDING	1M		4.209	4.464	2.724	0.61
SUM(v) ... ROWS BETWEEN 2 PRECEDING AND 2 FOLLOWING	1M		5.782	5.980	5.797	0.97
SUM(v) ... GROUPS BETWEEN 1 PRECEDING AND CURRENT ROW	1M			4.150	3.893	0.94
SUM(v) ... ROWS BETWEEN 2 PRECEDING AND 2 FOLLOWING EXCLUDE CURRENT ROW	1M			6.290	5.757	0.92

Unless stated otherwise the window is OVER (PARTITION BY k ORDER BY d, id).
ROW_NUMBER and LAG with ORDER BY are now faster than in 3.0.14.
RANK and the running SUM are 15-24% slower than in 3.0.14 (before the fix: 43-90%).
Frames that move with every row (2 PRECEDING AND 2 FOLLOWING, GROUPS, EXCLUDE) are unchanged within noise (±5%) at 150k rows and 3-8% faster at 1M rows.

[asfernandes]

Summary, please.

[tomaszdubiel18]

Summary

• Correctness: OK. No differences in results in 118 queries (including GROUPS, EXCLUDE and 1 million row checksums) and no change in the outcome of any of the 183 firebird-qa tests with window functions.
• Performance: OK. No regressions; window functions with ORDER BY are 19-54% faster (ROW_NUMBER with 1 million rows: 5.77 s → 2.63 s).
• Stability: OK. No crashes or engine errors; firebird.log is the same for both builds.
• Remark (informational): RANK and the running SUM are still 15-24% slower than in 3.0.14 (before the fix: 43-90%).
• Remark: the issue also affects 4.0 and 5.0, this PR targets master only.

[dyemanov]

Such a summary is what every AI generated report should end with (details are also welcome, but only if the summary is provided). Please take it as a rule of thumb for future contributions.

[tomaszdubiel18]

OK, no problem. Is it better to place it at the start or at the end of the report?

[dyemanov]

I'd suggest putting it at the start.