Merge Optimization

Merge Heap Guidelines

The merge process takes imported data in its raw form, typically partitioned by source and ordered according to its publication, and rewrites it persistently across historical storage partitions, optionally grouping the data on a subset of columns and sorting within those groups.

This is fundamentally a memory-intensive process. Merge must first assign each input row to an output partition, then must order the data for each output partition according to the specified grouping and sorting. Finally, merge must read and rewrite the data for each column in output order.

There are three primary users of memory in a merge.

  1. Indexes and other data structures used to determine ordering.
  2. Symbol tables for the output columns.
  3. Data buffers used to cache column data as it is read.

A good rule of thumb for determining the best value for your merge heap size is to double the value of the data buffer pool size:

buffer pool size = max_over_all_columns(column file data size) * nWritingThreads / nOutputPartitions / 0.85

heap size = 2 * buffer pool size

Ordering Information

From a memory optimization standpoint, there is not a great deal to be done about the size of ordering information (indexes, etc). The implementation disables some performance optimizations when output partitions exceed 1B rows, choosing to use a potentially more compressed representation (ordered sub-indexes) rather than the default (expanded arrays of input row keys). In the worst case, total ordering information should never significantly exceed 8 bytes per input row once the ordering step is complete. This occurs when data must be substantially re-ordered, such as when the grouping column values are repeated in order ("A", "B", "C", "A", "B", "C"), or when sorting rearranges many rows.

Symbol Tables

Symbol tables allow for significant compression of output data, but are often stored fully in-memory during the merge process, depending on String caching settings as described in the next section. They require storage that can be approximated as (20 bytes per unique string + 2 bytes per character across all unique strings).

Note

We currently store symbol manager data as it is computed for the duration of merge.

Data buffer pool

The data buffer pool is by far the most important driver of merge heap usage and merge performance. For a full explanation of the pool, its defaults across all services, configuration properties, and troubleshooting log lines, see the data buffer pool section of the process memory guide.

Merge worker sizing

For merge workers, the recommended pool size formula is:

buffer pool size = max_column_file_size × nWritingThreads / nOutputPartitions / 0.85

heap size = 2 × buffer pool size

In Deephaven versions prior to v1.20180326, or in low heap usage mode, omit the / nOutputPartitions term because at most one destination per column is written concurrently.

For specific workers, the QueryPerformanceLog and UpdatePerformanceLog provide information about the number and duration of repeated data reads. A large number of repeated reads suggests the pool should be larger; no repeated reads suggests it can be reduced.