uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Transparent inclusion, utilization, and validation of main memory domain indexes
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (UDBL)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. (UDBL)
2015 (English)In: Proc. 27th International Conference on Scientific and Statistical Database Management, New York: ACM Press, 2015Conference paper, Published paper (Refereed)
Abstract [en]

Main-memory database systems (MMDBs) are viable solutions for many scientific applications. Scientific and engineering data often require special indexing methods, and there is a large number of domain specific main memory indexing implementations developed. However, adding an index structure into a database system can be challenging. Mexima (Main memory External Index Manager) provides an MMDB where new main-memory index structures can be plugged-in without modifying the index implementations. This has allowed to plug into Mexima complex and highly optimized index structures implemented in C/C++ without code changes. To utilize new user defined indexes in queries transparently, Mexima automatically transforms query fragments into index operations based on index properly tables containing index meta-data. For scalable processing of complex numerical query expressions, Mexima includes an algebraic query transformation mechanism that reasons on numerical expressions to expose potential utilization of indexes. The index property tables furthermore enable validating the correctness of an index implementation by executing automatically generated test queries based on index meta-data. Experiments show that the performance penalty of using an index plugged into Mexima is low compared to using the corresponding stand-alone C/C++ implementation. Substantial performance gains are shown by the index exposing rewrite mechanisms.

Place, publisher, year, edition, pages
New York: ACM Press, 2015.
Keywords [en]
Domain Indexing; Extensible Databases; Query Processing; Automatic Testing
National Category
Computer Sciences
Research subject
Computer Science with specialization in Database Technology
Identifiers
URN: urn:nbn:se:uu:diva-280368DOI: 10.1145/2791347.2791375ISBN: 978-1-4503-3709-0 (print)OAI: oai:DiVA.org:uu-280368DiVA, id: diva2:910656
Conference
SSDBM 2015, June 29–July 1, San Diego, CA
Available from: 2015-06-29 Created: 2016-03-09 Last updated: 2018-01-10Bibliographically approved
In thesis
1. Main-Memory Query Processing Utilizing External Indexes
Open this publication in new window or tab >>Main-Memory Query Processing Utilizing External Indexes
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Many applications require storage and indexing of new kinds of data in main-memory, e.g. color histograms, textures, shape features, gene sequences, sensor readings, or financial time series. Even though, many domain index structures were developed, very a few of them are implemented in any database management system (DBMS), usually only B-trees and hash indexes. A major reason is that the manual effort to include a new index implementation in a regular DBMS is very costly and time-consuming because it requires integration with all components of the DBMS kernel. To alleviate this, there are some extensible indexing frameworks. However, they all require re-engineering the index implementations, which is a problem when the index has third-party ownership, when only binary code is available, or simply when the index implementation is complex to re-engineer. Therefore, the DBMS should allow including new index implementations without code changes and performance degradation. Furthermore, for high performance the query processor needs knowledge of how to process queries to utilize plugged-in index. Moreover, it is important that all functionalities of a plugged-in index implementation are correct.

The extensible main memory database system (MMDB) Mexima (Main-memory External Index Manager) addresses these challenges. It enables transparent plugging in main-memory index implementations without code changes. Index specific rewrite rules transform complex queries to utilize the indexes. Automatic test procedures validate the correctness of them based on user provided index meta-data. Moreover, the same optimization framework can also optimize complex queries sent to a back-end DBMS by exposing hidden indexes for its query optimizer.

Altogether, Mexima is a complete and extensible platform for transparently index integration, utilization, and evaluation.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2016. p. 45
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1352
Keywords
Database indexing, query processing, index structures, main-memory, index validation
National Category
Computer Sciences
Research subject
Computer Science with specialization in Database Technology
Identifiers
urn:nbn:se:uu:diva-280374 (URN)978-91-554-9509-1 (ISBN)
Public defence
2016-05-04, 2446, ITC, Lägerhyddsvägen 2, Uppsala, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2016-04-13 Created: 2016-03-09 Last updated: 2018-01-10

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Truong, ThanhRisch, Tore

Search in DiVA

By author/editor
Truong, ThanhRisch, Tore
By organisation
Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 212 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf