CS Events Monthly View

Qualifying Exam

A balls and bins analysis of insertion and update buffers


Download as iCal file

Tuesday, May 09, 2017, 01:00pm


External memory databases are traditionally based on B-trees. Insertion buffers aggregate database insertions, and only flush into the external memory structure itself when full, attempting to batch multiple insertions destined for the same B-tree leaf, and therefore perform those insertions with only one disk access. Insertion buffers are implemented, for example, in the InnoDB storage engine.
We develop a balls-and-bins model for insertion buffers and show that they have inherent limits on the amount of optimization they provide. This speedup is a small factor of m/n, where m is the buffer size and n is the number of leaves. Thus in databases with large rows as well as in big data settings, we might expect m/n = O(1), and therefore insertion buffers would only provide a constant improvement.

Speaker: Alexander Conway



Location : Hill 350


Prof. Martin Farach-Colton (Chair), Prof. William Steiger, Prof. Shan Muthukrishnan, Prof. Ahmed Elgammal

Event Type: Qualifying Exam



Dept. of Computer Science