What exactly happens when optimizer_prune_level = 1?

Question

This documentation link states that optimizer_prune_level

Controls the heuristics applied during query optimization to prune less-promising partial plans from the optimizer search space.

Can anyone help with the knowledge of what kind of heuristic principles are applied?

Consider this simple schema:

CREATE TABLE `college` (
  `colg_id` int(11) NOT NULL AUTO_INCREMENT,
  `colg_name` varchar(20) DEFAULT NULL,
  `colg_address` varchar(20) DEFAULT NULL,
  `avg_fees` int(11) DEFAULT NULL,
  PRIMARY KEY (`colg_id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8mb4

CREATE TABLE `department` (
  `dept_id` int(11) NOT NULL AUTO_INCREMENT,
  `dept_name` varchar(20) DEFAULT NULL,
  `dept_address` varchar(20) DEFAULT NULL,
  `dept_hod` varchar(20) DEFAULT NULL,
  `colg_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`dept_id`),
  KEY `colg_id_fk` (`colg_id`),
  KEY `dept_name` (`dept_name`),
  CONSTRAINT `department_ibfk_1` FOREIGN KEY (`colg_id`) REFERENCES `college` (`colg_id`)
) ENGINE=InnoDB AUTO_INCREMENT=101 DEFAULT CHARSET=utf8mb4

CREATE TABLE `student` (
  `stud_id` int(11) NOT NULL AUTO_INCREMENT,
  `stud_name` varchar(20) DEFAULT NULL,
  `stud_address` varchar(20) DEFAULT NULL,
  `dept_id` int(11) DEFAULT NULL,
  `year` int(11) DEFAULT NULL,
  PRIMARY KEY (`stud_id`),
  KEY `dept_id_fk` (`dept_id`),
  CONSTRAINT `student_ibfk_1` FOREIGN KEY (`dept_id`) REFERENCES `department` (`dept_id`)
) ENGINE=InnoDB AUTO_INCREMENT=1201 DEFAULT CHARSET=utf8mb4

Relation college contains 10 rows, department 100 rows and student 1100 rows.

For the following query

select * from college c, department d, student s where c.colg_id = d.colg_id and d.dept_id = s.dept_id;

-the optimizer trace is attached: trace.json.

Going off of the trace (with my perception abilities), the optimizer has even tried calculation of cost for joining college with student. A cross product join order plan is also considered amongst others. So is cross product avoidance not part of heuristics? At least for less number of joins? So heuristics change with number of joins? If yes how and any examples?

Answer 1

EAV (Entity Attribute Value) schema may benefit from ..level=1. This is because of messy WHERE clauses that have lots of essentially the same clauses

WHERE a1.e = 123 AND a1.attr = 'color' AND a1.val = 'red'
  AND a2.e = 123 AND a2.attr = 'shape' AND a2.val = 'round'
  AND a3.e = 123 AND a3.attr = 'size'  AND a3.val = 'big'
  AND a4.e = 123 AND a4.attr = 'style' AND a4.val = 'xyz'

Normally, the Optimizer would try a large number of different orders to look at the table. In reality, they are equally efficient, setting the parameter to 1 keeps the Optimizer from wasting effort.

In your example, the WHERE clauses should be in ON clauses since they describe how the tables are related. And your example has no WHERE clause for filtering.

Without filtering, a JOIN of 3 tables with sufficient indexes can be done by starting with any of the tables. For 3 tables, there would be 6 (3 factorial) orderings. For 10 tables, it would be millions. But, again, the Optimizer should not waste its time trying all combos.

If you tack a simple WHERE on for filtering, the Optimizer will quickly gravitate toward that table as being the best to start with, and the "level" won't come into play as much.