我们引入了无环连接上泊松采样的问题：通过对每个连接元组概念性地进行伯努利试验，以非均匀和特定于元组的概率计算连接查询结果的样本。我们提出了一种几乎是实例最优的无环连接上泊松采样算法，它的运行时间为O(N + k N)，其中N是输入数据库的大小，k是结果样本的大小。我们的算法依赖于两个构建模块：(1)建造一个随机访问索引，允许在给定一个数字i的情况下，随机访问第i个连接元组，而不需要完全物化(可能很大的)连接结果；(2)探测该索引以构建结果样本。我们研究了使这两个组件实用所需的工程权衡，专注于它们在列存储中的实现，并为两者识别了表现最佳的替代方案。我们在真实数据上的实验表明，这对替代方案显著优于用于泊松采样的重复伯努利试验算法，同时还表明，仅随机访问索引可以用来有效地实现Yannakakis的无环连接处理算法，且无需进行采样。这表明，就查询引擎设计而言，采用均匀的方法来处理经典的无环连接和泊松采样是可能的，并且与经典连接和采样算法相比，没有悔恨。
BEKKERS等人(Thu,)研究了这个问题。