程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> MYSQL數據庫 >> MySQL綜合教程 >> 探究MySQL優化器對索引和JOIN順序的選擇,mysqljoin

探究MySQL優化器對索引和JOIN順序的選擇,mysqljoin

編輯:MySQL綜合教程

探究MySQL優化器對索引和JOIN順序的選擇,mysqljoin


本文通過一個案例來看看MySQL優化器如何選擇索引和JOIN順序。表結構和數據准備參考本文最後部分"測試環境"。這裡主要介紹MySQL優化器的主要執行流程,而不是介紹一個優化器的各個組件(這是另一個話題)。

   我們知道,MySQL優化器只有兩個自由度:順序選擇;單表訪問方式;這裡將詳細剖析下面的SQL,看看MySQL優化器如何做出每一步的選擇。

explain
select *
from
 employee as A,department as B
where
   A.LastName = 'zhou'
 and B.DepartmentID = A.DepartmentID
 and B.DepartmentName = 'TBX';

1. 可能的選擇

   這裡看到JOIN的順序可以是A|B或者B|A,單表訪問方式也有多種,對於A表可以選擇:全表掃描和索引`IND_L_D`(A.LastName = 'zhou')或者`IND_DID`(B.DepartmentID = A.DepartmentID)。對於B也有三個選擇:全表掃描、索引IND_D、IND_DN。
2. MySQL優化器如何做
2.1 概述

   MySQL優化器主要工作包括以下幾部分:Query Rewrite(包括Outer Join轉換等)、const table detection、range analysis、JOIN optimization(順序和訪問方式選擇)、plan refinement。這個案例從range analysis開始。
2.2 range analysis

   這部分包括所有Range和index merge成本評估(參考1 參考2)。這裡,等值表達式也是一個range,所以這裡會評估其成本,計算出found records(表示對應的等值表達式,大概會選擇出多少條記錄)。

   本案例中,range analysis會針對A表的條件A.LastName = 'zhou'和B表的B.DepartmentName = 'TBX'分別做分析。其中:

表A A.LastName = 'zhou' found records: 51
表B B.DepartmentName = 'TBX' found records: 1

   這兩個條件都不是range,但是這裡計算的值仍然會存儲,在後面的ref訪問方式評估的時候使用。這裡的值是根據records_in_range接口返回,而對於InnoDB每次調用這個函數都會進行一次索引頁的采樣,這是一個很消耗性能的操作,對於很多其他的關系數據庫是使用"直方圖"的統計數據來避免這次操作(相信MariaDB後續版本也將實現直方圖統計信息)。
2.3 順序和訪問方式的選擇:窮舉

   MySQL通過枚舉所有的left-deep樹(也可以說所有的left-deep樹就是整個MySQL優化器的搜索空間),來找到最優的執行順序和訪問方式。
2.3.1 排序

   優化器先根據found records對所有表進行一個排序,記錄少的放前面。所以,這裡順序是B、A。
2.3.2 greedy search

   當表的數量較少(少於search_depth,默認是63)的時候,這裡直接蛻化為一個窮舉搜索,優化器將窮舉所有的left-deep樹找到最優的執行計劃。另外,優化器為了減少因為搜索空間龐大帶來巨大的窮舉消耗,所以使用了一個"偷懶"的參數prune_level(默認打開),具體如何"偷懶",可以參考JOIN順序選擇的復雜度。不過至少需要有三個表以上的關聯才會有"偷懶",所以本案例不適用。
2.3.3 窮舉

   JOIN的第一個表可以是:A或者B;如果第一個表選擇了A,第二個表可以選擇B;如果第一個表選擇了B,第二個表可以選擇A;

   因為前面的排序,B表的found records更少,所以JOIN順序窮舉時的第一個表先選擇B(這個是有講究的)。

(*) 選擇第一個JOIN的表為B
  (**) 確定B表的訪問方式
    因為B表為第一個表,所以無法使用索引IND_D(B.DepartmentID = A.DepartmentID),而只能使用IND_DN(B.DepartmentName = 'TBX')
      使用IND_DN索引的成本計算:1.2;其中IO成本為1。
      是否使用全表掃描:這裡會比較使用索引的IO成本和全表掃描的IO成本,前者為1,後者為2;所以忽略全表掃描
    所以,B表的訪問方式ref,使用索引IND_D

  (**) 從剩余的表中窮舉選出第二個JOIN的表,這裡剩余的表為:A
  (**) 將A表加入JOIN,並確定其訪問方式
    可以使用的索引為:`IND_L_D`(A.LastName = 'zhou')或者`IND_DID`(B.DepartmentID = A.DepartmentID)
    依次計算使用索引IND_L_D、IND_DID的成本:
    (***) IND_L_D A.LastName = 'zhou'
          在range analysis階段給出了A.LastName = 'zhou'對應的記錄約為:51。
          所以,計算IO成本為:51;ref做IO成本計算時會做一次修正,將其修正為worst_seek(參考)
          修正後IO成本為:15,總成本為:25.2
    (***) IND_DID B.DepartmentID = A.DepartmentID
          這是一個需要知道前面表的結果,才能計算的成本。所以range analysis是無法分析的
          這裡,我們看到前面表為B,found_record是1,所以A.DepartmentID只需要對應一條記錄就可以了
          因為具體取值不知道,也沒有直方圖,所以只能簡單依據索引統計信息來計算:
            索引IND_DID的列A.DepartmentID的Cardinality為1349,全表記錄數為1349
            所以,每一個值對應一條記錄,而前面表B只有一條記錄,所以這裡的found_record計算為1*1 = 1
            所以IO成本為:1,總成本為1.2
    (***) IND_L_D成本為25.2;IND_DID成本為1.2,所以選擇後者為當前表的訪問方式
  (**) 確定A使用索引IND_DID,訪問方式為ref
  (**) JOIN順序B|A,總成本為:1.2+1.2 = 2.4

(*) 選擇第一個JOIN的表為A
  (**) 確定A表的訪問方式
       因為A表是第一個表,所以無法使用索引`IND_DID`(B.DepartmentID = A.DepartmentID)
       那麼只能使用索引`IND_L_D`(A.LastName = 'zhou')
         使用IND_L_D索引的成本計算,總成本為25.2;參考前面計算;
  (**) 這裡訪問A表的成本已經是25.2,比之前的最優成本2.4要大,忽略該順序
       所以,這次窮舉搜索到此結束

   把上面的過程簡化如下:

(*) 選擇第一個JOIN的表為B
  (**) 確定B表的訪問方式
  (**) 從剩余的表中窮舉選出第二個JOIN的表,這裡剩余的表為:A
  (**) 將A表加入JOIN,並確定其訪問方式
    (***) IND_L_D A.LastName = 'zhou'
    (***) IND_DID B.DepartmentID = A.DepartmentID
    (***) IND_L_D成本為25.2;IND_DID成本為1.2,所以選擇後者為當前表的訪問方式
  (**) 確定A使用索引IND_DID,訪問方式為ref
  (**) JOIN順序B|A,總成本為:1.2+1.2 = 2.4

(*) 選擇第一個JOIN的表為A
  (**) 確定A表的訪問方式
  (**) 這裡訪問A表的成本已經是25.2,比之前的最優成本2.4要大,忽略該順序

   至此,MySQL優化器就確定了所有表的最佳JOIN順序和訪問方式。
3. 測試環境

MySQL: 5.1.48-debug-log innodb plugin 1.0.9

CREATE TABLE `department` (
 `DepartmentID` int(11) DEFAULT NULL,
 `DepartmentName` varchar(20) DEFAULT NULL,
 KEY `IND_D` (`DepartmentID`),
 KEY `IND_DN` (`DepartmentName`)
) ENGINE=InnoDB DEFAULT CHARSET=gbk;

CREATE TABLE `employee` (
 `LastName` varchar(20) DEFAULT NULL,
 `DepartmentID` int(11) DEFAULT NULL,
 KEY `IND_L_D` (`LastName`),
 KEY `IND_DID` (`DepartmentID`)
) ENGINE=InnoDB DEFAULT CHARSET=gbk;

for i in `seq 1 1000` ; do mysql -vvv -uroot test -e 'insert into department values (600000*rand(),repeat(char(65+rand()*58),rand()*20))'; done
for i in `seq 1 1000` ; do mysql -vvv -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),600000*rand())'; done

for i in `seq 1 50` ; do mysql -vvv -uroot test -e 'insert into employee values ("zhou",27760)'; done
for i in `seq 1 200` ; do mysql -vvv -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),27760)'; done
for i in `seq 1 1` ; do mysql -vvv -uroot test -e 'insert into department values (27760,"TBX")'; done

show index from employee;
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| Table  | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| employee |     1 | IND_L_D |      1 | LastName   | A     |    1349 |   NULL | NULL  | YES | BTREE   |     |
| employee |     1 | IND_DID |      1 | DepartmentID | A     |    1349 |   NULL | NULL  | YES | BTREE   |     |
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+

show index from department;
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| department |     1 | IND_D  |      1 | DepartmentID  | A     |    1001 |   NULL | NULL  | YES | BTREE   |     |
| department |     1 | IND_DN  |      1 | DepartmentName | A     |    1001 |   NULL | NULL  | YES | BTREE   |     |
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+

4. 構造一個Bad case

   因為關聯條件中MySQL使用索引統計信息做成本預估,所以數據分布不均勻的時候,就容易做出錯誤的判斷。簡單的我們構造下面的案例:

   表和索引結構不變,按照下面的方式構造數據:

for i in `seq 1 10000` ; do mysql -uroot test -e 'insert into department values (600000*rand(),repeat(char(65+rand()*58),rand()*20))'; done
for i in `seq 1 10000` ; do mysql -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),600000*rand())'; done

for i in `seq 1 1` ; do mysql -uroot test -e 'insert into employee values ("zhou",27760)'; done
for i in `seq 1 10` ; do mysql -uroot test -e 'insert into department values (27760,"TBX")'; done
for i in `seq 1 1000` ; do mysql -uroot test -e 'insert into department values (27760,repeat(char(65+rand()*58),rand()*20))';
done

explain
select *
from
 employee as A,department as B
where
   A.LastName = 'zhou'
 and B.DepartmentID = A.DepartmentID
 and B.DepartmentName = 'TBX';
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys  | key   | key_len | ref         | rows | Extra    |
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
| 1 | SIMPLE   | A   | ref | IND_L_D,IND_DID | IND_L_D | 43   | const        |  1 | Using where |
| 1 | SIMPLE   | B   | ref | IND_D,IND_DN  | IND_D  | 5    | test.A.DepartmentID |  1 | Using where |
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+

   可以看到這裡,MySQL執行計劃對表department使用了索引IND_D,那麼A表命中一條記錄為(zhou,27760);根據B.DepartmentID=27760將返回1010條記錄,然後根據條件DepartmentName = 'TBX'進行過濾。

   這裡可以看到如果B表選擇索引IND_DN,效果要更好,因為DepartmentName = 'TBX'僅僅返回10條記錄,再根據條件A.DepartmentID=B.DepartmentID過濾之。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved