join - 可以在单次传递中为内存结构构建 FULL JOIN(不使用 sql!)

Question

我正在构建一个内存中的柱状关系引擎。为了提取我想要进行后期实现的值，我在其中收集找到匹配项的位置/索引，并在最后收集这些值。

现在实现连接，我看不出覆盖所有其他情况的通用连接算法是如何实现的。 Left、Right & Inner 很容易，但 FULL/Outer 则不然。这是我使用嵌套循环的天真实现:

pub fn join(&self, compare:&BoolExpr) -> JoinPos
{
    //Allocate at least for inner joins...
    let total = cmp::max(self.left.len(), self.right.len());

    let mut cols_left  = Vec::with_capacity(total);
    let mut cols_right = Vec::with_capacity(total);
    let mut found = false;

    while !self.left.eof() {
        let left = self.left.tuple();
        while !self.right.eof() {
            let right = self.right.tuple();
            if compare(&left, &right) {
                //A match found. Record positions of both cursors
                cols_left.push(self.left.pos() as isize);
                cols_right.push(self.right.pos() as isize);
                found = true;
            }
            self.right.next();
        }
        //Not found a single match at the right cursor..
        if !found {
            cols_left.push(self.left.pos() as isize);
            cols_right.push(-1);
        }
        found = false;
        self.left.next();
        self.right.first();
    }

    JoinPos {
        left:cols_left,
        right:cols_right,
    }
}

现在，问题是我可以在没有另一遍的情况下找到左边的东西，而不是相反的东西:

Input:
L= [1, 2, 3]
R= [2, 3, 4]

Result. It capture the positions that match. -1 if not found
L | R
======
1   -1
2   1
3   2
-1  3

感谢@philipxy，我有了一个可行的解决方案:

pub fn join(&self, compare:&BoolExpr) -> JoinPos
{
    let total = cmp::max(self.left.len(), self.right.len());

    let mut right_not_founds = HashSet::new();
    let mut cols_left  = Vec::with_capacity(total);
    let mut cols_right = Vec::with_capacity(total);
    let mut found = false;
    let mut first = true;

    while !self.left.eof() {
        let left = self.left.tuple(&self.cols_left);
        while !self.right.eof() {
            let right = self.right.tuple(&self.cols_right);
            if first {
                right_not_founds.insert(self.right.pos());
            }

            if compare(&left, &right) {
                cols_left.push(self.left.pos() as isize);
                cols_right.push(self.right.pos() as isize);
                right_not_founds.remove(&self.right.pos());

                found = true;
            }
            self.right.next();
        }
        if !found {
            cols_left.push(self.left.pos() as isize);
            cols_right.push(-1);
        }
        found = false;
        first = false;
        self.left.next();
        self.right.first();
    }

    for pos in right_not_founds {
        cols_left.push(-1);
        cols_right.push(pos as isize);
    }

    JoinPos {
        left:cols_left,
        right:cols_right,
    }
}

Answer 1

全连接返回内连接元组联合不匹配的由空值扩展的左表元组联合不匹配的由空值扩展的右表元组。

目前您的代码输出左连接元组。外循环的每次迭代都会输出更多位于内连接中的元组，或者输出与任何右表元组都不匹配的左表元组的空扩展。要输出完整连接元组，您还必须输出与任何左表元组不匹配的每个右表元组的空扩展。您可以按如下方式执行此操作: 在循环之前定义一个设置变量。它最终将包含与任何左表元组不匹配的右表元组的所有位置/索引。在 if compare 之前，如果它是外循环的第一次迭代，则将正确的元组位置/索引插入到集合中。在 if compare 的嵌套 block 内，从集合中删除正确的元组位置/索引。