array_cat_agg is inefficient
- Dominant language
- C
- Stars
- 12.8k
- Forks
- 794
- Avg merge
- 2d 14h
- Merged PRs (30d)
- 31
Description
We distribute `array_agg` by combining on coordinator with `array_cat_agg`. `array_cat_agg` uses `array_cat` as its transition function. This copies the array with each call, which is O(N^2) since each element is copied for however many elements follow it. N is the number of shards. If we instead implemented an `array_cat_agg_sfunc` function with internal type, we could be O(N) by copying each array into the longer lived memory context, storing pointers to these in a List, & then allocating the final array in the final function
The current copying quickly outscales my current suggestion. Say we have 8 equally sized arrays from 8 shards. We'll be copying `2+3+4+5+6+7+8=35` elements whereas with my suggestion we'll be copying `1+1+1+1+1+1+1+1+8=16` elements. To draw this more graphically:
```
Given 8 arrays: 1 2 3 4 5 6 7 8
Currently our state grows like this, where I'm listing the elements we copy: 12, 123, 1234, 12345, 123456, 1234567, 12345678
Whereas I propose our state grows like this: 1 2 3 4 5 6 7 8 12345678
```
The downside is that we'd have to implement the function, whereas we currently leverage a postgres builtin. Whether that complexity is worth it depends on how much use `array_agg` sees, & whether that tends to be with `text[]` or not
Contributor guide
Assessment
This issue has not been assessed yet.