Fragment and replicate algorithms for non-equi-join evaluation on smart disks

Vassilis Stoumpos, Alex Delis

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

Abstract

The predicates in a non-equi-join can be anything but equality relations. Non-equi-join predicates can be as simple as an inequality expression between two join relation fields, or as complex as a user-defined function that carries out arbitrary complex comparisons. The nature of non-equi-join calls for predicate evaluation over all possible combinations of tuples in a two-way join. In this paper, we consider the family of fragment and replicate join algorithms that facilitates non-equijoin evaluation and adapt it in a Smart Disk environment. We use Smart Disk as an umbrella term for a variety of different storage devices featuring an embedded processor that may offload data processing from the main CPU. Our approach partially replicates one of the join relations in order to harness all processing capacity in the system. However, partial replication introduces problems with synchronizing concurrent algorithmic steps, load balancing, and selection among different join evaluation alternatives. We use a processing model to avoid performance pitfalls and autonomously select algorithm parameters. Through experimentation we find our proposed algorithms to utilize all system resources and, thus, yield better performance.

Original languageEnglish (US)
Title of host publicationProceedings - 2009 International Symposium on Autonomous Decentralized Systems, ISADS 2009
Pages471-478
Number of pages8
DOIs
StatePublished - 2009
Event2009 International Symposium on Autonomous Decentralized Systems, ISADS 2009 - Athens, Greece
Duration: Mar 23 2009Mar 25 2009

Publication series

NameProceedings - 2009 International Symposium on Autonomous Decentralized Systems, ISADS 2009

Conference

Conference2009 International Symposium on Autonomous Decentralized Systems, ISADS 2009
CountryGreece
CityAthens
Period3/23/093/25/09

Keywords

  • Active disks
  • Array of disks
  • Database join
  • Fragment and replicate parallelism
  • Non-equi-joins
  • Smart disks

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Fragment and replicate algorithms for non-equi-join evaluation on smart disks'. Together they form a unique fingerprint.

Cite this