4 papers
Poisson Sampling over Acyclic Joins
Liese Bekkers, Frank Neven, Lorrens Pantelis +1
We introduce the problem of Poisson sampling over joins: compute a sample of the result of a join query by conceptually performing a Bernoulli trial for each join tuple, using a no…
Database Theory in Action: Yannakakis' Algorithm
Paraschos Koutris, Stijn Vansummeren, Qichen Wang +2
Yannakakis' seminal algorithm is optimal for acyclic joins, yet it has not been widely adopted due to its poor performance in practice. This paper briefly surveys recent advancemen…
Using Read Promotion and Mixed Isolation Levels for Performant Yet Serializable Execution of Transaction Programs
Brecht Vandevoort, Alan Fekete, Bas Ketsman +2
We propose a theory that can determine the lowest isolation level that can be allocated to each transaction program in an application in a mixed-isolation-level setting, to guarant…
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores
Liese Bekkers, Frank Neven, Stijn Vansummeren +1
Acyclic join queries can be evaluated instance-optimally using Yannakakis' algorithm, which avoids needlessly large intermediate results through semi-join passes. Recent work propo…