How does the optimizer compare different execution plans of the same query? Let's say we have two complex and structurally different execution plans, how can I know if they are providing the same result?

closed as too broad by Kin Shah, Martin Smith, Mikael Eriksson, RolandoMySQLDBA, ypercubeᵀᴹ Mar 11 '14 at 18:58

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    If the optimizer produces 2 different plans for the same query, they better be producing the same results. Otherwise, there is a bug in the optimizer. – ypercubeᵀᴹ Mar 11 '14 at 13:53
  • 1
    You don't specify RDBMS and this question is far too broad anyway. SQL Server has various transformation rules that can be applied to sub trees to produce logically equivalent sub trees. It keeps track of these in the memo structure. See Query Optimizer Deep Dive and Inside the Optimizer: Constructing a Plan for some more details. – Martin Smith Mar 11 '14 at 14:23
  • Thanks @MartinSmith for the links, I wasn't aware of these transformation rules. – maya-bf Mar 11 '14 at 14:29
  • 1
    @ypercube - Except if the query uses non deterministic expressions such as filtering on ROW_NUMBER ordered on a non unique column. – Martin Smith Mar 11 '14 at 14:32
  • @MartinSmith, right, if the query is non-deterministic. – ypercubeᵀᴹ Mar 11 '14 at 14:37

The task of an optimizer is to create several execution plans and compare them (typically by costs). Each execution plan can be seen as logical transformation.

For example: a simple join would always be the cartesian product of two tables. Each row from the first is read and combined with each row in the other table. Than the join condition is checked and the resulting row is used or discarded.

That would be our live without optimizer. The optimizer is using set theory and boolean algebra to transform it. Each transformation leads to the same result. For instance tt doesn't matter if you first sort two sets independent and join them afterwards or first join them and sort them as one.

Other optimizations are the way rows are fetched or compared. There are for example many join algorithms like nested loop join, hash join or sort-merge join. Each algorithm has different advantages and disadvantages. But they operate on the same data. The only (hypothetical) way a execution plan could lead to other results is a difference in rows stored and the index. For that reason the indices have to be always updated as a row is inserted/updated/deleted.

  • If all transformations lead to the same result, what makes the specificity of an execution plan? – maya-bf Mar 11 '14 at 14:54
  • Some execution plans are faster than others. Faster can be for example: less cpu, less io. – Jens W. Mar 11 '14 at 15:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.