You are right that for Nested Loop Join, the choice of which table is the inner and which the outer table matters for perforamnce.
However, there is nothing in the documentation, in the link you provided, that implies that for a query that has a INNER JOIN b
, the table a
will be used as inner and b
as outer table when the Nested Loop Join algorithm is selected.
Any decent optimizer evaluates many different combinations of algorithms, placing of tables and order of execution, so I don't think there is any difference if you write a INNER JOIN b
or b INNER JOIN a
, the chosen execution plans should be the same in both cases. If there are exceptions to this, I would expect them to be for very complex queries with tens of joined tables and/or multiple groupings.
Testing and checking the actual execution plans is one way to confirm this. Another would be to analyze the source code of the query optimizer.
The general guidance when writing SQL (in whatever DBMS), is not to care at all about the table join orders. SQL code describes what you want as result, it doesn't tell the DBMS how to get it. And many optimizers now are really smarter and faster than most of us in choosing the best execution plan most of the time.
Unless documentation shows that the optimizer is naive or in a very early version and the way the queries are written, really affects the chosen execution plan.
Or testing/running of a specific query shows that it's slow and some obviously good plan was not chosen. Then you can experiment with hints (if the DBMS has such feature), try rewriting the query in different ways, check if statistics are updated, etc.
Although MySQL has no CTE functionality, there are two major ways to create CTE expressions:
TECHNIQUE #1 : Write Stored Procedures to Traverse Recursively
Rather than Reinventing the Wheel, please see my past posts on how to make stored procedures
TECHNIQUE #2 : Iterate Based on the Tree's Maximum Depth
First, here is some sample data
DROP DATABASE IF EXISTS dufran;
CREATE DATABASE dufran;
USE dufran;
CREATE TABLE reference
(
user INT NOT NULL AUTO_INCREMENT,
referee INT NOT NULL DEFAULT 0,
name VARCHAR(20) NOT NULL,
PRIMARY KEY (user)
);
INSERT INTO reference (name,referee) VALUES ('Rolando',0);
INSERT INTO reference (name,referee) VALUES ('Pamela',1);
INSERT INTO reference (name,referee) VALUES ('Carlik',2);
INSERT INTO reference (name,referee) VALUES ('Javonne',2);
INSERT INTO reference (name,referee) VALUES ('Dominique',2);
INSERT INTO reference (name,referee) VALUES ('Diamond',2);
INSERT INTO reference (name,referee) VALUES ('Azalia',3);
When loaded, this is the data
mysql> SELECT * FROM reference;
+------+---------+-----------+
| user | referee | name |
+------+---------+-----------+
| 1 | 0 | Rolando |
| 2 | 1 | Pamela |
| 3 | 2 | Carlik |
| 4 | 2 | Javonne |
| 5 | 2 | Dominique |
| 6 | 2 | Diamond |
| 7 | 3 | Azalia |
+------+---------+-----------+
7 rows in set (0.00 sec)
mysql>
Here is how you compute the maximum depth
SET @depth = 0;
SELECT MAX(@depth:=@depth+1) max_depth FROM
(SELECT DISTINCT referee FROM reference) A;
Here is the maximum depth for the sample data
mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT MAX(@depth:=@depth+1) max_depth FROM
-> (SELECT DISTINCT referee FROM reference) A;
+-----------+
| max_depth |
+-----------+
| 4 |
+-----------+
1 row in set (0.00 sec)
mysql>
Using this principle, iterate for the SELECT
columns and the LEFT JOIN
clauses
SET @depth = 0;
SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
INTO @sqllist FROM
(SELECT @depth:=@depth+1 dep FROM
(SELECT DISTINCT referee FROM reference) AA) A;
SET @depth1 = 0;
SET @depth2 = 1;
SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
FROM (SELECT DISTINCT referee FROM reference) AA) A;
SELECT @sqljoins;
SET @sqlstmt = CONCAT('SELECT ',@sqllist,
' FROM reference t1 ',@sqljoins);
SELECT @sqllist\G
SELECT @sqljoins\G
SELECT @sqlstmt\G
Here is the SQL generated
mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
-> INTO @sqllist FROM
-> (SELECT @depth:=@depth+1 dep FROM
-> (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)
mysql> SET @depth1 = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SET @depth2 = 1;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
-> FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
-> ' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
-> FROM (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)
mysql> SELECT @sqllist\G
*************************** 1. row ***************************
@sqllist: t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4
1 row in set (0.00 sec)
mysql> SELECT @sqljoins\G
*************************** 1. row ***************************
@sqljoins: LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)
mysql> SELECT @sqlstmt\G
*************************** 1. row ***************************
@sqlstmt: SELECT t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4 FROM reference t1 LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user
1 row in set (0.00 sec)
mysql>
Here is the big question, does the SQL work ??? Take the SQL and run it dynamically:
PREPARE s FROM @sqlstmt;
EXECUTE s;
DEALLOCATE PREPARE s;
Here is the result:
mysql> PREPARE s FROM @sqlstmt;
Query OK, 0 rows affected (0.00 sec)
Statement prepared
mysql> EXECUTE s;
+------+------+------+------+
| lvl1 | lvl2 | lvl3 | lvl4 |
+------+------+------+------+
| 1 | 2 | 3 | 7 |
| 1 | 2 | 4 | NULL |
| 1 | 2 | 5 | NULL |
| 1 | 2 | 6 | NULL |
| 2 | 3 | 7 | NULL |
| 2 | 4 | NULL | NULL |
| 2 | 5 | NULL | NULL |
| 2 | 6 | NULL | NULL |
| 3 | 7 | NULL | NULL |
| 4 | NULL | NULL | NULL |
| 5 | NULL | NULL | NULL |
| 6 | NULL | NULL | NULL |
| 7 | NULL | NULL | NULL |
+------+------+------+------+
13 rows in set (0.03 sec)
mysql> DEALLOCATE PREPARE s;
Query OK, 0 rows affected (0.00 sec)
mysql>
I scripted this to give you a starting point and some homework. Here is what I mean: You probably don't want to see NULL columns. You could do one of two things:
- Convert each
NULL
to IFNULL(lvl1,'')
, GROUP_CONCAT all columns.
- Compute the depth of a particular id and gather columns for it only.
Give it a Try !!!
UPDATE 2016-06-14 16:36 EDT
Someone just commented
Your max depth calculation is wrong. Proof: Add to your sample data: INSERT INTO reference (name,referee) VALUES ('Maria',4);
Let's try it out
mysql> INSERT INTO reference (name,referee) VALUES ('Maria',4);
Query OK, 1 row affected (0.00 sec)
mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT MAX(@depth:=@depth+1) max_depth FROM
-> (SELECT DISTINCT referee FROM reference) A;
+-----------+
| max_depth |
+-----------+
| 5 |
+-----------+
1 row in set (0.00 sec)
OK, it says the depth is 5. Is there visible proof of this ?
mysql> SET @depth = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT GROUP_CONCAT(CONCAT('t',dep,'.user AS lvl',dep))
-> INTO @sqllist FROM
-> (SELECT @depth:=@depth+1 dep FROM
-> (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)
mysql> SET @depth1 = 0;
Query OK, 0 rows affected (0.00 sec)
mysql> SET @depth2 = 1;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT GROUP_CONCAT(sqljoin SEPARATOR ' ') INTO @sqljoins
-> FROM (SELECT CONCAT('LEFT JOIN reference t',@depth2:=@depth2+1,
-> ' ON t',@depth2,'.referee = t',@depth1:=@depth1+1,'.user') sqljoin
-> FROM (SELECT DISTINCT referee FROM reference) AA) A;
Query OK, 1 row affected (0.00 sec)
mysql> SELECT @sqljoins;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @sqljoins |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
mysql> SET @sqlstmt = CONCAT('SELECT ',@sqllist,
-> ' FROM reference t1 ',@sqljoins);
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT @sqllist\G
*************************** 1. row ***************************
@sqllist: t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4,t5.user AS lvl5
1 row in set (0.00 sec)
mysql> SELECT @sqljoins\G
*************************** 1. row ***************************
@sqljoins: LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user
1 row in set (0.00 sec)
mysql> SELECT @sqlstmt\G
*************************** 1. row ***************************
@sqlstmt: SELECT t1.user AS lvl1,t2.user AS lvl2,t3.user AS lvl3,t4.user AS lvl4,t5.user AS lvl5 FROM reference t1 LEFT JOIN reference t2 ON t2.referee = t1.user LEFT JOIN reference t3 ON t3.referee = t2.user LEFT JOIN reference t4 ON t4.referee = t3.user LEFT JOIN reference t5 ON t5.referee = t4.user LEFT JOIN reference t6 ON t6.referee = t5.user
1 row in set (0.00 sec)
mysql> PREPARE s FROM @sqlstmt;
Query OK, 0 rows affected (0.00 sec)
Statement prepared
Guess what the output says ?
mysql> EXECUTE s;
+------+------+------+------+------+
| lvl1 | lvl2 | lvl3 | lvl4 | lvl5 |
+------+------+------+------+------+
| 1 | 2 | 3 | 7 | NULL |
| 1 | 2 | 4 | 8 | NULL |
| 1 | 2 | 5 | NULL | NULL |
| 1 | 2 | 6 | NULL | NULL |
| 2 | 3 | 7 | NULL | NULL |
| 2 | 4 | 8 | NULL | NULL |
| 2 | 5 | NULL | NULL | NULL |
| 2 | 6 | NULL | NULL | NULL |
| 3 | 7 | NULL | NULL | NULL |
| 4 | 8 | NULL | NULL | NULL |
| 5 | NULL | NULL | NULL | NULL |
| 6 | NULL | NULL | NULL | NULL |
| 7 | NULL | NULL | NULL | NULL |
| 8 | NULL | NULL | NULL | NULL |
+------+------+------+------+------+
14 rows in set (0.00 sec)
mysql> DEALLOCATE PREPARE s;
Query OK, 0 rows affected (0.00 sec)
mysql>
Just as my code predicted. The depth is 5 and the Dynamic SQL just proved it.
Best Answer
There are a couple issues I'll have to gloss over at this point due to lack of info:
invoices.status
valuesstatus='approved'
and one withstatus='closed'
Instead of trying to find all orders with invoices that are a) 'approved' and 'closed', or b) 'approved' or 'closed' ... just look for orders that have no invoices with a status other than 'approved' or 'closed':