Computer Science Department
School of Computer Science, Carnegie Mellon University


Non-blocking Lazy Schema Changes in
Multi-Version Database Management Systems

Yangjun Sheng

M.S. Thesis

May 2019


Keywords: DBMS, schema change, multi-version, non-blocking, concurrency control, catalog, index, transaction

The relational schema of a table in a database management system (DBMS) describes its logical attribute information and constraints. Despite the aim of separation between logical schema and physical data storage, in practice, the schema often dictates how a DBMS organizes data on disk or in memory. This tight coupling is because the database's physical schema must match its logical schema. The problem with this is that applications that incur frequent schema changes (e.g., add a column, change column type) may become slower or even unavailable during a change due to data migration. A better approach is to support non-blocking schema changes by storing multiple versions of tables and allow data migration happens lazily.

In this thesis, we introduce multi-version schemas that are based on multiversion concurrency control policies (MVCC) to support fast online schema changes. This approach maintains multiple tables of different schemas and allows transactions to see the correct versions of tuples. It migrates tuples from old schema to new schema lazily on demand. We show that multi-version schemas achieve non-blocking schema changes. We also show that the overhead of maintaining multiple schemas is small and the system can recover from performance degeneration caused by schema change fast when there is hotspot in the database.

68 pages

Thesis Committee:
Andy Pavlo (Chair)
Nathan Beckman

Srinivasan Seshan, Head, Computer Science Department
Tom M. Mitchell, Interim Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by