cockroachdb / cockroachdb/cockroach

sql/colexec: ordered aggregates (`string_agg`/`array_agg`/`json_agg` ... `ORDER BY`) return elements in the wrong order when the vectorized hash aggregator spills to disk

Open
#175,541 1 comment 0 reactions 0 assignees View on GitHub
C-bug O-community T-sql-queries X-blathers-triaged
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

## Describe the problem

An aggregate with its own `ORDER BY` — `string_agg(x, sep ORDER BY ...)`,
`array_agg(x ORDER BY ...)`, `json_agg(x ORDER BY ...)`, `concat_agg(x ORDER BY ...)` —
returns its elements **in the wrong order** when the vectorized hash aggregator
spills to disk and falls back to "external sort + ordered aggregation".

No error is raised and the statement reports success. The result is not truncated:
the multiset of aggregated elements is exactly right, only the order is wrong, so
nothing about the result looks suspicious.

The optimizer implements `agg(x ORDER BY y)` by sorting the *input* of the hash
aggregator on `y` and relying on the aggregator to append tuples to each group in
input order. The disk-spilling fallback re-sorts the partition on the **GROUP BY
columns only**, which destroys the intra-group ordering the aggregation depends on.

## To Reproduce

Single insecure node, defaults except `distsql_workmem`:

```
cockroach start-single-node --insecure --store=/path/to/store
```

```sql
CREATE TABLE one (id INT PRIMARY KEY, k INT, c STRING);
INSERT INTO one SELECT i, 1, chr(97 + (i*7)%26) FROM generate_series(0, 19999) g(i);
-- one group of 20 000 rows; c cycles through 'a'..'z'

-- string_agg(c, '' ORDER BY c, id) must be non-decreasing by construction,
-- so a correct result has 0 inversions. No reference query is needed.
SET distsql_workmem = '1MiB';
SELECT length(s) AS chars,
(SELECT count(*) FROM generate_series(1, length(s)-1) t(i)
WHERE substr(s,i,1) > substr(s,i+1,1)) AS inversions
FROM (SELECT string_agg(c, '' ORDER BY c, id) AS s FROM one GROUP BY k) x;
```

## Expected behavior

```
chars | inversions
--------+-------------
20000 | 0
```

which is what `SET distsql_workmem = '64MiB'` (the default) returns.

## Actual behavior

```
chars | inversions
--------+-------------
20000 | 5
```

The 20 000 characters come back as six internally sorted runs concatenated in the
wrong order — inversions at offsets 4987, 7355, 9794, 15264, 17632, e.g.
`...qqqqqqqq|jjjj...` at 4987 and `...nnnnnn|gggggg...` at 7355.

The result is **deterministic** — identical `md5(s)` on repeated runs, on fresh
sessions, and on both v26.2.6 and v26.3.0 (`8fdb31fe8e3aacb3b052bf9d9351b153`).

It is a pure reordering: with four groups (40 000 rows) the per-group character
histograms of the aggregated strings match the source exactly (0 mismatches), and
the total length is exactly 40 000. Only some groups are corrupted — in that case
one group of four, and its string ends in `mmm` instead of `zzz`:

```sql
CREATE TABLE multi (id INT PRIMARY KEY, g INT, c STRING);
INSERT INTO multi SELECT i, i%4, chr(97 + (i*7)%26) FROM generate_series(0, 39999) g(i);
SET distsql_workmem = '1MiB';
SELECT g, left(s,3) AS first3, right(s,3) AS last3,
(SELECT count(*) FROM generate_series(1,length(s)-1) t(i)
WHERE substr(s,i,1) > substr(s,i+1,1)) AS inversions
FROM (SELECT g, string_agg(c,'' ORDER BY c,id) AS s FROM multi GROUP BY g) x ORDER BY g;

g | first3 | last3 | inversions
---+--------+-------+------------
0 | aaa | yyy | 0
1 | bbb | zzz | 0
2 | aaa | mmm | 3 <-- wrong
3 | bbb | zzz | 0
```

### Scope

| | |
|---|---|
| Affected | `string_agg`, `array_agg`, `json_agg`, `concat_agg` with an aggregate `ORDER BY` |
| Engine | vectorized only — `SET vectorize = off` is correct at the same threshold |
| Versions | v26.2.6 and v26.3.0 both reproduce, byte-identical; the responsible code is unchanged on `master` |
| Not affected | `percentile_disc(...) WITHIN GROUP (ORDER BY ...)` (sorts its own state); `DISTINCT ON` (planned as `orderedDistinct` over a sort, no hash aggregator) |

All four aggregates are affected, each in its own query, on the 20 000-row table
above (inversion counts; 0 = correct):

| `distsql_workmem` | `string_agg` | `array_agg` | `concat_agg` | `json_agg` |
|---|---|---|---|---|
| 384 KiB | 0 | 0 | 0 | 0 |
| 512 KiB | 4 | 3 | 3 | 3 |
| 640 KiB | 5 | 4 | 4 | 4 |
| 768 KiB | 7 | 0 | 4 | 0 |
| 896 KiB | 6 | 0 | 0 | 0 |
| 1 MiB | 5 | 0 | 0 | 0 |
| 1280 KiB | 4 | 0 | 0 | 0 |
| 1536 KiB | 0 | 0 | 0 | 0 |

The exact window differs per aggregate because the aggregate's own state counts
against the same budget — which is also why combining two of them in one query
shifts it. `string_agg` and `array_agg` in a single statement are both wrong at
1 MiB, where `array_agg` alone is correct.

`EXPLAIN ANALYZE` at 1 MiB confirms both halves of the mechanism — the sort on the
aggregate's `ORDER BY` columns sits *below* the hash aggregator, which then spills:

```
max sql temp disk usage: 3.0 MiB

• group (hash)
│ group by: k
└── • render
└── • sort
│ order: +c,+id <-- the aggregate's ORDER BY
└── • scan
table: one@one_pkey
```

`EXPLAIN (VEC)`:

```
└ Node 1
└ *colexec.hashAggregator
└ *colexecbase.constBytesOp
└ *colexec.sortOp
└ *colfetcher.ColBatchScan
```

## Environment

- CockroachDB v26.2.6 (x86_64-pc-linux-gnu, built 2026/08/24, go1.25.13), release build
- also reproduced on v26.3.0 (built 2026/07/28), byte-identical wrong result
- single node, `start-single-node --insecure`, all settings default except
`distsql_workmem`
- Ubuntu 22.04.2, Linux 5.15.0, x86_64

Jira issue: CRDB-68448

Contributor guide

Open the contributing guide

Research direction

Start at the vectorized colexec.hashAggregator and its spill path, using the EXPLAIN and EXPLAIN (VEC) plans in the report to trace the sort below the hash aggregator. Check how aggregate ORDER BY columns are handled when spilled and add regression coverage for string_agg, array_agg, json_agg, and concat_agg under low distsql_workmem. Done means each aggregate preserves its requested order after spilling, matching the non-spilling result.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.