MySQL INNER JOIN算法的效率分析

一 19th, 2010 | Posted by | Filed under 数据库
发表评论 | Trackback

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

MySQL处理JOIN的方法如下：（摘自MySQL 5.1 参考手册中文版）

假定我们有一个如下形式的表T1、T2、T3的联接查询：

SELECT * FROM T1 INNER JOIN T2 ON P1(T1,T2)
INNER JOIN T3 ON P2(T2,T3)
WHERE P(T1,T2,T3).

这里，P1(T1,T2)和P2(T3,T3)是一些联接条件(表达式)，其中P(t1,t2,t3)是表T1、T2、T3的列的一个条件。

嵌套环联接算法将按下面的方式执行该查询：

FOR each row t1 in T1 {
    FOR each row t2 in T2 such that P1(t1,t2) {
        FOR each row t3 in T3 such that P2(t2,t3) {
            IF P(t1,t2,t3) {
                t:=t1||t2||t3; OUTPUT t;
            }
        }
    }
}

符号t1||t2||t3表示“连接行t1、t2和t3的列组成的行”。

其实我觉得，完全可以把P(t1, t2, t3)拆到进入循环前就处理，像这样（后来仔细看了文档，MySQL在内联接的时候还是会优化成这样的）：

FOR each row t1 in T1 {
    IF P(t1) {
        FOR each row t2 in T2 such that P1(t1,t2) {
            IF P(t2) {
                FOR each row t3 in T3 such that P2(t2,t3) {
                    IF P(t3) {
                        t:=t1||t2||t3; OUTPUT t;
                    }
                }
            }
        }
    }
}

甚至更快的是把条件全部合并起来：

FOR each row t1 in T1 {
    IF P(t1) {
        FOR each row t2 in T2 such that (P1(t1,t2) && P(t2)) {
            FOR each row t3 in T3 such that (P2(t2,t3) && P(t3)) {
                t:=t1||t2||t3; OUTPUT t;
            }
        }
    }
}

我写了个程序，把方法一（MySQL的方法）和方法三的效率进行比较，明显方法三要高。

#include <iostream>
#include <cstdlib>
#include <time.h>
#define MAXN 100000
 
using namespace std;
 
int a[MAXN];
int b[MAXN];
int c[MAXN];
int count = 0;
 
int main() {
	clock_t start, finish;
	double time1, time2;
 
	count = 0;
	srand(time(0));
 
	for(int i=0; i<MAXN; ++i) {
		a[i] = i;
		b[i] = MAXN-i;
		c[i] = rand()%MAXN;
	}
 
	start=clock();
	for(int i=0; i<MAXN; ++i) {
		for(int j=10; j<MAXN; ++j) {
			if (a[i]==b[j]) {
				for(int k=0; k<MAXN; ++k) {
					if(b[j]==c[k]) {
						if (a[i]>500 and b[j] < 800 and c[k]>120) {
							cout << ++count << ':' <<a[i] << ',' << b[j] << ',' << c[k] << endl;
						}
					}
				}
			}
		}
	}
	finish = clock();
	time1 = (double)(finish-start)/CLOCKS_PER_SEC;
 
	count = 0;
	start=clock();
	for(int i=0; i<MAXN; ++i) {
		if (a[i]>500) {
			for(int j=10; j<MAXN; ++j) {
				if (a[i]==b[j] and b[j] < 800) {
					for(int k=0; k<MAXN; ++k) {
						if(b[j]==c[k] and c[k]>120) {
							cout << ++count << ':' <<a[i] << ',' << b[j] << ',' << c[k] << endl;
						}
					}
				}
			}
		}
	}
	finish = clock();
	time2 = (double)(finish-start)/CLOCKS_PER_SEC;
 
	cout << time1 << "VS" << time2 << endl;
	return 0;
}

我跑的结果是，一共输出292条记录，21.82s VS 8.35s。
可见先做条件判断是很能提高效率的。
如有不正确，请不惜指教~

标签: , ,
  1. toontong
    九 16th, 201022:52
    回复 | 引用 | #1

    可以采用这种子查询过滤T1中合条件P1的数据，再进行join
    select * (SELECT * FROM T1 where p1(T1)) tmpT1 INNER JOIN T2 ON P1(tmpT1,T2)
    mysql连接有个优化原则，小表连大表。

    不知理解有错否！

    [回复]

    P.Linux 回复:
    九月 17th, 2010 at 10:48

    @toontong, 这种情况下，MySQL会选择对T1作条件选择，然后选择过滤后较小的那个表作为驱动表去关联另一个表

    [回复]

  2. NaturalLight
    十二 27th, 201000:03
    回复 | 引用 | #2

    你上面列出的情况应该是loop join的算法
    我记得当 join条件中有 equal condition的时候，会使用merge join或者hash join的算法，在这种情况下，join的效率会有数量级的提升

    [回复]

    P.Linux 回复:
    十二月 27th, 2010 at 09:23

    MySQL只有一种Join算法，Nested Loop Join。Hash Join是Oracle才有的

    [回复]

​