Abstract
Efficient and scalable processing of temporal anti-joins remains a significant research challenge in temporal databases. To address this issue, this paper introduces a novel temporal primitive designed for transforming a temporal anti-join, including conjunctive equality predicates on non-temporal attributes, into an equivalent algebraic expression involving a temporal inner join. The rationale behind this transformation is that the new expression can be decomposed into subtasks, allowing for parallel execution across multiple CPUs. Experimental results using real-world datasets demonstrate the superior efficiency and scalability of our solution for in-memory processing compared to existing solutions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
References
Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., Vitter, J.S.: Scalable sweeping-based spatial join. In: VLDB. p. 570-581. Morgan Kaufmann (1998)
Becker, B., Gschwind, S., Ohler, T., Seeger, B., Widmayer, P.: An asymptotically optimal multiversion b-tree. VLDB J. 5, 264–275 (1996)
Blanas, S., Li, Y., Patel, J.M.: Design and evaluation of main memory hash join algorithms for multi-core cpus. In: SIGMOD, pp. 37–48. ACM (2011)
Böhlen, M.H., Dignös, A., Gamper, J., Jensen, C.S.: Temporal data management - an overview. In: eBISS. LNBIP, vol. 324, pp. 51–83. Springer (2017)
Böhlen, M.H., Dignös, A., Gamper, J., Jensen, C.S.: Database technology for processing temporal data (invited paper). In: TIME. LIPIcs, vol. 120, pp. 2:1–2:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
Bouros, P., Lampropoulos, K., Tsitsigkos, D., Mamoulis, N., Terrovitis, M.: Band joins for interval data. In: EDBT, pp. 443–446 (2020)
Bouros, P., Mamoulis, N.: A forward scan based plane sweep algorithm for parallel interval joins. In: VLDB, pp. 1346–1357. ACM (2017)
Bouros, P., Mamoulis, N., Tsitsigkos, D., Terrovitis, M.: In-memory interval joins. VLDB J. 30, 667–691 (2021)
Cafagna, F., Böhlen, M.H.: Disjoint interval partitioning. VLDB J. 26, 447–466 (2017)
Christodoulou, G., Bouros, P., Mamoulis, N.: Hint: A hierarchical index for intervals in main memory. In: SIGMOD, pp. 1257–1270. ACM (2022)
Christodoulou, G., Bouros, P., Mamoulis, N.: Hint: a hierarchical interval index for allen relationships. The VLDB Journal (2023)
Dignös, A., Böhlen, M.H., Gamper, J.: Temporal alignment. In: SIGMOD, pp. 433–444. ACM (2012)
Dignös, A., Böhlen, M.H., Gamper, J.: Query time scaling of attribute values in interval timestamped databases. In: ICDE, pp. 1304–1307 (2013)
Dignös, A., Böhlen, M.H., Gamper, J.: Overlap interval partition join. In: SIGMOD. pp. 1459–1470. ACM (2014)
Dignös, A., Böhlen, M.H., Gamper, J., Jensen, C.S.: Extending the kernel of a relational dbms with comprehensive support for sequenced temporal queries. ACM Trans. Database Syst. 41(4), 26:1–26:46 (2016)
Dignös, A., Böhlen, M.H., Gamper, J., Jensen, C.S., Moser, P.: Leveraging range joins for the computation of overlap joins. VLDB J. 31(1), 75–99 (2022)
Dignös, A., Glavic, B., Niu, X., Gamper, J., Böhlen, M.H.: Snapshot semantics for temporal multiset relations. Proc. VLDB Endow. 12(6), 639–652 (2019)
Enderle, J., Hampel, M., Seidl, T.: Joining interval data in relational databases. In: SIGMOD Conference, pp. 683–694. ACM (2004)
Gao, D., Jensen, C.S., Snodgrass, R.T., Soo, M.D.: Join operations in temporal databases. VLDB J. 14, 2–29 (2005)
Gunadhi, H., Segev, A.: Query processing algorithms for temporal intersection joins. In: ICDE, pp. 336–344. IEEE Computer Society (1991)
Hu, X., Sintos, S., Gao, J., Agarwal, P.K., Yang, J.: Computing complex temporal join queries efficiently. In: SIGMOD, pp. 2076–2090. ACM (2022)
Jensen, C.S.: Jensen: temporal data management. IEEE Trans. Knowl. Data Eng. 11(1), 36–44 (1999)
Kaufmann, M., et al.: Timeline index: a unified data structure for processing queries on temporal data in SAP HANA. In: SIGMOD, pp. 1173–1184. ACM (2013)
Kriegel, H., Pötke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In: VLDB, pp. 407–418. Morgan Kaufmann (2000)
Kulkarni, K.G., Michels, J.: Temporal features in SQL: 2011. SIGMOD Rec. 41(3), 34–43 (2012)
Leung, T.C., Muntz, R.R.: Temporal query processing and optimization in multiprocessor database machines. In: VLDB, pp. 383–394. Morgan Kaufmann (1992)
Mirabi, M., Fathi, L., Dignös, A., Gamper, J., Binnig, C.: A new primitive for processing temporal joins. In: SSTD’23, pp. 106–109. ACM (2023)
Pfoser, D., Jensen, C.S.: Incremental join of time-oriented data. In: SSDBM, pp. 232–243. Computer Society (1999)
Piatov, D., Helmer, S., Dignös, A.: An interval join optimized for modern hardware. In: ICDE, pp. 1098–1109. IEEE Computer Society (2016)
Piatov, D., Helmer, S., Dignös, A., Persia, F.: Cache-efficient sweeping-based interval joins for extended allen relation predicates. VLDB J. 30(3), 379–402 (2021)
Raigoza, J., Sun, J.: Temporal join processing with hilbert curve space mapping. In: SAC, pp. 839–844. ACM (2014)
Segev, A., Gunadhi, H.: Event-join optimization in temporal relational databases. In: VLDB, pp. 205–215. Morgan Kaufmann (1989)
Soo, M.D., Snodgrass, R.T., Jensen, C.S.: Efficient evaluation of the valid-time natural join. In: ICDE, pp. 282–292. IEEE Computer Society (1994)
Zhang, D., Tsotras, V.J., Seeger, B.: Efficient temporal join processing using indices. In: ICDE, pp. 103–113. IEEE Computer Society (2002)
Acknowledgment
This work was partially supported by hessian. AI at TU Darmstadt and DFKI Darmstadt as well as by a grant from the Autonomous Province of Bozen-Bolzano “Research Südtirol/Alto Adige 2019” (project ISTeP).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Reppas, I., Mirabi, M., Fathi, L., Binnig, C., Dignös, A., Gamper, J. (2024). Parallel Processing of Temporal Anti-Joins in Memory. In: Onizuka, M., et al. Database Systems for Advanced Applications. DASFAA 2024. Lecture Notes in Computer Science, vol 14850. Springer, Singapore. https://doi.org/10.1007/978-981-97-5552-3_6
Download citation
DOI: https://doi.org/10.1007/978-981-97-5552-3_6
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-5551-6
Online ISBN: 978-981-97-5552-3
eBook Packages: Computer ScienceComputer Science (R0)