DigestJoin: Exploiting fast random reads for flash-based joins

Yu Li, Sai Tung On, Jianliang Xu, Byron Choi, Haibo Hu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

13 Citations (Scopus)


Flash disks have been an emerging secondary storage media. In particular, there have been portable devices, multimedia players and laptop computers that are configured with no magnetic disks but flash disks. It is envisioned that some RDBMSs will operate on flash disks in the near future. However, the I/O characteristics of flash disks are different from those of magnetic disks. Thus, in this paper, we study the core of query processing in RDBMSs- join processing- on flash disks. Specifically, we propose a new join method, called DigestJoin, to exploit fast random reads of flash disks. DigestJoin consists of two phases: (1) projecting the join attributes followed by a join on the projected attributes; and (2) fetching the full tuples that satisfy the join to produce the final join results. While the problem of tuple/page fetching with minimum I/O cost (in the second phase) is intractable, we propose three heuristic fetching strategies. We have implemented DigestJoin on a real flash disk for performance evaluation. Experiments on TPC-H datasets show that DigestJoin clearly outperforms the traditional sort-merge join under various system configurations.
Original languageEnglish
Title of host publicationProceedings - 2009 10th International Conference on Mobile Data Management
Subtitle of host publicationSystems, Services and Middleware, MDM 2009
Number of pages10
Publication statusPublished - 5 Oct 2009
Externally publishedYes
Event2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009 - Taipei, Taiwan
Duration: 18 May 200920 May 2009


Conference2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009

ASJC Scopus subject areas

  • Engineering(all)

Cite this