EXPLAIN EXTENDED

Answering questions asked on the site.

Denis Kuzmenok asks:

I need some help with a query I'm fighting with.

I have these tables:

Product

id	parent	name

Site

id	region	name

Price

id	product	site	value

For the products with a certain product.parent, I need to select minimal and maximal price within the given site.region, and return first 10 products ordered by the minimal price.

Each parent has 100 to 10,000 products, and there are 10,000,000 records in price table.

We have a classical OLAP task here: a fact table (price) and two dimension tables (product and site).

The task would be almost trivial if we were given the exact values of product and site. This way, we could build a composite index on these fields and value, filter on the exact values and get the first 10 values from the index.

However, we are given not the values of the dimensions themselves but those of the higher levels (parent for product and region for site).

Since the values of the levels are not stored in the facts table, we cannot index them. We need to join the dimension tables and filter on them.

This article describes four ways to join the tables, their efficiency varying depending on the density of the dimension values.

Since the only algorithm to make the joins MySQL is capable of is nested loops, basically, we need to define the order in which the tables would be joined.

There are three tables and, hence, 3! = 6 permutations that define all possible join orders:

However, two dimension tables are completely independent on each other. This means that if they come one after another in the join their order does not actually matter: they both will be searched for independent values. This reduces the number of actual combinations:

The joins must be designed so that the tables with most selective conditions go first. This means that the join order is determined by the density of the values satisfying the criteria. The more values from the table satisfy the search criteria, the later should the table come in the join, so that by the time the join occurs, most values would have been already sifted out.

Now, let's build the queries for all types of the join. To do this, we will create sample tables:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE product (
id INT NOT NULL PRIMARY KEY,
parent INT NOT NULL,
name TEXT NOT NULL
) ENGINE=InnoDB;

CREATE TABLE price (
id INT NOT NULL PRIMARY KEY,
product INT NOT NULL,
site INT NOT NULL,
value FLOAT NOT NULL
) ENGINE=InnoDB;

CREATE TABLE site (
id INT NOT NULL PRIMARY KEY,
region INT NOT NULL,
name TEXT NOT NULL
) ENGINE=InnoDB;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(250000);
COMMIT;

INSERT
INTO    product
SELECT  id, -FLOOR(LOG10(POWER(10, -10) + RAND(20100930) * (1 - POWER(10, -10))) * 500 / 10), CONCAT('Product ', id)
FROM    filler
ORDER BY
        id
LIMIT 250000;

INSERT
INTO    site
SELECT  id, -FLOOR(LOG10(POWER(10, -10) + RAND(20100930) * (1 - POWER(10, -10))) * 100 / 10), CONCAT('Site ', id)
FROM    filler
LIMIT 50000;

SET @r := 0;
INSERT
INTO    price
SELECT  @r := @r + 1,
        FLOOR(RAND(20100930 << 2) * 250000) + 1,
        FLOOR(RAND(20100930 << 3) * 50000) + 1,
        (RAND(20100930 << 4) * 100) + 20
FROM    product
CROSS JOIN
        (
        SELECT  id
        FROM    filler
        LIMIT 25
        ) q;

CREATE INDEX ix_product_parent ON product (parent);
CREATE INDEX ix_site_region ON site (region);
CREATE INDEX ix_price_site_product_value_id ON price (site, product, value, id);
CREATE INDEX ix_price_product_value_id ON price (product, value, id);
CREATE INDEX ix_price_value_id ON price (value, id);

Members of the dimensions are distributed logarithmically, reducing from the lower to the higher values.

Say, 11,379 products of 250,000 (4.55% of all products) belong to the parent 1, while only 2,906 products (1.16%) belong to the parent 30:

Same distribution applies to the sites:

Product/site, price

This is the most straightforward query. Since the product and site table come first, it's best for sparse products and sparse sites.

They will be filtered first and the results of the filtering cross joined (still returning relatively few values to join against the prices).

Here's the query:

SELECT  p.*, MIN(r.value) AS min_value
FROM    product p
CROSS JOIN
site s
STRAIGHT_JOIN
price r
ON      r.product = p.id
AND r.site = s.id
WHERE   p.parent = 100
AND s.region = 30
GROUP BY
p.id
ORDER BY
min_value
LIMIT 10

select `20100930_prices`.`p`.`id` AS `id`,`20100930_prices`.`p`.`parent` AS `parent`,`20100930_prices`.`p`.`name` AS `name`,min(`20100930_prices`.`r`.`value`) AS `min_value` from `20100930_prices`.`product` `p` join `20100930_prices`.`site` `s` straight_join `20100930_prices`.`price` `r` where ((`20100930_prices`.`r`.`site` = `20100930_prices`.`s`.`id`) and (`20100930_prices`.`r`.`product` = `20100930_prices`.`p`.`id`) and (`20100930_prices`.`s`.`region` = 30) and (`20100930_prices`.`p`.`parent` = 100)) group by `20100930_prices`.`p`.`id` order by min(`20100930_prices`.`r`.`value`) limit 10

We see that there is a filesort operation in the plan, but since there are relatively few values to sort, this operation is quite fast.

This query completes in 13 ms.

Site, product, price

This query is quite similar to the previous one, differing only in the JOIN order. It is best for sparse sites and dense products:

SELECT  p.*, MIN(r.value) AS min_value
FROM    site s
STRAIGHT_JOIN
price r
ON      r.site = s.id
STRAIGHT_JOIN
product p
ON      p.parent = 1
AND p.id = r.product
WHERE   s.region = 30
GROUP BY
p.id
ORDER BY
min_value
LIMIT 10

select `20100930_prices`.`p`.`id` AS `id`,`20100930_prices`.`p`.`parent` AS `parent`,`20100930_prices`.`p`.`name` AS `name`,min(`20100930_prices`.`r`.`value`) AS `min_value` from `20100930_prices`.`site` `s` straight_join `20100930_prices`.`price` `r` straight_join `20100930_prices`.`product` `p` where ((`20100930_prices`.`r`.`site` = `20100930_prices`.`s`.`id`) and (`20100930_prices`.`p`.`id` = `20100930_prices`.`r`.`product`) and (`20100930_prices`.`p`.`parent` = 1) and (`20100930_prices`.`s`.`region` = 30)) group by `20100930_prices`.`p`.`id` order by min(`20100930_prices`.`r`.`value`) limit 10

This query completes in 30 ms, since the conditions (in their totality) are less selective.

Product, price, site

This query is best for sparse products and dense sites:

In this query, we will replace the JOIN against the site table with an IN predicate, since we don't actually need any information from that table:

SELECT  p.*, MIN(r.value) AS min_value
FROM    product p
STRAIGHT_JOIN
price r
ON      r.product = p.id
WHERE   p.parent = 100
AND r.site IN
(
SELECT  id
FROM    site
WHERE   region = 1
)
GROUP BY
p.id
ORDER BY
min_value
LIMIT 10

select `20100930_prices`.`p`.`id` AS `id`,`20100930_prices`.`p`.`parent` AS `parent`,`20100930_prices`.`p`.`name` AS `name`,min(`20100930_prices`.`r`.`value`) AS `min_value` from `20100930_prices`.`product` `p` straight_join `20100930_prices`.`price` `r` where ((`20100930_prices`.`r`.`product` = `20100930_prices`.`p`.`id`) and (`20100930_prices`.`p`.`parent` = 100) and <in_optimizer>(`20100930_prices`.`r`.`site`,<exists>(<primary_index_lookup>(<cache>(`20100930_prices`.`r`.`site`) in site on PRIMARY where ((`20100930_prices`.`site`.`region` = 1) and (<cache>(`20100930_prices`.`r`.`site`) = `20100930_prices`.`site`.`id`)))))) group by `20100930_prices`.`p`.`id` order by min(`20100930_prices`.`r`.`value`) limit 10

Again, this query is 30 ms.

Price, product/site

This query is best for dense products and dense sites. This is the most complex query which would require some explanation.

At the first sight, it may seem that price cannot be filtered on. However, it's not true.

What we need is 10 lowest values from price satisfying certain conditions (right products and sites, and, additionally, products should be unique).

This means that we could make use of an index on price.value, scanning it until 10 records satisfying these conditions are returned. In this case, ORDER BY and LIMIT 10 would serve as filtering conditions: the scanning would cease as soon as the limit is reached.

And of course the more dense are the products and sites, the more is the probability for the conditions to be satisfied, the sooner the query completes.

Filtering on products and sites is easy, but to ensure that the products are unique, we will use the trick described in my previous article:

• 20 latest unique records

Basically, when filtering a price, we should not only make sure that it holds the correct product, but that it's the first (lowest) price for a given product.

This can be easily done with an additional ORDER BY / LIMIT in a subquery.

Here's the query:

SELECT  p.*, value AS min_value
FROM    price r
STRAIGHT_JOIN
product p
ON      p.id = r.product
WHERE   p.parent = 1
AND r.id =
(
SELECT  ri.id
FROM    price ri
WHERE   ri.product = p.id
AND ri.site IN
(
SELECT  id
FROM    site
WHERE   region = 1
)
ORDER BY
ri.product, ri.value, ri.id
LIMIT 1
)
ORDER BY
r.value, r.id
LIMIT 10

Field or reference '20100930_prices.p.id' of SELECT #2 was resolved in SELECT #1
select `20100930_prices`.`p`.`id` AS `id`,`20100930_prices`.`p`.`parent` AS `parent`,`20100930_prices`.`p`.`name` AS `name`,`20100930_prices`.`r`.`value` AS `min_value` from `20100930_prices`.`price` `r` straight_join `20100930_prices`.`product` `p` where ((`20100930_prices`.`p`.`id` = `20100930_prices`.`r`.`product`) and (`20100930_prices`.`p`.`parent` = 1) and (`20100930_prices`.`r`.`id` = (select `20100930_prices`.`ri`.`id` from `20100930_prices`.`price` `ri` where ((`20100930_prices`.`ri`.`product` = `20100930_prices`.`p`.`id`) and <in_optimizer>(`20100930_prices`.`ri`.`site`,<exists>(<primary_index_lookup>(<cache>(`20100930_prices`.`ri`.`site`) in site on PRIMARY where ((`20100930_prices`.`site`.`region` = 1) and (<cache>(`20100930_prices`.`ri`.`site`) = `20100930_prices`.`site`.`id`)))))) order by `20100930_prices`.`ri`.`product`,`20100930_prices`.`ri`.`value`,`20100930_prices`.`ri`.`id` limit 1))) order by `20100930_prices`.`r`.`value`,`20100930_prices`.`r`.`id` limit 10

We see that this query completes in only 14 ms despite the fact that we used the most populated parent and region. As I said before, the LIMIT 10 served as another filtering condition.

Summary

Let's run all possible queries for all possible distributions and record the query times in a table

P, S and R stand for product, site and price in the join order.

+Inf means that the query did not complete in a reasonable time and had to be terminated.

Conclusion

If limiting the results, MySQL allows filtering fact tables efficiently on higher level dimensions despite the fact these dimensions cannot be indexed. However, in each case the selectivity of the dimension level should be taken into account and the appropriate query should be used.

It should be noted that the queries involving a CROSS JOIN and index scan on the fact table perform intolerably poorly in the edge cases (too dense and too sparse dimensions, accordingly). On the other hand, the queries involving a join only differ in the join order which can be predicted by MySQL.

This means that when the dimension selectivity is unknown, a query using a plain join of all three tables (without forcing the join order) should be the query of choice:

SELECT  p.*, MIN(r.value) AS min_value
FROM    product p
CROSS JOIN
site s
JOIN    price r
ON      r.product = p.id
AND r.site = s.id
WHERE   p.parent = 1
AND s.region = 1
GROUP BY
p.id
ORDER BY
min_value
LIMIT 10

, since MySQL can select a join order quite close to optimal and the query would complete in reasonable time.

However, when the distribution on both dimensions is known, the appropriate query from the table above can be chosen.

Hope that helps.

I'm always glad to answer the questions regarding database queries.

Ask me a question