Use The Index, Luke Blog - Latest News About SQL Performance


Queries Without Table Access

The previous installment demonstrated how to use an index to cluster table rows together. The examples showed that even “anywhere” LIKE expressions can be tuned when the column is put into the index to avoid the table access.

Todays installment extends this concept and shows queries that don’t need to access the table at all. It’s about the so-called index-only scan, or, less descriptive, covering index.

Continuing with Data-Clusters

Today’s installment covers the first two parts from Chapter 5, „Clustering Data. It explains the “cluster” term and demonstrates the impact of clustering data with a simple example.

This will be the basis for the next installment, which explains why adding another where clause may slowdown statement execution. Not just a little bit, but by factors. That is actually the question that has the highest failure rate at the 3 minute test.

One Year and Three Minutes

Use The Index, Luke! was one today.

There was quite some progress during this year. Besides the steadily growing content, I am particularly happy that the appendices about execution plans and the example schema cover MySQL, PostgreSQL and SQL Server in addition to Oracle.

But what’s next?

The content will be completed until early 2012 (final outline in the Preface). The second volume of SQL Performance Explained—the e-book edition—will be published at that time as well. Additionally, Use The Index, Luke! will be translated gradually into German. There is, however, no fixed schedule for that, but you can already subscribe the German blog.

In the German-speaking area, I will also hold my "SQL Performance Basics Workshop for Developers". Individual online workshops are available worldwide in German or English language.

Finally, I have prepared something for the first anniversary of Use The Index, Luke. How good do you know SQL-Performance? I hope you had the feeling of success when you applied your experience from the book to your real-world problems. Did you actually blog or tweet about it? Let me know. However, you can also take the new 3-minute test to see how good you are. Although the test takes just three minutes, it’s not simple. Some of the questions are not yet covered by the book — don’t be surprised if you don’t get the perfect score. Short explanations are given at the end, longer ones will come in the next few month on Use The Index, Luke!

MySQL Row Generator

A row generator is a method to generate numbered rows on demand. It is possible to build a row generator with pure standard SQL—using recursive common table expressions (CTE), the with clause. If you never heard of the with clause, it’s probably because MySQL doesn’t implement that specific part of the SQL-99 standard (feature request from 2006). This article introduces generator views for MySQL. Not as powerful as recursive CTEs, but good enough in most cases. But before going into the implementation details, I’ll show you a use case for a row generator.

Row generators are useful to fill gaps in results. Consider the following query:

SELECT COUNT(*), sale_date
  FROM sales
 WHERE sale_date > CURDATE() - INTERVAL 1 MONTH
 GROUP BY sale_date
 ORDER BY sale_date;

The result will not contain rows for days where no sales record exists at all. You can complete the result with a row generator.

Imagine a view, GENERATOR, that returns numbered rows like this:

SELECT n
  FROM generator
 WHERE n < 31;

+-----+
|  n  |
+-----+
|   0 | 
|   1 | 
. . . .
|  29 | 
|  30 | 
+-----+
31 rows in set (0.00 sec)

This is the basic functionality of a row generator. Having that, it is quite simple to list all days since a month ago:

SELECT CURDATE() - INTERVAL n DAY dt
  FROM generator
 WHERE CURDATE() - INTERVAL n DAY 
     > CURDATE() - INTERVAL 1 MONTH;

+------------+
| dt         |
+------------+
| 2011-07-29 | 
| 2011-07-28 | 
. . . . . . . 
| 2011-07-01 |
| 2011-06-30 | 
+------------+
30 rows in set (0.00 sec)

Finally, we can use an outer join to combine the original result with the generated dates:

SELECT IFNULL(sales, 0) sales, dt sale_date
  FROM
     ( SELECT CURDATE() - INTERVAL n DAY dt
         FROM generator
        WHERE CURDATE() - INTERVAL n DAY 
            > CURDATE() - INTERVAL 1 MONTH
     ) dates
  LEFT OUTER JOIN
     ( SELECT COUNT(*) sales, sale_date
         FROM sales
        WHERE sale_date > CURDATE() - INTERVAL 1 MONTH
        GROUP BY sale_date
     ) sales
    ON (sales.sale_date = dates.dt)
 ORDER BY dt;

The left side of the join has all the generated dates so that the outer join pads the right wide with NULL, if there were no sale on that day. The IFNULL turns the missing sales count into a zero.

About our book “SQL Performance Explained”
Probably the best book on SQL performance I've read
Guillaume Lelarge on Amazon.co.uk (5 stars)

So far, so good. But the problem is that MySQL has no row generator that produces an arbitrary number of rows as needed. Still there is a technique that is good enough in most cases.

It starts with something rather ridiculous:

CREATE OR REPLACE VIEW generator_16
AS SELECT 0 n UNION ALL SELECT 1  UNION ALL SELECT 2  UNION ALL 
   SELECT 3   UNION ALL SELECT 4  UNION ALL SELECT 5  UNION ALL
   SELECT 6   UNION ALL SELECT 7  UNION ALL SELECT 8  UNION ALL
   SELECT 9   UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL
   SELECT 12  UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL 
   SELECT 15;

It is a generator to produces 16 rows. You can use the same technique for larger generators as well. E.g., to produce one million rows, like shown at the end of this article. Just kidding. There is, of course, a better way:

CREATE OR REPLACE VIEW generator_256
AS SELECT ( hi.n * 16 + lo.n ) AS n
     FROM generator_16 lo
        , generator_16 hi;

This view builds the cross join (Cartesian product) of the previous view with itself. That means it pairs every row from the "lo" side with all rows from the "hi" side of the join. The result has 265 rows (16x16).

Considering the introductory example, it is not only important to generate an arbitrary number of rows, we need numbered rows to make use of it. For that purpose, I threat the two sides of the cross join like digits in a hexadecimal number. The "lo" side building the least significant, the "hi" side the most significant digit. Explained by SQL:

SELECT CONCAT(LPAD(hi.n,2,' '), ' * 16 + '
            , LPAD(lo.n,2,' '), ' = '
            , LPAD(hi.n*16+lo.n, 3,' '))
              AS "HI        LO   SEQ"
  FROM generator_16 lo, generator_16 hi;

+--------------------+
| HI        LO   SEQ |
+--------------------+
|  0 * 16 +  0 =   0 | 
|  0 * 16 +  1 =   1 | 
|  0 * 16 +  2 =   2 | 
|  0 * 16 +  3 =   3 | 
|  0 * 16 +  4 =   4 | 
|  0 * 16 +  5 =   5 | 
|  0 * 16 +  6 =   6 | 
|  0 * 16 +  7 =   7 | 
|  0 * 16 +  8 =   8 | 
|  0 * 16 +  9 =   9 | 
|  0 * 16 + 10 =  10 | 
|  0 * 16 + 11 =  11 | 
|  0 * 16 + 12 =  12 | 
|  0 * 16 + 13 =  13 | 
|  0 * 16 + 14 =  14 | 
|  0 * 16 + 15 =  15 | 
|  1 * 16 +  0 =  16 | 
|  1 * 16 +  1 =  17 | 
. . . . . . . . . . .
| 15 * 16 + 14 = 254 | 
| 15 * 16 + 15 = 255 | 
+--------------------+
256 rows in set (0.00 sec)

I guess you know how to build a larger generator now?

There are, of course, some limitations:

  • The views are bounded

    They cannot produce an arbitrary number of rows. But you can prepare views that generate large number of rows (see below).

  • The views will always build the full Cartesian product

    Although you can limit the result with the where clause, the work to produce all rows is still done. It’s just filtering the unneeded. That means, it is very inefficient to use a large generator view if you need just a few rows.

Another aspect is that the result order is undefined—although the example above produces the numbers is ascending order. That’s just because the way MySQL joins the two views. If you build another meta view, e.g., GENERATOR_64K, you’ll note that the order is not ascending anymore—because of MySQLs Block Nested-Loop Join. But that doesn’t mean that the generator doesn’t work, each number is still generated exactly once. If you need a particular order, just use the ORDER BY clause on the outermost select.

Warning

Don’t use LIMIT to cut the view as needed because you might receive unexpected numbering. Please note that using ORDER BY and LIMIT in combination returns the correct result, but requires the intermediate result to be stored temporarily.

Use where to filter on the returned numbers. There is no need to store the intermediate result in that case.

Finally, here are some handy generator views up to 1 "mega-row". They use a minor improvement: bit-shift operations instead of arithmetics.

CREATE OR REPLACE VIEW generator_16
AS SELECT 0 n UNION ALL SELECT 1  UNION ALL SELECT 2  UNION ALL 
   SELECT 3   UNION ALL SELECT 4  UNION ALL SELECT 5  UNION ALL
   SELECT 6   UNION ALL SELECT 7  UNION ALL SELECT 8  UNION ALL
   SELECT 9   UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL
   SELECT 12  UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL 
   SELECT 15;

CREATE OR REPLACE VIEW generator_256
AS SELECT ( ( hi.n << 4 ) | lo.n ) AS n
     FROM generator_16 lo, generator_16 hi;

CREATE OR REPLACE VIEW generator_4k
AS SELECT ( ( hi.n << 8 ) | lo.n ) AS n
     FROM generator_256 lo, generator_16 hi;

CREATE OR REPLACE VIEW generator_64k
AS SELECT ( ( hi.n << 8 ) | lo.n ) AS n
     FROM generator_256 lo, generator_256 hi;

CREATE OR REPLACE VIEW generator_1m
AS SELECT ( ( hi.n << 16 ) | lo.n ) AS n
     FROM generator_64k lo, generator_16 hi;

Even the last view, producing 220 rows, returns the result in a seconds on current hardware. However, the only use I have for the GENERATOR_1M view is producing test data.

Always use the smallest possible generator for best performance.

If you like my way to explain things, you’ll love SQL Performance Explained.

Planning for Re-Use

There was a discussion about bind parameters and execution plan caching in a recent reddit thread about my "Avoid Smart Logic for Conditional WHERE clauses" page. My article mentions that bind variables make the actual values "invisible" for the optimizer resulting in a generic plan that can be cached and re-used later on. Jeff Davis emphasized that using bind parameters and the caching of execution plans are two distinct concepts and provided a PostgreSQL/Ruby example for that.

It took a week, but I can finally present my findings on that topic. The original article is already updated, but I think it is worth presenting it in a different from as well—like a FAQ:

What is an execution plan cache?

An execution plan cache reduces load by caching prepared execution plans. If the same statement is executed later on, the plan can be re-used without the optimization overhead.

Which databases use an execution plan cache?

DB2, Oracle and SQL Server use shared execution plan caches. That means an execution plan used in one session can be re-used by another sessions.

PostgreSQL caches query plans only as long as the prepared statement is open. The query plan is disposed when the prepared statement is closed.

MySQL has no execution plan cache (don’t confuse with Query [Result] Cache).

What has that to do with bind parameters?

The shared execution plan caches of DB2, Oracle and SQL Server use a hash value of the literal SQL string as key to the cache. Cached plans are not found if the SQL contains literal values that vary with each execution.

Place holders (bind parameters) unify the statement so that the SQL string is identical when executed with different values—thus, increasing the cache-hit rate.

Literal values in SQL kind of disable execution plan re-use?

In principle yes. However, there are so many applications that don’t use bind variables that database vendors built a workaround: they can turn literal values to placeholder expressions.

That means that there is a thin layer in the database that looks at every SQL string, checks for literals and transforms them to bind parameters before checking the execution plan cache. These feature is called PARAMETERIZATION in SQL Server. It defaults to simple—only the "simple" statements are automatically transformed to use bind parameters. The corresponding Oracle feature is CURSOR_SHARING. It defaults to EXACT which means that no magic is applied to the SQL strings.

What’s the downside of execution plan re-use?

Execution plan caches use the SQL string as key. Same SQL string, same execution plan. That means that the optimizer must plan for re-use. It cannot assume anything about the bind values used for later executions. The smart logic approach makes that quite obvious. The following cannot optimized "away" when planning for re-use:

 (last_name = :name OR :name IS NULL)

Besides that, the optimizer doesn’t consider column histograms when planning for re-use.

What are the vendors doing about it?

Oracle uses bind peeking and introduced adaptive cursor sharing with 11g. SQL Server uses parameter sniffing and query hints. DB2 has the re-optimizing hint REOPT.

The hint based approaches will essentially disable execution plan re-use for the respective statement. Oracle’s adaptive cursor sharing supports multiple execution plans per SQL string and learns from slow executions.

Can we have both: plan re-use and well optimized queries?

Sure. Disable parametrization magic, use bind parameters and write dynamic SQL for conditional filters.

Explicitly using bind parameters solves three problems at once: (1) SQL injection, (2) execution plan cache-hit rate and (3) having manual control to utilize histograms—the exception for bind parameters. Dynamic SQL will automatically lead to well optimized execution plans for conditional filters.

But concatenating SQL fragments is ugly!?!

Yes, it is—especially when using bind parameters. It is often not possible to provide bind values before the SQL string was passed to the database abstraction layer. That means that all the conditions need to be repeated.

Many ORM tools have a query builder that simplifies dynamic SQL a little. Some examples are available in the appendix.

About our book “SQL Performance Explained”
This book is definitively worth having in the company library.
” — Joe Celko

Should we Build SQL Strings Dynamically in 2011, as Jeff Davis asked?

There is, in theory, no benefit from dynamic SQL if the optimizer doesn’t plan for re-use. But it won’t hurt either—except if code gets ugly. However, the problem is that there is no standard way to put an optimizer into a "disposal mode" that doesn’t plan for re-use. PostgreSQL has a proprietary API solution, SQL Server has a hint that was buggy even in 2008 R2. DB2 has a different hint seems to work since years. Oracle doesn’t give control over "execution plan recycling" (workaround), MySQL never plans for re-use.

However, all of that is irrelevant if you use dynamic SQL for conditional filters. That just works. Always.

If you like my way to explain things, you’ll love SQL Performance Explained.

Sort-Merge Join in SQL Databases

Today's update explains the sort merge join with an animation. The sort-merge join needs the same indexes as the hash join, but has some unique properties when it comes to outer joins.

Dear Database Vendors

I have one wish for each database. Some of them are big wishes, so I thought I'll better send them early. Only six month until Christmas, you know ;)

Oracle

'' IS NULL? Are you serious? I know, it has always been that way, but does that mean it will stay so forever?

SQL Server

Could you please enable READ_COMMITTED_SNAPSHOT per default? Or, at least, make it a mandatory question during database creation? That could prevent so many locking problems.

PostgreSQL

Could you please implement index-only scans (aka "covering indexes")? It's a great performance feature, which I really miss in PostgreSQL.

MySQL

Could you please implement the hash join algorithm? So many applications suffer from poor join performance, just because MySQL doesn't have hash joins.

From today's perspective, it looks like my PostgreSQL wish is the only one that might come true. But I'll keep hoping for the others as well.

Hash Join versus ORM

Today's installment explains the hash join. It has very different performance characteristics as the nested loops join, requires different indexing, and opens a new challenge for Object-Relational mapping (ORM) tools.

Joining with ORM

Today's installment is the first part in the chapter about joining. The installment consists of two parts. First, explaining some general characteristics of joins. Second, explaining the nested loops join algorithm by example, covering the N+1 problem and other aspects of Object-Relational mapping (ORM).

Response Time and Throughput

The last installment demonstrated the effect of system load to response time. Although it's possible to compensate that by distributing the load to more hardware, it doesn't mean that more hardware solves all performance problems. Note that performance has two dimensions: response time and throughput. Adding hardware can easily improve throughput, but response time is hardly tunable with hardware.

Todays installment explains why the "big production hardware" won't solve response time issues, what scaling horizontally can do for you, and why NoSQL systems like CouchDB or MongoDB use B-Tree indexes as well.

About the Author

Photo of Markus Winand
Markus Winand tunes developers for high SQL performance. He also published the book SQL Performance Explained and offers in-house training as well as remote coaching at http://winand.at/