Vector/String Resize Performance Impact

flamegraph: svg.tar.gz

TPCH Q5 and similar queries suffer from large amount memcpy/realloc. This is caused by resizing vector-like data structures.

In the flamegraph, there are two major zones of such events:

1. In join operation, the column vector is resizing during the insertion of rows.
2. In data serialization process, the write buffer is resizing frequently on input.

The resizing process seems to take at least 50% time of the operation and hence become a major impact to the overall performance.

Possible Solutions from Algorithms

Reserve Space

The idea is to reserve enough space for the vector before insertion. It may require collect statistics on the size of items.

Use Append-Friendly Data Structures

If the operation does not require random-access, maybe we can use block list or root-ish array instead.

Possible Solutions from Infra

Centos 7 is too old to have a modern glibc that can utilize avx2 and erms. As you can see, the memcpy operation can only have limited speedup with ssse3. We may consider vendor our own glibc. Theoretically, this may bring up to 50% speed up of the resizing procedure

Start with the attached flamegraph and profile TPCH Q5, focusing on vector resizing during join row insertion and write-buffer resizing during serialization. Compare the proposed reservation, append-friendly data structures, and CentOS 7 memcpy alternatives; done should demonstrate reduced resizing and memcpy/realloc time, though the issue does not specify files, tests, or a target measurement.