… allows them to create a `FunctionLocalState` that is persisted across `Finalize` calls, and use this to speed up ordered aggregates (#23270)

Ordered aggregates need a lot of dynamically allocated state during
`Finalize`. Currently this is re-allocated for every vector. However,
this allocation can become a significant bottleneck when there are only
a few rows per aggregate, dominating the actual execution time for the
sort + aggregation phase.

As an example, the `Many Groups` benchmark in
#23231:

```sql
-- Many Groups
-- 1.5M groups, ~4 rows each group
select string_agg(l_comment order by l_linenumber) from lineitem group by l_orderkey;
```

This takes 0.7s on TPC-H SF1 after the `list` rework, but the majority
of time is spent on (re)-allocation of intermediate structs.

This PR adds the `init_local_state_finalize` callback that can be used
to cache intermediate structures during the `finalize`, and rewires the
ordered aggregates to use this infrastructure. This greatly speeds up
ordered aggregates with small groups. For the above benchmark, these are
the new timings:

| Version | Timing (s) |
|---------|------------|
| v1.5    | 2.5s       |
| main    | 0.75s      |
| new     | 0.2s       |

i.e. small ordered aggregates are now >10x faster than in v1.5 as a
combined result of using the linked lists together with the intermediate
state caching.

This PR adds support for state export to ordered aggregates. Now that
they follow the list infrastructure
(duckdb#23231) this is relatively
straightforward as we can already export/import their intermediate state
using the generic state export/import code.

The aggregate state is a `list` of structs, where the struct holds all
columns required by the aggregate and the order by. For example:

```sql
-- required columns are "l_comment", "l_orderkey"
select string_agg(l_comment order by l_orderkey) export_state from lineitem group by l_shipdate limit 5;
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                      string_agg(l_comment ORDER BY l_orderkey) EXPORT_STATE                                      │
│                                                         aggregate_state                                                          │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi, 'v1': 5601}]                                                                               │
│ [{'v0': ' carefully. i', 'v1': 5409}]                                                                                            │
│ [{'v0': ' carefully aroun', 'v1': 4800}]                                                                                         │
│ [{'v0': 'play. special, regular pint', 'v1': 3712}]                                                                              │
│ [{'v0': 'kages. blithe, c', 'v1': 1248}, {'v0': carefully final instr, 'v1': 3271}, {'v0': furiously furiously eve, 'v1': 5382}] │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
```

The main challenge then lies in the (re)-binding of the ordered
aggregates. Effectively this expands the function signature that is held
in the aggregate state with an `ORDER BY` clause:

```cpp
ext_info->properties.emplace("order_bys", Value::LIST(OrderByEntryType(), std::move(order_values)));
```

For `to_aggregate_state`, we get an extra parameter to define these
order terms, with the columns referenced by offset:

```sql
select finalize(to_aggregate_state([{'v0': 'world', 'v1': 2}, {'v0': 'hello', 'v1': 1}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 1, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

When a column is used both as an argument to the aggregate function, and
as a condition in the `ORDER BY` clause, it is contained only once in
the list. For example:

```sql
select string_agg(l_comment order by l_comment) export_state from lineitem group by l_shipdate limit 3;
┌───────────────────────────────────────────────────────┐
│ string_agg(l_comment ORDER BY l_comment) EXPORT_STATE │
│                    aggregate_state                    │
├───────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi}]                │
│ [{'v0': ' carefully. i'}]                             │
│ [{'v0': ' carefully aroun'}]                          │
└───────────────────────────────────────────────────────┘
```

Similarly we can then define the `ORDER BY` term to just refer to the
first column. The column will then be both part of the aggregate and
part of the `ORDER BY` clause:

```sql
select finalize(to_aggregate_state([{'v0': 'world'}, {'v0': 'hello'}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 0, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

… allows them to create a `FunctionLocalState` that is persisted across `Finalize` calls, and use this to speed up ordered aggregates (https://redirect.github.com/duckdb/duckdb/pull/23270)

Ordered aggregates need a lot of dynamically allocated state during
`Finalize`. Currently this is re-allocated for every vector. However,
this allocation can become a significant bottleneck when there are only
a few rows per aggregate, dominating the actual execution time for the
sort + aggregation phase.

As an example, the `Many Groups` benchmark in
duckdb#23231:

```sql
-- Many Groups
-- 1.5M groups, ~4 rows each group
select string_agg(l_comment order by l_linenumber) from lineitem group by l_orderkey;
```

This takes 0.7s on TPC-H SF1 after the `list` rework, but the majority
of time is spent on (re)-allocation of intermediate structs.

This PR adds the `init_local_state_finalize` callback that can be used
to cache intermediate structures during the `finalize`, and rewires the
ordered aggregates to use this infrastructure. This greatly speeds up
ordered aggregates with small groups. For the above benchmark, these are
the new timings:

| Version | Timing (s) |
|---------|------------|
| v1.5    | 2.5s       |
| main    | 0.75s      |
| new     | 0.2s       |

i.e. small ordered aggregates are now >10x faster than in v1.5 as a
combined result of using the linked lists together with the intermediate
state caching.

Upstream-commit: duckdb@61e2e64

…github.com/duckdb/duckdb/pull/23376)

This PR adds support for state export to ordered aggregates. Now that
they follow the list infrastructure
(duckdb#23231) this is relatively
straightforward as we can already export/import their intermediate state
using the generic state export/import code.

The aggregate state is a `list` of structs, where the struct holds all
columns required by the aggregate and the order by. For example:

```sql
-- required columns are "l_comment", "l_orderkey"
select string_agg(l_comment order by l_orderkey) export_state from lineitem group by l_shipdate limit 5;
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                      string_agg(l_comment ORDER BY l_orderkey) EXPORT_STATE                                      │
│                                                         aggregate_state                                                          │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi, 'v1': 5601}]                                                                               │
│ [{'v0': ' carefully. i', 'v1': 5409}]                                                                                            │
│ [{'v0': ' carefully aroun', 'v1': 4800}]                                                                                         │
│ [{'v0': 'play. special, regular pint', 'v1': 3712}]                                                                              │
│ [{'v0': 'kages. blithe, c', 'v1': 1248}, {'v0': carefully final instr, 'v1': 3271}, {'v0': furiously furiously eve, 'v1': 5382}] │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
```

The main challenge then lies in the (re)-binding of the ordered
aggregates. Effectively this expands the function signature that is held
in the aggregate state with an `ORDER BY` clause:

```cpp
ext_info->properties.emplace("order_bys", Value::LIST(OrderByEntryType(), std::move(order_values)));
```

For `to_aggregate_state`, we get an extra parameter to define these
order terms, with the columns referenced by offset:

```sql
select finalize(to_aggregate_state([{'v0': 'world', 'v1': 2}, {'v0': 'hello', 'v1': 1}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 1, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

When a column is used both as an argument to the aggregate function, and
as a condition in the `ORDER BY` clause, it is contained only once in
the list. For example:

```sql
select string_agg(l_comment order by l_comment) export_state from lineitem group by l_shipdate limit 3;
┌───────────────────────────────────────────────────────┐
│ string_agg(l_comment ORDER BY l_comment) EXPORT_STATE │
│                    aggregate_state                    │
├───────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi}]                │
│ [{'v0': ' carefully. i'}]                             │
│ [{'v0': ' carefully aroun'}]                          │
└───────────────────────────────────────────────────────┘
```

Similarly we can then define the `ORDER BY` term to just refer to the
first column. The column will then be both part of the aggregate and
part of the `ORDER BY` clause:

```sql
select finalize(to_aggregate_state([{'v0': 'world'}, {'v0': 'hello'}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 0, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

Upstream-commit: duckdb@22b2fa9

… allows them to create a `FunctionLocalState` that is persisted across `Finalize` calls, and use this to speed up ordered aggregates (https://redirect.github.com/duckdb/duckdb/pull/23270)

Ordered aggregates need a lot of dynamically allocated state during
`Finalize`. Currently this is re-allocated for every vector. However,
this allocation can become a significant bottleneck when there are only
a few rows per aggregate, dominating the actual execution time for the
sort + aggregation phase.

As an example, the `Many Groups` benchmark in
duckdb#23231:

```sql
-- Many Groups
-- 1.5M groups, ~4 rows each group
select string_agg(l_comment order by l_linenumber) from lineitem group by l_orderkey;
```

This takes 0.7s on TPC-H SF1 after the `list` rework, but the majority
of time is spent on (re)-allocation of intermediate structs.

This PR adds the `init_local_state_finalize` callback that can be used
to cache intermediate structures during the `finalize`, and rewires the
ordered aggregates to use this infrastructure. This greatly speeds up
ordered aggregates with small groups. For the above benchmark, these are
the new timings:

| Version | Timing (s) |
|---------|------------|
| v1.5    | 2.5s       |
| main    | 0.75s      |
| new     | 0.2s       |

i.e. small ordered aggregates are now >10x faster than in v1.5 as a
combined result of using the linked lists together with the intermediate
state caching.

Upstream-commit: duckdb@61e2e64

…github.com/duckdb/duckdb/pull/23376)

This PR adds support for state export to ordered aggregates. Now that
they follow the list infrastructure
(duckdb#23231) this is relatively
straightforward as we can already export/import their intermediate state
using the generic state export/import code.

The aggregate state is a `list` of structs, where the struct holds all
columns required by the aggregate and the order by. For example:

```sql
-- required columns are "l_comment", "l_orderkey"
select string_agg(l_comment order by l_orderkey) export_state from lineitem group by l_shipdate limit 5;
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                      string_agg(l_comment ORDER BY l_orderkey) EXPORT_STATE                                      │
│                                                         aggregate_state                                                          │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi, 'v1': 5601}]                                                                               │
│ [{'v0': ' carefully. i', 'v1': 5409}]                                                                                            │
│ [{'v0': ' carefully aroun', 'v1': 4800}]                                                                                         │
│ [{'v0': 'play. special, regular pint', 'v1': 3712}]                                                                              │
│ [{'v0': 'kages. blithe, c', 'v1': 1248}, {'v0': carefully final instr, 'v1': 3271}, {'v0': furiously furiously eve, 'v1': 5382}] │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
```

The main challenge then lies in the (re)-binding of the ordered
aggregates. Effectively this expands the function signature that is held
in the aggregate state with an `ORDER BY` clause:

```cpp
ext_info->properties.emplace("order_bys", Value::LIST(OrderByEntryType(), std::move(order_values)));
```

For `to_aggregate_state`, we get an extra parameter to define these
order terms, with the columns referenced by offset:

```sql
select finalize(to_aggregate_state([{'v0': 'world', 'v1': 2}, {'v0': 'hello', 'v1': 1}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 1, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

When a column is used both as an argument to the aggregate function, and
as a condition in the `ORDER BY` clause, it is contained only once in
the list. For example:

```sql
select string_agg(l_comment order by l_comment) export_state from lineitem group by l_shipdate limit 3;
┌───────────────────────────────────────────────────────┐
│ string_agg(l_comment ORDER BY l_comment) EXPORT_STATE │
│                    aggregate_state                    │
├───────────────────────────────────────────────────────┤
│ [{'v0': usual instructions. slyly fi}]                │
│ [{'v0': ' carefully. i'}]                             │
│ [{'v0': ' carefully aroun'}]                          │
└───────────────────────────────────────────────────────┘
```

Similarly we can then define the `ORDER BY` term to just refer to the
first column. The column will then be both part of the aggregate and
part of the `ORDER BY` clause:

```sql
select finalize(to_aggregate_state([{'v0': 'world'}, {'v0': 'hello'}], 'string_agg', ['VARCHAR'], [NULL], [{'column': 0, 'order': 'ASC NULLS LAST'}])) as result;
┌─────────────┐
│   result    │
│   varchar   │
├─────────────┤
│ hello,world │
└─────────────┘
```

Upstream-commit: duckdb@22b2fa9