P.Linux Laboratory

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/database/mysql_outer_join_analyse.html

上次讨论了MySQL INNER JOIN算法的效率，怪自己没看仔细官方文档，实际上MySQL对内联查询采用了“下推”的方法，见官方文档。
理论上下推也是可以用到外联接上的，没看懂官方的那段伪代码，根据自己的想法写了一段测试代码，就是昨天代码的改进。

下面是官方给出的采用下推的算法：

FOR each row t1 in T1 such that C1(t1) {
  BOOL f1:=FALSE;
  FOR each row t2 in T2
      such that P1(t1,t2) AND (f1?C2(t2):TRUE) {
    BOOL f2:=FALSE;
    FOR each row t3 in T3
        such that P2(t2,t3) AND (f1&&f2?C3(t3):TRUE) {
      IF (f1&&f2?TRUE:(C2(t2) AND C3(t3))) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f2=TRUE;
      f1=TRUE;
    }
    IF (!f2) {
      IF (f1?TRUE:C2(t2) && P(t1,t2,NULL)) {
        t:=t1||t2||NULL; OUTPUT t;
      }
      f1=TRUE;
    }
  }
  IF (!f1 && P(t1,NULL,NULL)) {
      t:=t1||NULL||NULL; OUTPUT t;
  }
}

下面是我写的测试，包括内联查询和左联查询的测试：

#include 
#include 
#include 
#define MAXN 10000
#define LIMIT 500

using namespace std;

//计时器
class Timer {
public :
	//构造函数
	Timer ();
	//析构函数
	~Timer ();
	//开始计时
	void begin();
	//计时结束
	void end();
	//获取时间
	double get_time();
private :
	clock_t start, finish;
	double time;
};

Timer::Timer () {
	start = 0;
	finish = 0;
}

Timer::~Timer () {
	start = 0;
	finish = 0;
}

void Timer::begin () {
	start = clock();
}

void Timer::end () {
	finish = clock();
}

double Timer::get_time() {
	time = (double)(finish-start)/CLOCKS_PER_SEC;
	return time;
}

int a[MAXN];
int b[MAXN];
int c[MAXN];
int d[MAXN];
int p[4][2];

//初始化测试数据
void init () {
	srand(time(0));
	//参与关键查询的数据
	//cout << "a\tb\tc\td" << endl;
	for(int i=0; ip[0][0] && a[i]p[1][0] && b[j]p[2][0] && c[k]p[0][0] && a[i]p[1][0] && b[j]p[2][0] && c[k]p[0][0] && a[i]p[1][0] && b[j]p[2][0] && c[k]p[0][0] && a[i]p[1][0] && b[j]p[0][0] && a[i]p[0][0] && a[i]p[1][0] && b[j]p[2][0] && c[k]p[0][0] && a[i]p[1][0] && b[j]p[2][0] && c[k] " << count2 << " <> " << count3 << endl;
	}
	
	return ;
}

int main() {
	init();
	innerJoin();
	leftJoin();
	return 0;
}

对于左联查询，我的测试结果是，Test2的方法好于Test1，Test3经常还不如Test1，虽然加入了选择条件判断。
主要原因应该是，C++判断AND条件只要有一个不满足就判定为false，于是if越少判断越快。
欢迎探讨MySQL的算法实现和效率。