ROVEC: Runtime Optimization of Vectorized Expression Evaluation for Column Store

Due to the increasing demand for scalable and interactive data analytics, column stores have become the de-facto choice in many analytical databases. As a common and fundamental operation in column stores, expression evaluation has a remarkable effect on many queries. To speed up expression evaluation, vectorized techniques such as <underline>S</underline>ingle-<underline>I</underline>nstruction-<underline>M</underline>ultiple-<underline>D</underline>ata (SIMD) instructions are widely used. However, there are few works concerning dedicated optimizations for SIMD-based expression evaluation for column stores. In this paper, we propose a runtime optimization framework named ROVEC that enables effective optimizations for SIMD-based expression evaluation. The key idea is to optimize logical expression at execution time, by leveraging lightweight compression and fine-grained statistics associated with the compressed data. ROVEC removes unnecessary type casting and finds the tightest type during evaluation, which maximizes the concurrent operands in SIMD instructions. ROVEC can be applied to many expression-evaluation-intensive operators (e.g., table scan and theta join) for different data types (e.g., numeric, time and string). To validate the effectiveness of ROVEC, we integrate it into a columnar database PolarDB-C. Our evaluation results show that ROVEC improves up to <inline-formula><tex-math notation="LaTeX">$125\%$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>125</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq1-3124669.gif"/></alternatives></inline-formula> (<inline-formula><tex-math notation="LaTeX">$60\%$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>60</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq2-3124669.gif"/></alternatives></inline-formula> on average) throughput of table scan and up to <inline-formula><tex-math notation="LaTeX">$50\%$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>50</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq3-3124669.gif"/></alternatives></inline-formula> (<inline-formula><tex-math notation="LaTeX">$30\%$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>30</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq4-3124669.gif"/></alternatives></inline-formula> on average) latency of theta join.