| <!DOCTYPE html> |
| <html lang="en"> |
| <head> |
| <meta charset="UTF-8"> |
| <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> |
| |
| <title>Apache Wayang</title> |
| <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" integrity="sha384-TX8t27EcRE3e/ihU7zmQxVncDAy5uIKz4rEkgIXeMed4M0jlfIDPvg6uqKI2xXr2" crossorigin="anonymous"> |
| <link rel="stylesheet" href="../../static/css/color.css"> |
| <link rel="stylesheet" href="../../static/fa/css/all.min.css"> |
| <link rel="icon" type="image/png" href="../../static/img/wayang-favicon.png" /> |
| <style> |
| .service-item { |
| text-align: center; |
| } |
| .italic { |
| font-style: italic; |
| } |
| .bold { |
| font-weight: bold; |
| } |
| hr { |
| border: 1px dotted #555555; |
| width: 80%; |
| } |
| p { |
| text-align: justify; |
| } |
| </style> |
| </head> |
| <!-- TODO: the padding of the body need to be resposive --> |
| <body style="padding: 4em; background: white"> |
| |
| <div class="container shadow-lg p-3 mb-5 bg-white rounded"> |
| <nav class="sticky-top navbar navbar-expand-lg navbar-light d-flex bd-highlight mt-n3 mx-n3 shadow mb-4" style="background: #A6A6A6"> |
| <a class="p-2 flex-grow-1 bd-highlight navbar-brand"> |
| <img src="../../static/img/logo-plain.png"> |
| </a> |
| <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarText" aria-controls="navbarText" aria-expanded="false" aria-label="Toggle navigation"> |
| <span class="navbar-toggler-icon"></span> |
| </button> |
| <div class="collapse navbar-collapse" id="navbarText"> |
| <ul class="navbar-nav mr-auto" style="margin-left: 25%"> |
| <li class="nav-item active"> |
| <a class="nav-link" href="../../index.html">Home <span class="sr-only">(current)</span></a> |
| </li> |
| <li class="nav-item"> |
| <a class="nav-link" href="../../about.html">About</a> |
| </li> |
| <li class="nav-item"> |
| <a class="nav-link" href="../../documentation.html">Documentation</a> |
| </li> |
| <li class="nav-item"> |
| <a class="nav-link" href="../../publications.html">Publications</a> |
| </li> |
| <li class="nav-item dropdown"> |
| <a class="nav-link dropdown-toggle" data-toggle="dropdown" href="#" role="button" aria-haspopup="true" aria-expanded="false">Apache</a> |
| <div class="dropdown-menu"> |
| <a class="dropdown-item" href="http://www.apache.org/foundation/how-it-works.html">Apache Software Foundation</a> |
| <a class="dropdown-item" href="http://www.apache.org/licenses/">Apache License</a> |
| <a class="dropdown-item" href="http://www.apache.org/foundation/sponsorship.html">Sponsorship</a> |
| <a class="dropdown-item" href="http://www.apache.org/foundation/thanks.html">Thanks</a> |
| </div> |
| </li> |
| </li> |
| </ul> |
| </div> |
| </nav> |
| |
| <div class="row mb-3 mt-n5 d-flex align-items-center" style="background-image: url(../../static/img/background-1.png); height: 10em; background-position: 50%"> |
| <div class="col" style="text-align: center"> |
| <h1 style="color: white; font-size: 4em">Publication</h1> |
| <h2 style="color: white; font-size: 2em">"Lightning Fast and Space Efficient Inequality Joins"</h2> |
| </div> |
| </div> |
| |
| <div class="row justify-content-md-center mb-4"> |
| <div class="col-10 "> |
| <div class="post-info-wrapper"> |
| <p class="italic">By <span class="bold">Zuhair Khayyat, William Lucia, Meghna Singh, Mourad Ouzzani, Paolo Papotti, Jorge-Arnulfo Quiané-Ruiz, Nan Tang and Panos Kalnis</span> on <span class="bold">2015</span></p> |
| </div> |
| <hr /> |
| <p> |
| Inequality joins, which join relational tables on inequality conditions, are used in various applications. While there have been a wide range of optimization methods for joins in database systems, from algorithms such as sort-merge join and band join, to various indices such as B+-tree, R∗-tree and Bitmap, inequality joins have received little attention and queries containing such joins are usually very slow. In this paper, we introduce fast inequality join algorithms. We put columns to be joined in sorted arrays and we use permutation arrays to encode positions of tuples in one sorted array w.r.t. the other sorted array. In contrast to sort-merge join, we use space efficient bit-arrays that enable optimizations, such as Bloom filter indices, for fast computation of the join results. We have implemented a centralized version of these algorithms on top of PostgreSQL, and a distributed version on top of Spark SQL. We have compared against well known optimization techniques for inequality joins and show that our solution is more scalable and several orders of magnitude faster. |
| </p> |
| <hr /> |
| |
| </div> |
| <div class="col-10 text-center"> |
| <a href="../../static/pdf/paper/iejoin.pdf" class="btn btn-success"> |
| <i class="far fa-file-pdf"></i> Download |
| </a> |
| </div> |
| </div> |
| |
| <nav class="navbar fixed-bottom navbar-light bg-light position-relative mb-n3 mx-n3 mb-4" style="background: #A6A6A6"> |
| <div class="row justify-content-center"> |
| <div class="col-10 text-center"> |
| <p style="text-align: justify"> |
| Apache Wayang is an effort undergoing Incubation at The Apache Software Foundation (ASF), sponsored by the Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not necessarily a reflection of the completeness or stability of the code, it does indicate that the project has yet to be fully endorsed by the ASF. |
| </p> |
| <a href="http://incubator.apache.org/"> |
| <img src="../../static/img/egg-logo.png"> |
| </a> |
| <br /> |
| <p> |
| Copyright © 2021 The Apache Software Foundation.<br /> |
| Licensed under the Apache License, Version 2.0.<br /> |
| Apache, the Apache Feather logo, and the Apache Incubator project logo are trademarks of The Apache Software Foundation. |
| </p> |
| </div> |
| </div> </nav> |
| </div> |
| |
| |
| |
| |
| <script src="https://code.jquery.com/jquery-3.5.1.slim.min.js" integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script> |
| <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.1/dist/umd/popper.min.js" integrity="sha384-9/reFTGAW83EW2RDu2S0VKaIzap3H66lZH81PoYlFhbGU+6BZp6G7niu735Sk7lN" crossorigin="anonymous"></script> |
| <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" integrity="sha384-w1Q4orYjBQndcko6MimVbzY0tgp4pWB4lZ7lr30WKz0vr/aWKhXdBNmNb5D92v7s" crossorigin="anonymous"></script> |
| |
| |
| </body> |
| </html> |
