EXPLAIN EXTENDED

From Stack Overflow:

I have a logfile which logs the insert/delete/updates from all kinds of tables.

I would like to get an overview of for example the last 20 people which records where updated, ordered by the last update (datetime DESC)

A common solution for such a task would be writing an aggregate query with ORDER BY and LIMIT:

SELECT  person, MAX(ts) AS last_update
FROM    logfile
GROUP BY
        person
ORDER BY
        last_update DESC
LIMIT 20

What’s bad in this solution? Performance, as usual.

Since last_update is an aggregate, it cannot be indexed. And ORDER BY on unindexed fields results in our good old friend, filesort.

Note that even in this case the indexes can be used and the full table scan can be avoided: if there is an index on (person, ts), MySQL will tend to use a loose index scan on this index, which can save this query if there are relatively few persons in the table. However, if there are many (which is what we can expect for a log table), loose index scan can even degrade performance and generally will be avoided by MySQL.

We should use another approach here. Let’s create a sample table and test this approach:
Read the rest of this entry »

Answering questions asked on the site.

Frode Underhill asks:

I have some applications that are logging to a MySQL database table.

The table is pretty standard on the form:

time BIGINT(20)	source TINYINT(4)	severity ENUM	text VARCHAR(255)

, where source identifies the system that generated the log entry.

There are very many entries in the table (>100 million), of which 99.9999% are debug or info messages.

I’m making an interface for browsing this log, which means I’ll be doing queries like

SELECT  *
FROM    log
WHERE   source = 2
        AND severity IN (1,2)
        AND time > 12345
ORDER BY
        time ASC
LIMIT 30

, if I want to find debug or info log entries from a certain point in time, or

SELECT  *
FROM    log
WHERE   source = 2
        AND severity IN (1,2)
        AND time < 12345
ORDER BY
        time DESC
LIMIT 30

for finding entries right before a certain time.

How would one go about indexing & querying such a table?

I thought I had it figured out (I pretty much just tried every different combination of columns in an index), but there’s always some set of parameters that results in a really slow query.

The problem is that you cannot use a single index both for filtering and ordering if you have a ranged condition (severity IN (1, 2) in this case).

Recently I wrote an article with a proposal to improve SQL optimizer to handle these conditions. If a range has low cardinality (this is, there are few values that con possibly satisfy the range), then the query could be improved by rewriting the range as a series of individual queries, each one using one of the values constituting the range in an equijoin:

• Things SQL needs: determining range cardinality

No optimizers can handle this condition automatically yet, so we’ll need to emulate it.

Since the severity field is defined as an enum with only 5 values possible, any range condition on this field can be satisfied by no more than 5 distinct values, thus making this table ideal for rewriting the query.

Let’s create a sample table:
Read the rest of this entry »

In one of the previous articles I discussed performance of the three methods to implement an anti-join in MySQL.

Just a quick reminder: an anti-join is an operation that returns all records from one table which share a value of a certain column with no records from another table.

In SQL, there are at least three methods to implement it:

LEFT JOIN / IS NULL

SELECT  o.*
FROM    outer o
LEFT JOIN
        inner i
ON      i.value = o.value
WHERE   i.value IS NULL

NOT IN

SELECT  o.*
FROM    outer o
WHERE   o.value NOT IN
        (
        SELECT  value
        FROM    inner
        )

NOT EXISTS

SELECT  o.*
FROM    outer o
WHERE   NOT EXISTS
        (
        SELECT  NULL
        FROM    inner i
        WHERE   i.value = o.value
        )

When inner.value is marked as NOT NULL, all these queries are semantically equivalent and with proper indexing have similarly optimized execution plans in MySQL.

Now, what if inner.value is not nullable and does contain some NULL values?

Let’s create some sample tables:
Read the rest of this entry »

Answering questions asked on the site.

Ivo Radev asks:

I am trying to make a very simple query.

We have a log table which different machines write to. Given the machine list, I need to find the latest log timestamp.

Currently, the query looks like this:

SELECT  MAX(log_time)
FROM    log_table
WHERE   log_machine IN ($machines)

, and I pass the comma-separated list of $machines from PHP.

The weird thing is that the query is literally instant when there is only one machine (any) in the list but slow when there are multiple machines.

I’m considering doing it in separate queries and then process the results in PHP. However I’d like to know if there is a fast solution in MySQL.

Most probably, there is a composite index on (log_machine, log_time) which is being used for the query.

Usually, a query like this:

SELECT  MAX(log_time)
FROM    log_table

on the indexed field log_time can be served with a single index seek on the index.

Indeed, the MAX(log_time), by definition, is the latest entry in the index order, and can be fetched merely by finding the trailing index entry. It’s a matter of several page reads in the B-Tree, each one following the rightmost link to the lower-level page.

Similarly, this query:

SELECT  MAX(log_time)
FROM    log_table
WHERE   log_machine = $my_machine

can be served with a single index seek too. However, the index should include log_machine as a leading column.

In this case, a set of records satisfying the WHERE clause of the query is represented by a single logically continuous block of records in the index, each one sharing the same value of log_machine. MAX(log_time) will of course be held by the last record in this block. MySQL just finds that last record and takes the log_time out of it.

Now, what if we have a multiple condition on log_machine?
Read the rest of this entry »

Answering questions asked on the site.

Nate asks:

I know you’ve addressed similar issues related to the greatest-per-group query but this seems to be a different take on that.

Example table:

t_group

item_id	group_id	score
100	1	2
100	2	3
200	1	1
300	1	4
300	2	2

Each item may be in multiple groups. Each instance of an item in that group is given a score (how relevant it is the the group).

So given the data above, when querying for group 1 it should return items 200 and 300 (item 100‘s highest score is for group 2, so it’s excluded).

The classical greatest-n-per-group problem requires selecting a single record from each group holding a group-wise maximum. This case is a little bit different: for a given group, we need to select all records holding an item-wise maximum.

Let’s create a sample table:
Read the rest of this entry »

Answering questions asked on the site.

James asks:

Your series on hierarchical queries in MySQL is tremendous! I’m using it to create a series of threaded conversations.

I’m wondering if there is a way to paginate these results.

Specifically, let’s say I want to limit the conversations to return 10 root nodes (parent=0) and all of their children in a query.

I can’t just limit the final query, because that will clip off children. I’ve tried to add LIMITs to your stored functions, but I’m not getting the magic just right.

How would you go about doing this?

A quick reminder: MySQL does not support recursion (either CONNECT BY style or recursive CTE style), so using an adjacency list model is a somewhat complicated task.

However, it is still possible. The main idea is storing the recursion state in a session variable and call a user-defined function repeatedly to iterate over the tree, thus emulating recursion. The article mentioned in the question shows how to do that.

Normally, reading and assigning session variables in the same query is discouraged in MySQL, since the order of evaluation is not guaranteed. However, in the case we only use the table as a dummy recordset and no values of the records are actually used in the function, so the actual values returned by the function are completely defined by the function itself. The table is only used to ensure that the function is called enough times, and to present its results in form of a native resultset (which can be returned or joined with).

To do something with the logic of the function (like, imposing a limit on the parent nodes without doing the same on the child nodes), we, therefore, should tweak the function code, not the query that calls the functions. The only thing that matters in such a query is the number of records returned and we don’t know it in design time.

Limiting the parent nodes is quite simple: we just use another session variable to track the number of parent branches yet to be returned and stop processing as soon as the limit is hit, that is the variable becomes zero.

Let’s create a sample table and see how to do this:
Read the rest of this entry »

Answering questions asked on the site.

Andrew Stillard asks:

I have a store which will hold around 50,000 products in a products table. Each product will have 14 options, giving 700,000 options in total. These are held in an options table which is joined via the product id.

Users search for products based on the options via an Advanced Search menu.

The users need to be able to select multiple options upon which to query. I would normally use a JOIN if it was just the one option to select upon, but because its a variable number i thought it would be best to loop through the WHERE EXISTS statement.

The issue i have currently is that the query is taking a minimum of 18 seconds (And that was a query when the tables only had a fraction of the total products in).
If you can help us speed this up, or suggest an alternative idea that would be greatly appreciated.

The option table mentioned here is in fact an implementation of the EAV model in a relational database.

Each record basically contains 3 things: id of the product it describes; id of the option and the value of the given option for the given product. These fields represent entity, attribute and value, respectively.

This model is very easy to maintain and expand should the need arise: all we have to do to define an extra attribute is to add a record to the EAV table with the name and the value of the attribute. This is a DML operation rather than a DDL one.

However, this model has a serious drawback: we cannot efficiently search for two or more options at once. An index can only be defined on several fields from a single record, so we can only search for a single option using an index.

There are two approaches to writing a query which would search for the entities with the certain conditions on several attributes at once:

1. For each attribute, find all entities for which the conditions on the given attribute hold, then aggregate the resulting entities, using COUNT(*) as a filter. The number of entity entries should be equal to the number of the attributes.
2. Takes each entity and for each attribute, check if the condition holds.

The first approach uses a GROUP BY, the second one uses EXISTS.

Let’s create a sample table and see which one is more efficient:
Read the rest of this entry »

From Stack Overflow:

Suppose you’ve visited sites S0 … S50. All except S0 are 48% female; S0 is 100% male.

I’m guessing your gender, and I want to have a value close to 100%, not just the 49% that a straight average would give.

Also, consider that most demographics (i.e. everything other than gender) does not have the average at 50%. For example, the average probability of having kids 0-17 is ~37%.

The more a given site’s demographics are different from this average (e.g. maybe it’s a site for parents, or for child-free people), the more it should count in my guess of your status.

What’s the best way to calculate this?

This is a classical application of Bayes’ Theorem.

The formula to calculate the posterior probability is:

P(A|B) = P(B|A) × P(A) / P(B) = P(B|A) × P(A) / (P(B|A) × P(A) + P(B|A*) × P(A*))

, where:

• P(A|B) is the posterior probability of the visitor being a male (given that he visited the site)
• P(A) is the prior probability of the visitor being a male (initially, 50%)
• P(B) is the probability of (any Internet user) visiting the site
• P(B|A) is the probability of a user visiting the site, given that he is a male
• P(A*) is the prior probability of the visitor not being a male (initially, 50%)
• P(B|A*) is the probability of a user visiting the site, given that she is not a male.

Read the rest of this entry »

Answering questions asked on the site.

Vlad Enache asks:

In MySQL I have a table called meanings with three columns:

meanings

person	word	meaning
1	1	4
1	2	19
1	2	7
1	3	5

word has 16 possible values, meaning has 26.

A person assigns one or more meanings to each word. In the sample above, person 1 assigned two meanings to word 2.

There will be thousands of persons.

I need to find the top three meanings for each of the 16 words, with their frequencies. Something like:

• word 1: meaning 5 (35% of people), meaning 19 (22% of people), meaning 2 (13% of people)
• word 2: meaning 8 (57%), meaning 1 (18%), meaning 22 (7%)

etc.

Is it possible to solve this with a single MySQL query?

This task is a typical greatest-n-per-group problem.

Earlier I described some solutions to it, one using session variables, and another one using LIMIT in a subquery. However, these solutions imply that the records are taken from a single table, while this task needs to retrieve three greatest aggregates, not three greatest records. It is not recommended to mix the session variables with the JOINs, and using the LIMIT solution would be inefficient, since the aggregates can not be indexed.

Some databases, namely, PostgreSQL, used to exploit the array functionality for this task (before the window functions were introduced in 8.4).

Unfortunately, MySQL does not support arrays, but we can emulate this behavior using string functions and GROUP_CONCAT.

Let’s create a sample table:
Read the rest of this entry »

From Stack Overflow:

I have a table product with products and table sale with all sale operations that were done on these products.

I would like to get 10 most often sold products today and what I did is this:

SELECT  p.*, COUNT(s.id) AS sumsell
FROM    product p
LEFT JOIN
        sale s
ON      s.product_id = p.id
        AND s.dt >= '2010-01-01'
        AND s.dt < '2010-01-02'
GROUP BY
        p.id
ORDER BY
        sumsell DESC
LIMIT 10

, but performance of it is very slow.

What can I do to increase performance of this particular query?

The query involves a LEFT JOIN which in MySQL world means that products will be made leading in the query. Each record of product will be taken and checked against sale table to find out the number of matching records. If no matching records are found, 0 is returned.

Let’s create the sample tables:
Read the rest of this entry »