String Data Encoding Schemes In Depth

…’physics’, ‘math’, ‘math’, ‘math’, ‘math’, ‘physics’, ‘physics’, ‘chemistry’, …

… [1’physics’], [4‘math’], [2’physics’], [1’chemistry’]...

View the Encoding Scheme in information_schema.COLUMNAR_SEGMENTS

The information_schema.COLUMNAR_SEGMENTS view stores information about each segment of a columnar table. Users can query the encoding column of a columnar segment to find out what encoding scheme is used for that segment. For example,

SELECT column_name, segment_id, encoding, uncompressed_size, compressed_size
FROM information_schema.COLUMNAR_SEGMENTS 
     WHERE table_name = ‘Sales’ and segment_id = 3;

+-------------------+------------+--------------------------+--------------------------------+--------------------------------+
| column_name       | segment_id | encoding                 | uncompressed_size              | compressed_size                |
+-------------------+------------+--------------------------+--------------------------------+--------------------------------+
| country           |          3 | StringDictionary         | 2867200                        | 1200                           |
| item_name         |          3 | StringDictionary         | 6392648                        | 3128                           |
| tx_id             |          3 | Integer                  | 16384                          | 420                            |
...

Encoding Scheme Selection in the Columnstore Storage Engine

The choice of encoding scheme in the columnstore storage engine is per segment. The goal is to both maximize storage savings and lower the query latency.

When a segment needs to be written to files on disk, the columnstore storage engine checks the properties of the data, iterates through the set of desired encoding schemes and does trial compressions, compares their compression ratios taking into account the following rules and heuristics, and eventually picks one and writes the encoded data to the blob files. The rules and heuristics include:

1. String Dictionary or seekable string RLE are favored over other encoding schemes because query execution can directly operate on the encoded data to boost performance in addition to the storage savings.

2. Dictionary encoding will not be picked when data uniqueness is larger than 70%.

3. Seekable RLE will not be chosen when the average run length is less than 1.1.

4. The choice between string dictionary encoding and string RLE is based on their compression ratios if they both pass Rules 2 and 3.

5. Seekable LZ4 will be considered with an additional 20% penalty, i.e. only when the LZ4 compression ratio leads to a compressed size less than the best compressed size by another encoding scheme minus 20% uncompressed size. This heuristic correction to make LZ4 less favorite is due to the consideration in Rule 1.

6. Seekable string encoding will be considered if all other encoding schemes cannot meet the requirements.

As mentioned earlier, some metadata is also collected and the data organization in files is structured to support efficient point-access of rows in the file.

SingleStore offers users the option to specify an encoding scheme for a column if they have a valid reason to override the storage engine’s internal choice. To specify an encoding scheme, use option <encoding> provided in the CREATE TABLE statement:  For example:

CREATE TABLE t (a int, b varchar(50) option 'StringDictionary', Sort key(a));

Operating on Encoded String Data During Query Execution

Filtering directly on string data encoded with dictionary or RLE encoding is supported during query execution.

Encoded data can be directly processed to boost query performance with a filtering on an encoded column. For example, the filter T.a = xyz, on a string dictionary encoded column segment first finds the result of the filter for every entry in the dictionary. Then, while scanning the segment, the query execution system simply takes the encoded ID number for each value in T.a and uses it to look up the result of the string comparison for that ID that was computed in the initial scan of the dictionary.

That execution pattern tends to be much quicker than doing an actual string comparison. Other kinds of operations can also be done directly on encoded data ID values, including the comparison of ID values needed to do group-by operations.

The encoding for a blob depends on its type and data. The encoding may hinge both on the ordering and cardinality for numeric delta encoding and dictionary encoding, respectively. It impacts the execution speed, as well as enables SIMD operations on encoded data.

Table of String Data Encoding Schemes

Summary

SingleStore columnstore tables store string data in a number of different encoded forms. The encoding scheme decision is per segment, on-the-fly, dynamic, and adaptive. The decision process takes the compression ratio, the operationability of the encoded data during query execution, and heuristics into account. The algorithms are considered in the following order of preference: String Dictionary Encoding and Seekable String RLE, Seekable LZ4 Encoding, Seekable String Encoding. By enhancing the basic encoding schemes with seekable implementations, SingleStore gets the best outcome of storage savings and low query latency for point-access queries.