Adaptive flash sorting for memory-constrained embedded devices
Ramon Lawrence · 2021
Databases running on embedded devices require efficient sorting algorithms for aggregation, joins, and output ordering. Previous research has produced algorithms optimized for small-memory, flash embedded devices that either use multiple read passes to avoid writes or optimize the external merge sort algorithm. Depending on the data input distribution and memory characteristics, neither approach always outperforms the other. This work produces an adaptive flash sorting algorithm that dynamically determines the best sorting approach at run-time. Experimental results demonstrate that the adaptive sorting algorithm combines the best features of both approaches and allows overall superior performance.