WL#4803: pluggable query cache module

Affects: Server-6.0   —   Status: Assigned   —   Priority: Medium

Today the query cache is a central part of the server, where the server uses the
query cache to handle some server logic. The query cache uses both calls to the
network and calls directly to the storage engines to serve its needs.

This task is about making the query cache a module by reworking the structure so
that the query cache will be a stand alone module without any dependencies on
the server.

Make the query cache pluggable by:
- Create a pluggable API, using the service registry in WL#3859
- Refactoring the code using the guidelines in WL#4739
- Remove server dependencies

This will allow:
- other implementations, such as query cache on memcached or NDB.
- fixing the current implementation to scale better.
- better encapsulation
- unit testing.

The first part will be to make the query cache working as a module, removing the
server dependencies and creating an API that can be used for other
implementations of a query cache.

The plan:
To be done by the end of May 2009:
- Create an API that has no server function dependencies.
- Implement the API in the server (i.e adding logic in the server to handle the
query cache API)
- Modify the current query cache to work with the new API
- Create a unit test by using the new API, for verifying that the query cache
fullfills the API.


When WL#4739 has decided on the structure:
- Restructuring the code/files to comply.

When WL#3859 is implemented
- Make the API to work as a service API (For use as an example).
The first part will be to create a generic API to the query cache where the
server responsibility is:
- Check if a query string is in the query cache and if no match register the
query if it looks like a select
- verify that no tables in the query is invalidated
- return the result to the client
- register used tables to already registered query
- appending results to already registered query 1)
- ending a registered query with either failure or EOF packet information (to
allow different server_status values for the same result)
- aborting a registered query / releasing the query handle
- invalidating tables and databases when they are changed
Possible future expansions
- [optionally] check if a parsed query can be served from the query cache
- [optionally] allow invalidated results not older than max_qc_age to be accepted 2)

And the query cache responsibility is:
- looking up if the query string is already cached and if not storing the query
string
- storing used tables per query
- storing result per query
- handling removal of queries/results/tables references based on
invalidation/age or other measurement.
Possible future expansions
- [optionally] store parse data for a query, allowing better matching of queries
- [optionally] store invalidation timestamps per table 2)
- [optionally] have statistics per query, per table 2)

1) By appending each package sent to the client, the server does not need to
store the full result set before copying it to the cache.
2) These also needs added syntax to be possible to use and is not in the scope
of this worklog.

Note: There are also some connection dependent flags that needs to be stored as
a part of the query, such as 4.1 protocol, binary results, character sets,
collation, etc.

It is up to the query cache how to handle the case where a query string is in
the cache, but not yet complete (i.e. still running) possible choice is waiting
on the already running query or skip the query cache for that query and run it
in parallel.


The flow for a non yet cached query should be:
- Server checks if the query string is in the query cache the query cache
answers 'no match' and returns a handle to the new query (if select)
- Server parses the query, and if not cachable, it removes it from the query cache.
  [a future extention could be to also register the parse data, and check if
that has a match in the cache]
- Server registers every table used in the query (including engine specific
data, such as transaction info) to the query cache (which stores the link
between the query and the table)
[Could be possible to do this at the end instead, to only register tables that
was used, but then one have to verify it with the invalidation of tables procedures]
- As the server sends the results to the client, they are also appended to the
query cache
- When the server sends the EOF to the client this is copied and is used for
finishing the query with the cache, making the query available to server from
the cache.

If something goes wrong the server sends an abort to the query cache which
handle the unfinished query.

The flow for a cached query should be:
- Server checks if the query string is in the query cache
    the query cache replies with a handle to the cached query.
- The server loops through all tables (by asking the query cache for all tables
used by the query) and verifys that they are not invalidated (info from query
cache) and the table is still in a valid state (by letting the storage engine
compare with the engine specific data stored when the query was executed)
- The server verifies that the user have right to access the tables (Note: can
be extended to column as well, but that is not handled within this worklog).
- The server takes the result package by package and sends it to the client
- For the last package the server may alter the server_status in the EOF bytes.
- The server releases the query handle.
proposal for the query cache interface (qcp_interface.h)
/* Copyright (C) 2009 Sun Microsystems, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


/**
  @file

  @details
  Query cache functions for storing and retreiving a query with
  its associated tables and results.
*/

/**
  Forward declarations
*/
class THD;
/* Why is TABLE_LIST a struct and not a class ? */
struct TABLE_LIST;

/**
  @defgroup Query_cache_store Storing a query
  @{

  Storing a query and its used tables and the result to the cache.

  The calls must follow the call graph described below, qcp_start_store_query
  -> qcp_store_table x num_tables -> qcp_store_result x M ->
  qcp_end_store_query.
  The server is only allowed to call qcp_abort if the qcp_start_store_query and
  the following calls all was successful (return == 0)
  and before qc_end_store_query was called.

  <pre>
  --------------------------------------------
  | Server wants to add a query to the cache |
  | (after parsing, before execution.        |
  | Server has already checked with all used |
  | table handlers through                   |
  | register_query_cache_table that it is    |
  | allowed to cache the query, and if       |
  | the engine has returned any callback or  |
  | engine_data).                            |
  --------------------------------------------
            |
           \/
  -------------------------
  | qcp_start_store_query | -> ret != 0 caching failed,
  -------------------------             qc_state is invalid.
    | ret == 0                          (qcp_start_store_query is responsible
    |                                    for the clean-up if it fails.)
    |
    |   -----------------
    \-->|qcp_store_table| -> ret != 0   See above
        -----------------
ret == 0  ^  |      | (call nr == num_tables given in qcp_start_store_query)
          |  |      |
          \--/      |
(call nr <          |
 num_tables)       \/
               ------------------------------------------
               | Server must now call qcp_store_result  |
               | for each packet sent to the client in  |
               | sending order.                         |
               | (Server can now start the execution)   |
               | (the cache can release some internals) |
               ------------------------------------------
                 |
                 |
                \/
      --------------------
      | qcp_store_result | -> ret != 0  See above, and the server is not
      -------------------               allowed to call qcp_store_result
        ^  |         |                  again for this query.
        |  |         |                  (qc_state is now invalid!)
        \--/         |
(for each packet     |
 sent to client)     |
                     |   (when the server has sent its last result packet
                     |    to the client, server execution done)
                    \/
  -----------------------
  | qcp_end_store_query |
  -----------------------
                   | ret != 0   the query was not added to the cache.
                   | ret == 0   the query was added to the cache.
                  \/
  ----------------------------------------------------------------
  | The cache is now done with the query and qc_state is invalid |
  ----------------------------------------------------------------
  </pre>   
*/

/**
  @brief
  Store a query string in the cache, and prepare for associate tables to it

  @param[in,out] qc_state   Query specific state, storing state between calls
  @param query_string       The query string to cache
  @param query_length       Length of query string
  @param flags              Binary string of server internal flag data
  @param query_length       Length of flags
  @param current_db         Used database
  @param current_db_length  Length of current_db string
  @param tables_type        Flags of types of tables (if tables are
                            Transactional and/or non transactional)
  @param num_tables         Number of tables that is used by query.

  @return Operation status
    @retval 0      Success
    @retval != 0   Failure (qc_state is not updated either)

  @note
  Before the server calls qcp_start_store_query it should have counted all used
  tables and verified that all tables, and their handlers,
  accepts being cached, and allowed to store callback functions and data
  to be reverified before sending the result to the client from the cache.
*/
int qcp_start_store_query(void **qc_state,
                          const char *query_string, uint query_length,
                          const uchar *flags, uint flags_length,
                          const char *current_db, uint current_db_length,
                          uint8 tables_type, uint num_tables);
                                       
/**
  @brief
  Register a table that was used by the query.

  @param qc_state         Query specific state, as returned from
                          qcp_start_store_query.
  @param table_key        Table key in form of 'db\\0table\\0'.
  @param table_key_length Length of table_key, including both '\\0'.
  @param callback         Function pointer to callback function
                          (returned from handler::register_query_cache_table).
  @param engine_data      Table specific engine_data
                          (returned from handler::register_query_cache_table).

  @return Operation status
    @retval 0      Success
    @retval != 0   Failure (qc_state is not valid any longer)

  @note
  If qcp_start_store_query was OK, then call qcp_store_table for each
  table/view used in query.

  engine_data is defined in handler.h, handler::register_query_cache_table as:
  (ulonglong) Storage engine specific data which could be anything.

  callback is defined in handler.h, handler::register_query_cache_table as:
  A generic (but static) call back function which is called each time
  a statement that uses the registered table is matched against the query cache.
  
  From handler.h:
  If engine_data supplied with register_query_cache_table is different from
  engine_data supplied with the callback function, and the callback returns
  FALSE, a table invalidation on the current table will occur.

  Upon success for register_query_cache_table the engine_callback will point
  to the storage engine call back function, if any, and engine_data will point
  to any storage engine data used in the specific implementation.


*/            
int qcp_store_table(void* qc_state,
                    const char *table_key, size_t table_key_length,
                    void *callback, ulonglong engine_data);

/**
  @brief
  Adding result to the cached query.

  @param qc_state         Query specific state, as returned from
                          qcp_start_store_query.
  @param packet           Packet to add to the query.
  @param packet_length    Length of the packet

  @return Operation status
    @retval 0      Success
    @retval != 0   Failure (qc_state is not valid any longer)

  @note
  When the server sends results to the client in net_real_write and
  the results should be appended to the query cache,
  it calls this for every packet.
*/
int qcp_store_result(void *qc_state, uchar *packet, uint packet_length);

/**
  @brief
  Finalize storing the query and make it available for serving.

  @param qc_state         Query specific state, as returned from
                          qcp_start_store_query.
  @param last_packet_nr   Last packet nr sent to client.
  @param limit_found_rows Number of rows found.

  @return Operation status
    (qc_state is not valid any longer)
    @retval 0      Success
    @retval != 0   Failure

  @note
  last_packet_nr is used to keep the packet nr in sync after the results has
  been returned.
  limit_found_rows is used for supporting FOUND_ROWS() function in next query.
*/
int qcp_end_store_query(void *qc_state, uint last_packet_nr, ha_rows
limit_found_rows);
/*@}*/

/** @defgroup Query_cache_get Finding a cached query
 @{

  Look up if the query is in the cache, and if so, retreiving the tables that
  was used by the query and all its results packets, to serve the client.

  The calls must follow the call graph described below, qcp_start_get_query ->
  qcp_get_table x N -> qcp_get_result x M -> qcp_end_get_query.
  The server is only allowed to call qcp_abort if the qcp_start_get_query and
  the following calls all was successful (return >= 0)
  and before qc_end_get_query was called.

<pre>

  ----------------------------------------------------------------------------
  | The server has the full query string from the client and                 |
  | wants to use the query cache if possible, to avoid parsing and execution |
  ----------------------------------------------------------------------------
      |
     \/
  -----------------------
  | qcp_start_get_query | ret != 0 -> Query not found in cache or not usable
  -----------------------             (qc_state is invalid, Server must parse
      |  ret == 0 (qc_state is valid)  and execute the query).
     \/
   -----------------
   | qcp_get_table | ret < 0 ->  Query cache error (qc_state is invalid,
   -----------------             Server must parse and execute).
     |     ^      |  ret > 0 (table returned)
     |     |      |  
     |     \-----/   Server decides if it continues with a new call or
     |               aborts with qcp_abort (depending on callback, engine_data
     | ret == 0      and invalidated_time).
    \/
  ------------------
  | qcp_get_result | ret < 0 -> Query cache error (qc_state is invalid,
  ------------------            Server must send error to the client if it has
     |     ^      |             already sent a packet, otherwise parse/execute.
     |     |      |
     |     |      |  ret > 0 (result returned)  
     |     \-----/   Server sends the packet to the client and continues with
     |               qcp_get_result as long as there are more results or
     |               aborts with qcp_abort (in case of sending errors).
     |
     | ret == 0
    \/
  ---------------------
  | qcp_end_get_query |
  ---------------------
    |               
    | (qc_state is invalid)
   \/
  -------------------------------------------------------------------------
  | All results are sent to the client,                                   |
  | the server can now update thd->limit_found_rows and the query is done |
  -------------------------------------------------------------------------

</pre>
*/
/**
  @brief
  Find query in the cache

  @param[in,out] qc_state   Query specific state, storing state between calls
  @param query_string       The query string to cache
  @param query_length       Length of query string
  @param flags              Binary string of server internal flag data
  @param query_length       Length of flags
  @param current_db         Used database
  @param current_db_length  Length of current_db string
  @param[out] tables_type   Flags of types of tables (if tables are
                            transactional and/or non transactional)

  @return Found query
    @retval 0    Usable query was found in cache
    @retval != 0 No usable query was found in cache
*/
int qcp_start_get_query(void **qc_state,
                        const char *query_string, uint query_length,
                        const uchar *flags, uint flags_length,
                        const char *current_db, uint current_db_length,
                        uint8 *tables_type);

/**
  @brief
  Get table used by query, one for each call.

  @param qc_state              Query specific state, as returned from
                               qcp_start_get_query.
  @param[out] table_key        Table key in form of 'db\\0table\\0'.
  @param[out] table_key_length Length of table_key, including both '\\0'.
  @param[out] callback         Function pointer to callback function
  @param[out] engine_data      Table specific engine_data
  @param[out] invalidate_time  Table invalidation time_t, 0 if not invalidated.

  @return Table found
    @retval 0    No more table used by query.
    @retval < 0  Error, qcp_get_table aborts the query and qc_state is invalid.
    @retval > 0  Table found.

  @note
  Get a table that is used in the query, to let the server validate its state
  with its handler through the callback/engine_data.
  The server must loop over this function until there is no more tables
  (or server calls qcp_abort).
  invalidate_time is set to the time when the table version used by the query
  was invalidated.
  The server may allow sending results, which includes tables that has been
  invalidated after the query was cached, if the client has explicitly set
  a session variable allowing the server to so.
  If the query cache does not supports invalidation time, it will invalidate
  all queries imediately.
*/
int qcp_get_table(void *qc_state,
                  uchar **table_key, size_t *table_key_length,
                  void **callback, ulonglong *engine_data,
                  time_t *invalidate_time);


/**
  @brief
  Get the result packages in order, one for each call.

  @param qc_state              Query specific state, as returned from
                               qcp_start_get_query.
  @param[out] result           Result packet.
  @param[out] result_length    Length of result packet.

  @result Result found
    @retval 0    No more results.
    @retval < 0  Error qcp_get_result aborts the query and qc_state is invalid.
    @retval > 0  Result exists.
*/
int qcp_get_result(void *qc_state, uchar **result, size_t *result_length);

/**
  @brief
  Finalize the cached query, and release it.

  @param qc_state              Query specific state, as returned from
                               qcp_start_store_query.
  @param[out] last_packet_nr   Last packet nr sent to client.
  @param[out] limit_found_rows Number of rows found.

  @return Operation status
    (qc_state is not valid any longer)
    @retval 0      Success
    @retval != 0   Failure

  @note
  All results are sent to the client, allow the query cache to
  release resources.
  last_packet_nr is used to keep the packet nr in sync after the results has
  been returned.
  limit_found_rows is used for supporting FOUND_ROWS() function in next query.

*/
void qcp_end_get_query(void *qc_state, uint *last_pkt_nr,
                       ha_rows *limit_found_rows);
/*@}*/

/** @defgroup Query_cache_abort Abort the current cache operation
 @{*/
/**
  @brief
  Abort the current query cache operation.

  @param qc_state      NULL or a valid qc_state from either
                       qcp_start_store_query or qcp_start_get_query.
  @note
  Used by the server only with a valid qc_state or qc_state == NULL.
  (i.e. between qcp_start_store_query and qcp_end_store_query or
  between qcp_start_get_query and qcp_end_get_query)
*/
void qcp_abort(void *qc_state);
/**@}*/

/**
  @defgroup Query_cache_invalidate Invalidating tables
  @{*/
/**
  @brief
  Invalidate a table in the cache

  Invalidate a table, so that queries in the cache that uses that table will
  be marked as invalid.
  Include the current time that may be used by the query cache to support
  caching of invalidated results.

  @param table_key          Table to invalidate in form 
                            'db_name\\0table_name\\0'.
  @param table_key_length   Length of table_key, including both '\\0'.
  @param invalidate_time    Current time of invalidation.
*/
void qcp_invalidate_table(uchar *table_key, size_t table_key_length, time_t
invalidate_time);
/*@}*/


/**
  @defgroup Query_cache_init Init/Deinit the query cache
  @{*/
/**
  @brief
  Initialization of the cache.

  @param size    Size of the query cache.

  @retval 0     OK, cache is initialized with the given size.
  @retval != 0  Failure, cache is not initialized.

  @note
  The server is not allowed to call any qcp_* functions before qcp_init has
  returned 0.
*/
int qcp_init(size_t size);


/**
  @brief
  De-initialization of the cache.

  The query cache releases all resources.

  @note
  The cache must allow all current queries that has returned 0 for
  qcp_get_table, and not aborted or called qcp_end_get_query to continue.
  For all other cases it must return error. This is as long as there are
  valid qc_state in any query.
  The server must not call any other functions than qcp_get_result or
  qcp_end_get_query until this call returns. After it has returned, qcp_init
  must be called before any other qcp_* call is allowed.

*/
void qcp_deinit();
/*@}*/

/**
  @defgroup Query_cache_manage Managing the query cache
  @{
*/
/**
  @brief
  Resize the cache.

  Changing the maximum allowed size to be used by the query cache.

  @param new_size   New maximum allowed size for query cache.

  @return Resize was performed successfully.
    @retval 0    OK, cache has changed its max allowed size.
    @retval != 0 Failure, cache has not changed its max allowed size.
*/
int qcp_resize(size_t new_size);

/**
  @brief
  Empty the cache

  @return Cache is now empty.
    @retval 0    OK, cache is now empty.
    @retval != 0 Failure, cache may still have content.

  @note optional
*/
int qcp_empty();
/**
  @brief
  Compact the cache.

  Tell the cache to rearrange the content for optimal usage of the storage.

  @return Cache is now compacted
    @retval 0    OK
    @retval != 0 Failure, cache may still not be compacted

  @note optional
*/
int qcp_pack();
/*@}*/