III: Small: Just in Time Datastructures

Indexes have always been a critical component of any database. Now that "big data" is a household term, they're more crucial than ever before. Indexes keep data organized, making it faster and easier for you to get at anything from the microblogs in your stream to the money in your bank account. Of course, it's sometimes hard to figure out how to best keep data organized. For example, online social media often needs to handle over a hundred thousand new messages in a single second. That's a lot of data that needs to be organized, and it needs to be organized fast to keep up with the users' needs. The Just-in-Time Data Structures project is exploring ways to make indexes smarter, better able to prioritize their work, and better able to adapt to changing workload patterns. Specifically, we're generalizing a class of index data structures called adaptive indexes. In an adaptive index, data is organized as a side-effect of query processing. In a just-in-time data structure, user-defined policies specify how an index is to be transformed in reaction to queries and new data. Like a just-in-time compiler, the index is adaptively optimized for the workload that is currently being presented to it. In addition to laying the foundations for research on just-in-time data structures, we are exploring how to design workload-optimal policies, and how just-in-time data structures can be adapted for incremental view maintenance.