均匀采样和近似计数是现代数据库应用的基本原语，范围从查询优化到近似查询处理。尽管最近的突破为全连接查询建立了最优采样和计数算法，但联接-投影查询仍然存在显著的差距，这些查询在现实工作负载中无处不在。现有的“提出与验证”框架对于这些查询存在基本效率低下的问题，当投影显著减少输出大小时，通常会导致复杂度过高。在本文中，我们为基本类的联接-投影查询，包括矩阵、星型和链型查询，提出了首个渐近最优算法。通过利用一种新颖的基于拒绝的采样策略和混合计数简化，我们实现了相比现有技术的多项式加速。我们通过匹配的通信复杂度下界来确认结果的最优性，这些下界即使在快速矩阵乘法等代数技术面前也依然成立。最后，我们勾勒出问题空间的理论极限。尽管矩阵和星型查询允许高效的亚线性时间算法，但我们为链型查询建立了显著更强的下界，表明一般情况下不可能存在亚线性算法。
Hu et al.（周）研究了这个问题。