\n","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"In this paper we establish that leapfrog triejoin is also worst-case optimal,\nup to a log factor, in the sense of NPRR","italic":true}]},{"type":"p","children":[{"type":"text","text":"Author: Todd L. Veldhuizen. 2014."}]},{"type":"p","children":[{"type":"text","text":"In Proceedings of the 17th International Conference on Database Theory (ICDT\n‘14).","italic":true}]},{"type":"p","children":[{"type":"text","text":"Recent years have seen exciting developments in join algorithms.In 2008,\nAtserias, Grohe and Marx (henceforth AGM) proved a tight bound on the maximum\nresult size of a full conjunctive query, given constraints on the input relation\nsizes. In 2012, Ngo, Porat, R«e and Rudra (henceforth NPRR) devised a join\nalgorithm with worst-case running time proportional to the AGM bound [8]. Our\ncommercial database system LogicBlox employs a novel join algorithm, leapfrog\ntriejoin, which compared conspicuously well to the NPRR algorithm in preliminary\nbenchmarks. This spurred us to analyze the complexity of leapfrog triejoin. In\nthis paper we establish that leapfrog triejoin is also worst-case optimal, up to\na log factor, in the sense of NPRR. We improve on the results of NPRR by proving\nthat leapfrog triejoin achieves worst-case optimality for finer-grained classes\nof database instances, such as those defined by constraints on projection\ncardinalities. We show that NPRR is not worst-case optimal for such classes,\ngiving a counterexample where leapfrog triejoin runs inO(nlogn)time and NPRR\nruns in Θ(n1.375)time. On a practical note, leapfrog triejoin can be implemented\nusing conventional data structures such as B-trees, and extends naturally to ∃1\nqueries. We believe our algorithm offers a useful addition to the existing\ntoolbox of join algorithms, being easy to absorb, simple to implement, and\nhaving a concise optimality proof."}]},{"type":"p","children":[{"type":"text","text":"Read the PDF:\n"},{"type":"a","url":"https://arxiv.org/pdf/1210.0481.pdf","title":null,"children":[{"type":"text","text":"Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm"}]}]}],"_content_source":{"queryId":"src/content/resources/leapfrog-triejoin-a-simple-worst-case-optimal-join-algorithm.mdx","path":["resource","body"]}},"_content_source":{"queryId":"src/content/resources/leapfrog-triejoin-a-simple-worst-case-optimal-join-algorithm.mdx","path":["resource"]}}},"errors":null,"query":"\n query resource($relativePath: String!) {\n resource(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...ResourceParts\n }\n}\n \n fragment ResourceParts on Resource {\n __typename\n title\n description\n date\n image\n categories\n authors {\n __typename\n name\n link\n }\n seo {\n __typename\n keywords\n description\n image\n image_alt\n canonical_url\n author\n published\n modified\n language\n robots\n site_name\n content_type\n }\n body\n}\n ","variables":{"relativePath":"leapfrog-triejoin-a-simple-worst-case-optimal-join-algorithm.mdx"}},"src/content/meta/meta.md":{"data":{"meta":{"_sys":{"filename":"meta","basename":"meta.md","breadcrumbs":["meta"],"path":"src/content/meta/meta.md","relativePath":"meta.md","extension":".md"},"id":"src/content/meta/meta.md","__typename":"Meta","banner":{"__typename":"MetaBanner","enabled":true,"content":{"type":"root","children":[{"type":"p","children":[{"type":"text","text":"Check out "},{"type":"a","url":"/resources/highlights-of-relationalai-at-snowflake-data-cloud-summit-2024","title":"SF summit highlights","children":[{"type":"text","text":"highlights"}]},{"type":"text","text":" of RelationalAI at "},{"type":"text","text":"Snowflake's Data Cloud Summit 2024!","bold":true}]}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner","content"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner"]}},"header":{"__typename":"MetaHeader","links":[{"__typename":"MetaHeaderLinks","text":"Product","url":"/product","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",0]}},{"__typename":"MetaHeaderLinks","text":"Company","url":"/company","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",1]}},{"__typename":"MetaHeaderLinks","text":"Docs","url":"/docs","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",2]}},{"__typename":"MetaHeaderLinks","text":"Resources","url":"/resources/all/1","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",3]}},{"__typename":"MetaHeaderLinks","text":"Get Started","url":"/get-started","style":"cta","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",4]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header"]}},"footer":{"__typename":"MetaFooter","sections":[{"__typename":"MetaFooterSections","name":"Product","links":[{"__typename":"MetaFooterSectionsLinks","text":"Overview","url":"/product","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Use Cases","url":"/product#for-problems-that-matter","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Capabilities","url":"/product#a-new-toolset","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0]}},{"__typename":"MetaFooterSections","name":"Resources","links":[{"__typename":"MetaFooterSectionsLinks","text":"Documentation","url":"/docs/getting_started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"News","url":"/resources/news/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Research","url":"/resources/research/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Releases","url":"/resources/releases/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",3]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1]}},{"__typename":"MetaFooterSections","name":"About Us","links":[{"__typename":"MetaFooterSectionsLinks","text":"Our Company","url":"/company","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Contact Us","url":"/get-started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Careers","url":"/careers","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Legal","url":"/legal","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",3]}},{"__typename":"MetaFooterSectionsLinks","text":"GDPR","url":"/gdpr","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",4]}},{"__typename":"MetaFooterSectionsLinks","text":"Security & Trust","url":"https://trust.relational.ai/","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",5]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2]}}],"socials":[{"__typename":"MetaFooterSocials","text":"GitHub","url":"https://github.com/RelationalAI","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/github.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",0]}},{"__typename":"MetaFooterSocials","text":"LinkedIn","url":"https://www.linkedin.com/company/relationalai/about","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/linkedin.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",1]}},{"__typename":"MetaFooterSocials","text":"Twitter","url":"https://twitter.com/relationalai","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/twitter.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta"]}}},"errors":null,"query":"\n query meta($relativePath: String!) {\n meta(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...MetaParts\n }\n}\n \n fragment MetaParts on Meta {\n __typename\n banner {\n __typename\n enabled\n content\n }\n header {\n __typename\n links {\n __typename\n text\n url\n style\n }\n }\n footer {\n __typename\n sections {\n __typename\n name\n links {\n __typename\n text\n url\n }\n }\n socials {\n __typename\n text\n url\n icon\n }\n }\n}\n ","variables":{"relativePath":"./meta.md"}}};
globalThis.tina_info = tina;
})();
Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm · RelationalAI
Check out highlights of RelationalAI at Snowflake's Data Cloud Summit 2024!
Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm
In this paper we establish that leapfrog triejoin is also worst-case optimal,
up to a log factor, in the sense of NPRR
Author: Todd L. Veldhuizen. 2014.
In Proceedings of the 17th International Conference on Database Theory (ICDT
‘14).
Recent years have seen exciting developments in join algorithms.In 2008,
Atserias, Grohe and Marx (henceforth AGM) proved a tight bound on the maximum
result size of a full conjunctive query, given constraints on the input relation
sizes. In 2012, Ngo, Porat, R«e and Rudra (henceforth NPRR) devised a join
algorithm with worst-case running time proportional to the AGM bound [8]. Our
commercial database system LogicBlox employs a novel join algorithm, leapfrog
triejoin, which compared conspicuously well to the NPRR algorithm in preliminary
benchmarks. This spurred us to analyze the complexity of leapfrog triejoin. In
this paper we establish that leapfrog triejoin is also worst-case optimal, up to
a log factor, in the sense of NPRR. We improve on the results of NPRR by proving
that leapfrog triejoin achieves worst-case optimality for finer-grained classes
of database instances, such as those defined by constraints on projection
cardinalities. We show that NPRR is not worst-case optimal for such classes,
giving a counterexample where leapfrog triejoin runs inO(nlogn)time and NPRR
runs in Θ(n1.375)time. On a practical note, leapfrog triejoin can be implemented
using conventional data structures such as B-trees, and extends naturally to ∃1
queries. We believe our algorithm offers a useful addition to the existing
toolbox of join algorithms, being easy to absorb, simple to implement, and
having a concise optimality proof.