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
- Only adjacent equal values are combined. RLE is not dictionary compression and does not combine equal values separated by another value.
- NULL state is part of run identity. NULL and non-NULL elements never share a run.
- A physical repeat count has type
mco_seq_rle_count_tand stores at most 255 logical elements. Longer logical runs are represented by consecutive physical runs.- Public sequence counts, positions, search results, and range boundaries remain logical element counts.
- The number of physical runs that fit in a tile depends on the stored value width. Applications must use the iterator's reported
tile_size.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:
PlainmcoseqandmcoseqmathRLEmcoseqrleandmcoseqrlemathThe 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_PLAINorMCO_SEQUENCE_LIBRARY_RLEinmco_core_load(). The indirect loader accepts the environment variableMCO_SEQUENCE_LIBRARYwith the valuePLAINorRLE.Use
mco_sequence_library_loaded()to query a dynamically loaded configuration andmco_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()andmco_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
nextcallback exposes physical tile items. With RLE, each item is a run and its logical multiplicity is returned bymco_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
ifrom one tile with itemifrom the other. Use typed logical traversal, decode each iterator, process each field independently, or use an RLE-aware multi-input sequence function.Related Topics