Polishing Structural Bulk Updates in a Native XML Database

Abstract

BaseX is a native XML database on the foundation of a fixed-length, sequential document encoding. Built with a strong focus on reading performance, this thesis shows that the Pre/Dist/Size encoding is yet perfectly capable of handling massive bulk update transactions. Despite its theoretical limitations regarding structural changes of the tree, we show that performance is indeed restricted by the document order and disk access patterns. During tests with the XQuery Update Facility (XQUF), we delete 1.8 million nodes in 22.4 seconds, evenly distributed over a 1.1GB XMark document instance. Compared to the prior approach, this equals a reduction of processing time by 99.99%. To achieve this, we extend the obligatory implementation of the XQUF pending update list with an additional low-level layer, that pre-calculates tree structure adjustments in-memory. This layer adds little overhead and further enables us to merge update operations and curb fragmentation that finds its origin at the user level. To not violate the document order, the XQUF is only arduously brought together with the concept of efficient bulk updates. A method is introduced that imposes an order on update primitives to finally get a ready-to-apply sequence of atomic updates. The reviewed implementation is fully consistent with the XQUF specification and has already proven rock-solid efficiency in production use. A few theoretical paragraphs on alternative approaches, disk access patterns and memory consumption highlight sleeping potential and prepare further progression.