Возможно за один проход создать FULL JOIN для структуры в памяти (без использования sql!) - PullRequest
Новая
       41

Возможно за один проход создать FULL JOIN для структуры в памяти (без использования sql!)

0 голосов
/ 09 сентября 2018

Я создаю колоночный реляционный движок в памяти. Для извлечения значений я хочу провести позднюю материализацию, где я собираю позиции / индексы, где было найдено совпадение, и в конце собираю значения.

Теперь, реализуя объединения, я не вижу, как работает общий алгоритм объединения, который охватывает все остальные случаи. Левый, Правый и Внутренний легко, но 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,
    }
}

1 Ответ

0 голосов
/ 09 сентября 2018

Полное объединение возвращает внутреннее объединение кортежей объединение несопоставленных кортежей левой таблицы, расширенных нулями Объединение несопоставленных правых кортежей таблиц, расширенных нулями.

В настоящее время ваш код выводит левые кортежи. Каждая итерация внешнего цикла выводит больше кортежей, которые находятся во внутреннем соединении, либо выводит нулевое расширение кортежа левой таблицы, который не соответствует ни одному кортежу правой таблицы. Для вывода полных объединений вы должны также вывести нулевое расширение каждого правого табличного кортежа, который не соответствует ни одному левому табличному кортежу. Вы можете сделать это следующим образом: Определить переменную набора перед циклами. В конечном итоге он будет содержать все позиции / индексы для правых кортежей таблиц, которые не соответствуют ни одному левому кортежу. Непосредственно перед if compare, если это первая итерация внешнего цикла, вставьте правильную позицию / индекс кортежа в набор. Внутри вложенного блока if compare удалите правую позицию / индекс кортежа из набора.

...