~drizzle-trunk/drizzle/development

/*****************************************************************************

Copyright (C) 1996, 2009, Innobase Oy. All Rights Reserved.

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., 51 Franklin

St, Fifth Floor, Boston, MA 02110-1301 USA

*****************************************************************************/

/**************************************************//**

@file que/que0que.c

Query graph

Created 5/27/1996 Heikki Tuuri

*******************************************************/

#include "que0que.h"

#ifdef UNIV_NONINL

#include "que0que.ic"

#endif

#include "usr0sess.h"

#include "trx0trx.h"

#include "trx0roll.h"

#include "row0undo.h"

#include "row0ins.h"

#include "row0upd.h"

#include "row0sel.h"

#include "row0purge.h"

#include "dict0crea.h"

#include "log0log.h"

#include "eval0proc.h"

#include "eval0eval.h"

#include "pars0types.h"

#define QUE_PARALLELIZE_LIMIT	(64 * 256 * 256 * 256)

#define QUE_ROUND_ROBIN_LIMIT	(64 * 256 * 256 * 256)

#define QUE_MAX_LOOPS_WITHOUT_CHECK	16

#ifdef UNIV_DEBUG

/* If the following flag is set TRUE, the module will print trace info

of SQL execution in the UNIV_SQL_DEBUG version */

UNIV_INTERN ibool	que_trace_on		= FALSE;

#endif /* UNIV_DEBUG */

/* Short introduction to query graphs

   ==================================

A query graph consists of nodes linked to each other in various ways. The

execution starts at que_run_threads() which takes a que_thr_t parameter.

que_thr_t contains two fields that control query graph execution: run_node

and prev_node. run_node is the next node to execute and prev_node is the

last node executed.

Each node has a pointer to a 'next' statement, i.e., its brother, and a

pointer to its parent node. The next pointer is NULL in the last statement

of a block.

Loop nodes contain a link to the first statement of the enclosed statement

list. While the loop runs, que_thr_step() checks if execution to the loop

node came from its parent or from one of the statement nodes in the loop. If

it came from the parent of the loop node it starts executing the first

statement node in the loop. If it came from one of the statement nodes in

the loop, then it checks if the statement node has another statement node

following it, and runs it if so.

To signify loop ending, the loop statements (see e.g. while_step()) set

que_thr_t->run_node to the loop node's parent node. This is noticed on the

next call of que_thr_step() and execution proceeds to the node pointed to by

the loop node's 'next' pointer.

For example, the code:

X := 1;

WHILE X < 5 LOOP

 X := X + 1;

 X := X + 1;

X := 5

will result in the following node hierarchy, with the X-axis indicating

'next' links and the Y-axis indicating parent/child links:

A - W - A

    |

    |

    A - A

A = assign_node_t, W = while_node_t. */

/* How a stored procedure containing COMMIT or ROLLBACK commands

is executed?

The commit or rollback can be seen as a subprocedure call.

The problem is that if there are several query threads

currently running within the transaction, their action could

mess the commit or rollback operation. Or, at the least, the

operation would be difficult to visualize and keep in control.

Therefore the query thread requesting a commit or a rollback

sends to the transaction a signal, which moves the transaction

to TRX_QUE_SIGNALED state. All running query threads of the

transaction will eventually notice that the transaction is now in

this state and voluntarily suspend themselves. Only the last

query thread which suspends itself will trigger handling of

the signal.

When the transaction starts to handle a rollback or commit

signal, it builds a query graph which, when executed, will

roll back or commit the incomplete transaction. The transaction

is moved to the TRX_QUE_ROLLING_BACK or TRX_QUE_COMMITTING state.

If specified, the SQL cursors opened by the transaction are closed.

When the execution of the graph completes, it is like returning

from a subprocedure: the query thread which requested the operation

starts running again. */

/**********************************************************************//**

Moves a thread from another state to the QUE_THR_RUNNING state. Increments

the n_active_thrs counters of the query graph and transaction.

***NOTE***: This is the only function in which such a transition is allowed

to happen! */

static

void

que_thr_move_to_run_state(

/*======================*/

	que_thr_t*	thr);	/*!< in: an query thread */

/***********************************************************************//**

Adds a query graph to the session's list of graphs. */

UNIV_INTERN

void

que_graph_publish(

/*==============*/

	que_t*	graph,	/*!< in: graph */

	sess_t*	sess)	/*!< in: session */

{

	ut_ad(mutex_own(&kernel_mutex));

	UT_LIST_ADD_LAST(graphs, sess->graphs, graph);

}

/***********************************************************************//**

Creates a query graph fork node.

@return	own: fork node */

UNIV_INTERN

que_fork_t*

que_fork_create(

/*============*/

	que_t*		graph,		/*!< in: graph, if NULL then this

					fork node is assumed to be the

					graph root */

	que_node_t*	parent,		/*!< in: parent node */

	ulint		fork_type,	/*!< in: fork type */

	mem_heap_t*	heap)		/*!< in: memory heap where created */

{

	que_fork_t*	fork;

	ut_ad(heap);

	fork = static_cast<que_fork_t *>(mem_heap_alloc(heap, sizeof(que_fork_t)));

	fork->common.type = QUE_NODE_FORK;

	fork->n_active_thrs = 0;

	fork->state = QUE_FORK_COMMAND_WAIT;

	if (graph != NULL) {

		fork->graph = graph;

	} else {

		fork->graph = fork;

	}

	fork->common.parent = parent;

	fork->fork_type = fork_type;

	fork->caller = NULL;

	UT_LIST_INIT(fork->thrs);

	fork->sym_tab = NULL;

	fork->info = NULL;

	fork->heap = heap;

	return(fork);

}

/***********************************************************************//**

Creates a query graph thread node.

@return	own: query thread node */

UNIV_INTERN

que_thr_t*

que_thr_create(

/*===========*/

	que_fork_t*	parent,	/*!< in: parent node, i.e., a fork node */

	mem_heap_t*	heap)	/*!< in: memory heap where created */

{

	que_thr_t*	thr;

	ut_ad(parent && heap);

	thr = static_cast<que_thr_t *>(mem_heap_alloc(heap, sizeof(que_thr_t)));

	thr->common.type = QUE_NODE_THR;

	thr->common.parent = parent;

	thr->magic_n = QUE_THR_MAGIC_N;

	thr->graph = parent->graph;

	thr->state = QUE_THR_COMMAND_WAIT;

	thr->is_active = FALSE;

	thr->run_node = NULL;

	thr->resource = 0;

	thr->lock_state = QUE_THR_LOCK_NOLOCK;

	UT_LIST_ADD_LAST(thrs, parent->thrs, thr);

	return(thr);

}

/**********************************************************************//**

Moves a suspended query thread to the QUE_THR_RUNNING state and may release

a single worker thread to execute it. This function should be used to end

the wait state of a query thread waiting for a lock or a stored procedure

completion. */

UNIV_INTERN

void

que_thr_end_wait(

/*=============*/

	que_thr_t*	thr,		/*!< in: query thread in the

					QUE_THR_LOCK_WAIT,

					or QUE_THR_PROCEDURE_WAIT, or

					QUE_THR_SIG_REPLY_WAIT state */

	que_thr_t**	next_thr)	/*!< in/out: next query thread to run;

					if the value which is passed in is

					a pointer to a NULL pointer, then the

					calling function can start running

					a new query thread; if NULL is passed

					as the parameter, it is ignored */

{

	ibool	was_active;

	ut_ad(mutex_own(&kernel_mutex));

	ut_ad(thr);

	ut_ad((thr->state == QUE_THR_LOCK_WAIT)

	      || (thr->state == QUE_THR_PROCEDURE_WAIT)

	      || (thr->state == QUE_THR_SIG_REPLY_WAIT));

	ut_ad(thr->run_node);

	thr->prev_node = thr->run_node;

	was_active = thr->is_active;

	que_thr_move_to_run_state(thr);

	if (was_active) {

		return;

	}

	if (next_thr && *next_thr == NULL) {

		*next_thr = thr;

	} else {

		ut_a(0);

		srv_que_task_enqueue_low(thr);

	}

}

/**********************************************************************//**

Same as que_thr_end_wait, but no parameter next_thr available. */

UNIV_INTERN

void

que_thr_end_wait_no_next_thr(

/*=========================*/

	que_thr_t*	thr)	/*!< in: query thread in the QUE_THR_LOCK_WAIT,

				or QUE_THR_PROCEDURE_WAIT, or

				QUE_THR_SIG_REPLY_WAIT state */

{

	ibool	was_active;

	ut_a(thr->state == QUE_THR_LOCK_WAIT);	/* In MySQL this is the

						only possible state here */

	ut_ad(mutex_own(&kernel_mutex));

	ut_ad(thr);

	ut_ad((thr->state == QUE_THR_LOCK_WAIT)

	      || (thr->state == QUE_THR_PROCEDURE_WAIT)

	      || (thr->state == QUE_THR_SIG_REPLY_WAIT));

	was_active = thr->is_active;

	que_thr_move_to_run_state(thr);

	if (was_active) {

		return;

	}

	/* In MySQL we let the OS thread (not just the query thread) to wait

	for the lock to be released: */

	srv_release_mysql_thread_if_suspended(thr);

	/* srv_que_task_enqueue_low(thr); */

}

/**********************************************************************//**

Inits a query thread for a command. */

UNIV_INLINE

void

que_thr_init_command(

/*=================*/

	que_thr_t*	thr)	/*!< in: query thread */

{

	thr->run_node = thr;

	thr->prev_node = thr->common.parent;

	que_thr_move_to_run_state(thr);

}

/**********************************************************************//**

Starts execution of a command in a query fork. Picks a query thread which

is not in the QUE_THR_RUNNING state and moves it to that state. If none

can be chosen, a situation which may arise in parallelized fetches, NULL

is returned.

@return a query thread of the graph moved to QUE_THR_RUNNING state, or

NULL; the query thread should be executed by que_run_threads by the

caller */

UNIV_INTERN

que_thr_t*

que_fork_start_command(

/*===================*/

	que_fork_t*	fork)	/*!< in: a query fork */

{

	que_thr_t*	thr;

	que_thr_t*	suspended_thr = NULL;

	que_thr_t*	completed_thr = NULL;

	fork->state = QUE_FORK_ACTIVE;

	fork->last_sel_node = NULL;

	suspended_thr = NULL;

	completed_thr = NULL;

	/* Choose the query thread to run: usually there is just one thread,

	but in a parallelized select, which necessarily is non-scrollable,

	there may be several to choose from */

	/* First we try to find a query thread in the QUE_THR_COMMAND_WAIT

	state. Then we try to find a query thread in the QUE_THR_SUSPENDED

	state, finally we try to find a query thread in the QUE_THR_COMPLETED

	state */

	thr = UT_LIST_GET_FIRST(fork->thrs);

	/* We make a single pass over the thr list within which we note which

	threads are ready to run. */

	while (thr) {

		switch (thr->state) {

		case QUE_THR_COMMAND_WAIT:

			/* We have to send the initial message to query thread

			to start it */

			que_thr_init_command(thr);

			return(thr);

		case QUE_THR_SUSPENDED:

			/* In this case the execution of the thread was

			suspended: no initial message is needed because

			execution can continue from where it was left */

			if (!suspended_thr) {

				suspended_thr = thr;

			}

			break;

		case QUE_THR_COMPLETED:

			if (!completed_thr) {

				completed_thr = thr;

			}

			break;

		case QUE_THR_LOCK_WAIT:

			ut_error;

		}

		thr = UT_LIST_GET_NEXT(thrs, thr);

	}

	if (suspended_thr) {

		thr = suspended_thr;

		que_thr_move_to_run_state(thr);

	} else if (completed_thr) {

		thr = completed_thr;

		que_thr_init_command(thr);

	}

	return(thr);

}

/**********************************************************************//**

After signal handling is finished, returns control to a query graph error

handling routine. (Currently, just returns the control to the root of the

graph so that the graph can communicate an error message to the client.) */

UNIV_INTERN

void

que_fork_error_handle(

/*==================*/

	trx_t*	/*trx __attribute__((unused))*/,	/*!< in: trx */

	que_t*	fork)	/*!< in: query graph which was run before signal

			handling started, NULL not allowed */

{

	que_thr_t*	thr;

	ut_ad(mutex_own(&kernel_mutex));

	ut_ad(trx->sess->state == SESS_ERROR);

	ut_ad(UT_LIST_GET_LEN(trx->reply_signals) == 0);

	ut_ad(UT_LIST_GET_LEN(trx->wait_thrs) == 0);

	thr = UT_LIST_GET_FIRST(fork->thrs);

	while (thr != NULL) {

		ut_ad(!thr->is_active);

		ut_ad(thr->state != QUE_THR_SIG_REPLY_WAIT);

		ut_ad(thr->state != QUE_THR_LOCK_WAIT);

		thr->run_node = thr;

		thr->prev_node = thr->child;

		thr->state = QUE_THR_COMPLETED;

		thr = UT_LIST_GET_NEXT(thrs, thr);

	}

	thr = UT_LIST_GET_FIRST(fork->thrs);

	que_thr_move_to_run_state(thr);

	ut_a(0);

	srv_que_task_enqueue_low(thr);

}

/****************************************************************//**

Tests if all the query threads in the same fork have a given state.

@return TRUE if all the query threads in the same fork were in the

given state */

UNIV_INLINE

ibool

que_fork_all_thrs_in_state(

/*=======================*/

	que_fork_t*	fork,	/*!< in: query fork */

	ulint		state)	/*!< in: state */

{

	que_thr_t*	thr_node;

	thr_node = UT_LIST_GET_FIRST(fork->thrs);

	while (thr_node != NULL) {

		if (thr_node->state != state) {

			return(FALSE);

		}

		thr_node = UT_LIST_GET_NEXT(thrs, thr_node);

	}

	return(TRUE);

}

/**********************************************************************//**

Calls que_graph_free_recursive for statements in a statement list. */

static

void

que_graph_free_stat_list(

/*=====================*/

	que_node_t*	node)	/*!< in: first query graph node in the list */

{

	while (node) {

		que_graph_free_recursive(node);

		node = que_node_get_next(node);

	}

}

/**********************************************************************//**

Frees a query graph, but not the heap where it was created. Does not free

explicit cursor declarations, they are freed in que_graph_free. */

UNIV_INTERN

void

que_graph_free_recursive(

/*=====================*/

	que_node_t*	node)	/*!< in: query graph node */

{

	que_fork_t*	fork;

	que_thr_t*	thr;

	undo_node_t*	undo;

	sel_node_t*	sel;

	ins_node_t*	ins;

	upd_node_t*	upd;

	tab_node_t*	cre_tab;

	ind_node_t*	cre_ind;

	purge_node_t*	purge;

	if (node == NULL) {

		return;

	}

	switch (que_node_get_type(node)) {

	case QUE_NODE_FORK:

		fork = static_cast<que_fork_t *>(node);

		thr = UT_LIST_GET_FIRST(fork->thrs);

		while (thr) {

			que_graph_free_recursive(thr);

			thr = UT_LIST_GET_NEXT(thrs, thr);

		}

		break;

	case QUE_NODE_THR:

		thr = static_cast<que_thr_t *>(node);

		if (thr->magic_n != QUE_THR_MAGIC_N) {

			fprintf(stderr,

				"que_thr struct appears corrupt;"

				" magic n %lu\n",

				(unsigned long) thr->magic_n);

			mem_analyze_corruption(thr);

			ut_error;

		}

		thr->magic_n = QUE_THR_MAGIC_FREED;

		que_graph_free_recursive(thr->child);

		break;

	case QUE_NODE_UNDO:

		undo = static_cast<undo_node_t *>(node);

		mem_heap_free(undo->heap);

		break;

	case QUE_NODE_SELECT:

		sel = static_cast<sel_node_t *>(node);

		sel_node_free_private(sel);

		break;

	case QUE_NODE_INSERT:

		ins = static_cast<ins_node_t *>(node);

		que_graph_free_recursive(ins->select);

		mem_heap_free(ins->entry_sys_heap);

		break;

	case QUE_NODE_PURGE:

		purge = static_cast<purge_node_t *>(node);

		mem_heap_free(purge->heap);

		break;

	case QUE_NODE_UPDATE:

		upd = static_cast<upd_node_t *>(node);

		if (upd->in_mysql_interface) {

			btr_pcur_free_for_mysql(upd->pcur);

		}

		que_graph_free_recursive(upd->cascade_node);

		if (upd->cascade_heap) {

			mem_heap_free(upd->cascade_heap);

		}

		que_graph_free_recursive(upd->select);

		mem_heap_free(upd->heap);

		break;

	case QUE_NODE_CREATE_TABLE:

		cre_tab = static_cast<tab_node_t *>(node);

		que_graph_free_recursive(cre_tab->tab_def);

		que_graph_free_recursive(cre_tab->col_def);

		que_graph_free_recursive(cre_tab->commit_node);

		mem_heap_free(cre_tab->heap);

		break;

	case QUE_NODE_CREATE_INDEX:

		cre_ind = static_cast<ind_node_t *>(node);

		que_graph_free_recursive(cre_ind->ind_def);

		que_graph_free_recursive(cre_ind->field_def);

		que_graph_free_recursive(cre_ind->commit_node);

		mem_heap_free(cre_ind->heap);

		break;

	case QUE_NODE_PROC:

		que_graph_free_stat_list(((proc_node_t*)node)->stat_list);

		break;

	case QUE_NODE_IF:

		que_graph_free_stat_list(((if_node_t*)node)->stat_list);

		que_graph_free_stat_list(((if_node_t*)node)->else_part);

		que_graph_free_stat_list(((if_node_t*)node)->elsif_list);

		break;

	case QUE_NODE_ELSIF:

		que_graph_free_stat_list(((elsif_node_t*)node)->stat_list);

		break;

	case QUE_NODE_WHILE:

		que_graph_free_stat_list(((while_node_t*)node)->stat_list);

		break;

	case QUE_NODE_FOR:

		que_graph_free_stat_list(((for_node_t*)node)->stat_list);

		break;

	case QUE_NODE_ASSIGNMENT:

	case QUE_NODE_EXIT:

	case QUE_NODE_RETURN:

	case QUE_NODE_COMMIT:

	case QUE_NODE_ROLLBACK:

	case QUE_NODE_LOCK:

	case QUE_NODE_FUNC:

	case QUE_NODE_ORDER:

	case QUE_NODE_ROW_PRINTF:

	case QUE_NODE_OPEN:

	case QUE_NODE_FETCH:

		/* No need to do anything */

		break;

	default:

		fprintf(stderr,

			"que_node struct appears corrupt; type %lu\n",

			(unsigned long) que_node_get_type(node));

		mem_analyze_corruption(node);

		ut_error;

	}

}

/**********************************************************************//**

Frees a query graph. */

UNIV_INTERN

void

que_graph_free(

/*===========*/

	que_t*	graph)	/*!< in: query graph; we assume that the memory

			heap where this graph was created is private

			to this graph: if not, then use

			que_graph_free_recursive and free the heap

			afterwards! */

{

	ut_ad(graph);

	if (graph->sym_tab) {

		/* The following call frees dynamic memory allocated

		for variables etc. during execution. Frees also explicit

		cursor definitions. */

		sym_tab_free_private(graph->sym_tab);

	}

	if (graph->info && graph->info->graph_owns_us) {

		pars_info_free(graph->info);

	}

	que_graph_free_recursive(graph);

	mem_heap_free(graph->heap);

}

/****************************************************************//**

Performs an execution step on a thr node.

@return	query thread to run next, or NULL if none */

static

que_thr_t*

que_thr_node_step(

/*==============*/

	que_thr_t*	thr)	/*!< in: query thread where run_node must

				be the thread node itself */

{

	ut_ad(thr->run_node == thr);

	if (thr->prev_node == thr->common.parent) {

		/* If control to the node came from above, it is just passed

		on */

		thr->run_node = thr->child;

		return(thr);

	}

	mutex_enter(&kernel_mutex);

	if (que_thr_peek_stop(thr)) {

		mutex_exit(&kernel_mutex);

		return(thr);

	}

	/* Thread execution completed */

	thr->state = QUE_THR_COMPLETED;

	mutex_exit(&kernel_mutex);

	return(NULL);

}

/**********************************************************************//**

Moves a thread from another state to the QUE_THR_RUNNING state. Increments

the n_active_thrs counters of the query graph and transaction if thr was

not active.

***NOTE***: This and ..._mysql are  the only functions in which such a

transition is allowed to happen! */

static

void

que_thr_move_to_run_state(

/*======================*/

	que_thr_t*	thr)	/*!< in: an query thread */

{

	trx_t*	trx;

	ut_ad(thr->state != QUE_THR_RUNNING);

	trx = thr_get_trx(thr);

	if (!thr->is_active) {

		(thr->graph)->n_active_thrs++;

		trx->n_active_thrs++;

		thr->is_active = TRUE;

		ut_ad((thr->graph)->n_active_thrs == 1);

		ut_ad(trx->n_active_thrs == 1);

	}

	thr->state = QUE_THR_RUNNING;

}

/**********************************************************************//**

Decrements the query thread reference counts in the query graph and the

transaction. May start signal handling, e.g., a rollback.

*** NOTE ***:

This and que_thr_stop_for_mysql are the only functions where the reference

count can be decremented and this function may only be called from inside

que_run_threads or que_thr_check_if_switch! These restrictions exist to make

the rollback code easier to maintain. */

static

void

que_thr_dec_refer_count(

/*====================*/

	que_thr_t*	thr,		/*!< in: query thread */

	que_thr_t**	next_thr)	/*!< in/out: next query thread to run;

					if the value which is passed in is

					a pointer to a NULL pointer, then the

					calling function can start running

					a new query thread */

{

	que_fork_t*	fork;

	trx_t*		trx;

	ulint		fork_type;

	ibool		stopped;

	fork = static_cast<que_fork_t *>(thr->common.parent);

	trx = thr_get_trx(thr);

	mutex_enter(&kernel_mutex);

	ut_a(thr->is_active);

	if (thr->state == QUE_THR_RUNNING) {

		stopped = que_thr_stop(thr);

		if (!stopped) {

			/* The reason for the thr suspension or wait was

			already canceled before we came here: continue

			running the thread */

			/* fputs("!!!!!!!! Wait already ended: continue thr\n",

			stderr); */

			if (next_thr && *next_thr == NULL) {

				/* Normally srv_suspend_mysql_thread resets

				the state to DB_SUCCESS before waiting, but

				in this case we have to do it here,

				otherwise nobody does it. */

				trx->error_state = DB_SUCCESS;

				*next_thr = thr;

			} else {

				ut_error;

				srv_que_task_enqueue_low(thr);

			}

			mutex_exit(&kernel_mutex);

			return;

		}

	}

	ut_ad(fork->n_active_thrs == 1);

	ut_ad(trx->n_active_thrs == 1);

	fork->n_active_thrs--;

	trx->n_active_thrs--;

	thr->is_active = FALSE;

	if (trx->n_active_thrs > 0) {

		mutex_exit(&kernel_mutex);

		return;

	}

	fork_type = fork->fork_type;

	/* Check if all query threads in the same fork are completed */

	if (que_fork_all_thrs_in_state(fork, QUE_THR_COMPLETED)) {

		switch (fork_type) {

		case QUE_FORK_ROLLBACK:

			/* This is really the undo graph used in rollback,

			no roll_node in this graph */

			ut_ad(UT_LIST_GET_LEN(trx->signals) > 0);

			ut_ad(trx->handling_signals == TRUE);

			trx_finish_rollback_off_kernel(fork, trx, next_thr);

			break;

		case QUE_FORK_PURGE:

		case QUE_FORK_RECOVERY:

		case QUE_FORK_MYSQL_INTERFACE: