Optimising queue-based semi-stream joins by introducing a queue of frequent pages

M. Asif Naeem, Gerald Weber, Christof Lutteroth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Semi-stream joins perform a join between a stream and a disk-based table. These joins can easily deal with typical workloads in online real-time data warehousing in many scenarios and with relatively modest system requirements. The disk access is page-based. In the past, several proposals have been made to exploit skew in the distribution of the join attribute. Such skew is a common result of natural short- or longtailed distributions in master data. Several semi-stream joins use caching strategies in order to improve performance. This works up to a point, but these algorithms still require relatively slow processing of stream data that matches with the infrequent tuples in the master data. In this work we explore the possibility of an additional strategy to exploit data skew: disk pages that are frequently accessed as a whole are accessed with priority. We show that considerable gain in service rate can be achieved with this strategy, while keeping memory consumption low. In essence we gain a three-stage approach to deal with skewed, unsorted data: caching plus our new strategy plus processing of the long tail of the distribution. We also present a cost model for our approach and validate our approach empirically.

Original languageEnglish
Title of host publicationDatabases Theory and Applications - 27th Australasian Database Conference, ADC 2016, Proceedings
EditorsM. A. Cheema, W. Zhang, L. Chang
PublisherSpringer Verlag
Pages407-418
Number of pages12
ISBN (Print)9783319469218
DOIs
Publication statusPublished - 1 Jan 2016
Event27th Australasian Database Conference on Databases Theory and Applications, ADC 2016 - Sydney, USA United States
Duration: 28 Sep 201629 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9877

Conference

Conference27th Australasian Database Conference on Databases Theory and Applications, ADC 2016
CountryUSA United States
CitySydney
Period28/09/1629/09/16

Keywords

  • Indexing
  • Performance optimisation
  • Semi-stream join

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimising queue-based semi-stream joins by introducing a queue of frequent pages'. Together they form a unique fingerprint.

  • Cite this

    Asif Naeem, M., Weber, G., & Lutteroth, C. (2016). Optimising queue-based semi-stream joins by introducing a queue of frequent pages. In M. A. Cheema, W. Zhang, & L. Chang (Eds.), Databases Theory and Applications - 27th Australasian Database Conference, ADC 2016, Proceedings (pp. 407-418). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9877 ). Springer Verlag. https://doi.org/10.1007/978-3-319-46922-5_32