Energy-efficient Scans by Weaving Indexes into the Storage Layout in Computing Platforms for Internet of Things

Recent advances in computing are widely leveraged to design energy-efficient computing platforms for Internet of Things. Especially, scans is a crucial operation that consumes major energy in main-memory column-stores. Scanning a column involves returning a result bit vector to indicate whether each record satisfies a predicate (i.e., a filter condition) or not. ByteSlice, as an existing storage layout, chops the data into multiple bytes, thus possessing early-stop capability by comparing high-order bytes while scanning data. However, the width of columns is usually not multiples of byte, and in these cases, the last-byte of ByteSlice layout is padded with zeros, which wastes the computation energy and the memory bandwidth. To make the scan operation energy-efficient, a lightweight index is squeezed into the bits that originally padded with zeros. In this way, our proposed storage layout DIFusion integrates the data and the index in a unified structure. DIFusion enables an energy-efficient scan because it inherits the early-stopping capability from ByteSlice and possesses the data-skipping ability at the same time. The experimental evaluation on TPC-H, SSB and the real workload shows promising speedup for scans on DIFusion.