EmergencyEMERGENCY? Get 24/7 Help Now!

Report on XLDB Tutorial on Data Structures and Algorithms


Posted on:

|

By:


PREVIOUS POST
NEXT POST
Share Button

Bradley and I (Michael) gave the tutorial on Data Structures and Algorithms for Big Databases at the 6th XLDB Conference last month.

The tutorial was organized as follows:

  • Module 0: Tutorial overview and introductions. We describe an observed (but not necessary) tradeoff in ingestion, querying, and freshness in traditional database.
  • Module 1: I/O model and cache-oblivious analysis.
  • Module 2: Write-optimized data structures. We give the optimal trade-off between inserts and point queries. We show how to build data structures that lie on this tradeoff curve.
  • Module 2 continued: Write-optimized data structures perform writes much faster than point queries; this asymmetry affects the design of an ACID compliant database.
  • Module 3: Case study – TokuFS. How to design and build a write-optimized file systems.
  • Module 4: Page-replacement algorithms. We give relevant theorems on the performance of page-replacement strategies such as LRU.
  • Module 5: Index design, including covering indexes.
  • Module 6: Log-structured merge trees and fractional cascading.
  • Module 7: Bloom filters.

These algorithms and data structures are used both in NoSQL implementations such as MongoDB, HBase and in SQL-oriented implementations such as MySQL and TokuDB.

The slides are available here.

Here are impressions from the experience. First, we feel grateful to have spoken before such an engaged and high-powered group of attendees. We welcome followup interactions with the colleagues that we met. We hope to have an opportunity to give a similar tutorial again in the not-too-distant future.

Second, we appreciated the longer format of a four-hour tutorial, rather than a short talk. It’s not easy to prepare a tutorial comprising four hours of advanced data structures; it must be even harder to sit through one. Nonetheless, it was refreshing to delve into topics the way we like to do in the classroom. JRR Tolkien said about The Lord of the Rings that, in retrospect, he felt that the book was too short. Intense as a four-hour tutorial may be, I feel the same way about our tutorial. Another couple of hours (after an appropriate break) would have been great.

An aside: JRR Tolkien was right. The Lord of the Rings is too short.

Share Button
PREVIOUS POST
NEXT POST


Tags:

, , , , , , ,

Categories:
Tokutek, TokuView


Comments

Leave a Reply

Percona’s widely read Percona Data Performance blog highlights our expertise in enterprise-class software, support, consulting and managed services solutions for both MySQL® and MongoDB® across traditional and cloud-based platforms. The decades of experience represented by our consultants is found daily in numerous and relevant blog posts.

Besides specific database help, the blog also provides notices on upcoming events and webinars.

Want to get weekly updates listing the latest blog posts? Subscribe to our blog now! Submit your email address below.

No, thank you. Please do not ask me again.