citusdata / citusdata/citus

array_cat_agg is inefficient

Open
#3,525 0 comments 0 reactions 0 assignees View on GitHub
1-2 days performance
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.