Techniques for aligned run-length encoding

摘要

Techniques for Aligned Run-Length Encoding (ARLE) are described. ARLE is an encoding scheme that transforms sets of same-valued consecutive rows into one or more runs, while enforcing boundaries between the runs at set intervals (e.g. every predetermined number of rows). Consecutive rows that contain the same value, but which cross one or more interval boundaries, are encoded as multiple runs that are divided along those interval boundaries. According to one technique, a database server accelerates query processing by setting the interval size to the word size of the processor performing the predicate comparisons. According to another technique, a database server accelerates row lookup by maintaining an offset array that stores the run offsets into the ARLE data of the run that begins each interval.

主权项

1. A method comprising:
receiving tabular data, wherein the tabular data is divided into a plurality of rows, each of which includes data for at least one column; encoding at least part of the tabular data as a sequence of runs, each run in the sequence containing at least a run length value for an amount of rows represented by the run and a data value common to the rows represented by the run, wherein at least two consecutive runs of the sequence contain a same data value; wherein the method is performed by one or more computing devices.