Memory-Efficient Search Trees for Database Management Systems [pdf]
A lot to digest.  Presumably the compression schemes outlined in the paper would benefit columns generally, and not just keys, and would have a positive impact on row-size which would in turn benefit general performance?<p>One short-string-compression-library to compare with might be <a href="https://github.com/antirez/smaz" rel="nofollow">https://github.com/antirez/smaz</a> by the Antirez, the author of redis.<p>In the last decade Tokudb and then MyRocks showed how to do a fast storage engine for data too big to fit in traditional RDBMS.  They are multi-level, they do page-level compression etc.  And yet there is still so many easy wins yet to be had.<p>Generally, databases are completely inefficient and there is just so much low-hanging fruit; if the team size working on e.g. myrocks could be doubled, and tasked with looking at the inefficiencies in the server as well as the storage engine, things might change.  I have a list in my head of the various really-promising-ideas that databases don't actually do:<p>* linux doesn't have a syscall batching system, but if it did, the number of context switches would be cut down dramatically.  Research in 2010 <a href="https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Soares.pdf" rel="nofollow">https://www.usenix.org/legacy/events/osdi10/tech/full_papers...</a> proved this and it wouldn't just be databases that benefit.  These days context switching is more expensive than ever.<p>* database engines all use blocking io.  Finally io_uring offers workable async io and that would benefit database storage engines immensely.  See <a href="https://fosdem.org/2020/schedule/event/rust_techniques_sled/" rel="nofollow">https://fosdem.org/2020/schedule/event/rust_techniques_sled/</a><p>* tokudb showed that simply not tracking the affected row count could speed things up massively (tokudb called it NOAR)<p>* query engines often don't handle things that a few more lines of code would handle efficiently.  I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql evaluating constraints that it can against the other columns in the key before dereferencing the row?  Arrgh.  Dumb dumb dumb.  Etc.