MIT6.5830 Lab 2: GoDB Operators实验记录（二）

2023年11月6日

文章访问量：

标签：Golang

Lab2实验记录：Join

Filter（其实就是where）完成后，接下来接着完成Join。

实验步骤
完成join

在Mysql中，如果我们只使用join而不用on，那么会出现笛卡儿积。但这里没提到这点，所以我们暂时不管。

老样子，先补全desc。EqualityJoin里面能拿到desc的就两个*Operator。那直接写上即可。

func (hj *EqualityJoin[T]) Descriptor() *TupleDesc {
	// TODO: some code goes here
	desc := ((*hj.left).Descriptor()).merge((*hj.right).Descriptor())
	return desc
}

接下来补全迭代器。有一说一，很难。

实验思路
什么是Join

在此补全Iterator之前，我们得先想想什么是Join。

写者注
2023/11/8：停更一两周，先把期中考试和下学期的实习搞定了先。

写者注
打算找个时间先巩固一下前面写的内容，再恶补一下数据库底层原理再回来写。不然面试问到细节老是忘。

我回来了（2024/8/23）
有始有终

Man, what can I say?

毕竟很久没写，有些概念都和变量都忘了。写的时候顺带复习下之前的知识。

Join
完成Exercise 1

相信写过多表连结SQL题的都比较熟悉Join的用法。比如A JOIN B，每从A取出一行数据，都需要遍历一次B中所有元组并进行拼接。

这里也是一样，比如我们可以先从测试样例入手，看看输入输出是什么。由于排版问题，这里肯定展示不了所有的变量，可以自己打个断点看看。

简单来说，给了两个数据相同的表hf和hf2。还给了两个元组outT1，outT2。

name	age
sam	25
george jones	999
george jones	999

我在写join的时候，一直想着on是不是要分开实现，但发现不用。比如outT1调用的joinTuples是我们在lab1中补全的代码（如下），作用是合并两个元组。当时我还没发现什么，现在才发现这一步已经自带了ON的操作，因为可以看到合并之后描述符字段是不变的。相当于JOIN之后并不会多几列出来。

// Merge two tuples together, producing a new tuple with the fields of t2 appended to t1.
func joinTuples(t1 *Tuple, t2 *Tuple) *Tuple {
	// TODO: some code goes here
	if t1 == nil && t2 == nil {
		return nil
	} else if t1 == nil {
		return t2
	} else if t2 == nil {
		return t1
	}
	newfield := append(t1.Fields, t2.Fields...)
	return &Tuple{Desc: t1.Desc, Fields: newfield}
}

仔细观察测试样例这段代码，我们可以判断出执行的操作应该是 hf JOIN hf2。其中还用到了int类型的字段age。转换成SQL语句那就是

hf JOIN hf2 ON hf.age = hf2.age

最后的检验可以看到，join之后的表有五组数据，其中sam出现一次，george出现四次，也符合上面SQL的结果。

  leftField := FieldExpr{td.Fields[1]}
	join, err := NewIntJoin(hf, &leftField, hf2, &leftField, 100)
	if err != nil {
		t.Errorf("unexpected error initializing join")
		return
	}
	iter, err := join.Iterator(tid)
	if err != nil {
		t.Fatalf(err.Error())
	}
	if iter == nil {
		t.Fatalf("iter was nil")
	}
	cnt := 0
	cntOut1 := 0
	cntOut2 := 0
	for {
		t, _ := iter()
		if t == nil {
			break
		}
		if t.equals(outT1) {
			cntOut1++
		} else if t.equals(outT2) {
			cntOut2++
		}
		//fmt.Printf("got tuple %v: %v\n", cnt, t)
		cnt++
	}
	if cnt != 5 {
		t.Errorf("unexpected number of join results (%d, expected 5)", cnt)
	}
	if cntOut1 != 1 {
		t.Errorf("unexpected number of t1 results (%d, expected 1)", cntOut1)
	}
	if cntOut2 != 4 {
		t.Errorf("unexpected number of t2 results (%d, expected 4)", cntOut2)
	}

知道不用实现ON，那接下来就是补全迭代器了。需要注意的是ON左右两边可能为表达式，不能直接根据左右字段的Fields.EvalExpr去进行比较。这点在markdown里面已有注明。

有了思路，写就完事了。每从左迭代器取出一个元组，就重新初始化右迭代器再循环取出元组，并比较左右元组的字段是否相等。

func (joinOp *EqualityJoin[T]) Iterator(tid TransactionID) (func() (*Tuple, error), error) {

	// TODO: some code goes here
	leftIter, err := (*joinOp.left).Iterator(tid)
	if err != nil {
		return nil, err
	}
	rightIter, err := (*joinOp.right).Iterator(tid)
	if err != nil {
		return nil, err
	}
	var leftTuple, rightTuple *Tuple
	return func() (*Tuple, error) {
		for {
			if leftTuple == nil {
				leftTuple, err = leftIter()
				if err != nil {
					return nil, err
				}
				if leftTuple == nil {
					return nil, nil
				}
				rightIter, err = (*joinOp.right).Iterator(tid)
				if err != nil {
					return nil, err
				}
			}
			for {
				rightTuple, err = rightIter()
				if err != nil {
					return nil, err
				}
				if rightTuple == nil {
					leftTuple = nil
					break
				}
				v, _ := joinOp.leftField.EvalExpr(leftTuple)
				leftDesc := joinOp.getter(v)
				v, _ = joinOp.rightField.EvalExpr(rightTuple)
				rightDesc := joinOp.getter(v)
				if leftDesc == rightDesc {
					return joinTuples(leftTuple, rightTuple), nil
				}
			}
		}
	}, nil
}

跑一下，过。不过我没做optional exercise。我直接跑了下发现会超时10s+。提示说不用嵌套循环才能过TestBigJoinOptional。我记得join还有分为hash join和merge join，有兴趣的可以自行了解。

Lab2看了下，一共有7个exercise。顿时感觉前路艰辛啊。