  Modern database applications often change their schemas to keep up with the
changing requirements. However, support for online and transactional schema
evolution remains challenging in existing database systems. Specifically, prior
work often takes ad hoc approaches to schema evolution with 'patches' applied
to existing systems, leading to many corner cases and often incomplete
functionality. Applications therefore often have to carefully schedule
downtimes for schema changes, sacrificing availability.
  This paper presents Tesseract, a new approach to online and transactional
schema evolution without the aforementioned drawbacks. We design Tesseract
based on a key observation: in widely used multi-versioned database systems,
schema evolution can be modeled as data modification operations that change the
entire table, i.e., data-definition-as-modification (DDaM). This allows us to
support schema almost 'for free' by leveraging the concurrency control
protocol. By simple tweaks to existing snapshot isolation protocols, on a
40-core server we show that under a variety of workloads, Tesseract is able to
provide online, transactional schema evolution without service downtime, and
retain high application performance when schema evolution is in progress.
