{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T02:10:51Z","timestamp":1773281451852,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>\n                    We present a novel linear-time acyclic join algorithm, TreeTracker Join (\n                    <jats:sans-serif>TTJ<\/jats:sans-serif>\n                    ). The algorithm can be understood as the pipelined binary hash join with a simple twist: upon a hash lookup failure,\n                    <jats:sans-serif>TTJ<\/jats:sans-serif>\n                    resets execution to the binding of the tuple causing the failure, and removes the offending tuple from its relation. Compared to the best known linear-time acyclic join algorithm, Yannakakis\u2019s algorithm,\n                    <jats:sans-serif>TTJ<\/jats:sans-serif>\n                    shares the same asymptotic complexity while imposing lower overhead. Further, we prove that when measuring query performance by counting the number of hash probes,\n                    <jats:sans-serif>TTJ<\/jats:sans-serif>\n                    will match or outperform binary hash join on the same plan. This property holds independently of the plan and independently of acyclicity. We are able to extend our theoretical results to cyclic queries by introducing a new hypergraph decomposition method called tree convolution. Tree convolution iteratively identifies and contracts acyclic subgraphs of the query hypergraph. The method avoids redundant calculations associated with tree decomposition and may be of independent interest. Empirical results on TPC-H, the Join Order Benchmark, and the Star Schema Benchmark demonstrate favorable results.\n                  <\/jats:p>","DOI":"10.1145\/3774325","type":"journal-article","created":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T06:20:06Z","timestamp":1761891606000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["TreeTracker Join: Simple, Optimal, Fast"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3036-2777","authenticated-orcid":false,"given":"Zeyuan","family":"Hu","sequence":"first","affiliation":[{"name":"The University of Texas at Austin","place":["Austin, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6887-9395","authenticated-orcid":false,"given":"Yisu Remy","family":"Wang","sequence":"additional","affiliation":[{"name":"Computer Science, University of California, Los Angeles","place":["Los Angeles, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8838-2890","authenticated-orcid":false,"given":"Daniel P","family":"Miranker","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin","place":["Austin, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,6]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Java Microbenchmark Harness (JMH). (n.d.). Retrieved November 15 2025 from https:\/\/github.com\/openjdk\/jmh"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","unstructured":"Liese Bekkers Frank Neven Stijn Vansummeren and Yisu Remy Wang. 2025. Instance-optimal acyclic join processing without regret: Engineering the yannakakis algorithm in column stores. Proc. VLDB Endow. 18 8 (2025) 2413\u20132426. Retrieved from https:\/\/www.vldb.org\/pvldb\/vol18\/p2413-vansummeren.pdf","DOI":"10.14778\/3742728.3742737"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","unstructured":"Altan Birler Alfons Kemper and Thomas Neumann. 2024. Robust join processing with diamond hardened joins. Proc. VLDB Endow. 17 11 (2024) 3215\u20133228. DOI:10.14778\/3681954.3681995","DOI":"10.14778\/3681954.3681995"},{"key":"e_1_3_3_7_2","volume-title":"Query Compilation in a Distributed Database System","author":"Daniels Dean","year":"1982","unstructured":"Dean Daniels. 1982. Query Compilation in a Distributed Database System. Ph.D. Dissertation. Massachusetts Institute of Technology, Department of Electrical Engineering."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","unstructured":"Rina Dechter. 1990. Enhancement schemes for constraint processing: Backjumping learning and cutset decomposition. Artificial Intelligence 41 3 (1990) 273\u2013312. DOI:10.1016\/0004-3702(90)90046-3","DOI":"10.1016\/0004-3702(90)90046-3"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"Kevin P. Gaffney Martin Prammer Laurence C. Brasfield D. Richard Hipp Dan R. Kennedy and Jignesh M. Patel. 2022. SQLite: Past present and future. Proc. VLDB Endow. 15 12 (2022) 3535\u20133547. DOI:10.14778\/3554821.3554842","DOI":"10.14778\/3554821.3554842"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497528"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_3_3_13_2","volume-title":"On the Universal Relation","author":"Graham M.","year":"1980","unstructured":"M. Graham. 1980. On the Universal Relation. Technical Report. University of Toronto, Computer Systems Research Group."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497486"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","unstructured":"Roberto J. Bayardo Jr. and Daniel P. Miranker. 1994. An optimal backtrack algorithm for tree-structured constraint satisfaction problems. Artificial Intelligence 71 1 (1994) 159\u2013181. DOI:10.1016\/0004-3702(94)90064-7","DOI":"10.1016\/0004-3702(94)90064-7"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","unstructured":"Phokion G. Kolaitis and Moshe Y. Vardi. 2000. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences 61 2 (2000) 302\u2013332. DOI:10.1006\/JCSS.2000.1713","DOI":"10.1006\/JCSS.2000.1713"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","unstructured":"Kukjin Lee Anshuman Dutt Vivek R. Narasayya and Surajit Chaudhuri. 2023. Analyzing the impact of cardinality estimation on execution plans in microsoft SQL server. Proc. VLDB Endow. 16 11 (2023) 2871\u20132883. DOI:10.14778\/3611479.3611494","DOI":"10.14778\/3611479.3611494"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","unstructured":"Viktor Leis Andrey Gubichev Atanas Mirchev Peter Boncz Alfons Kemper and Thomas Neumann. 2015. How good are query optimizers really? Proc. VLDB Endow. 9 3(2015) 204\u2013215. DOI:10.14778\/2850583.2850594","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_3_3_20_2","first-page":"149","volume-title":"Proceedings of the VLDB\u201986 12th International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan","author":"Mackert Lothar F.","year":"1986","unstructured":"Lothar F. Mackert and Guy M. Lohman. 1986. R* optimizer validation and performance evaluation for distributed queries. In Proceedings of the VLDB\u201986 12th International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann, 149\u2013159. Retrieved from http:\/\/www.vldb.org\/conf\/1986\/P149.PDF"},{"key":"e_1_3_3_21_2","volume-title":"Proceedings of the International Symposium on the Applications of Constraint Databases","author":"Miranker Daniel P.","year":"1997","unstructured":"Daniel P. Miranker, Roberto J. Bayardo, and Vasilis Samoladas. 1997. Query evaluation as constraint search; an overview of early results. In Proceedings of the International Symposium on the Applications of Constraint Databases. Retrieved from https:\/\/api.semanticscholar.org\/CorpusID:8644835"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","unstructured":"Thomas Neumann. 2011. Efficiently compiling efficient query plans for modern hardware. Proc. VLDB Endow. 4 9 (2011) 539\u2013550. DOI:10.14778\/2002938.2002940","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","unstructured":"Hung Q. Ngo Ely Porat Christopher R\u00e9 and Atri Rudra. 2018. Worst-case optimal join algorithms. Journal of the ACM 65 3(2018) 40 pages. DOI:10.1145\/3180143","DOI":"10.1145\/3180143"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","unstructured":"Hung Q. Ngo Ely Porat Christopher R\u00e9 and Atri Rudra. 2018. Worst-case optimal join algorithms. Journal of the ACM 65 3 (2018) 16:1\u201316:40. DOI:10.1145\/3180143","DOI":"10.1145\/3180143"},{"key":"e_1_3_3_25_2","volume-title":"Star Schema Bechmark - Revision 3, June 5, 2009","author":"O\u2019Neil Pat","year":"2009","unstructured":"Pat O\u2019Neil, Betty O\u2019Neil, and Xuedong Chen. 2009. Star Schema Bechmark - Revision 3, June 5, 2009. resreport. UMass\/Boston. Retrieved November 15, 2025 from https:\/\/www.cs.umb.edu\/poneil\/StarSchemaB.PDF"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233360"},{"key":"e_1_3_3_28_2","unstructured":"SQLite Documentation. 2024. Query Planning and Optimization. Retrieved July 24 2024 from https:\/\/www.sqlite.org\/optoverview.html#hash_joins. (2024)."},{"key":"e_1_3_3_29_2","unstructured":"SQLite Documentation Team. 2025. The SQLite Bytecode Engine. Retrieved August 21 2025 from https:\/\/www.sqlite.org\/opcode.html. (2025)."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","unstructured":"Robert Endre Tarjan and Mihalis Yannakakis. 1984. Simple linear-time algorithms to test chordality of graphs test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs. SIAM Journal on Computing 13 3 (1984) 566\u2013579. DOI:10.1137\/0213035","DOI":"10.1137\/0213035"},{"key":"e_1_3_3_31_2","unstructured":"Transaction Processing Performance Council (TPC). TPC-H Benchmark. Online. (n.d.). Retrieved November 18 2021 from http:\/\/tpc.org\/tpc_documents_current_versions\/pdf\/tpc-h_v3.0.0.pdf"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","unstructured":"Nikolaos Tziavelis Wolfgang Gatterbauer and Mirek Riedewald. 2025. Any-k algorithms for enumerating ranked answers to conjunctive queries. ACM Trans. Database Syst. 51 1 (September 2025). DOI:10.1145\/3734517","DOI":"10.1145\/3734517"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","unstructured":"Nikolaos Tziavelis Wolfgang Gatterbauer and Mirek Riedewald. 2024. Ranked enumeration for database queries. SIGMOD Rec. 53 3 (2024) 6\u201319. DOI:10.1145\/3703922.3703924","DOI":"10.1145\/3703922.3703924"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","unstructured":"Todd Veldhuizen. 2014. Triejoin: A simple worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT) 17 13 (2014) 96\u2013106. DOI:10.5441\/002\/ICDT.2014.13","DOI":"10.5441\/002\/ICDT.2014.13"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","unstructured":"Qichen Wang Bingnan Chen Binyang Dai Ke Yi Feifei Li and Liang Lin. 2025. Yannakakis+: Practical acyclic query evaluation with theoretical guarantees. Proceedings of the ACM on Management of Data 3 3(2025) 28 pages. DOI:10.1145\/3725423","DOI":"10.1145\/3725423"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","unstructured":"Qichen Wang Xiao Hu Binyang Dai and Ke Yi. 2023. Change propagation without joins. Proc. VLDB Endow. 16 5 (2023) 1046\u20131058. DOI:10.14778\/3579075.3579080","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","unstructured":"Yisu Remy Wang Max Willsey and Dan Suciu. 2023. Free join: Unifying worst-case optimal and traditional joins. Proceedings of the ACM on Management of Data 1 2 (2023) 150:1\u2013150:23. DOI:10.1145\/3589295","DOI":"10.1145\/3589295"},{"key":"e_1_3_3_39_2","first-page":"82","volume-title":"Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society, 82\u201394."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","unstructured":"Junyi Zhao Kai Su Yifei Yang Xiangyao Yu Paraschos Koutris and Huanchen Zhang. 2025. Debunking the myth of join ordering: Toward robust SQL analytics. Proceedings of the ACM on Management of Data 3 3(2025) 28 pages. DOI:10.1145\/3725283","DOI":"10.1145\/3725283"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","unstructured":"Jianqiao Zhu Navneet Potti Saket Saurabh and Jignesh M. Patel. 2017. Looking ahead makes query plans robust. Proc. VLDB Endow. 10 8 (2017) 889\u2013900. DOI:10.14778\/3090163.3090167","DOI":"10.14778\/3090163.3090167"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:17:47Z","timestamp":1773227867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,6]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3774325"],"URL":"https:\/\/doi.org\/10.1145\/3774325","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,6]]},"assertion":[{"value":"2025-03-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}