WL#1293: QueryCache: Do not spawn second query execution if it is already running

For some loads query cache behaviour might be greatly improved, if query cache 
would not launch second query execution if exactly the same cachable query is
already running, but instead wait for it to complete and return results.
 
Example case: After table update queries are invalidated and users waiting for
page to load using "reload" bored by long page creation time.

This is feature request from Sony.de and RightNow Technologies.

1. Analysis
1.1 Detecting query execution
1.2 Releasing queued queries
1.3 Query cache invalidation
2. Measure the query throughput
3. Measure the query latency
4. Measure the query cache hit rate

1. Analysis
=======

1.1 Detecting query execution
======================

In order to detect that a query is already running any new query must have
registered its identity in the cache before the result set arrives.
Fortunately, such a place holder query-object already exists. The place holder
insertion happens when the server has parsed the query and opened and locked the
associated tables.

Currently the place holder is used when a new query is checked for a cached
result set. If there exist a place holder but no result set, the new query will
proceed to ordinary execution. This behaviour will be changed to let the query
wait for the expected result set to arrive instead.

This detection scheme isn't perfect, because a place holder isn't inserted
directly after the check for competing queries. Instead the mutex protecting the
query cache is released to allow for other clients to concurrently access the
cache and it isn't acquired until later when the query tables are locked and
opened. Closing this gap is a complex task which might not be worth while, at
least not as a first step (see benchmarking below).

It is however possible to narrow the gap where the place holder isn't effective
somewhat more by moving the query insertion step to be done before the
optimization step (but still after the tables are locked and opened).


1.2 Releasing queued queries
===================
Cacheable queries which are queued up and waiting, will be released once the
executing query is finished or invalidated. Upon release, the cache is
investigated again and one of the following can happen:
1. Success: The cached result set is retrieved and returned to the client and we
have gained performance.
2. Cache invalidation: The cached result set is being or has been invalidated.
The queued query will attempt to follow ordinary execution path.
3. Unexpected: An error has occurred. The queued queries will attempt to follow
ordinary execution path.


1.3 Query cache invalidation
===================
When the cache is invalidated the following should happen:

1. Query cache is invalidated while the query request intensity is high.
2. Query cache goes off line by setting status FLUSH_IN_PROGRESS.
  2a. All incoming queries are queued while waiting for the invalidation process
to finish.
  2b. Are there any queued up queries? Not in the usual case since it is
reasonable to expect that invalidation doesn't happen very frequently. In the
rare case that there are queries in the queue, they will continue to the parser
phase.
3. Query cache goes back online and all waiting statement threads are awoken.
  3a. Server load rises as the first batch of statements hit the parser.
4. The server load starts to drop as soon as the first query inserts a place
holder and the request queue (a _second_ queue) starts to build up.
5. The result set is finished and the queue is released.

One use case where the result set queue would be particularly efficient is cache
invalidation. In order to take full advantage of the pre-loading effect,
incoming SELECT statements should wait until the invalidation is finished
instead of bypassing the query cache and letting statements hit the parser. To
fully exploit this optimization a change needs to be done to the way incoming
queries behaves during cache invalidation. Instead of bypassing the query cache
on invalidation as currently implemented, there need to be an option to block
incoming query requests until invalidation is done. (*)

The new implementation will take advantage of the query cache mode DEMAND which
specifies that only SELECT statements with the SQL_CACHE hint will be cached.
Queries cached this way will also wait on the cache invalidation process to
finish instead of falling back to the ordinary execution path.

This presents the user with two query cache strategies: The implicit cache,
where all queries are cached but no query will wait on the invalidation process,
and the explicit cache where cacheable queries will wait for the invalidation
process to finish. The difference is motivated by the idea that queries which
are explicitly declared to be cached probably will be issued significantly more
often than any other query.

Footnote
*) The reason behind the current implementation stems from issues with high
level mutexes freezing the entire server. By bypassing the query cache we may
sometimes gain performance in regards to latency. The result sets are returned
more deterministic but slower in case of too high server load. By forcing
statements to wait on the invalidation to finish we may gain performance in
regard to query through put as the query cache will become available faster.


2. Measure the query throughput
====================

TODO: Use sysbench

MySQL server is started and initialized with the following statements:
 set global query_cache_size=52428800;
 use test;
 create table t1 (a int);
 
The table t1 is loaded with the numbers 1 .. 1000000 so there will be a
measurable penalty in returning the result set for the entire table. Then 20
concurrent threads are started simultaneously, each one issuing the statement
 select * from t1;

It isn't possible to guarantee that exactly one thread will now be returning the
result set, and the other 19 threads will be waiting for this result set to be
finished. The reason for this is that the query isn't registered at the same
time it is checked for existence, but much later after we parsed and opened the
associated tables. This is why we will have to measure the time it takes in
average with and without the patch.

The total time from the point where the threads are started is measured. The
test is then repeated with query cache disabled and on the unpatched version of
the server. Result should show that, in average, we've gained in performance or
this is a bad worklog.

3. Measure the query latency
==================
TODO

4. Measure the query hit rate
==================
TODO

1. Overview
2. Adding a new predicate
3. Narrow the gap

1. Overview
========

1.1 Changes made
============

*  Which subsystems are influenced.
- execution of a SELECT statement will affected but without significant impact
to the general functionality.

* Which files will be affected.
- sql_cache.cc, sql_cache.h, sql_parse.cc

* Are we adding any classes or global routines?
- No

* Any new public structures?
- None

* Which methods will be added and to which classes?
- Query_cache::wait_for_query

* An analysis of the flaws in the suggested design.
- When a query is checked for duplicate queries running in the system, it is not
immediately stored under the same mutex. This causes some queries close in time
to be parsed and executed concurrently.


1.2 Definitions
=========

Definition: A place holder object is a query which hasn't yet got a result set.


2. Adding a new predicate
================

Each time a new result set is finished all threads waiting on the predicate 'a
result set is done' should be signalled. Upon receiving the signal each thread
must verify that the result set has indeed arrived. The best way to do this is
by checking the place holder object for an associated result set writer. If no
writer is present then the query is cancelled or the result set is finished.

The cached query container needs to be checked for a place holder again before
the new result set can be used. Was the query cancelled the waiting threads will
be released to ordinary query execution, were they too probably will be cancelled.

It is important that even though a query is cancelled, it means that the 'result
set is done' and a signal should be emitted. It is preferred that the writer is
dropped before cancellation but it is not required since the released threads
also have to recheck any cached result set for sanity or fall back on ordinary
execution.

3. Narrow the gap
==============

The function query_cache_store should be moved so that it is as close to the
open_and_lock_table function as possible, to minimize the risk of having several
equal queries executing concurrently.