MIL Primitives for Querying a Fragmented World.

Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
  author    = {Peter A. Boncz and
               Martin L. Kersten},
  title     = {MIL Primitives for Querying a Fragmented World},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {2},
  year      = {1999},
  pages     = {101-119},
  ee        = {db/journals/vldb/BonczK99.html},
  bibsource = {DBLP,}


In query-intensive database application areas, like decision support and data mining, systems that use vertical fragmentation have a significant performance advantage. In order to support relational or object oriented applications on top of such a fragmented data model, a flexible yet powerful intermediate language is needed. This problem has been successfully tackled in Monet, a modern extensible database kernel developed by our group. We focus on the design choices made in the Monet interpreter language (MIL), its algebraic query language, and outline how its concept of tactical optimization enhances and simplifies the optimization of complex queries. Finally, we summarize the experience gained in Monet by creating a highly efficient implementation of MIL.

Key Words

Database systems - Query optimization - Query languages - Main-memory techniques - Vertical fragmentation

Copyright © 1999 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224 BibTeX
Peter A. Boncz, Tim Rühl, Fred Kwakkel: The Drill Down Benchmark. VLDB 1998: 628-632 BibTeX
Peter A. Boncz, Annita N. Wilschut, Martin L. Kersten: Flattening an Object Algebra to Provide Performance. ICDE 1998: 568-577 BibTeX
Peter A. Boncz, Wilko Quak, Martin L. Kersten: Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing. EDBT 1996: 147-166 BibTeX
Peter A. Boncz, Fred Kwakkel, Martin L. Kersten: High Performance Support for OO Traversals in Monet. BNCOD 1996: 152-169 BibTeX
R. G. G. Cattell: ODMG-93: A Standard for Object-Oriented DBMSs. SIGMOD Conference 1994: 480 BibTeX
Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412 BibTeX
Latha S. Colby, Richard L. Cole, Edward Haslam, Nasi Jazayeri, Galt Johnson, William J. McKenna, Lee Schumacher, David Wilhite: Redbrick Vista: Aggregate Computation and Management. ICDE 1998: 174-177 BibTeX
Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160 BibTeX
George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279 BibTeX
Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992) BibTeX
Jochen Doppelhammer, Thomas Höppler, Alfons Kemper, Donald Kossmann: Database Performance in the Real World - TPC-D and SAP R/3 (Experience Paper). SIGMOD Conference 1997: 123-134 BibTeX
Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, Hamid Pirahesh: Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Min. Knowl. Discov. 1(1): 29-53(1997) BibTeX
Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, Sunita Sarawagi: On the Computation of Multidimensional Aggregates. VLDB 1996: 506-521 BibTeX
Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992) BibTeX
Robert H. Gerber: Informix Online XPS. SIGMOD Conference 1995: 463 BibTeX
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366 BibTeX
Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 BibTeX
Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277 BibTeX
Navin Kabra, David J. DeWitt: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998: 106-117 BibTeX
Martin L. Kersten, M. F. N. de Boer: Query Optimization Strategies for Browsing Sessions. ICDE 1994: 478-487 BibTeX
Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643 BibTeX
Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït, Mikal Ziane: Invited Project Review: Industrial-strength parallel query optimization: issues and lessons. Inf. Syst. 19(4): 311-330(1994) BibTeX
Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303 BibTeX
Niels Nes, Martin L. Kersten: The Acoi Algebra: a Query Algebra for Image Retrieval Systems. BNCOD 1998: 77-88 BibTeX
Michael Novak, Georges Gardarin, Patrick Valduriez: Flora: A Functional-Style Language for Object and relational Algebra. DEXA 1994: 37-46 BibTeX
Patrick E. O'Neil: Model 204 Architecture and Performance. HPTS 1987: 40-59 BibTeX
Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315 BibTeX
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
Ambuj Shatdal, Chander Kant, Jeffrey F. Naughton: Cache Conscious Algorithms for Relational Query Processing. VLDB 1994: 510-521 BibTeX
Michael Stonebraker, Jeff Anton, Michael Hirohama: Extendability in POSTGRES. IEEE Data Eng. Bull. 10(2): 16-23(1987) BibTeX
Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases. ICDE 1995: 80-89 BibTeX
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
Carel A. van den Berg, Martin L. Kersten: An Analysis of a Dynamic Query Optimization Scheme for Different Data Distributions. Query Processing for Advanced Database Systems, Dagstuhl 1991: 449-472 BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990) BibTeX
Seth J. White: Pointer Swizzling Techniques for Object-Oriented Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1994
Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:36 2009