Does the logical query processing change when indexes are involved?

Question

I highly recommend this book.

This book explains in a great way the behavior of a sql query, but my doubt is,

1. How is a sql query processed when there are indexes, that is, would this behavior change?

My doubt is because I am a "teacher" and I would like to teach more details to my students.

2. This explains it in SQL Server, but I'm pretty sure it applies the same in MySQL, is that correct?
3. Do we have 2 logical query processings, one with indexes and one without indexes?

I am afraid to explain it and that this will change when there are indexes, so I want to make sure if this does not change when there are indexes involved.

Answer 1

Indexes would indeed affect the physical operations, altering access paths, I/O CPU etc.

However your diagram is logical. Indexes do not change the nature of these operations, only how they might be processed for a given query.

Edit to expand a bit on this based on the other answer:

Assume you have

Select * from people where NAME ='bob';

Logically, we know that we need a subset of the people table in our results.

That can be achieved by scanning the entire table or, with the presence of an index on name, it may choose to use that (based on statistics - presence of an index is no guarantee it will get used for a given query or even the same query with a different value).

Physically we used quite a different set of storage access patterns & CPU in each case.

Logically, we end up with the same result.

Similarly if you have a query with ORDER BY

Select * from people where NAME between 'barney' and 'bob' order by NAME

The order is required so logically, we have to sort the result. Physically, if the index is used, the DB engine "knows" it can expect the results already in order so may not do a sort. On the other hand, if there is enough data to warrant parallel processing, it might need to do a sort at the end or merge the result streams together. The point is, the ordering has been achieved and you don't need to care how*.

*until you get into performance problem solving when the optimiser gets it wrong.

Answer 2

SELECTs have a "standard" processing model that dates back half a century. Different vendors deviate from the standard, mostly in failing to implement all the pieces of the standard and/or implementing extra features. The page you show is for T-SQL.

MySQL's "LIMIT" has similar functionality to the "TOP" in that description but a different implementation.

MySQL does not have Pivot/Unpivot.

An important thing to take away from that page is the order of events as shown on the bottom half of the page. This is dedicated by the standard and required in the syntax. For example, ON, WHERE, and HAVING, though they all do "filtering", come at distinctly different points. WHERE comes before grouping has been done, so you cannot reference aggregates while HAVING comes after, so you can.

INDEXing is not on that page because it is an optimization, not a specification of action. As such, it must not change the end results.

One thing you should teach is that a SELECT delivers an unordered list of rows -- unless there is an explicit ORDER BY clause. I can fabricate an example where the identical query delivers rows in a different order depending on the existence of an INDEX and whether the Optimizer decided to use that index instead of doing a table scan.

When you get into teaching implementation, you must discuss how the table and its indexes are stored. And how INDEXes can be used to speed up a SELECT significantly. Here are 3 examples:

• Brute force ("table scan") -- Read the table (ignore any indexes), check each for filtering (WHERE) and then do the other stuff.
• Use an index do do the filtering first, then worry about the other steps.
• Use an index (assuming it is ordered, such as a BTree) for the GROUP BY and/or ORDER BY. This avoids a sort.

Here are some index differences:

MySQL stores the data in a B+Tree, thereby ordering by the PRIMARY KEY. Others have a variety of options for how to the data is stored.

MySQL has B+Tree, SPATIAL, and FULLTEXT indexes. Others may have Bit, Hash, etc.

MySQL navigates from the Index BTree to the data via a copy of the PK; others may use a "record id".

Example of change

SELECT x FROM t WHERE  x LIKE '*blah*'  ORDER BY date;

How different indexes lead to different execution plans:

• With no indexes, the query will be processed with a table scan, filtering on x as it reads rows, generating a temp table, and sorting that temp table, and finally deliver the the ordered results. (Note that the page says nothing about temp tables.)
• With INDEX(x), the physical processing will filter on x first. Then build a temp and sort it.
• With INDEX(date, x), it is very likely to use the index, which is "covering", to avoid touching the data and to avoid sorting. (Note: The data is in 0ne structure on disk; each index is in another structure.)

Similarly, certain optimizations can simplify GROUP BY based on what index is available.