How do I use EXPLAIN to *predict* performance of a MySQL query?

EXPLAIN won't give you any indication of how long a query will take. At best you could use it to guess which of two queries might be faster, but unless one of them is obviously badly written then even that is going to be very hard.

You should also be aware that if you're using sub-queries, even running EXPLAIN can be slow (almost as slow as the query itself in some cases).

As far as I'm aware, MySQL doesn't provide any way to estimate the time a query will take to run. Could you log the time each query takes to run, then build an estimate based on the history of past similar queries?

I think if you want to have a chance of building something reasonably reliable out of this, what you should do is build a statistical model out of table sizes and broken-down EXPLAIN result components correlated with query processing times. Trying to build a query execution time predictor based on thinking about the contents of an EXPLAIN is just going to spend way too long giving embarrassingly poor results before it gets refined to vague usefulness.

MySQL EXPLAIN has a column called Key. If there is something in this column, this is a very good indication, it means that the query will use an index.

Queries that use indicies are generally safe to use since they were likely thought out by the database designer when (s)he designed the database.

However

There is another field called Extra. This field sometimes contains the text using_filesort.

This is very very bad. This literally means MySQL knows that the query will have a result set larger than the available memory, and therefore will start to swap the data to disk in order to sort it.

Conclusion

Instead of trying to predict the time a query takes, simply look at these two indicators. If a query is using_filesort, deny the user. And depending on how strict you want to be, if the query is not using any keys, you should also deny it.

Read more about the resultset of the MySQL EXPLAIN statement