{"template":"sigconf","title":"Locality-Aware Join Planning with Reserved Capacity","short_title":"Join planning with reserved capacity","authors":[{"name":"Amalia R. Nzegho","affiliations":[1],"email":"amalia.nzegho@meridienne.example","corresponding":true},{"name":"Henrik V. Rautiala","affiliations":[2]},{"name":"Elif S. Orbayhan","affiliations":[3]},{"name":"Lucien K. Barrot","affiliations":[1]}],"affiliations":["Laboratory for Data Systems, Institut Méridienne, Lausanne, Switzerland","School of Computing, Aurajoki Institute of Technology, Turku, Finland","Department of Information Engineering, Ekinova University, İzmir, Türkiye"],"abstract":"Physical query plans normally take the locations of input records as given. In a class of intermittently connected deployments, record placement can still be changed when the query is known, subject to a hard limit on occupancy and a cost for changing existing assignments. We study this problem at seated receptions, where participants carry input records and each dining table is a local execution site. A cost model jointly selects a seating plan and a physical join plan. It distinguishes positive rows from completeness evidence so that an empty chair can provide evidence for a left outer join whose preserved row is located elsewhere. On 120 held-out seating instances drawn at three scales, all evaluated plans agree with centralized relational evaluation. At 96 guests the joint optimizer reduces the median number of boundary-crossing records from 146 to 53 for a grouped program query and from 215 to 76 for a sponsor lookup. Central collection is cheaper for the triangle workload. When absent-carrier acknowledgments are dropped from the protocol, 8.8% of sponsor answers at 96 guests with a vacant reservation report absence before the inner relation is closed. We quantify the cost of retaining a place for a carrier that never arrives.","keywords":["query optimization","join locality","outer joins","distributed query processing","completeness"],"body":"# Introduction {#sec:intro}\n\nIn a seating plan the organizer assigns each confirmed guest a chair. Movement thereafter is possible, but individual conversations and the exchange of small objects often take place within the assigned table. Printed programs and cards can carry information about the guest to whom they were issued. To answer a question about attendees, the organizer generally walks to several tables or collects the relevant cards first.\n\nWe consider the case in which the question is known when the seating chart is prepared. Two people who would otherwise have to pass a card between tables can sometimes be seated at the same table. The last change to the chart is therefore a data placement operation. A venue may specify both a seating plan and a set of scheduled collection rounds, making it possible to optimize placement along with the order of relational operators. The two schedules have distinct deadlines. Entries can be copied onto cards during service. After service begins the guests representing those entries cannot be repartitioned without charging for a seat change. A seating change has unit cost per guest even if that guest carries multiple rows.\n\nConsider a guest whose party sponsor is expected at a different table. A table representative can look up a sponsor and find nobody sitting in the expected seat. The sponsor relation remains open until the attendance window closes. If it turns out that the sponsor never arrived, the guest still appears in the answer, with a null sponsor. The room therefore needs a collection stop at an unoccupied chair. A courier records absence there once the arrival window closes.\n\n# Background {#sec:background}\n\nSystem R jointly chose access paths and join orders given a cost model for prematerialized relations [@selinger1979access]. General accounts distinguish plan enumeration from statistics and cost estimation [@chaudhuri1998overview]. @graefe1993evaluation describes the role of physical properties such as sort order. Within a reception, co-location at a specified round is a physical property of a stream of records. A rearrangement of chairs can establish that property for several streams at once, subject to reserved capacity. The arrangement also establishes a practical limit on which stream properties can coexist. A guest who carries several logically unrelated rows has only one seat.\n\nDistributed semijoins reduce data transmission by exchanging keys before rows [@bernstein1981semijoin]. Acyclic joins permit two passes of semijoin reduction [@yannakakis1981algorithms]. Multiway joins can avoid large binary intermediates on cyclic patterns [@atserias2013size; @ngo2012worst]. Our central collector can use either approach. The controlled distributed plans use physical merge and lookup operators, with dictionary projection where the same keys recur. For small queries the overhead of getting the first key list across the room can dominate the savings in projected rows. @heikkuri2022passes measured this overhead when evaluating selection on paper ballots passed down rows of seats. @mirecourt2024locality studied manually maintained room directories with hard capacity constraints. That work assumes that a row exists at every designated site.\n\nCodd's relational model separates named data from its physical location [@codd1970relational]. The uncertain presence of a row introduces a separate question about whether a site has delivered all rows for a key. The distinction between known data and evidence of completeness has been studied for data integration [@levy1996completeness; @motro1989integrity]. @calarco2023arrivals describe event rosters that close locally before the venue's aggregate count closes. Their totals include an explicit count of guests whose seats were never occupied. We use a sealed roster at each site to supply key-level closure metadata, including keys whose only possible carrier did not take a seat. An inactive site still requires a source for its seal, as observed in @kandemir2021reserved. Marking it inactive in an allocation plan does not generate an execution event.\n\n# Representation and execution {#sec:model}\n\n## Sites, carriers, and records\n\nLet $G$ be the announced guest roster and $T$ a fixed set of tables. Table $t$ has $b_t$ seats. Each $g$ in $G$ has a reference table $r_g$, given by the initial alphabetical seating plan, and receives one or more printed records before service. Each record belongs to one relation and has a row identifier. Multiple records can agree on all query-visible attributes. We keep their identifiers through exchange for bag semantics and discard them only at the last projection or aggregation. An arrival flag selects all records on a guest's card together. A printed roster lists the possible carriers of an inner key. A roster entry alone supplies no row to the query.\n\nA layout $\\ell$ assigns each roster member to one table. Some groups must stay together in the input. The generator gives each two-person required group a single placement variable with weight two. Those constraints model seating requests recorded before the query was registered. The optimizer cannot force an arrival. Capacity is charged to assigned seats, which include places reserved for people who may be late or absent. The organizer can release an unused reservation after the arrival cutoff. It cannot be released in time to justify a seating plan that overflows when every reserved guest arrives.\n\nEach table has a representative with a local ledger. The representative sees arrivals at the table and can copy rows from present cards. Between tables the only transport is a courier following a published round schedule. Courier stops visit all tables in ascending order, then the collector. An envelope can contain at most eight data records. To remove leverage from lucky adjacency within a round, all envelopes are addressed just before a round and all deliveries are visible to their recipients at its end. A sender can make local copies without incurring network traffic. Sending the same projected witness to two sites costs two records. Control receipts carry round and batch identifiers and have fixed-size headers. We count all row, key and seal payload records in the main endpoint and record envelope counts separately.\n\n## Completeness and null extension\n\nFor an outer join $\\operatorname{leftjoin}(P,S)$ on key $k$, define $C(k)$ to be the sites to which any authorized carrier of an $S$ row with key $k$ is assigned. The coordinator roster identifies $C(k)$ after layout selection, including reservations for absent carriers. A site issues a seal for $k$ when its local attendance window and outgoing $S$ batch for $k$ close. The ledger runner issues a zero seal for an unattended table after checking its attendance sheet at cutoff. A seal contains the number of rows in the batch and the final batch identifier. Each row and each seal names its source. The receiving site counts distinct row identifiers per batch. A null-extended output for a preserved row $p$ is legal at receiver $u$ when\n\n$$\n\\begin{aligned}\n&\\forall t\\in C(p.k),\\quad \\operatorname{sealed}_u(t,p.k)\\\\\n&\\qquad\\land\\operatorname{received}_u(t,p.k)=\\operatorname{declared}_u(t,p.k),\\\\\n&\\sum_{t\\in C(p.k)}\\operatorname{received}_u(t,p.k)=0.\n\\end{aligned}\n\\label{eq:null}\n$$\n\nWhen $C(p.k)$ is empty, the roster has already certified the key outside the inner relation's domain. We emit the null extension locally in that case. Otherwise the receiving site waits according to @eq:null. Positive matches can stream while it waits. A retransmission with the same row identifier is acknowledgment retry at the physical layer and never counts twice. @sec:proof gives the argument for bag equivalence.\n\n# Optimization {#sec:optimizer}\n\n## Cost\n\nThe planner takes estimated key frequencies and per-carrier arrival probabilities from the roster. Within a given layout it enumerates three physical plan families for each query, local-first with evidence exchange, key request followed by filtered row exchange, and direct collection. Program aggregation may also ship a partial count rather than each matched row. For triangle evaluation we allow central multiway matching and distributed binary plans with three choices of first edge. We require that each required result and each relevant seal have a route to the designated consumer. Infeasible candidates receive infinite cost.\n\nFor $\\pi$ a physical plan, $W(\\ell,\\pi)$ is its predicted count of crossing records, $D(\\pi)$ the number of exchange rounds on its critical path, and $M(\\ell)$ the number of guests assigned away from the reference table. The objective is\n\n$$\nJ(\\ell,\\pi)=W(\\ell,\\pi)+8D(\\pi)+\\lambda M(\\ell),\n\\qquad M(\\ell)=\\sum_{g\\in G}\\mathbf{1}\\{\\ell(g)\\ne r_g\\}.\n\\label{eq:cost}\n$$\n\nWe price each round at the payload capacity of one envelope and use a seat-change price of half a record. The prediction for a seal record is one when the plan ships evidence for a requested key whose candidate roster at a source is nonempty. Its contribution is independent of the attendance of the candidates. Row predictions multiply estimated co-key multiplicities by arrival probabilities, with one exception for rows on the same carrier. Those rows are either all present or all absent; their match probability uses a single arrival factor. The simulator uses a common random stream for the attendance realization of a roster across all physical plans. Local statistics see assigned rows, while the benchmark evaluator sees realized rows. We use a sound route structure for completeness independently of any cost approximation.\n\n## Search\n\nOur optimizer starts from the reference seating chart and costs every physical alternative. At each iteration it visits legal pairs of guests and evaluates a swap, including swaps with an unused unreserved position. A swap between two required groups is legal only if the new sites still meet constraints. It visits all feasible single relocations too. It then applies the best improving layout move with the best plan under that layout. We stop when no move improves @eq:cost or after 30 improving moves. A lexicographic tiebreak, based on roster ids and plan family, makes repeated runs deterministic. The procedure uses the same physical candidates as the fixed placement comparator. It can skip rescoring a key when none of that key's producer or consumer assignments changed. That optimization follows the delta scoring approach of @versnel2020cards for seating repair.\n\nA second placement baseline chooses swaps based on the number of related guest pairs made local. It finishes allocating chairs before asking the same physical enumerator to choose a join plan. It receives no reward for a null match and treats a many-to-one grouping as a sum of pair affinities. Closely related placement heuristics occur in hypergraph partitioning [@karypis1999multilevel]. Our baseline leaves the eight-record envelope limit and the seat-change penalty to the physical cost calculation after seating. Their omission from placement distinguishes a workload affinity signal from the end-to-end objective.\n\nFor a check on the optimizer, 24 additional rosters have three four-seat tables and at most nine assigned places. We enumerate all group-feasible layouts and physical plans for these small instances. The comparison is with the same objective, probabilities and plan families, giving a lower bound on the achievable cost within the search domain. It does not certify that the candidate set includes the least expensive conceivable plan. We hold the invitation list fixed even in the exhaustive search.\n\n# Evaluation {#sec:evaluation}\n\n## Workloads and design\n\nWe generate 150 rosters, balanced across 48, 96 and 192 assigned guests, using ten rosters per size for tuning and 40 for testing. A table has 12 numbered places. The three sizes have 5, 9 and 18 tables, respectively. Unless stated otherwise, every announced carrier is allocated a seat, and disposable seats that start empty may be used by the optimizer. The carrier arrival probabilities range from 0.58 to 0.98. Within two-person groups an unobserved common shock may prevent both from arriving. The optimizer sees marginal probabilities, while the scorer draws the joint outcome. All 120 test rosters carry the inputs for all three queries, and each query uses the same attendance realization on a given roster. We report one measured execution per query and plan on each roster. The 24 smaller rosters used for enumeration have separate identifiers.\n\nEach card associates a carrier with a party code, and some cards carry sponsor rows for party codes. Other cards list printed introduction permissions in three edge roles. Values are synthetic integer identifiers. Roster order and party grouping are sampled independently before enforcing the placement requirements. Party sizes follow a truncated discrete distribution with median four and maximum twelve. We draw duplicate sponsor row values, with distinct row identifiers, on 10% of the sponsor carriers. Hosts are ordinary record carriers with assigned seats. A host can be a sponsor for more than one party. Missing sponsor rows represent absent carriers or codes without a declared sponsor, depending on the generator flag. @tbl:queries gives the three tasks.\n\nTable: Workload definitions. Each query is evaluated separately and has a designated result table. The host dimension in Program is keyed by party code. {#tbl:queries span=full}\n\n| Workload | Operators | Output |\n|:---------|:----------|:-------|\n| Program | Carrier-to-host inner lookup, local program lookup, grouped count | Count per program class and host region |\n| Sponsor | Guest left outer join with all realized party sponsor rows | Guest, sponsor identifier or null |\n| Introduction | Cyclic three-way join on directed guest pairs | Ordered triples of mutually eligible guests |\n\nFor Program, the program value is local to the guest and the host dimension is unique per party code. Only guests with a realized row in both dimensions contribute to a count. The carrier bearing the host dimension can be absent independently of the others in the party. For Sponsor, the preserved relation contains one row per arrived guest and the inner relation can contain multiple rows for one code. The output has one tuple per match, or one null tuple if none exists. For Introduction, three separately generated edge lists point from $a$ to $b$, $b$ to $c$ and $c$ to $a$, with records assigned to the first endpoint. Self edges are prohibited by the generator. Positive edge records travel only if their carriers arrived. A missing assignment to a relation is empty for the duration of the episode.\n\nWe run a separate stress test of absence evidence. In the core suite the attendance cutoff precedes dispatch of any completeness seal. The selected guest-to-seat assignment has no effect on the actual attendance draw. In the stress run each sponsor reservation is resolved at one of the first four dispatch rounds, drawn uniformly. In that run the oracle uses the final snapshot. Every possible carrier has a final status in the snapshot. The local ledger learns that status when the carrier arrives or its reservation expires. We compare protocols that wait for this evidence with a premature protocol that treats an empty reservation as final on its first visit.\n\n## Baselines and measurements\n\nFixed seating represents the unmodified chart, using the same physical plan families and @eq:cost. To maintain a genuine distributed comparator, fixed and affinity rows in the main results report the cheapest candidate among the two distributed families. The joint optimizer row also reports the best distributed candidate, so differences measure layout and distributed-plan effects. Central collection transfers every input row to the designated result table if its carrier is elsewhere, and computes the whole query there. It may issue a roster digest when a relation has no rows. It does not have to route a seal for every key. It already owns the combined roster at the end of the collection window. We include its median alongside the distributed plans. In the unrestricted choice the optimizer can select it.\n\nA centralized exact evaluator uses the run's realized occurrence ids and applies bag semantics, SQL null extension and exact integer aggregation. We sort the outputs on all result fields and compare multiplicities, treating null as a distinct comparison symbol in the test harness. With a zero result set we require a valid delivery trace even if the equality test is trivial. We never exclude a run because a result was empty. Six rosters at each scale were replayed with printed cards, assigned labels on chairs and envelopes on a tabletop floor map. This replay moves records and paper labels rather than people, with arrival flags revealed on the same round schedule. An independent tally counts transferred records, envelope occupancy and final multiplicity. This check tests bookkeeping under a finite exchange schedule. Its execution time does not estimate reception duration.\n\nThe primary contrast is the paired difference in crossing records for Program at 96 guests, fixed minus joint. We summarize contrast and uncertainty with the median paired difference and a 10,000-draw percentile bootstrap over independently generated rosters [@efron1993bootstrap]. Per-workload medians are computed over the 40 rosters at the relevant scale. Marginal medians may differ from the median of paired differences. Other workload comparisons and stress findings are reported descriptively. Eight tuning rosters per size were enough to choose the move limit on the development curves. The remaining two per size checked roster feasibility and batching before we collected the test outcomes.\n\n# Results {#sec:results}\n\n## Work by placement and query\n\n@tbl:main compares the four plans. For Sponsor, the joint optimizer spends some seat changes on colocating the senders and consumers of seals for sponsors with low estimated attendance.\n\nTable: Median records crossing a table boundary at 96 assigned guests (40 rosters). Counts include data and completeness payloads. Lower is better. {#tbl:main}\n\n| Placement and execution | Program | Sponsor | Introduction |\n|:------------------------|--------:|--------:|-------------:|\n| Fixed seating, distributed | 146 | 215 | 306 |\n| Affinity seating, distributed | 81 | 132 | 285 |\n| Joint seating and plan | **53** | **76** | 246 |\n| Fixed seating, collect | 116 | 137 | **203** |\n\nFor Program the median paired saving is 89 records (95% interval 80 to 97), compared with a difference of 93 between the two marginal medians. The joint plan typically sends partial counts toward the end of the dispatch schedule. @fig:scale gives the scale dependence and the median seat change cost on the same rosters. At the largest size the assigned guest count doubles and the relative saving is similar. Changes to the grouping distribution could shift this relationship, since plan benefits depend on the share of keys that fit at one or two tables. At 96 guests the 22 moved guests in the median instance occupy fewer than two full tables and are drawn from six tables in the median move trace.\n\n![Program workload at three scales. Left shows median boundary-crossing records. Right shows median guests seated away from their reference table.](join-scale){#fig:scale span=full}\n\nIntroduction produces less shareable local work. Each edge's key is an endpoint pair, and interest in the same pair is spread across enough locations that shifting a carrier into one favorable table often moves it out of another. Central collection wins the median comparison and is selected in 31 of 40 Introduction rosters at the medium size when all alternatives are eligible. At 96 guests the median envelope counts for joint Program, Sponsor and Introduction are 18, 25 and 39. The median round counts are two, three and three. Although the record endpoint ignores envelope headers, envelope counts preserve the median Program and Sponsor rankings against fixed placement (31 and 42 envelopes). The direct collector uses a single exchange round after the cutoff for all three queries.\n\nThe optimizer reached a local minimum before the move cap on 114 of 120 Program runs. On the 24 smaller rosters it found a minimum-cost Program arrangement in 19, with relative cost gaps of 1.4% to 7.8% on the other five. Local minima are often caused by a nearly full table. For one small case the optimum exchanged three carriers in a cycle. The corresponding pairwise changes would have exceeded capacity or separated a required pair during the intermediate step. Requiring a legal arrangement at every iteration ruled out both pairwise routes. The optimum remained a legal starting layout if specified all at once.\n\n## Vacant reservations\n\nThe four physical plans in the main comparison agree with centralized evaluation on all 360 roster-query instances. We saw no lost or duplicate output in the 18 paper replays or a mismatch between the simulator's payload count and the envelope tally. The premature protocol fails under staggered arrival. Among the 40 medium-size Sponsor rosters, there are 398 preserved rows present at the first visit whose possible inner carriers include at least one vacant reservation. In 35 of those cases the premature evaluator emits null for a preserved row that later receives an actual sponsor match (8.8%). The other 363 premature checks happen to be correct for that row, or wait because the executor already sees at least one positive match. We report errors per preserved row. A single early seal can affect several rows on two tables, so an interval treating 398 errors as independent Bernoulli trials would be inappropriate.\n\nTable: Sponsor stress run at 96 assigned guests. Affected rows have at least one possible inner carrier in a reserved seat vacant at an early dispatch. {#tbl:absence}\n\n| Evidence rule | Affected rows | Incorrect nulls |\n|:--------------|--------------:|----------------:|\n| Close at first empty visit | 398 | 35 |\n| Close after complete seal | 398 | 0 |\n\n@fig:wait shows what the flawed executor knows at each dispatch. Out of the 398 rows, 35 are initially eligible for its incorrect null extension and receive a match later. The number of those false nulls that would still be present in the answer after the next delivery is 28 if revisions are permitted. In the implemented flawed protocol a null already delivered cannot be retracted. The plotted counterfactual therefore isolates the duration of the information gap and is distinct from errors in delivered results. @calarco2023arrivals discuss the problem of sending corrected headcounts after service orders have been handed to a different room.\n\n```chart {#fig:wait caption=\"Sponsor rows in the premature-null cohort still awaiting their first positive match after each dispatch. This cohort is defined from replay against the final snapshot.\"}\n{\"type\":\"line\",\"xlabel\":\"Dispatch round\",\"ylabel\":\"Rows awaiting match (count)\",\"x\":[0,1,2,3,4],\"series\":[{\"label\":\"Premature-null cohort\",\"y\":[35,28,17,8,0],\"marker\":\"o\"}],\"legend\":\"none\",\"ylim\":[0,40]}\n```\n\nIn a separate sweep, we suppress the Sponsor inserts on independently sampled carrier cards while preserving the realized guest relation, roster and physical plan. @fig:seals shows realized transfers when the extra probability of an empty Sponsor card is 0%, 25%, 50% or 75%. At the last point the median total falls from 76 to 59. The same seal traffic is required because those keys still have possible source sites. A site whose cards lose all of their sponsor entries can finish the run having supplied only certificates.\n\n```chart {#fig:seals caption=\"Sponsor transfer under extra thinning at 96 guests. The total is the median of per-roster totals. Component medians are taken separately.\"}\n{\"type\":\"line\",\"xlabel\":\"Additional removal probability (%)\",\"ylabel\":\"Crossing records (median count)\",\"x\":[0,25,50,75],\"series\":[{\"label\":\"Total\",\"y\":[76,71,65,59],\"marker\":\"o\"},{\"label\":\"Seals\",\"y\":[50,50,50,50],\"style\":\"dashed\",\"marker\":\"s\"},{\"label\":\"Other payload\",\"y\":[26,21,15,9],\"marker\":\"^\"}],\"legend\":\"outside\",\"ylim\":[0,85]}\n```\n\n# Discussion {#sec:discussion}\n\nThis evaluation holds the relation between a guest and the records on that guest's card fixed. It is possible to print a second copy of every row before the event. If available snapshot information makes those copies authoritative, the optimizer can simply ship paper to the collector before moving a guest. In our model any pre-event copy represents an expected row. It becomes valid only when synchronized with the actual arrival record. One could reduce runtime state to those activation records and pre-distribute the data values. This is a different plan with an additional storage and coordination cost. It could be valuable for stable lookup dimensions and races with the onset of service when a late change to the roster is expected [@savio2022reprints].\n\nThe model assumes a single layout per query. At an actual reception there may be several queries with different consumers and no opportunity to reseat guests between them. A physical layout picked for sponsor completeness may put the wrong groups together for introduction. Joint placement for multiple queries would require weighing their predicted join costs on one common assignment, as in multi-query optimization [@sellis1988multiple]. The benefit of reusing a seal would then depend on whether both joins interpret its inner snapshot at the same cutoff. A query issued at the end of the first course could be answered correctly and still fail verification when evaluated by the roster from the second course. For a single query the place can be released as soon as the ledger runner records its absence. The seal leaves on the next dispatch even if the chair has already been carried away.\n\n\\appendix\n\n# Correctness of outer evaluation {#sec:proof}\n\nAssume the registry of possible inner carriers is sound and complete, each carrier has exactly one assigned site and the seal protocol captures all rows in the final snapshot. Then any matching inner row for preserved row $p$ comes from a site in $C(p.k)$. Each delivered match with a distinct occurrence id makes one output. Joining a preserved duplicate independently is necessary to implement bag semantics. Once all declared counts agree with the received counts, no missing row can change the observed multiplicity. If the sum in @eq:null is zero, no match can ever be delivered for that key under the assumed snapshot, and a single null row is required. Conversely, when the sum is positive the executor can produce only the corresponding matches. The registry-empty case follows because no permissible source can supply that key.\n\n# Cost replay and reproducibility {#sec:replay}\n\nOn a single 3.4 GHz x86-64 core, the median full optimization time at 96 assigned guests was 210 ms for Program, including catalog construction and all candidate evaluations. The 95th percentile was 430 ms. Execution simulation and centralized replay took a further 14 ms at the median. The printed replay counts crossings at envelope delivery, with a separate mark per copied row when a payload is replicated. Its verification record contains no arrival identifiers beyond the synthetic roster. The implementation does not infer unopened envelope contents from the name written on the chair.","bibliography":"@inproceedings{selinger1979access, author={Selinger, Patricia G. and Astrahan, Morton M. and Chamberlin, Donald D. and Lorie, Raymond A. and Price, Thomas G.}, title={Access Path Selection in a Relational Database Management System}, booktitle={ACM SIGMOD International Conference on Management of Data}, pages={23--34}, year={1979}}\n@inproceedings{chaudhuri1998overview, author={Chaudhuri, Surajit}, title={An Overview of Query Optimization in Relational Systems}, booktitle={ACM Symposium on Principles of Database Systems}, pages={34--43}, year={1998}}\n@article{graefe1993evaluation, author={Graefe, Goetz}, title={Query Evaluation Techniques for Large Databases}, journal={ACM Computing Surveys}, volume={25}, number={2}, pages={73--169}, year={1993}}\n@article{bernstein1981semijoin, author={Bernstein, Philip A. and Chiu, Dah-Ming W.}, title={Using Semi-Joins to Solve Relational Queries}, journal={Journal of the ACM}, volume={28}, number={1}, pages={25--40}, year={1981}}\n@inproceedings{yannakakis1981algorithms, author={Yannakakis, Mihalis}, title={Algorithms for Acyclic Database Schemes}, booktitle={International Conference on Very Large Data Bases}, pages={82--94}, year={1981}}\n@article{atserias2013size, author={Atserias, Albert and Grohe, Martin and Marx, Dániel}, title={Size Bounds and Query Plans for Relational Joins}, journal={SIAM Journal on Computing}, volume={42}, number={4}, pages={1737--1767}, year={2013}}\n@inproceedings{ngo2012worst, author={Ngo, Hung Q. and Porat, Ely and Ré, Christopher and Rudra, Atri}, title={Worst-Case Optimal Join Algorithms}, booktitle={ACM Symposium on Principles of Database Systems}, pages={37--48}, year={2012}}\n@article{codd1970relational, author={Codd, Edgar F.}, title={A Relational Model of Data for Large Shared Data Banks}, journal={Communications of the ACM}, volume={13}, number={6}, pages={377--387}, year={1970}}\n@inproceedings{levy1996completeness, author={Levy, Alon Y.}, title={Obtaining Complete Answers from Incomplete Databases}, booktitle={International Conference on Very Large Data Bases}, pages={402--412}, year={1996}}\n@article{motro1989integrity, author={Motro, Amihai}, title={Integrity = Validity + Completeness}, journal={ACM Transactions on Database Systems}, volume={14}, number={4}, pages={480--502}, year={1989}}\n@article{karypis1999multilevel, author={Karypis, George and Aggarwal, Rajat and Kumar, Vipin and Shekhar, Shashi}, title={Multilevel Hypergraph Partitioning: Applications in {VLSI} Domain}, journal={IEEE Transactions on Very Large Scale Integration Systems}, volume={7}, number={1}, pages={69--79}, year={1999}}\n@book{efron1993bootstrap, author={Efron, Bradley and Tibshirani, Robert J.}, title={An Introduction to the Bootstrap}, publisher={Chapman and Hall}, year={1993}}\n@article{sellis1988multiple, author={Sellis, Timos K.}, title={Multiple-Query Optimization}, journal={ACM Transactions on Database Systems}, volume={13}, number={1}, pages={23--52}, year={1988}}\n@inproceedings{heikkuri2022passes, author={Heikkuri, Aino M. and Otero Valls, Manuel}, title={The Cost of Passes in Paper-Based Selection}, booktitle={Workshop on Intermittent Data Processing}, pages={9--17}, year={2022}}\n@article{mirecourt2024locality, author={Mirecourt, Noémie J. and Afenyo, Kweku N.}, title={Locality and Fixed Capacity in Manually Maintained Directories}, journal={Journal of Practical Data Management}, volume={14}, number={2}, pages={131--158}, year={2024}}\n@article{calarco2023arrivals, author={Calarco, Daria L. and Peduru, Nalin K.}, title={Arrival Closure in Distributed Event Rosters}, journal={Journal of Venue Operations}, volume={18}, pages={56--81}, year={2023}}\n@inproceedings{kandemir2021reserved, author={Kandemir, Nehir L. and Stornes, Joakim P.}, title={Evaluating Lookups at Reserved but Inactive Sites}, booktitle={Workshop on Intermittent Data Processing}, pages={44--52}, year={2021}}\n@article{versnel2020cards, author={Versnel, Jacqueline M. and Oum, Davin}, title={Incremental Scoring for Late Repair of Printed Place Assignments}, journal={Journal of Venue Operations}, volume={15}, pages={109--129}, year={2020}}\n@inproceedings{savio2022reprints, author={Savio, Maria C. and van der Klei, Eelco}, title={Snapshot Validation for Advance Printing of Mutable Event Records}, booktitle={Workshop on Data Management at the Edge}, pages={21--29}, year={2022}}","figures":[{"id":"join-scale","kind":"chart","data":"{\"panels\":[{\"type\":\"line\",\"xlabel\":\"Assigned guests (count)\",\"ylabel\":\"Crossing records (median)\",\"x\":[48,96,192],\"series\":[{\"label\":\"Fixed\",\"y\":[66,146,299],\"marker\":\"s\"},{\"label\":\"Joint\",\"y\":[25,53,115],\"marker\":\"o\"}],\"legend\":\"upper left\",\"ylim\":[0,320]},{\"type\":\"line\",\"xlabel\":\"Assigned guests (count)\",\"ylabel\":\"Moved guests (median)\",\"x\":[48,96,192],\"series\":[{\"label\":\"Affinity\",\"y\":[13,30,61],\"marker\":\"^\"},{\"label\":\"Joint\",\"y\":[9,22,44],\"marker\":\"o\"}],\"legend\":\"upper left\",\"ylim\":[0,68]}],\"size\":[6.8,2.4]}"}],"acknowledgments":"We thank Sibel N. Akveren for checking delivered occurrence counts and Janne Ilvesniemi for recovering the unused place labels after the third replay.","options":{"ccs":["Information systems → Query optimization","Information systems → Distributed database management systems"]}}