Updating a cracked database

ABSTRACT

A cracked database is a datastore continuously reorganized based on operations being executed. For each query, the data of interest is physically reclustered to speed-up future access to the same, overlapping or even disjoint data. This way, a cracking DBMS self-organizes and adapts itself to the workload.

So far, cracking has been considered for static databases only. In this paper, we introduce several novel algorithms for high-volume insertions, deletions and updates against a cracked database. We show that the nice performance properties of a cracked database can be maintained in a dynamic environment where updates interleave with queries. Our algorithms comply with the cracking philosophy, i.e., a table is informed on pending insertions and deletions, but only when the relevant data is needed for query processing just enough pending update actions are applied.

We discuss details of our implementation in the context of an open-source DBMS and we show through a detailed experimental evaluation that our algorithms always manage to keep the cost of querying a cracked datastore with pending updates lower than the non-cracked case.

REFERENCES

• 1: S. Agrawal et al. Database Tuning Advisor for Microsoft SQL Server 2005. In VLDB, 2004.
• 2: M. A. Bender and H. Hu. An Adaptive Packed Memory Array. In SIGMOD, 2006.
• 3: Peter A. Boncz , Martin L. Kersten, MIL primitives for querying a fragmented world, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.101-119, October 1999 [doi>10.1007/s007780050076]
• 4: S. Chaudhuri and G. Weikum. Rethinking Database System Architecture: Towards a Self-Tuning RISC-Style Database System. In VLDB, 2000.
• 5: S. Idreos, M. Kersten, and S. Manegold. Database Cracking. In CIDR, 2007.
• 6: M. Kersten and S. Manegold. Cracking the Database Store. In CIDR, 2005.
• 7: P. Seshadri and A. N. Swami. Generalized partial indexes. In ICDE, 1995.
• 8: Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]
• 9: M. Stonebraker, The case for partial indexes, ACM SIGMOD Record, v.18 n.4, p.4-11, Dec. 1989 [doi>10.1145/74120.74121]
• 10: M. Stonebraker et al. C-Store: A Column Oriented DBMS. In VLDB, 2005.
• 11: A. S. Szalay et al. The SDSS SkyServer: Public Access to the Sloan Digital Sky Server Data. In SIGMOD, 2002.
• 12: D. C. Zilio et al. DB2 Design Advisor: Integrated Automatic Physical Database Design. In VLDB, 2004.
• 13: MonetDB. http://monetdb.cwi.nl/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Design, Performance

Keywords:
database cracking, self-organization, updates