For the occasion of the PhD defence of Holger Pirk (MIT, Cambridge, MA, USA) on Friday May 1, 2015, at 12:00 noon in the Agnietenkapel,
we are pleased to organize a "Pre-Labour Day Database Afternoon"
on Thursday April 30, 2015, from 14:00 to 17:00, in room L0.17 @ CWI
with three esteemed speakers:
Johannes Gehrke
(Distinguished Engineer at Microsoft and the Tisch University Professor in the Department of Computer Science at Cornell University)
Title: Deferring the Effect of Transactions
Abstract:
ACID Transactions have for decades provided the gold standard in strong consistency. I will describe applications and models for deferring the effect of transactions on the state of the system while maintaining one-copy serializability. In our first model of a quantum database, we can commit transactions while deferring assignments of values in these transactions to optimize the allocation of resources. In our second model, we permit parts of a replicated or distributed database system to be inconsistent during execution, as long as this inconsistency is bounded and does not affect transaction correctness. Our fully automated approach uses program analysis to extract semantic information about permissible levels of inconsistency; it generates treaties between sites that allow sites to operate independently until treaties are violated.
Goetz Graefe
(Fellow at HP Labs)
Title: Instant restart after a system failure
Abstract:
Database system failures and the subsequent recovery disrupt many transactions and entire applications, usually for an extended duration. For those failures, new on-demand “instant” recovery techniques reduce application downtime from minutes or hours to seconds. These new recovery techniques work for databases, file systems, key-value stores, and all other data stores that employ write-ahead logging.
In traditional recovery from a system failure, e.g., a crash of the database server process, applications may resume and start new transactions after recovery has performed the “redo” actions of all log records written since the last checkpoint and then all “undo” (compensation) actions for failed transactions, i.e., those left incomplete at the time of the crash. Both “redo” and “undo” phases may require many random database reads and thus a relatively long time. The design and some implementations of ARIES support new transactions concurrent to the “undo” phase after lock acquisition during the “redo” phase. For even earlier application availability, the new, “instant” recovery technique permits new database transactions before any “redo” and “undo” work, imposes little load concurrent to new transactions, and prioritizes recovery of database contents according to the needs of new transactions. Concurrently to “redo” and “undo” recovery guided by new transactions, traditional restart recovery scanning the pre-crash recovery log forward and backward ensures that all recovery actions complete in about the same time as traditional recovery without concurrent new transactions.
Johann-Christoph Freytag
(Professor for Databases and Information Systems at the Humboldt-Universität zu Berlin)
Title: Adapting Tree Structures for Processing with SIMD Instructions
Abstract:
In this talk, we show how to accelerate the processing of tree-based index structures by using SIMD instructions. We adapt the B+-Tree and prefix B-Tree (trie) by changing the search algorithm on inner nodes from binary search to k-ary search.
We develop adaptations of tree structures that satisfy the specific constraints of SIMD instructions. We present algorithms for transforming the original tree layout into a SIMD-friendly layout. Our adapted B+-Tree speeds up search processes by a factor of up to eight for small data types compared to the original B+-Tree using binary search. Furthermore, our adapted prefix B-Tree enables a high search performance even for larger data types.
This work was done together with Steffen Zeuch and Frank Huber.
