RLE Compression

Run-Length Encoding (RLE) is an alternative implementation of sequence storage and processing. It stores an exact value together with the number of adjacent logical elements that repeat that value. RLE can reduce storage and computation when a sequence contains long runs of equal adjacent values.

When RLE Helps

For example, adding the following two sequences requires ten element-wise additions with plain storage:

    x = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
    y = { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

The RLE implementation represents each input as one run. An RLE-aware addition aligns those runs, performs one addition, and associates the ten-element logical span with the result.

RLE is not universally faster or smaller. A sequence of mostly unique values requires one repeat-count byte and control information for almost every value. That representation uses more space and more control flow than plain sequence storage. Select RLE for workloads with enough adjacent repetition to offset this overhead.

Physical Runs and Logical Elements

Unary RLE-aware operators evaluate a function once for a run when the result is constant over that run. Binary operators align the remaining spans of their two current runs. Aggregates multiply or otherwise weight a physical value by its logical repeat count.

Select the Sequence Implementation

The implementation is selected for the process, not for an individual field:

Plain
mcoseq and mcoseqmath
RLE
mcoseqrle and mcoseqrlemath

The two pairs export the same common sequence symbols and must not be linked together as competing implementations. Applications using the dynamic core loader select MCO_SEQUENCE_LIBRARY_PLAIN or MCO_SEQUENCE_LIBRARY_RLE in mco_core_load(). The indirect loader accepts the environment variable MCO_SEQUENCE_LIBRARY with the value PLAIN or RLE.

Use mco_sequence_library_loaded() to query a dynamically loaded configuration and mco_seq_is_rle() to query the active sequence implementation.

Plain and RLE sequence fields have different persistent representations. Open a database containing sequence data with the same sequence implementation that created it. The runtime does not automatically convert stored fields between the two representations.

Representation-Neutral Traversal

The typed functions mco_seq_next_TYPE() and mco_seq_get_TYPE() return logical elements. With RLE, they expand each run, so most applications do not need separate traversal code. Sequence operators and aggregates supplied by the RLE libraries are also run-aware.

mco_seq_rle_decode() creates an expanded iterator over an input iterator. It does not rewrite the stored database field. The function is also valid with the plain implementation, where it behaves as a compatible pass-through.

Direct Tile Traversal

Calling an iterator's raw next callback exposes physical tile items. With RLE, each item is a run and its logical multiplicity is returned by mco_seq_rle_count(). With plain sequences, that function returns 1. The following loop is therefore valid with either implementation:

    mco_uint2 i;
    mco_seq_rle_count_t count;
    double close_sum = 0.0;
    MCO_RET rc;

    while ((rc = close_iterator.next(&close_iterator)) == MCO_S_OK)
    {
        for (i = 0; i < close_iterator.tile_size; ++i)
        {
            count = mco_seq_rle_count(&close_iterator, (int)i);
            if (!MCO_SEQ_IS_NULL(&close_iterator, i))
            {
                close_sum +=
                    (double)close_iterator.tile.u.arr_float[i] * count;
            }
        }
    }
    if (rc == MCO_S_CURSOR_END)
        rc = MCO_S_OK;

Independently compressed columns can have different run boundaries and different physical tile sizes. Do not load two RLE tiles and pair item i from one tile with item i from the other. Use typed logical traversal, decode each iterator, process each field independently, or use an RLE-aware multi-input sequence function.

Related Topics