item_subselect.cc source code [MariaDB/sql/item_subselect.cc]

1	/ Copyright (c) 2002, 2016, Oracle and/or its affiliates.*
2	Copyright (c) 2010, 2016, MariaDB
3
4	This program is free software; you can redistribute it and/or modify
5	it under the terms of the GNU General Public License as published by
6	the Free Software Foundation; version 2 of the License.
7
8	This program is distributed in the hope that it will be useful,
9	but WITHOUT ANY WARRANTY; without even the implied warranty of
10	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11	GNU General Public License for more details.
12
13	You should have received a copy of the GNU General Public License
14	along with this program; if not, write to the Free Software
15	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA /*
16
17	/**
18	@file
19
20	@brief
21	subselect Item
22
23	@todo
24	- add function from mysql_select that use JOIN as parameter to JOIN*
25	methods (sql_select.h/sql_select.cc)
26	*/
27
28	#ifdef USE_PRAGMA_IMPLEMENTATION
29	#pragma implementation // gcc: Class implementation
30	#endif
31
32	#include "mariadb.h"
33	#include "sql_priv.h"
34	/*
35	It is necessary to include set_var.h instead of item.h because there
36	are dependencies on include order for set_var.h and item.h. This
37	will be resolved later.
38	*/
39	#include "sql_class.h" // set_var.h: THD
40	#include "set_var.h"
41	#include "sql_select.h"
42	#include "sql_parse.h" // check_stack_overrun
43	#include "sql_cte.h"
44	#include "sql_test.h"
45
46	double get_post_group_estimate(JOIN* join, double join_op_rows);
47
48	LEX_CSTRING exists_outer_expr_name= { STRING_WITH_LEN("<exists outer expr>") };
49
50	int check_and_do_in_subquery_rewrites(JOIN *join);
51
52	Item_subselect::Item_subselect(THD *thd_arg):
53	Item_result_field (thd_arg), Used_tables_and_const_cache (),
54	value_assigned(`0`), own_engine(`0`), thd(`0`), old_engine(`0`),
55	have_to_be_excluded(`0`),
56	inside_first_fix_fields(`0`), done_first_fix_fields(FALSE),
57	expr_cache(`0`), forced_const(FALSE), substitution(`0`), engine(`0`), eliminated(FALSE),
58	changed(`0`), is_correlated(FALSE), with_recursive_reference(`0`)
59	{
60	DBUG_ENTER("Item_subselect::Item_subselect");
61	DBUG_PRINT("enter", ("this: %p", this));
62	sortbuffer.str= `0`;
63
64	#ifndef DBUG_OFF
65	exec_counter= `0`;
66	#endif
67	reset();
68	/*
69	Item value is NULL if select_result_interceptor didn't change this value
70	(i.e. some rows will be found returned)
71	*/
72	null_value= TRUE;
73	DBUG_VOID_RETURN;
74	}
75
76
77	void Item_subselect::init(st_select_lex *select_lex,
78	select_result_interceptor *result)
79	{
80	/*
81	Please see Item_singlerow_subselect::invalidate_and_restore_select_lex(),
82	which depends on alterations to the parse tree implemented here.
83	*/
84
85	DBUG_ENTER("Item_subselect::init");
86	DBUG_PRINT("enter", ("select_lex: %p this: %p",
87	select_lex, this));
88	unit= select_lex->master_unit();
89
90	if (unit->item)
91	{
92	engine= unit->item->engine;
93	parsing_place= unit->item->parsing_place;
94	if (unit->item->substype() == EXISTS_SUBS &&
95	((Item_exists_subselect *)unit->item)->exists_transformed)
96	{
97	/ it is permanent transformation of EXISTS to IN /
98	unit->item= this;
99	engine->change_result(this, result, FALSE);
100	}
101	else
102	{
103	/*
104	Item can be changed in JOIN::prepare while engine in JOIN::optimize
105	=> we do not copy old_engine here
106	*/
107	unit->thd->change_item_tree((Item)&unit->item, this**);
108	engine->change_result(this, result, TRUE);
109	}
110	}
111	else
112	{
113	SELECT_LEX *outer_select= unit->outer_select();
114	/*
115	do not take into account expression inside aggregate functions because
116	they can access original table fields
117	*/
118	parsing_place= (outer_select->in_sum_expr ?
119	NO_MATTER :
120	outer_select->parsing_place);
121	if (unit->is_unit_op() && unit->first_select()->next_select())
122	engine= new subselect_union_engine (unit, result, this);
123	else
124	engine= new subselect_single_select_engine (select_lex, result, this);
125	}
126	{
127	SELECT_LEX *upper= unit->outer_select();
128	if (upper->parsing_place == IN_HAVING)
129	upper->subquery_in_having= `1`;
130	/ The subquery is an expression cache candidate /
131	upper->expr_cache_may_be_used[upper->parsing_place]= TRUE;
132	}
133	DBUG_PRINT("info", ("engine: %p", engine));
134	DBUG_VOID_RETURN;
135	}
136
137	st_select_lex *
138	Item_subselect::get_select_lex()
139	{
140	return unit->first_select();
141	}
142
143	void Item_subselect::cleanup()
144	{
145	DBUG_ENTER("Item_subselect::cleanup");
146	Item_result_field::cleanup();
147	if (old_engine)
148	{
149	if (engine)
150	engine->cleanup();
151	engine= old_engine;
152	old_engine= `0`;
153	}
154	if (engine)
155	engine->cleanup();
156	reset();
157	filesort_buffer.free_sort_buffer();
158	my_free(sortbuffer.str);
159	sortbuffer.str= `0`;
160
161	value_assigned= `0`;
162	expr_cache= `0`;
163	forced_const= FALSE;
164	DBUG_PRINT("info", ("exec_counter: %d", exec_counter));
165	#ifndef DBUG_OFF
166	exec_counter= `0`;
167	#endif
168	DBUG_VOID_RETURN;
169	}
170
171
172	void Item_singlerow_subselect::cleanup()
173	{
174	DBUG_ENTER("Item_singlerow_subselect::cleanup");
175	value= `0`; row= `0`;
176	Item_subselect::cleanup();
177	DBUG_VOID_RETURN;
178	}
179
180
181	void Item_in_subselect::cleanup()
182	{
183	DBUG_ENTER("Item_in_subselect::cleanup");
184	if (left_expr_cache)
185	{
186	left_expr_cache->delete_elements();
187	delete left_expr_cache;
188	left_expr_cache= NULL;
189	}
190	/*
191	TODO: This breaks the commented assert in add_strategy().
192	in_strategy&= ~SUBS_STRATEGY_CHOSEN;
193	*/
194	first_execution= TRUE;
195	pushed_cond_guards= NULL;
196	Item_subselect::cleanup();
197	DBUG_VOID_RETURN;
198	}
199
200
201	void Item_allany_subselect::cleanup()
202	{
203	/*
204	The MAX/MIN transformation through injection is reverted through the
205	change_item_tree() mechanism. Revert the select_lex object of the
206	query to its initial state.
207	*/
208	for (SELECT_LEX *sl= unit->first_select();
209	sl; sl= sl->next_select())
210	if (test_set_strategy(SUBS_MAXMIN_INJECTED))
211	sl->with_sum_func= false;
212	Item_in_subselect::cleanup();
213	}
214
215
216	Item_subselect::~Item_subselect()
217	{
218	DBUG_ENTER("Item_subselect::~Item_subselect");
219	DBUG_PRINT("enter", ("this: %p", this));
220	if (own_engine)
221	delete engine;
222	else
223	engine->cleanup();
224	engine= NULL;
225	DBUG_VOID_RETURN;
226	}
227
228	bool
229	Item_subselect::select_transformer(JOIN *join)
230	{
231	DBUG_ENTER("Item_subselect::select_transformer");
232	DBUG_ASSERT(thd == join->thd);
233	DBUG_RETURN(false);
234	}
235
236
237	bool Item_subselect::fix_fields(THD thd_param, Item *ref)
238	{
239	char const *save_where= thd_param->where;
240	uint8 uncacheable;
241	bool res;
242
243	thd= thd_param;
244
245	DBUG_ASSERT(unit->thd == thd);
246
247	status_var_increment(thd_param->status_var.feature_subquery);
248
249	DBUG_ASSERT(fixed == `0`);
250	engine->set_thd((thd= thd_param));
251	if (!done_first_fix_fields)
252	{
253	done_first_fix_fields= TRUE;
254	inside_first_fix_fields= TRUE;
255	upper_refs.empty();
256	/*
257	psergey-todo: remove _first_fix_fields calls, we need changes on every
258	execution
259	*/
260	}
261
262	eliminated= FALSE;
263	parent_select= thd_param->lex->current_select;
264
265	if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
266	return TRUE;
267
268	for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
269	{
270	if (sl->tvc)
271	{
272	wrap_tvc_in_derived_table(thd, sl);
273	}
274	}
275
276	if (!(res= engine->prepare(thd)))
277	{
278	// all transformation is done (used by prepared statements)
279	changed= `1`;
280	inside_first_fix_fields= FALSE;
281
282	/*
283	Substitute the current item with an Item_in_optimizer that was
284	created by Item_in_subselect::select_in_like_transformer and
285	call fix_fields for the substituted item which in turn calls
286	engine->prepare for the subquery predicate.
287	*/
288	if (substitution)
289	{
290	/*
291	If the top item of the WHERE/HAVING condition changed,
292	set correct WHERE/HAVING for PS.
293	*/
294	if (unit->outer_select()->where == (*ref))
295	unit->outer_select()->where= substitution;
296	else if (unit->outer_select()->having == (*ref))
297	unit->outer_select()->having= substitution;
298
299	(*ref)= substitution;
300	substitution->name = name;
301	if (have_to_be_excluded)
302	engine->exclude();
303	substitution= `0`;
304	thd->where= "checking transformed subquery";
305	if (!(*ref)->fixed)
306	res= (*ref)->fix_fields(thd, ref);
307	goto end;
308
309	}
310	// Is it one field subselect?
311	if (engine->cols() > max_columns)
312	{
313	my_error(ER_OPERAND_COLUMNS, MYF(`0`), `1`);
314
315	goto end;
316	}
317	fix_length_and_dec();
318	}
319	else
320	goto end;
321
322	if ((uncacheable= engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
323	with_recursive_reference)
324	{
325	const_item_cache= `0`;
326	if (uncacheable & UNCACHEABLE_RAND)
327	used_tables_cache\|= RAND_TABLE_BIT;
328	}
329	fixed= `1`;
330
331	end:
332	done_first_fix_fields= FALSE;
333	inside_first_fix_fields= FALSE;
334	thd->where= save_where;
335	return res;
336	}
337
338
339	bool Item_subselect::enumerate_field_refs_processor(void *arg)
340	{
341	List_iterator<Ref_to_outside> it(upper_refs);
342	Ref_to_outside *upper;
343
344	while ((upper= it ++))
345	{
346	if (upper->item &&
347	upper->item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
348	return TRUE;
349	}
350	return FALSE;
351	}
352
353	bool Item_subselect::mark_as_eliminated_processor(void *arg)
354	{
355	eliminated= TRUE;
356	return FALSE;
357	}
358
359
360	/**
361	Remove a subselect item from its unit so that the unit no longer
362	represents a subquery.
363
364	@param arg unused parameter
365
366	@return
367	FALSE to force the evaluation of the processor for the subsequent items.
368	*/
369
370	bool Item_subselect::eliminate_subselect_processor(void *arg)
371	{
372	unit->item= NULL;
373	unit->exclude_from_tree();
374	eliminated= TRUE;
375	return FALSE;
376	}
377
378
379	/**
380	Adjust the master select of the subquery to be the fake_select which
381	represents the whole UNION right above the subquery, instead of the
382	last query of the UNION.
383
384	@param arg pointer to the fake select
385
386	@return
387	FALSE to force the evaluation of the processor for the subsequent items.
388	*/
389
390	bool Item_subselect::set_fake_select_as_master_processor(void *arg)
391	{
392	SELECT_LEX fake_select= (SELECT_LEX) arg;
393	/*
394	Move the st_select_lex_unit of a subquery from a global ORDER BY clause to
395	become a direct child of the fake_select of a UNION. In this way the
396	ORDER BY that is applied to the temporary table that contains the result of
397	the whole UNION, and all columns in the subquery are resolved against this
398	table. The transformation is applied only for immediate child subqueries of
399	a UNION query.
400	*/
401	if (unit->outer_select()->master_unit()->fake_select_lex == fake_select)
402	{
403	/*
404	Set the master of the subquery to be the fake select (i.e. the whole
405	UNION), instead of the last query in the UNION.
406	*/
407	fake_select->add_slave(unit);
408	DBUG_ASSERT(unit->outer_select() == fake_select);
409	/ Adjust the name resolution context hierarchy accordingly. /
410	for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
411	sl->context.outer_context= &(fake_select->context);
412	/*
413	Undo Item_subselect::eliminate_subselect_processor because at that phase
414	we don't know yet that the ORDER clause will be moved to the fake select.
415	*/
416	unit->item= this;
417	eliminated= FALSE;
418	}
419	return FALSE;
420	}
421
422
423	bool Item_subselect::mark_as_dependent(THD thd, st_select_lex select,
424	Item *item)
425	{
426	if (inside_first_fix_fields)
427	{
428	is_correlated= TRUE;
429	Ref_to_outside *upper;
430	if (!(upper= new (thd->stmt_arena->mem_root) Ref_to_outside ()))
431	return TRUE;
432	upper->select= select;
433	upper->item= item;
434	if (upper_refs.push_back(upper, thd->stmt_arena->mem_root))
435	return TRUE;
436	}
437	return FALSE;
438	}
439
440
441	/*
442	Adjust attributes after our parent select has been merged into grandparent
443
444	DESCRIPTION
445	Subquery is a composite object which may be correlated, that is, it may
446	have
447	1. references to tables of the parent select (i.e. one that has the clause
448	with the subquery predicate)
449	2. references to tables of the grandparent select
450	3. references to tables of further ancestors.
451
452	Before the pullout, this item indicates:
453	- #1 with table bits in used_tables()
454	- #2 and #3 with OUTER_REF_TABLE_BIT.
455
456	After parent has been merged with grandparent:
457	- references to parent and grandparent tables should be indicated with
458	table bits.
459	- references to greatgrandparent and further ancestors - with
460	OUTER_REF_TABLE_BIT.
461	*/
462
463	void Item_subselect::fix_after_pullout(st_select_lex *new_parent,
464	Item *ref, bool* merge)
465	{
466	recalc_used_tables(new_parent, TRUE);
467	parent_select= new_parent;
468	}
469
470
471	class Field_fixer: public Field_enumerator
472	{
473	public:
474	table_map used_tables; / Collect used_tables here /
475	st_select_lex new_parent; /* Select we're in /
476	virtual void visit_field(Item_field *item)
477	{
478	//for (TABLE_LIST tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local)*
479	//{
480	// if (tbl->table == field->table)
481	// {
482	used_tables\|= item->field->table->map;
483	// return;
484	// }
485	//}
486	//used_tables \|= OUTER_REF_TABLE_BIT;
487	}
488	};
489
490
491	/*
492	Recalculate used_tables_cache
493	*/
494
495	void Item_subselect::recalc_used_tables(st_select_lex *new_parent,
496	bool after_pullout)
497	{
498	List_iterator_fast<Ref_to_outside> it(upper_refs);
499	Ref_to_outside *upper;
500	DBUG_ENTER("recalc_used_tables");
501
502	used_tables_cache= `0`;
503	while ((upper= it ++))
504	{
505	bool found= FALSE;
506	/*
507	Check if
508	1. the upper reference refers to the new immediate parent select, or
509	2. one of the further ancestors.
510
511	We rely on the fact that the tree of selects is modified by some kind of
512	'flattening', i.e. a process where child selects are merged into their
513	parents.
514	The merged selects are removed from the select tree but keep pointers to
515	their parents.
516	*/
517	for (st_select_lex *sel= upper->select; sel; sel= sel->outer_select())
518	{
519	/*
520	If we've reached the new parent select by walking upwards from
521	reference's original select, this means that the reference is now
522	referring to the direct parent:
523	*/
524	if (sel == new_parent)
525	{
526	found= TRUE;
527	/*
528	upper->item may be NULL when we've referred to a grouping function,
529	in which case we don't care about what it's table_map really is,
530	because item->with_sum_func==1 will ensure correct placement of the
531	item.
532	*/
533	if (upper->item)
534	{
535	// Now, iterate over fields and collect used_tables() attribute:
536	Field_fixer fixer;
537	fixer.used_tables= `0`;
538	fixer.new_parent= new_parent;
539	upper->item->walk(&Item::enumerate_field_refs_processor, `0`, &fixer);
540	used_tables_cache \|= fixer.used_tables;
541	upper->item->walk(&Item::update_table_bitmaps_processor, FALSE, NULL);
542	/*
543	if (after_pullout)
544	upper->item->fix_after_pullout(new_parent, &(upper->item));
545	upper->item->update_used_tables();
546	*/
547	}
548	}
549	}
550	if (!found)
551	used_tables_cache\|= OUTER_REF_TABLE_BIT;
552	}
553	/*
554	Don't update const_tables_cache yet as we don't yet know which of the
555	parent's tables are constant. Parent will call update_used_tables() after
556	he has done const table detection, and that will be our chance to update
557	const_tables_cache.
558	*/
559	DBUG_PRINT("exit", ("used_tables_cache: %llx", used_tables_cache));
560	DBUG_VOID_RETURN;
561	}
562
563
564	/**
565	Determine if a subquery is expensive to execute during query optimization.
566
567	@details The cost of execution of a subquery is estimated based on an
568	estimate of the number of rows the subquery will access during execution.
569	This measure is used instead of JOIN::read_time, because it is considered
570	to be much more reliable than the cost estimate.
571
572	@return true if the subquery is expensive
573	@return false otherwise
574	*/
575	bool Item_subselect::is_expensive()
576	{
577	double examined_rows= `0`;
578	bool all_are_simple= true;
579
580	/ check extremely simple select /
581	if (!unit->first_select()->next_select()) // no union
582	{
583	/*
584	such single selects works even without optimization because
585	can not makes loops
586	*/
587	SELECT_LEX *sl= unit->first_select();
588	JOIN *join = sl->join;
589	if (join && !join->tables_list && !sl->first_inner_unit())
590	return false;
591	}
592
593
594	for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
595	{
596	JOIN *cur_join= sl->join;
597
598	/ not optimized subquery /
599	if (!cur_join)
600	return true;
601
602	/*
603	If the subquery is not optimised or in the process of optimization
604	it supposed to be expensive
605	*/
606	if (cur_join->optimization_state != JOIN::OPTIMIZATION_DONE)
607	return true;
608
609	if (!cur_join->tables_list && !sl->first_inner_unit())
610	continue;
611
612	/*
613	Subqueries whose result is known after optimization are not expensive.
614	Such subqueries have all tables optimized away, thus have no join plan.
615	*/
616	if ((cur_join->zero_result_cause \|\| !cur_join->tables_list))
617	continue;
618
619	/*
620	This is not simple SELECT in union so we can not go by simple condition
621	*/
622	all_are_simple= false;
623
624	/*
625	If a subquery is not optimized we cannot estimate its cost. A subquery is
626	considered optimized if it has a join plan.
627	*/
628	if (!cur_join->join_tab)
629	return true;
630
631	if (sl->first_inner_unit())
632	{
633	/*
634	Subqueries that contain subqueries are considered expensive.
635	@todo: accumulate the cost of subqueries.
636	*/
637	return true;
638	}
639
640	examined_rows+= cur_join->get_examined_rows();
641	}
642
643	// here we are sure that subquery is optimized so thd is set
644	return !all_are_simple &&
645	(examined_rows > thd->variables.expensive_subquery_limit);
646	}
647
648
649	bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
650	void *argument)
651	{
652	if (!(unit->uncacheable & ~UNCACHEABLE_DEPENDENT) && engine->is_executed() &&
653	!unit->describe)
654	{
655	/*
656	The subquery has already been executed (for real, it wasn't EXPLAIN's
657	fake execution) so it should not matter what it has inside.
658
659	The actual reason for not walking inside is that parts of the subquery
660	(e.g. JTBM join nests and their IN-equality conditions may have been
661	invalidated by irreversible cleanups (those happen after an uncorrelated
662	subquery has been executed).
663	*/
664	return (this->*processor)(argument);
665	}
666
667	if (walk_subquery)
668	{
669	for (SELECT_LEX *lex= unit->first_select(); lex; lex= lex->next_select())
670	{
671	List_iterator<Item> li(lex->item_list);
672	Item *item;
673	ORDER *order;
674
675	if (lex->where && (lex->where)->walk(processor, walk_subquery, argument))
676	return `1`;
677	if (lex->having && (lex->having)->walk(processor, walk_subquery,
678	argument))
679	return `1`;
680	/ TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? /
681
682	while ((item=li ++))
683	{
684	if (item->walk(processor, walk_subquery, argument))
685	return `1`;
686	}
687	for (order= lex->order_list.first ; order; order= order->next)
688	{
689	if ((*order->item)->walk(processor, walk_subquery, argument))
690	return `1`;
691	}
692	for (order= lex->group_list.first ; order; order= order->next)
693	{
694	if ((*order->item)->walk(processor, walk_subquery, argument))
695	return `1`;
696	}
697	}
698	}
699	return (this->*processor)(argument);
700	}
701
702
703	bool Item_subselect::exec()
704	{
705	subselect_engine *org_engine= engine;
706
707	DBUG_ENTER("Item_subselect::exec");
708	DBUG_ASSERT(fixed);
709
710	/*
711	Do not execute subselect in case of a fatal error
712	or if the query has been killed.
713	*/
714	if (unlikely(thd->is_error() \|\| thd->killed))
715	DBUG_RETURN(true);
716
717	DBUG_ASSERT(!thd->lex->context_analysis_only);
718	/*
719	Simulate a failure in sub-query execution. Used to test e.g.
720	out of memory or query being killed conditions.
721	*/
722	DBUG_EXECUTE_IF("subselect_exec_fail", DBUG_RETURN(true););
723
724	bool res= engine->exec();
725
726	#ifndef DBUG_OFF
727	++exec_counter;
728	#endif
729	if (engine != org_engine)
730	{
731	/*
732	If the subquery engine changed during execution due to lazy subquery
733	optimization, or because the original engine found a more efficient other
734	engine, re-execute the subquery with the new engine.
735	*/
736	DBUG_RETURN(exec());
737	}
738	DBUG_RETURN(res);
739	}
740
741
742	void Item_subselect::get_cache_parameters(List<Item> &parameters)
743	{
744	Collect_deps_prm prm= {&parameters, // parameters
745	unit->first_select()->nest_level_base, // nest_level_base
746	`0`, // count
747	unit->first_select()->nest_level, // nest_level
748	TRUE // collect
749	};
750	walk(&Item::collect_outer_ref_processor, TRUE, &prm);
751	}
752
753	int Item_in_subselect::optimize(double out_rows, double* *cost)
754	{
755	int res;
756	DBUG_ENTER("Item_in_subselect::optimize");
757	DBUG_ASSERT(fixed);
758	SELECT_LEX *save_select= thd->lex->current_select;
759	JOIN *join= unit->first_select()->join;
760
761	thd->lex->current_select= join->select_lex;
762	if ((res= join->optimize()))
763	DBUG_RETURN(res);
764
765	/ Calculate #rows and cost of join execution /
766	join->get_partial_cost_and_fanout(join->table_count - join->const_tables,
767	table_map(-`1`),
768	cost, out_rows);
769
770	/*
771	Adjust join output cardinality. There can be these cases:
772	- Have no GROUP BY and no aggregate funcs: we won't get into this
773	function because such join will be processed as a merged semi-join
774	(TODO: does it really mean we don't need to handle such cases here at
775	all? put ASSERT)
776	- Have no GROUP BY but have aggregate funcs: output is 1 record.
777	- Have GROUP BY and have (or not) aggregate funcs: need to adjust output
778	cardinality.
779	*/
780	thd->lex->current_select= save_select;
781	if (!join->group_list && !join->group_optimized_away &&
782	join->tmp_table_param.sum_func_count)
783	{
784	DBUG_PRINT("info",("Materialized join will have only 1 row (it has "
785	"aggregates but no GROUP BY"));
786	*out_rows= `1`;
787	}
788
789	/ Now with grouping /
790	if (join->group_list_for_estimates)
791	{
792	DBUG_PRINT("info",("Materialized join has grouping, trying to estimate it"));
793	double output_rows= get_post_group_estimate(join, *out_rows);
794	DBUG_PRINT("info",("Got value of %g", output_rows));
795	*out_rows= output_rows;
796	}
797
798	DBUG_RETURN(res);
799
800	}
801
802
803	/**
804	Check if an expression cache is needed for this subquery
805
806	@param thd Thread handle
807
808	@details
809	The function checks whether a cache is needed for a subquery and whether
810	the result of the subquery can be put in cache.
811
812	@retval TRUE cache is needed
813	@retval FALSE otherwise
814	*/
815
816	bool Item_subselect::expr_cache_is_needed(THD *thd)
817	{
818	return ((engine->uncacheable() & UNCACHEABLE_DEPENDENT) &&
819	engine->cols() == `1` &&
820	optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
821	!(engine->uncacheable() & (UNCACHEABLE_RAND \|
822	UNCACHEABLE_SIDEEFFECT)) &&
823	!with_recursive_reference);
824	}
825
826
827	/**
828	Check if the left IN argument contains NULL values.
829
830	@retval TRUE there are NULLs
831	@retval FALSE otherwise
832	*/
833
834	inline bool Item_in_subselect::left_expr_has_null()
835	{
836	return (*(optimizer->get_cache()))->null_value;
837	}
838
839
840	/**
841	Check if an expression cache is needed for this subquery
842
843	@param thd Thread handle
844
845	@details
846	The function checks whether a cache is needed for a subquery and whether
847	the result of the subquery can be put in cache.
848
849	@note
850	This method allows many columns in the subquery because it is supported by
851	Item_in_optimizer and result of the IN subquery will be scalar in this
852	case.
853
854	@retval TRUE cache is needed
855	@retval FALSE otherwise
856	*/
857
858	bool Item_in_subselect::expr_cache_is_needed(THD *thd)
859	{
860	return (optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
861	!(engine->uncacheable() & (UNCACHEABLE_RAND \|
862	UNCACHEABLE_SIDEEFFECT)) &&
863	!with_recursive_reference);
864	}
865
866
867	/*
868	Compute the IN predicate if the left operand's cache changed.
869	*/
870
871	bool Item_in_subselect::exec()
872	{
873	DBUG_ENTER("Item_in_subselect::exec");
874	DBUG_ASSERT(fixed);
875	/*
876	Initialize the cache of the left predicate operand. This has to be done as
877	late as now, because Cached_item directly contains a resolved field (not
878	an item, and in some cases (when temp tables are created), these fields
879	end up pointing to the wrong field. One solution is to change Cached_item
880	to not resolve its field upon creation, but to resolve it dynamically
881	from a given Item_ref object.
882	TODO: the cache should be applied conditionally based on:
883	- rules - e.g. only if the left operand is known to be ordered, and/or
884	- on a cost-based basis, that takes into account the cost of a cache
885	lookup, the cache hit rate, and the savings per cache hit.
886	*/
887	if (!left_expr_cache && (test_strategy(SUBS_MATERIALIZATION)))
888	init_left_expr_cache();
889
890	/*
891	If the new left operand is already in the cache, reuse the old result.
892	Use the cached result only if this is not the first execution of IN
893	because the cache is not valid for the first execution.
894	*/
895	if (!first_execution && left_expr_cache &&
896	test_if_item_cache_changed(*left_expr_cache) < `0`)
897	DBUG_RETURN(FALSE);
898
899	/*
900	The exec() method below updates item::value, and item::null_value, thus if
901	we don't call it, the next call to item::val_int() will return whatever
902	result was computed by its previous call.
903	*/
904	DBUG_RETURN(Item_subselect::exec());
905	}
906
907
908	Item::Type Item_subselect::type() const
909	{
910	return SUBSELECT_ITEM;
911	}
912
913
914	void Item_subselect::fix_length_and_dec()
915	{
916	engine->fix_length_and_dec(`0`);
917	}
918
919
920	table_map Item_subselect::used_tables() const
921	{
922	return (table_map) ((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN)?
923	used_tables_cache : `0L`);
924	}
925
926
927	bool Item_subselect::const_item() const
928	{
929	DBUG_ASSERT(thd);
930	return (thd->lex->context_analysis_only \|\| with_recursive_reference ?
931	FALSE :
932	forced_const \|\| const_item_cache);
933	}
934
935	Item Item_subselect::get_tmp_table_item(THD thd_arg)
936	{
937	if (!with_sum_func && !const_item())
938	return new (thd->mem_root) Item_temptable_field (thd_arg, result_field);
939	return copy_or_same(thd_arg);
940	}
941
942	void Item_subselect::update_used_tables()
943	{
944	if (!forced_const)
945	{
946	recalc_used_tables(parent_select, FALSE);
947	if (!(engine->uncacheable() & ~UNCACHEABLE_EXPLAIN))
948	{
949	// did all used tables become static?
950	if (!(used_tables_cache & ~engine->upper_select_const_tables()) &&
951	! with_recursive_reference)
952	const_item_cache= `1`;
953	}
954	}
955	}
956
957
958	void Item_subselect::print(String *str, enum_query_type query_type)
959	{
960	if (query_type & QT_ITEM_SUBSELECT_ID_ONLY)
961	{
962	str->append(STRING_WITH_LEN("(subquery#"));
963	if (unit && unit->first_select())
964	{
965	char buf[`64`];
966	ll2str(unit->first_select()->select_number, buf, `10`, `0`);
967	str->append(buf);
968	}
969	else
970	str->append("NULL"); // TODO: what exactly does this mean?
971
972	str->append(")");
973	return;
974	}
975	if (engine)
976	{
977	str->append(`'('`);
978	engine->print(str, query_type);
979	str->append(`')'`);
980	}
981	else
982	str->append("(...)");
983	}
984
985
986	Item_singlerow_subselect::Item_singlerow_subselect(THD thd, st_select_lex select_lex):
987	Item_subselect (thd), value(`0`)
988	{
989	DBUG_ENTER("Item_singlerow_subselect::Item_singlerow_subselect");
990	init(select_lex, new (thd->mem_root) select_singlerow_subselect (thd, this));
991	maybe_null= `1`;
992	max_columns= UINT_MAX;
993	DBUG_VOID_RETURN;
994	}
995
996	st_select_lex *
997	Item_singlerow_subselect::invalidate_and_restore_select_lex()
998	{
999	DBUG_ENTER("Item_singlerow_subselect::invalidate_and_restore_select_lex");
1000	st_select_lex *result= get_select_lex();
1001
1002	DBUG_ASSERT(result);
1003
1004	/*
1005	This code restore the parse tree in it's state before the execution of
1006	Item_singlerow_subselect::Item_singlerow_subselect(),
1007	and in particular decouples this object from the SELECT_LEX,
1008	so that the SELECT_LEX can be used with a different flavor
1009	or Item_subselect instead, as part of query rewriting.
1010	*/
1011	unit->item= NULL;
1012
1013	DBUG_RETURN(result);
1014	}
1015
1016	Item_maxmin_subselect::Item_maxmin_subselect(THD *thd,
1017	Item_subselect *parent,
1018	st_select_lex *select_lex,
1019	bool max_arg):
1020	Item_singlerow_subselect (thd), was_values(TRUE)
1021	{
1022	DBUG_ENTER("Item_maxmin_subselect::Item_maxmin_subselect");
1023	max= max_arg;
1024	init(select_lex,
1025	new (thd->mem_root) select_max_min_finder_subselect (thd,
1026	this, max_arg, parent->substype() == Item_subselect::ALL_SUBS));
1027	max_columns= `1`;
1028	maybe_null= `1`;
1029	max_columns= `1`;
1030
1031	/*
1032	Following information was collected during performing fix_fields()
1033	of Items belonged to subquery, which will be not repeated
1034	*/
1035	used_tables_cache= parent->get_used_tables_cache();
1036	const_item_cache= parent->const_item();
1037
1038	DBUG_VOID_RETURN;
1039	}
1040
1041	void Item_maxmin_subselect::cleanup()
1042	{
1043	DBUG_ENTER("Item_maxmin_subselect::cleanup");
1044	Item_singlerow_subselect::cleanup();
1045
1046	/*
1047	By default it is TRUE to avoid TRUE reporting by
1048	Item_func_not_all/Item_func_nop_all if this item was never called.
1049
1050	Engine exec() set it to FALSE by reset_value_registration() call.
1051	select_max_min_finder_subselect::send_data() set it back to TRUE if some
1052	value will be found.
1053	*/
1054	was_values= TRUE;
1055	DBUG_VOID_RETURN;
1056	}
1057
1058
1059	void Item_maxmin_subselect::print(String *str, enum_query_type query_type)
1060	{
1061	str->append(max?"<max>":"<min>", `5`);
1062	Item_singlerow_subselect::print(str, query_type);
1063	}
1064
1065
1066	void Item_maxmin_subselect::no_rows_in_result()
1067	{
1068	/*
1069	Subquery predicates outside of the SELECT list must be evaluated in order
1070	to possibly filter the special result row generated for implicit grouping
1071	if the subquery is in the HAVING clause.
1072	If the predicate is constant, we need its actual value in the only result
1073	row for queries with implicit grouping.
1074	*/
1075	if (parsing_place != SELECT_LIST \|\| const_item())
1076	return;
1077	value= (new (thd->mem_root) Item_null (thd))->get_cache(thd);
1078	null_value= `0`;
1079	was_values= `0`;
1080	make_const();
1081	}
1082
1083
1084	void Item_singlerow_subselect::no_rows_in_result()
1085	{
1086	/*
1087	Subquery predicates outside of the SELECT list must be evaluated in order
1088	to possibly filter the special result row generated for implicit grouping
1089	if the subquery is in the HAVING clause.
1090	If the predicate is constant, we need its actual value in the only result
1091	row for queries with implicit grouping.
1092	*/
1093	if (parsing_place != SELECT_LIST \|\| const_item())
1094	return;
1095	value= (new (thd->mem_root) Item_null (thd))->get_cache(thd);
1096	reset();
1097	make_const();
1098	}
1099
1100
1101	void Item_singlerow_subselect::reset()
1102	{
1103	Item_subselect::reset();
1104	if (value)
1105	{
1106	for(uint i= `0`; i < engine->cols(); i++)
1107	row[i]->set_null();
1108	}
1109	}
1110
1111
1112	/**
1113	@todo
1114	- We cant change name of Item_field or Item_ref, because it will
1115	prevent it's correct resolving, but we should save name of
1116	removed item => we do not make optimization if top item of
1117	list is field or reference.
1118	- switch off this optimization for prepare statement,
1119	because we do not rollback this changes.
1120	Make rollback for it, or special name resolving mode in 5.0.
1121
1122	@param join Join object of the subquery (i.e. 'child' join).
1123
1124	@retval false The subquery was transformed
1125	*/
1126	bool
1127	Item_singlerow_subselect::select_transformer(JOIN *join)
1128	{
1129	DBUG_ENTER("Item_singlerow_subselect::select_transformer");
1130	if (changed)
1131	DBUG_RETURN(false);
1132	DBUG_ASSERT(join->thd == thd);
1133
1134	SELECT_LEX *select_lex= join->select_lex;
1135	Query_arena *arena= thd->stmt_arena;
1136
1137	if (!select_lex->master_unit()->is_unit_op() &&
1138	!select_lex->table_list.elements &&
1139	select_lex->item_list.elements == `1` &&
1140	!select_lex->item_list.head()->with_sum_func &&
1141	/*
1142	We cant change name of Item_field or Item_ref, because it will
1143	prevent it's correct resolving, but we should save name of
1144	removed item => we do not make optimization if top item of
1145	list is field or reference.
1146	TODO: solve above problem
1147	*/
1148	!(select_lex->item_list.head()->type() == FIELD_ITEM \|\|
1149	select_lex->item_list.head()->type() == REF_ITEM) &&
1150	!join->conds && !join->having &&
1151	/*
1152	switch off this optimization for prepare statement,
1153	because we do not rollback this changes
1154	TODO: make rollback for it, or special name resolving mode in 5.0.
1155	*/
1156	!arena->is_stmt_prepare_or_first_sp_execute()
1157	)
1158	{
1159	have_to_be_excluded= `1`;
1160	if (thd->lex->describe)
1161	{
1162	char warn_buff[MYSQL_ERRMSG_SIZE];
1163	sprintf(warn_buff, ER_THD(thd, ER_SELECT_REDUCED),
1164	select_lex->select_number);
1165	push_warning(thd, Sql_condition::WARN_LEVEL_NOTE,
1166	ER_SELECT_REDUCED, warn_buff);
1167	}
1168	substitution= select_lex->item_list.head();
1169	/*
1170	as far as we moved content to upper level we have to fix dependences & Co
1171	*/
1172	substitution->fix_after_pullout(select_lex->outer_select(),
1173	&substitution, TRUE);
1174	}
1175	DBUG_RETURN(false);
1176	}
1177
1178
1179	void Item_singlerow_subselect::store(uint i, Item *item)
1180	{
1181	row[i]->store(item);
1182	row[i]->cache_value();
1183	}
1184
1185	const Type_handler Item_singlerow_subselect::type_handler() const*
1186	{
1187	return engine->type_handler();
1188	}
1189
1190	void Item_singlerow_subselect::fix_length_and_dec()
1191	{
1192	if ((max_columns= engine->cols()) == `1`)
1193	{
1194	engine->fix_length_and_dec(row= &value);
1195	}
1196	else
1197	{
1198	if (!(row= (Item_cache) current_thd->alloc(sizeof*(Item_cache) *
1199	max_columns)))
1200	return;
1201	engine->fix_length_and_dec(row);
1202	value= *row;
1203	}
1204	unsigned_flag= value->unsigned_flag;
1205	/*
1206	If there are not tables in subquery then ability to have NULL value
1207	depends on SELECT list (if single row subquery have tables then it
1208	always can be NULL if there are not records fetched).
1209	*/
1210	if (engine->no_tables())
1211	maybe_null= engine->may_be_null();
1212	else
1213	{
1214	for (uint i= `0`; i < max_columns; i++)
1215	row[i]->maybe_null= TRUE;
1216	}
1217	}
1218
1219
1220	/**
1221	Add an expression cache for this subquery if it is needed
1222
1223	@param thd_arg Thread handle
1224
1225	@details
1226	The function checks whether an expression cache is needed for this item
1227	and if if so wraps the item into an item of the class
1228	Item_cache_wrapper with an appropriate expression cache set up there.
1229
1230	@note
1231	used from Item::transform()
1232
1233	@return
1234	new wrapper item if an expression cache is needed,
1235	this item - otherwise
1236	*/
1237
1238	Item* Item_singlerow_subselect::expr_cache_insert_transformer(THD *tmp_thd,
1239	uchar *unused)
1240	{
1241	DBUG_ENTER("Item_singlerow_subselect::expr_cache_insert_transformer");
1242
1243	DBUG_ASSERT(thd == tmp_thd);
1244
1245	if (expr_cache)
1246	DBUG_RETURN(expr_cache);
1247
1248	if (expr_cache_is_needed(tmp_thd) &&
1249	(expr_cache= set_expr_cache(tmp_thd)))
1250	{
1251	init_expr_cache_tracker(tmp_thd);
1252	DBUG_RETURN(expr_cache);
1253	}
1254	DBUG_RETURN(this);
1255	}
1256
1257
1258	uint Item_singlerow_subselect::cols() const
1259	{
1260	return engine->cols();
1261	}
1262
1263	bool Item_singlerow_subselect::check_cols(uint c)
1264	{
1265	if (c != engine->cols())
1266	{
1267	my_error(ER_OPERAND_COLUMNS, MYF(`0`), c);
1268	return `1`;
1269	}
1270	return `0`;
1271	}
1272
1273	bool Item_singlerow_subselect::null_inside()
1274	{
1275	for (uint i= `0`; i < max_columns ; i++)
1276	{
1277	if (row[i]->null_value)
1278	return `1`;
1279	}
1280	return `0`;
1281	}
1282
1283	void Item_singlerow_subselect::bring_value()
1284	{
1285	if (!exec() && assigned())
1286	null_value= `0`;
1287	else
1288	reset();
1289	}
1290
1291	double Item_singlerow_subselect::val_real()
1292	{
1293	DBUG_ASSERT(fixed == `1`);
1294	if (forced_const)
1295	return value->val_real();
1296	if (!exec() && !value->null_value)
1297	{
1298	null_value= FALSE;
1299	return value->val_real();
1300	}
1301	else
1302	{
1303	reset();
1304	return `0`;
1305	}
1306	}
1307
1308	longlong Item_singlerow_subselect::val_int()
1309	{
1310	DBUG_ASSERT(fixed == `1`);
1311	if (forced_const)
1312	return value->val_int();
1313	if (!exec() && !value->null_value)
1314	{
1315	null_value= FALSE;
1316	return value->val_int();
1317	}
1318	else
1319	{
1320	reset();
1321	return `0`;
1322	}
1323	}
1324
1325	String Item_singlerow_subselect::val_str(String str)
1326	{
1327	DBUG_ASSERT(fixed == `1`);
1328	if (forced_const)
1329	return value->val_str(str);
1330	if (!exec() && !value->null_value)
1331	{
1332	null_value= FALSE;
1333	return value->val_str(str);
1334	}
1335	else
1336	{
1337	reset();
1338	return `0`;
1339	}
1340	}
1341
1342
1343	my_decimal Item_singlerow_subselect::val_decimal(my_decimal decimal_value)
1344	{
1345	DBUG_ASSERT(fixed == `1`);
1346	if (forced_const)
1347	return value->val_decimal(decimal_value);
1348	if (!exec() && !value->null_value)
1349	{
1350	null_value= FALSE;
1351	return value->val_decimal(decimal_value);
1352	}
1353	else
1354	{
1355	reset();
1356	return `0`;
1357	}
1358	}
1359
1360
1361	bool Item_singlerow_subselect::val_bool()
1362	{
1363	DBUG_ASSERT(fixed == `1`);
1364	if (forced_const)
1365	return value->val_bool();
1366	if (!exec() && !value->null_value)
1367	{
1368	null_value= FALSE;
1369	return value->val_bool();
1370	}
1371	else
1372	{
1373	reset();
1374	return `0`;
1375	}
1376	}
1377
1378
1379	bool Item_singlerow_subselect::get_date(MYSQL_TIME *ltime,ulonglong fuzzydate)
1380	{
1381	DBUG_ASSERT(fixed == `1`);
1382	if (forced_const)
1383	return value->get_date(ltime, fuzzydate);
1384	if (!exec() && !value->null_value)
1385	{
1386	null_value= FALSE;
1387	return value->get_date(ltime, fuzzydate);
1388	}
1389	else
1390	{
1391	reset();
1392	return `1`;
1393	}
1394	}
1395
1396
1397	Item_exists_subselect::Item_exists_subselect(THD *thd,
1398	st_select_lex *select_lex):
1399	Item_subselect (thd), upper_not(NULL), abort_on_null(`0`),
1400	emb_on_expr_nest(NULL), optimizer(`0`), exists_transformed(`0`)
1401	{
1402	DBUG_ENTER("Item_exists_subselect::Item_exists_subselect");
1403	init(select_lex, new (thd->mem_root) select_exists_subselect (thd, this));
1404	max_columns= UINT_MAX;
1405	null_value= FALSE; //can't be NULL
1406	maybe_null= `0`; //can't be NULL
1407	value= `0`;
1408	DBUG_VOID_RETURN;
1409	}
1410
1411
1412	void Item_exists_subselect::print(String *str, enum_query_type query_type)
1413	{
1414	str->append(STRING_WITH_LEN("exists"));
1415	Item_subselect::print(str, query_type);
1416	}
1417
1418
1419	bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
1420	{
1421	if (unlikely(unit_arg->fake_select_lex &&
1422	unit_arg->fake_select_lex->test_limit()))
1423	return(`1`);
1424
1425	SELECT_LEX *sl= unit_arg->first_select();
1426	for (; sl; sl= sl->next_select())
1427	{
1428	if (unlikely(sl->test_limit()))
1429	return(`1`);
1430	}
1431	return(`0`);
1432	}
1433
1434	Item_in_subselect::Item_in_subselect(THD thd, Item left_exp,
1435	st_select_lex *select_lex):
1436	Item_exists_subselect (thd), left_expr_cache(`0`), first_execution(TRUE),
1437	in_strategy(SUBS_NOT_TRANSFORMED),
1438	pushed_cond_guards(NULL), do_not_convert_to_sj(FALSE), is_jtbm_merged(FALSE),
1439	is_jtbm_const_tab(FALSE), is_flattenable_semijoin(FALSE),
1440	is_registered_semijoin(FALSE),
1441	upper_item(`0`)
1442	{
1443	DBUG_ENTER("Item_in_subselect::Item_in_subselect");
1444	DBUG_PRINT("info", ("in_strategy: %u", (uint)in_strategy));
1445	left_expr_orig= left_expr= left_exp;
1446	/ prepare to possible disassembling the item in convert_subq_to_sj() /
1447	if (left_exp->type() == Item::ROW_ITEM)
1448	left_expr_orig= new (thd->mem_root)
1449	Item_row (thd, static_cast<Item_row*>(left_exp));
1450	func= &eq_creator;
1451	init(select_lex, new (thd->mem_root) select_exists_subselect (thd, this));
1452	max_columns= UINT_MAX;
1453	maybe_null= `1`;
1454	reset();
1455	//if test_limit will fail then error will be reported to client
1456	test_limit(select_lex->master_unit());
1457	DBUG_VOID_RETURN;
1458	}
1459
1460	int Item_in_subselect::get_identifier()
1461	{
1462	return engine->get_identifier();
1463	}
1464
1465	Item_allany_subselect::Item_allany_subselect(THD thd, Item left_exp,
1466	chooser_compare_func_creator fc,
1467	st_select_lex *select_lex,
1468	bool all_arg):
1469	Item_in_subselect (thd), func_creator(fc), all(all_arg)
1470	{
1471	DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
1472	left_expr_orig= left_expr= left_exp;
1473	/ prepare to possible disassembling the item in convert_subq_to_sj() /
1474	if (left_exp->type() == Item::ROW_ITEM)
1475	left_expr_orig= new (thd->mem_root)
1476	Item_row (thd, static_cast<Item_row*>(left_exp));
1477	func= func_creator(all_arg);
1478	init(select_lex, new (thd->mem_root) select_exists_subselect (thd, this));
1479	max_columns= `1`;
1480	abort_on_null= `0`;
1481	reset();
1482	//if test_limit will fail then error will be reported to client
1483	test_limit(select_lex->master_unit());
1484	DBUG_VOID_RETURN;
1485	}
1486
1487
1488	/**
1489	Initialize length and decimals for EXISTS and inherited (IN/ALL/ANY)
1490	subqueries
1491	*/
1492
1493	void Item_exists_subselect::init_length_and_dec()
1494	{
1495	decimals= `0`;
1496	max_length= `1`;
1497	max_columns= engine->cols();
1498	}
1499
1500
1501	void Item_exists_subselect::fix_length_and_dec()
1502	{
1503	DBUG_ENTER("Item_exists_subselect::fix_length_and_dec");
1504	init_length_and_dec();
1505	/*
1506	We need only 1 row to determine existence (i.e. any EXISTS that is not
1507	an IN always requires LIMIT 1)
1508	*/
1509	thd->change_item_tree(&unit->global_parameters()->select_limit,
1510	new (thd->mem_root) Item_int (thd, (int32) `1`));
1511	DBUG_PRINT("info", ("Set limit to 1"));
1512	DBUG_VOID_RETURN;
1513	}
1514
1515
1516	void Item_in_subselect::fix_length_and_dec()
1517	{
1518	DBUG_ENTER("Item_in_subselect::fix_length_and_dec");
1519	init_length_and_dec();
1520	/*
1521	Unlike Item_exists_subselect, LIMIT 1 is set later for
1522	Item_in_subselect, depending on the chosen strategy.
1523	*/
1524	DBUG_VOID_RETURN;
1525	}
1526
1527
1528	/**
1529	Add an expression cache for this subquery if it is needed
1530
1531	@param thd_arg Thread handle
1532
1533	@details
1534	The function checks whether an expression cache is needed for this item
1535	and if if so wraps the item into an item of the class
1536	Item_cache_wrapper with an appropriate expression cache set up there.
1537
1538	@note
1539	used from Item::transform()
1540
1541	@return
1542	new wrapper item if an expression cache is needed,
1543	this item - otherwise
1544	*/
1545
1546	Item* Item_exists_subselect::expr_cache_insert_transformer(THD *tmp_thd,
1547	uchar *unused)
1548	{
1549	DBUG_ENTER("Item_exists_subselect::expr_cache_insert_transformer");
1550	DBUG_ASSERT(thd == tmp_thd);
1551
1552	if (expr_cache)
1553	DBUG_RETURN(expr_cache);
1554
1555	if (substype() == EXISTS_SUBS && expr_cache_is_needed(tmp_thd) &&
1556	(expr_cache= set_expr_cache(tmp_thd)))
1557	{
1558	init_expr_cache_tracker(tmp_thd);
1559	DBUG_RETURN(expr_cache);
1560	}
1561	DBUG_RETURN(this);
1562	}
1563
1564
1565	void Item_exists_subselect::no_rows_in_result()
1566	{
1567	/*
1568	Subquery predicates outside of the SELECT list must be evaluated in order
1569	to possibly filter the special result row generated for implicit grouping
1570	if the subquery is in the HAVING clause.
1571	If the predicate is constant, we need its actual value in the only result
1572	row for queries with implicit grouping.
1573	*/
1574	if (parsing_place != SELECT_LIST \|\| const_item())
1575	return;
1576	value= `0`;
1577	null_value= `0`;
1578	make_const();
1579	}
1580
1581	double Item_exists_subselect::val_real()
1582	{
1583	DBUG_ASSERT(fixed == `1`);
1584	if (!forced_const && exec())
1585	{
1586	reset();
1587	return `0`;
1588	}
1589	return (double) value;
1590	}
1591
1592	longlong Item_exists_subselect::val_int()
1593	{
1594	DBUG_ASSERT(fixed == `1`);
1595	if (!forced_const && exec())
1596	{
1597	reset();
1598	return `0`;
1599	}
1600	return value;
1601	}
1602
1603
1604	/**
1605	Return the result of EXISTS as a string value
1606
1607	Converts the true/false result into a string value.
1608	Note that currently this cannot be NULL, so if the query exection fails
1609	it will return 0.
1610
1611	@param decimal_value[out] buffer to hold the resulting string value
1612	@retval Pointer to the converted string.
1613	Can't be a NULL pointer, as currently
1614	EXISTS cannot return NULL.
1615	*/
1616
1617	String Item_exists_subselect::val_str(String str)
1618	{
1619	DBUG_ASSERT(fixed == `1`);
1620	if (!forced_const && exec())
1621	reset();
1622	str->set((ulonglong)value,&my_charset_bin);
1623	return str;
1624	}
1625
1626
1627	/**
1628	Return the result of EXISTS as a decimal value
1629
1630	Converts the true/false result into a decimal value.
1631	Note that currently this cannot be NULL, so if the query exection fails
1632	it will return 0.
1633
1634	@param decimal_value[out] Buffer to hold the resulting decimal value
1635	@retval Pointer to the converted decimal.
1636	Can't be a NULL pointer, as currently
1637	EXISTS cannot return NULL.
1638	*/
1639
1640	my_decimal Item_exists_subselect::val_decimal(my_decimal decimal_value)
1641	{
1642	DBUG_ASSERT(fixed == `1`);
1643	if (!forced_const && exec())
1644	reset();
1645	int2my_decimal(E_DEC_FATAL_ERROR, value, `0`, decimal_value);
1646	return decimal_value;
1647	}
1648
1649
1650	bool Item_exists_subselect::val_bool()
1651	{
1652	DBUG_ASSERT(fixed == `1`);
1653	if (!forced_const && exec())
1654	{
1655	reset();
1656	return `0`;
1657	}
1658	return value != `0`;
1659	}
1660
1661
1662	double Item_in_subselect::val_real()
1663	{
1664	/*
1665	As far as Item_in_subselect called only from Item_in_optimizer this
1666	method should not be used
1667	*/
1668	DBUG_ASSERT(`0`);
1669	DBUG_ASSERT(fixed == `1`);
1670	if (forced_const)
1671	return value;
1672	DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
1673	! engine->is_executed());
1674	null_value= was_null= FALSE;
1675	if (exec())
1676	{
1677	reset();
1678	return `0`;
1679	}
1680	if (was_null && !value)
1681	null_value= TRUE;
1682	return (double) value;
1683	}
1684
1685
1686	longlong Item_in_subselect::val_int()
1687	{
1688	/*
1689	As far as Item_in_subselect called only from Item_in_optimizer this
1690	method should not be used
1691	*/
1692	DBUG_ASSERT(`0`);
1693	DBUG_ASSERT(fixed == `1`);
1694	if (forced_const)
1695	return value;
1696	DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
1697	! engine->is_executed());
1698	null_value= was_null= FALSE;
1699	if (exec())
1700	{
1701	reset();
1702	return `0`;
1703	}
1704	if (was_null && !value)
1705	null_value= TRUE;
1706	return value;
1707	}
1708
1709
1710	String Item_in_subselect::val_str(String str)
1711	{
1712	/*
1713	As far as Item_in_subselect called only from Item_in_optimizer this
1714	method should not be used
1715	*/
1716	DBUG_ASSERT(`0`);
1717	DBUG_ASSERT(fixed == `1`);
1718	if (forced_const)
1719	goto value_is_ready;
1720	DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
1721	! engine->is_executed());
1722	null_value= was_null= FALSE;
1723	if (exec())
1724	{
1725	reset();
1726	return `0`;
1727	}
1728	if (was_null && !value)
1729	{
1730	null_value= TRUE;
1731	return `0`;
1732	}
1733	value_is_ready:
1734	str->set((ulonglong)value, &my_charset_bin);
1735	return str;
1736	}
1737
1738
1739	bool Item_in_subselect::val_bool()
1740	{
1741	DBUG_ASSERT(fixed == `1`);
1742	if (forced_const)
1743	return value;
1744	DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
1745	! engine->is_executed() \|\| with_recursive_reference);
1746	null_value= was_null= FALSE;
1747	if (exec())
1748	{
1749	reset();
1750	return `0`;
1751	}
1752	if (was_null && !value)
1753	null_value= TRUE;
1754	return value;
1755	}
1756
1757	my_decimal Item_in_subselect::val_decimal(my_decimal decimal_value)
1758	{
1759	/*
1760	As far as Item_in_subselect called only from Item_in_optimizer this
1761	method should not be used
1762	*/
1763	DBUG_ASSERT(`0`);
1764	if (forced_const)
1765	goto value_is_ready;
1766	DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) \|\|
1767	! engine->is_executed());
1768	null_value= was_null= FALSE;
1769	DBUG_ASSERT(fixed == `1`);
1770	if (exec())
1771	{
1772	reset();
1773	return `0`;
1774	}
1775	if (was_null && !value)
1776	null_value= TRUE;
1777	value_is_ready:
1778	int2my_decimal(E_DEC_FATAL_ERROR, value, `0`, decimal_value);
1779	return decimal_value;
1780	}
1781
1782
1783	/**
1784	Prepare a single-column IN/ALL/ANY subselect for rewriting.
1785
1786	@param join Join object of the subquery (i.e. 'child' join).
1787
1788	@details
1789
1790	Prepare a single-column subquery to be rewritten. Given the subquery.
1791
1792	If the subquery has no tables it will be turned to an expression between
1793	left part and SELECT list.
1794
1795	In other cases the subquery will be wrapped with Item_in_optimizer which
1796	allow later to turn it to EXISTS or MAX/MIN.
1797
1798	@retval false The subquery was transformed
1799	@retval true Error
1800	*/
1801
1802	bool
1803	Item_in_subselect::single_value_transformer(JOIN *join)
1804	{
1805	SELECT_LEX *select_lex= join->select_lex;
1806	DBUG_ENTER("Item_in_subselect::single_value_transformer");
1807	DBUG_ASSERT(thd == join->thd);
1808
1809	/*
1810	Check that the right part of the subselect contains no more than one
1811	column. E.g. in SELECT 1 IN (SELECT ..) the right part is (SELECT * ...)*
1812	*/
1813	// psergey: duplicated_subselect_card_check
1814	if (select_lex->item_list.elements > `1`)
1815	{
1816	my_error(ER_OPERAND_COLUMNS, MYF(`0`), `1`);
1817	DBUG_RETURN(true);
1818	}
1819
1820	Item* join_having= join->having ? join->having : join->tmp_having;
1821	if (!(join_having \|\| select_lex->with_sum_func \|\|
1822	select_lex->group_list.elements) &&
1823	select_lex->table_list.elements == `0` && !join->conds &&
1824	!select_lex->master_unit()->is_unit_op())
1825	{
1826	Item where_item= (Item) select_lex->item_list.head();
1827	/*
1828	it is single select without tables => possible optimization
1829	remove the dependence mark since the item is moved to upper
1830	select and is not outer anymore.
1831	*/
1832	where_item->walk(&Item::remove_dependence_processor, `0`,
1833	select_lex->outer_select());
1834	/*
1835	fix_field of substitution item will be done in time of
1836	substituting.
1837	Note that real_item() should be used instead of
1838	original left expression because left_expr can be
1839	runtime created Ref item which is deleted at the end
1840	of the statement. Thus one of 'substitution' arguments
1841	can be broken in case of PS.
1842	*/
1843	substitution= func->create(thd, left_expr, where_item);
1844	have_to_be_excluded= `1`;
1845	if (thd->lex->describe)
1846	{
1847	char warn_buff[MYSQL_ERRMSG_SIZE];
1848	sprintf(warn_buff, ER_THD(thd, ER_SELECT_REDUCED),
1849	select_lex->select_number);
1850	push_warning(thd, Sql_condition::WARN_LEVEL_NOTE,
1851	ER_SELECT_REDUCED, warn_buff);
1852	}
1853	DBUG_RETURN(false);
1854	}
1855
1856	/*
1857	Wrap the current IN predicate in an Item_in_optimizer. The actual
1858	substitution in the Item tree takes place in Item_subselect::fix_fields.
1859	*/
1860	if (!substitution)
1861	{
1862	/ We're invoked for the 1st (or the only) SELECT in the subquery UNION /
1863	substitution= optimizer;
1864
1865	SELECT_LEX *current= thd->lex->current_select;
1866
1867	thd->lex->current_select= current->return_after_parsing();
1868	if (!optimizer \|\| optimizer->fix_left(thd))
1869	{
1870	thd->lex->current_select= current;
1871	DBUG_RETURN(true);
1872	}
1873	thd->lex->current_select= current;
1874
1875	/ We will refer to upper level cache array => we have to save it for SP /
1876	optimizer->keep_top_level_cache();
1877
1878	/*
1879	As far as Item_in_optimizer does not substitute itself on fix_fields
1880	we can use same item for all selects.
1881	*/
1882	expr= new (thd->mem_root) Item_direct_ref (thd, &select_lex->context,
1883	(Item**)optimizer->get_cache(),
1884	"<no matter>",
1885	&in_left_expr_name);
1886	}
1887
1888	DBUG_RETURN(false);
1889	}
1890
1891
1892	/**
1893	Apply transformation max/min transwormation to ALL/ANY subquery if it is
1894	possible.
1895
1896	@param join Join object of the subquery (i.e. 'child' join).
1897
1898	@details
1899
1900	If this is an ALL/ANY single-value subselect, try to rewrite it with
1901	a MIN/MAX subselect. We can do that if a possible NULL result of the
1902	subselect can be ignored.
1903	E.g. SELECT FROM t1 WHERE b > ANY (SELECT a FROM t2) can be rewritten*
1904	with SELECT FROM t1 WHERE b > (SELECT MAX(a) FROM t2).*
1905	We can't check that this optimization is safe if it's not a top-level
1906	item of the WHERE clause (e.g. because the WHERE clause can contain IS
1907	NULL/IS NOT NULL functions). If so, we rewrite ALL/ANY with NOT EXISTS
1908	later in this method.
1909
1910	@retval false The subquery was transformed
1911	@retval true Error
1912	*/
1913
1914	bool Item_allany_subselect::transform_into_max_min(JOIN *join)
1915	{
1916	DBUG_ENTER("Item_allany_subselect::transform_into_max_min");
1917	if (!test_strategy(SUBS_MAXMIN_INJECTED \| SUBS_MAXMIN_ENGINE))
1918	DBUG_RETURN(false);
1919	Item **place= optimizer->arguments() + `1`;
1920	SELECT_LEX *select_lex= join->select_lex;
1921	Item *subs;
1922	DBUG_ASSERT(thd == join->thd);
1923
1924	/*
1925	*/
1926	DBUG_ASSERT(!substitution);
1927
1928	/*
1929	Check if optimization with aggregate min/max possible
1930	1 There is no aggregate in the subquery
1931	2 It is not UNION
1932	3 There is tables
1933	4 It is not ALL subquery with possible NULLs in the SELECT list
1934	*/
1935	if (!select_lex->group_list.elements && /1/
1936	!select_lex->having && /1/
1937	!select_lex->with_sum_func && /1/
1938	!(select_lex->next_select()) && /2/
1939	select_lex->table_list.elements && /3/
1940	(!select_lex->ref_pointer_array [`0`]->maybe_null \|\| /4/
1941	substype() != Item_subselect::ALL_SUBS)) /4/
1942	{
1943	Item_sum_hybrid *item;
1944	nesting_map save_allow_sum_func;
1945	if (func->l_op())
1946	{
1947	/*
1948	(ALL && (> \|\| =>)) \|\| (ANY && (< \|\| =<))
1949	for ALL condition is inverted
1950	*/
1951	item= new (thd->mem_root) Item_sum_max (thd,
1952	select_lex->ref_pointer_array [`0`]);
1953	}
1954	else
1955	{
1956	/*
1957	(ALL && (< \|\| =<)) \|\| (ANY && (> \|\| =>))
1958	for ALL condition is inverted
1959	*/
1960	item= new (thd->mem_root) Item_sum_min (thd,
1961	select_lex->ref_pointer_array [`0`]);
1962	}
1963	if (upper_item)
1964	upper_item->set_sum_test(item);
1965	thd->change_item_tree(&select_lex->ref_pointer_array [`0`], item);
1966	{
1967	List_iterator<Item> it(select_lex->item_list);
1968	it ++;
1969	thd->change_item_tree(it.ref(), item);
1970	}
1971
1972	DBUG_EXECUTE("where",
1973	print_where(item, "rewrite with MIN/MAX", QT_ORDINARY););
1974
1975	save_allow_sum_func= thd->lex->allow_sum_func;
1976	thd->lex->allow_sum_func\|=
1977	(nesting_map)`1` << thd->lex->current_select->nest_level;
1978	/*
1979	Item_sum_(max\|min) can't substitute other item => we can use 0 as
1980	reference, also Item_sum_(max\|min) can't be fixed after creation, so
1981	we do not check item->fixed
1982	*/
1983	if (item->fix_fields(thd, `0`))
1984	DBUG_RETURN(true);
1985	thd->lex->allow_sum_func= save_allow_sum_func;
1986	/ we added aggregate function => we have to change statistic /
1987	count_field_types(select_lex, &join->tmp_table_param, join->all_fields,
1988	`0`);
1989	if (join->prepare_stage2())
1990	DBUG_RETURN(true);
1991	subs= new (thd->mem_root) Item_singlerow_subselect (thd, select_lex);
1992
1993	/*
1994	Remove other strategies if any (we already changed the query and
1995	can't apply other strategy).
1996	*/
1997	set_strategy(SUBS_MAXMIN_INJECTED);
1998	}
1999	else
2000	{
2001	Item_maxmin_subselect *item;
2002	subs= item= new (thd->mem_root) Item_maxmin_subselect (thd, this, select_lex, func->l_op());
2003	if (upper_item)
2004	upper_item->set_sub_test(item);
2005	/*
2006	Remove other strategies if any (we already changed the query and
2007	can't apply other strategy).
2008	*/
2009	set_strategy(SUBS_MAXMIN_ENGINE);
2010	}
2011	/*
2012	The swap is needed for expressions of type 'f1 < ALL ( SELECT ....)'
2013	where we want to evaluate the sub query even if f1 would be null.
2014	*/
2015	subs= func->create_swap(thd, *(optimizer->get_cache()), subs);
2016	thd->change_item_tree(place, subs);
2017	if (subs->fix_fields(thd, &subs))
2018	DBUG_RETURN(true);
2019	DBUG_ASSERT(subs == (place)); // There was no substitutions*
2020
2021	select_lex->master_unit()->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
2022	select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
2023
2024	DBUG_RETURN(false);
2025	}
2026
2027
2028	bool Item_in_subselect::fix_having(Item having, SELECT_LEX select_lex)
2029	{
2030	bool fix_res= `0`;
2031	DBUG_ASSERT(thd);
2032	if (!having->fixed)
2033	{
2034	select_lex->having_fix_field= `1`;
2035	fix_res= having->fix_fields(thd, `0`);
2036	select_lex->having_fix_field= `0`;
2037	}
2038	return fix_res;
2039	}
2040
2041	bool Item_allany_subselect::is_maxmin_applicable(JOIN *join)
2042	{
2043	/*
2044	Check if max/min optimization applicable: It is top item of
2045	WHERE condition.
2046	*/
2047	return (abort_on_null \|\| (upper_item && upper_item->is_top_level_item())) &&
2048	!(join->select_lex->master_unit()->uncacheable & ~UNCACHEABLE_EXPLAIN) && !func->eqne_op();
2049	}
2050
2051
2052	/**
2053	Create the predicates needed to transform a single-column IN/ALL/ANY
2054	subselect into a correlated EXISTS via predicate injection.
2055
2056	@param join[in] Join object of the subquery (i.e. 'child' join).
2057	@param where_item[out] the in-to-exists addition to the where clause
2058	@param having_item[out] the in-to-exists addition to the having clause
2059
2060	@details
2061	The correlated predicates are created as follows:
2062
2063	- If the subquery has aggregates, GROUP BY, or HAVING, convert to
2064
2065	SELECT ie FROM ... HAVING subq_having AND
2066	trigcond(oe $cmp$ ref_or_null_helper<ie>)
2067
2068	the addition is wrapped into trigger only when we want to distinguish
2069	between NULL and FALSE results.
2070
2071	- Otherwise (no aggregates/GROUP BY/HAVING) convert it to one of the
2072	following:
2073
2074	= If we don't need to distinguish between NULL and FALSE subquery:
2075
2076	SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
2077
2078	= If we need to distinguish between those:
2079
2080	SELECT ie FROM ...
2081	WHERE subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
2082	HAVING trigcond(<is_not_null_test>(ie))
2083
2084	@retval false If the new conditions were created successfully
2085	@retval true Error
2086	*/
2087
2088	bool
2089	Item_in_subselect::create_single_in_to_exists_cond(JOIN *join,
2090	Item **where_item,
2091	Item **having_item)
2092	{
2093	SELECT_LEX *select_lex= join->select_lex;
2094	DBUG_ASSERT(thd == join->thd);
2095	/*
2096	The non-transformed HAVING clause of 'join' may be stored in two ways
2097	during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
2098	*/
2099	Item* join_having= join->having ? join->having : join->tmp_having;
2100	DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
2101
2102	*where_item= NULL;
2103	*having_item= NULL;
2104
2105	if (join_having \|\| select_lex->with_sum_func \|\|
2106	select_lex->group_list.elements)
2107	{
2108	const char tmp= this*->full_name();
2109	LEX_CSTRING field_name= {tmp, safe_strlen(tmp)};
2110	Item *item= func->create(thd, expr,
2111	new (thd->mem_root) Item_ref_null_helper (
2112	thd,
2113	&select_lex->context,
2114	this,
2115	&select_lex->
2116	ref_pointer_array [`0`],
2117	(char *)"<ref>",
2118	&field_name));
2119	if (!abort_on_null && left_expr->maybe_null)
2120	{
2121	/*
2122	We can encounter "NULL IN (SELECT ...)". Wrap the added condition
2123	within a trig_cond.
2124	*/
2125	disable_cond_guard_for_const_null_left_expr(`0`);
2126	item= new (thd->mem_root) Item_func_trig_cond (thd, item, get_cond_guard(`0`));
2127	}
2128
2129	if (!join_having)
2130	item->name = in_having_cond;
2131	if (fix_having(item, select_lex))
2132	DBUG_RETURN(true);
2133	*having_item= item;
2134	}
2135	else
2136	{
2137	Item item= (Item) select_lex->item_list.head();
2138	if (item->type() != REF_ITEM \|\|
2139	((Item_ref*)item)->ref_type() != Item_ref::VIEW_REF)
2140	item= item->real_item();
2141
2142	if (select_lex->table_list.elements)
2143	{
2144	Item *having= item;
2145	Item *orig_item= item;
2146
2147	item= func->create(thd, expr, item);
2148	if (!abort_on_null && orig_item->maybe_null)
2149	{
2150	having= new (thd->mem_root) Item_is_not_null_test (thd, this, having);
2151	if (left_expr->maybe_null)
2152	{
2153	disable_cond_guard_for_const_null_left_expr(`0`);
2154	if (!(having= new (thd->mem_root) Item_func_trig_cond (thd, having,
2155	get_cond_guard(`0`))))
2156	DBUG_RETURN(true);
2157	}
2158	having->name = in_having_cond;
2159	if (fix_having(having, select_lex))
2160	DBUG_RETURN(true);
2161	*having_item= having;
2162
2163	item= new (thd->mem_root) Item_cond_or (thd, item,
2164	new (thd->mem_root) Item_func_isnull (thd, orig_item));
2165	}
2166	/*
2167	If we may encounter NULL IN (SELECT ...) and care whether subquery
2168	result is NULL or FALSE, wrap condition in a trig_cond.
2169	*/
2170	if (!abort_on_null && left_expr->maybe_null)
2171	{
2172	disable_cond_guard_for_const_null_left_expr(`0`);
2173	if (!(item= new (thd->mem_root) Item_func_trig_cond (thd, item,
2174	get_cond_guard(`0`))))
2175	DBUG_RETURN(true);
2176	}
2177
2178	/*
2179	TODO: figure out why the following is done here in
2180	single_value_transformer but there is no corresponding action in
2181	row_value_transformer?
2182	*/
2183	item->name = in_additional_cond;
2184	if (!item->fixed && item->fix_fields(thd, `0`))
2185	DBUG_RETURN(true);
2186	*where_item= item;
2187	}
2188	else
2189	{
2190	if (select_lex->master_unit()->is_unit_op())
2191	{
2192	LEX_CSTRING field_name= {STRING_WITH_LEN("<result>") };
2193	Item *new_having=
2194	func->create(thd, expr,
2195	new (thd->mem_root) Item_ref_null_helper (thd,
2196	&select_lex->context,
2197	this,
2198	&select_lex->ref_pointer_array [`0`],
2199	(char *)"<no matter>",
2200	&field_name));
2201	if (!abort_on_null && left_expr->maybe_null)
2202	{
2203	disable_cond_guard_for_const_null_left_expr(`0`);
2204	if (!(new_having= new (thd->mem_root) Item_func_trig_cond (thd, new_having,
2205	get_cond_guard(`0`))))
2206	DBUG_RETURN(true);
2207	}
2208
2209	new_having->name = in_having_cond;
2210	if (fix_having(new_having, select_lex))
2211	DBUG_RETURN(true);
2212	*having_item= new_having;
2213	}
2214	else
2215	DBUG_ASSERT(false);
2216	}
2217	}
2218
2219	DBUG_RETURN(false);
2220	}
2221
2222
2223	/**
2224	Wrap a multi-column IN/ALL/ANY subselect into an Item_in_optimizer.
2225
2226	@param join Join object of the subquery (i.e. 'child' join).
2227
2228	@details
2229	The subquery predicate is wrapped into an Item_in_optimizer. Later the query
2230	optimization phase chooses whether the subquery under the Item_in_optimizer
2231	will be further transformed into an equivalent correlated EXISTS by injecting
2232	additional predicates, or will be executed via subquery materialization in its
2233	unmodified form.
2234
2235	@retval false The subquery was transformed
2236	@retval true Error
2237	*/
2238
2239	bool
2240	Item_in_subselect::row_value_transformer(JOIN *join)
2241	{
2242	SELECT_LEX *select_lex= join->select_lex;
2243	uint cols_num= left_expr->cols();
2244
2245	DBUG_ENTER("Item_in_subselect::row_value_transformer");
2246	DBUG_ASSERT(thd == join->thd);
2247
2248	// psergey: duplicated_subselect_card_check
2249	if (select_lex->item_list.elements != cols_num)
2250	{
2251	my_error(ER_OPERAND_COLUMNS, MYF(`0`), cols_num);
2252	DBUG_RETURN(true);
2253	}
2254
2255	/*
2256	Wrap the current IN predicate in an Item_in_optimizer. The actual
2257	substitution in the Item tree takes place in Item_subselect::fix_fields.
2258	*/
2259	if (!substitution)
2260	{
2261	//first call for this unit
2262	SELECT_LEX_UNIT *master_unit= select_lex->master_unit();
2263	substitution= optimizer;
2264
2265	SELECT_LEX *current= thd->lex->current_select;
2266	thd->lex->current_select= current->return_after_parsing();
2267	if (!optimizer \|\| optimizer->fix_left(thd))
2268	{
2269	thd->lex->current_select= current;
2270	DBUG_RETURN(true);
2271	}
2272
2273	// we will refer to upper level cache array => we have to save it in PS
2274	optimizer->keep_top_level_cache();
2275
2276	thd->lex->current_select= current;
2277	/*
2278	The uncacheable property controls a number of actions, e.g. whether to
2279	save/restore (via init_save_join_tab/restore_tmp) the original JOIN for
2280	plans with a temp table where the original JOIN was overridden by
2281	make_simple_join. The UNCACHEABLE_EXPLAIN is ignored by EXPLAIN, thus
2282	non-correlated subqueries will not appear as such to EXPLAIN.
2283	*/
2284	master_unit->uncacheable\|= UNCACHEABLE_EXPLAIN;
2285	select_lex->uncacheable\|= UNCACHEABLE_EXPLAIN;
2286	}
2287
2288	DBUG_RETURN(false);
2289	}
2290
2291
2292	/**
2293	Create the predicates needed to transform a multi-column IN/ALL/ANY
2294	subselect into a correlated EXISTS via predicate injection.
2295
2296	@details
2297	The correlated predicates are created as follows:
2298
2299	- If the subquery has aggregates, GROUP BY, or HAVING, convert to
2300
2301	(l1, l2, l3) IN (SELECT v1, v2, v3 ... HAVING having)
2302	=>
2303	EXISTS (SELECT ... HAVING having and
2304	(l1 = v1 or is null v1) and
2305	(l2 = v2 or is null v2) and
2306	(l3 = v3 or is null v3) and
2307	is_not_null_test(v1) and
2308	is_not_null_test(v2) and
2309	is_not_null_test(v3))
2310
2311	where is_not_null_test used to register nulls in case if we have
2312	not found matching to return correct NULL value.
2313
2314	- Otherwise (no aggregates/GROUP BY/HAVING) convert the subquery as follows:
2315
2316	(l1, l2, l3) IN (SELECT v1, v2, v3 ... WHERE where)
2317	=>
2318	EXISTS (SELECT ... WHERE where and
2319	(l1 = v1 or is null v1) and
2320	(l2 = v2 or is null v2) and
2321	(l3 = v3 or is null v3)
2322	HAVING is_not_null_test(v1) and
2323	is_not_null_test(v2) and
2324	is_not_null_test(v3))
2325	where is_not_null_test registers NULLs values but reject rows.
2326
2327	in case when we do not need correct NULL, we have simplier construction:
2328	EXISTS (SELECT ... WHERE where and
2329	(l1 = v1) and
2330	(l2 = v2) and
2331	(l3 = v3)
2332
2333	@param join[in] Join object of the subquery (i.e. 'child' join).
2334	@param where_item[out] the in-to-exists addition to the where clause
2335	@param having_item[out] the in-to-exists addition to the having clause
2336
2337	@retval false If the new conditions were created successfully
2338	@retval true Error
2339	*/
2340
2341	bool
2342	Item_in_subselect::create_row_in_to_exists_cond(JOIN * join,
2343	Item **where_item,
2344	Item **having_item)
2345	{
2346	SELECT_LEX *select_lex= join->select_lex;
2347	uint cols_num= left_expr->cols();
2348	/*
2349	The non-transformed HAVING clause of 'join' may be stored in two ways
2350	during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
2351	*/
2352	Item* join_having= join->having ? join->having : join->tmp_having;
2353	bool is_having_used= (join_having \|\| select_lex->with_sum_func \|\|
2354	select_lex->group_list.first \|\|
2355	!select_lex->table_list.elements);
2356	LEX_CSTRING list_ref= { STRING_WITH_LEN("<list ref>")};
2357	DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
2358	DBUG_ASSERT(thd == join->thd);
2359
2360	*where_item= NULL;
2361	*having_item= NULL;
2362
2363	if (is_having_used)
2364	{
2365	/ TODO: say here explicitly if the order of AND parts matters or not. /
2366	Item *item_having_part2= `0`;
2367	for (uint i= `0`; i < cols_num; i++)
2368	{
2369	DBUG_ASSERT((left_expr->fixed &&
2370
2371	select_lex->ref_pointer_array[i]->fixed) \|\|
2372	(select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
2373	((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
2374	Item_ref::OUTER_REF));
2375	if (select_lex->ref_pointer_array [i]->
2376	check_cols(left_expr->element_index(i)->cols()))
2377	DBUG_RETURN(true);
2378
2379	Item *item_eq=
2380	new (thd->mem_root)
2381	Item_func_eq (thd, new (thd->mem_root)
2382	Item_direct_ref (thd, &select_lex->context,
2383	(*optimizer->get_cache())->
2384	addr(i),
2385	(char *)"<no matter>",
2386	&in_left_expr_name),
2387	new (thd->mem_root)
2388	Item_ref (thd, &select_lex->context,
2389	&select_lex->ref_pointer_array [i],
2390	(char *)"<no matter>",
2391	&list_ref));
2392	Item *item_isnull=
2393	new (thd->mem_root)
2394	Item_func_isnull (thd,
2395	new (thd->mem_root)
2396	Item_ref (thd, &select_lex->context,
2397	&select_lex->ref_pointer_array [i],
2398	(char *)"<no matter>",
2399	&list_ref));
2400	Item col_item= new* (thd->mem_root)
2401	Item_cond_or (thd, item_eq, item_isnull);
2402	if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
2403	get_cond_guard(i))
2404	{
2405	disable_cond_guard_for_const_null_left_expr(i);
2406	if (!(col_item= new (thd->mem_root)
2407	Item_func_trig_cond (thd, col_item, get_cond_guard(i))))
2408	DBUG_RETURN(true);
2409	}
2410	having_item= and_items(thd, having_item, col_item);
2411
2412	Item *item_nnull_test=
2413	new (thd->mem_root)
2414	Item_is_not_null_test (thd, this,
2415	new (thd->mem_root)
2416	Item_ref (thd, &select_lex->context,
2417	&select_lex->
2418	ref_pointer_array [i],
2419	(char *)"<no matter>",
2420	&list_ref));
2421	if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
2422	get_cond_guard(i) )
2423	{
2424	disable_cond_guard_for_const_null_left_expr(i);
2425	if (!(item_nnull_test=
2426	new (thd->mem_root)
2427	Item_func_trig_cond (thd, item_nnull_test, get_cond_guard(i))))
2428	DBUG_RETURN(true);
2429	}
2430	item_having_part2= and_items(thd, item_having_part2, item_nnull_test);
2431	item_having_part2->top_level_item();
2432	}
2433	having_item= and_items(thd, having_item, item_having_part2);
2434	}
2435	else
2436	{
2437	for (uint i= `0`; i < cols_num; i++)
2438	{
2439	Item item, item_isnull;
2440	DBUG_ASSERT((left_expr->fixed &&
2441	select_lex->ref_pointer_array[i]->fixed) \|\|
2442	(select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
2443	((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
2444	Item_ref::OUTER_REF));
2445	if (select_lex->ref_pointer_array [i]->
2446	check_cols(left_expr->element_index(i)->cols()))
2447	DBUG_RETURN(true);
2448	item= new (thd->mem_root)
2449	Item_func_eq (thd,
2450	new (thd->mem_root)
2451	Item_direct_ref (thd, &select_lex->context,
2452	(*optimizer->get_cache())->
2453	addr(i),
2454	(char *)"<no matter>",
2455	&in_left_expr_name),
2456	new (thd->mem_root)
2457	Item_direct_ref (thd, &select_lex->context,
2458	&select_lex->
2459	ref_pointer_array [i],
2460	(char *)"<no matter>",
2461	&list_ref));
2462	if (!abort_on_null && select_lex->ref_pointer_array [i]->maybe_null)
2463	{
2464	Item *having_col_item=
2465	new (thd->mem_root)
2466	Item_is_not_null_test (thd, this,
2467	new (thd->mem_root)
2468	Item_ref (thd, &select_lex->context,
2469	&select_lex->ref_pointer_array [i],
2470	(char *)"<no matter>",
2471	&list_ref));
2472
2473	item_isnull= new (thd->mem_root)
2474	Item_func_isnull (thd,
2475	new (thd->mem_root)
2476	Item_direct_ref (thd, &select_lex->context,
2477	&select_lex->
2478	ref_pointer_array [i],
2479	(char *)"<no matter>",
2480	&list_ref));
2481	item= new (thd->mem_root) Item_cond_or (thd, item, item_isnull);
2482	if (left_expr->element_index(i)->maybe_null && get_cond_guard(i))
2483	{
2484	disable_cond_guard_for_const_null_left_expr(i);
2485	if (!(item= new (thd->mem_root)
2486	Item_func_trig_cond (thd, item, get_cond_guard(i))))
2487	DBUG_RETURN(true);
2488	if (!(having_col_item= new (thd->mem_root)
2489	Item_func_trig_cond (thd, having_col_item, get_cond_guard(i))))
2490	DBUG_RETURN(true);
2491	}
2492	having_item= and_items(thd, having_item, having_col_item);
2493	}
2494	if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
2495	get_cond_guard(i))
2496	{
2497	if (!(item= new (thd->mem_root)
2498	Item_func_trig_cond (thd, item, get_cond_guard(i))))
2499	DBUG_RETURN(true);
2500	}
2501	where_item= and_items(thd, where_item, item);
2502	}
2503	}
2504
2505	if (*where_item)
2506	{
2507	if (!(where_item)->fixed && (where_item)->fix_fields(thd, `0`))
2508	DBUG_RETURN(true);
2509	(*where_item)->top_level_item();
2510	}
2511
2512	if (*having_item)
2513	{
2514	if (!join_having)
2515	(*having_item)->name = in_having_cond;
2516	if (fix_having(*having_item, select_lex))
2517	DBUG_RETURN(true);
2518	(*having_item)->top_level_item();
2519	}
2520
2521	DBUG_RETURN(false);
2522	}
2523
2524
2525	bool
2526	Item_in_subselect::select_transformer(JOIN *join)
2527	{
2528	return select_in_like_transformer(join);
2529	}
2530
2531	bool
2532	Item_exists_subselect::select_transformer(JOIN *join)
2533	{
2534	return select_prepare_to_be_in();
2535	}
2536
2537
2538	/**
2539	Create the predicates needed to transform an IN/ALL/ANY subselect into a
2540	correlated EXISTS via predicate injection.
2541
2542	@param join_arg Join object of the subquery.
2543
2544	@retval FALSE ok
2545	@retval TRUE error
2546	*/
2547
2548	bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
2549	{
2550	bool res;
2551
2552	DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE \|\|
2553	engine->engine_type() == subselect_engine::UNION_ENGINE);
2554	/*
2555	TODO: the call to init_cond_guards allocates and initializes an
2556	array of booleans that may not be used later because we may choose
2557	materialization.
2558	The two calls below to create_XYZ_cond depend on this boolean array.
2559	If the dependency is removed, the call can be moved to a later phase.
2560	*/
2561	init_cond_guards();
2562	if (left_expr->cols() == `1`)
2563	res= create_single_in_to_exists_cond(join_arg,
2564	&(join_arg->in_to_exists_where),
2565	&(join_arg->in_to_exists_having));
2566	else
2567	res= create_row_in_to_exists_cond(join_arg,
2568	&(join_arg->in_to_exists_where),
2569	&(join_arg->in_to_exists_having));
2570
2571	/*
2572	The IN=>EXISTS transformation makes non-correlated subqueries correlated.
2573	*/
2574	if (!left_expr->const_item() \|\| left_expr->is_expensive())
2575	{
2576	join_arg->select_lex->uncacheable\|= UNCACHEABLE_DEPENDENT_INJECTED;
2577	join_arg->select_lex->master_unit()->uncacheable\|=
2578	UNCACHEABLE_DEPENDENT_INJECTED;
2579	}
2580	/*
2581	The uncacheable property controls a number of actions, e.g. whether to
2582	save/restore (via init_save_join_tab/restore_tmp) the original JOIN for
2583	plans with a temp table where the original JOIN was overridden by
2584	make_simple_join. The UNCACHEABLE_EXPLAIN is ignored by EXPLAIN, thus
2585	non-correlated subqueries will not appear as such to EXPLAIN.
2586	*/
2587	join_arg->select_lex->master_unit()->uncacheable\|= UNCACHEABLE_EXPLAIN;
2588	join_arg->select_lex->uncacheable\|= UNCACHEABLE_EXPLAIN;
2589	return (res);
2590	}
2591
2592
2593	/**
2594	Transform an IN/ALL/ANY subselect into a correlated EXISTS via injecting
2595	correlated in-to-exists predicates.
2596
2597	@param join_arg Join object of the subquery.
2598
2599	@retval FALSE ok
2600	@retval TRUE error
2601	*/
2602
2603	bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
2604	{
2605	SELECT_LEX *select_lex= join_arg->select_lex;
2606	Item *where_item= join_arg->in_to_exists_where;
2607	Item *having_item= join_arg->in_to_exists_having;
2608
2609	DBUG_ENTER("Item_in_subselect::inject_in_to_exists_cond");
2610	DBUG_ASSERT(thd == join_arg->thd);
2611
2612	if (select_lex->min_max_opt_list.elements)
2613	{
2614	/*
2615	MIN/MAX optimizations have been applied to Item_sum objects
2616	of the subquery this subquery predicate in opt_sum_query().
2617	Injection of new condition invalidates this optimizations.
2618	Thus those optimizations must be rolled back.
2619	*/
2620	List_iterator_fast<Item_sum> it(select_lex->min_max_opt_list);
2621	Item_sum *item;
2622	while ((item= it ++))
2623	{
2624	item->clear();
2625	item->reset_forced_const();
2626	}
2627	if (where_item)
2628	where_item->update_used_tables();
2629	if (having_item)
2630	having_item->update_used_tables();
2631	}
2632
2633	if (where_item)
2634	{
2635	List<Item> *and_args= NULL;
2636	/*
2637	If the top-level Item of the WHERE clause is an AND, detach the multiple
2638	equality list that was attached to the end of the AND argument list by
2639	build_equal_items_for_cond(). The multiple equalities must be detached
2640	because fix_fields merges lower level AND arguments into the upper AND.
2641	As a result, the arguments from lower-level ANDs are concatenated after
2642	the multiple equalities. When the multiple equality list is treated as
2643	such, it turns out that it contains non-Item_equal object which is wrong.
2644	*/
2645	if (join_arg->conds && join_arg->conds->type() == Item::COND_ITEM &&
2646	((Item_cond*) join_arg->conds)->functype() == Item_func::COND_AND_FUNC)
2647	{
2648	and_args= ((Item_cond*) join_arg->conds)->argument_list();
2649	if (join_arg->cond_equal)
2650	and_args->disjoin((List<Item> *) &join_arg->cond_equal->current_level);
2651	}
2652
2653	where_item= and_items(thd, join_arg->conds, where_item);
2654	if (!where_item->fixed && where_item->fix_fields(thd, `0`))
2655	DBUG_RETURN(true);
2656	// TIMOUR TODO: call optimize_cond() for the new where clause
2657	thd->change_item_tree(&select_lex->where, where_item);
2658	select_lex->where->top_level_item();
2659	join_arg->conds= select_lex->where;
2660
2661	/ Attach back the list of multiple equalities to the new top-level AND. /
2662	if (and_args && join_arg->cond_equal)
2663	{
2664	/ The argument list of the top-level AND may change after fix fields. /
2665	and_args= ((Item_cond*) join_arg->conds)->argument_list();
2666	List_iterator<Item_equal> li(join_arg->cond_equal->current_level);
2667	Item_equal *elem;
2668	while ((elem= li ++))
2669	{
2670	and_args->push_back(elem, thd->mem_root);
2671	}
2672	}
2673	}
2674
2675	if (having_item)
2676	{
2677	Item* join_having= join_arg->having ? join_arg->having:join_arg->tmp_having;
2678	having_item= and_items(thd, join_having, having_item);
2679	if (fix_having(having_item, select_lex))
2680	DBUG_RETURN(true);
2681	// TIMOUR TODO: call optimize_cond() for the new having clause
2682	thd->change_item_tree(&select_lex->having, having_item);
2683	select_lex->having->top_level_item();
2684	join_arg->having= select_lex->having;
2685	}
2686	join_arg->thd->change_item_tree(&unit->global_parameters()->select_limit,
2687	new (thd->mem_root)
2688	Item_int (thd, (int32) `1`));
2689	unit->select_limit_cnt= `1`;
2690
2691	DBUG_RETURN(false);
2692	}
2693
2694
2695	/*
2696	If this select can potentially be converted by EXISTS->IN conversion, wrap it
2697	in an Item_in_optimizer object. Final decision whether to do the conversion
2698	is done at a later phase.
2699	*/
2700
2701	bool Item_exists_subselect::select_prepare_to_be_in()
2702	{
2703	bool trans_res= FALSE;
2704	DBUG_ENTER("Item_exists_subselect::select_prepare_to_be_in");
2705	if (!optimizer &&
2706	thd->lex->sql_command == SQLCOM_SELECT &&
2707	!unit->first_select()->is_part_of_union() &&
2708	optimizer_flag(thd, OPTIMIZER_SWITCH_EXISTS_TO_IN) &&
2709	(is_top_level_item() \|\|
2710	(upper_not && upper_not->is_top_level_item())))
2711	{
2712	Query_arena *arena, backup;
2713	bool result;
2714	arena= thd->activate_stmt_arena_if_needed(&backup);
2715	result= (!(optimizer= new (thd->mem_root) Item_in_optimizer (thd, new (thd->mem_root) Item_int (thd, `1`), this)));
2716	if (arena)
2717	thd->restore_active_arena(arena, &backup);
2718	if (result)
2719	trans_res= TRUE;
2720	else
2721	substitution= optimizer;
2722	}
2723	DBUG_RETURN(trans_res);
2724	}
2725
2726	/**
2727	Check if 'func' is an equality in form "inner_table.column = outer_expr"
2728
2729	@param func Expression to check
2730	@param local_field OUT Return "inner_table.column" here
2731	@param outer_expr OUT Return outer_expr here
2732
2733	@return true - 'func' is an Equality.
2734	*/
2735
2736	static bool check_equality_for_exist2in(Item_func *func,
2737	Item_ident **local_field,
2738	Item **outer_exp)
2739	{
2740	Item **args;
2741	if (func->functype() != Item_func::EQ_FUNC)
2742	return FALSE;
2743	DBUG_ASSERT(func->argument_count() == `2`);
2744	args= func->arguments();
2745	if (args[`0`]->real_type() == Item::FIELD_ITEM &&
2746	args[`0`]->all_used_tables() != OUTER_REF_TABLE_BIT &&
2747	args[`1`]->all_used_tables() == OUTER_REF_TABLE_BIT)
2748	{
2749	/ It is Item_field or Item_direct_view_ref) /
2750	DBUG_ASSERT(args[`0`]->type() == Item::FIELD_ITEM \|\|
2751	args[`0`]->type() == Item::REF_ITEM);
2752	local_field= (Item_ident )args[`0`];
2753	*outer_exp= args[`1`];
2754	return TRUE;
2755	}
2756	else if (args[`1`]->real_type() == Item::FIELD_ITEM &&
2757	args[`1`]->all_used_tables() != OUTER_REF_TABLE_BIT &&
2758	args[`0`]->all_used_tables() == OUTER_REF_TABLE_BIT)
2759	{
2760	/ It is Item_field or Item_direct_view_ref) /
2761	DBUG_ASSERT(args[`1`]->type() == Item::FIELD_ITEM \|\|
2762	args[`1`]->type() == Item::REF_ITEM);
2763	local_field= (Item_ident )args[`1`];
2764	*outer_exp= args[`0`];
2765	return TRUE;
2766	}
2767
2768	return FALSE;
2769	}
2770
2771	typedef struct st_eq_field_outer
2772	{
2773	Item **eq_ref;
2774	Item_ident *local_field;
2775	Item *outer_exp;
2776	} EQ_FIELD_OUTER;
2777
2778
2779	/**
2780	Check if 'conds' is a set of AND-ed outer_expr=inner_table.col equalities
2781
2782	@detail
2783	Check if 'conds' has form
2784
2785	outer1=inner_tbl1.col1 AND ... AND outer2=inner_tbl1.col2 AND remainder_cond
2786
2787	@param conds Condition to be checked
2788	@parm result Array to collect EQ_FIELD_OUTER elements describing
2789	inner-vs-outer equalities the function has found.
2790	@return
2791	false - some inner-vs-outer equalities were found
2792	true - otherwise.
2793	*/
2794
2795	static bool find_inner_outer_equalities(Item **conds,
2796	Dynamic_array<EQ_FIELD_OUTER> &result)
2797	{
2798	bool found= FALSE;
2799	EQ_FIELD_OUTER element;
2800	if (is_cond_and(*conds))
2801	{
2802	List_iterator<Item> li(((Item_cond)*conds)->argument_list());
2803	Item *item;
2804	while ((item= li ++))
2805	{
2806	if (item->type() == Item::FUNC_ITEM &&
2807	check_equality_for_exist2in((Item_func *)item,
2808	&element.local_field,
2809	&element.outer_exp))
2810	{
2811	found= TRUE;
2812	element.eq_ref= li.ref();
2813	if (result.append(element))
2814	goto alloc_err;
2815	}
2816	}
2817	}
2818	else if ((*conds)->type() == Item::FUNC_ITEM &&
2819	check_equality_for_exist2in((Item_func )conds,
2820	&element.local_field,
2821	&element.outer_exp))
2822	{
2823	found= TRUE;
2824	element.eq_ref= conds;
2825	if (result.append(element))
2826	goto alloc_err;
2827	}
2828
2829	return !found;
2830	alloc_err:
2831	return TRUE;
2832	}
2833
2834	/**
2835	Converts EXISTS subquery to IN subquery if it is possible and has sense
2836
2837	@param opt_arg Pointer on THD
2838
2839	@return TRUE in case of error and FALSE otherwise.
2840	*/
2841
2842	bool Item_exists_subselect::exists2in_processor(void *opt_arg)
2843	{
2844	THD thd= (THD )opt_arg;
2845	SELECT_LEX first_select=unit->first_select(), save_select;
2846	JOIN *join= first_select->join;
2847	Item **eq_ref= NULL;
2848	Item_ident *local_field= NULL;
2849	Item *outer_exp= NULL;
2850	Item left_exp= NULL; Item_in_subselect in_subs;
2851	Query_arena *arena= NULL, backup;
2852	int res= FALSE;
2853	List<Item> outer;
2854	Dynamic_array<EQ_FIELD_OUTER> eqs(`5`, `5`);
2855	bool will_be_correlated;
2856	DBUG_ENTER("Item_exists_subselect::exists2in_processor");
2857
2858	if (!optimizer \|\|
2859	!optimizer_flag(thd, OPTIMIZER_SWITCH_EXISTS_TO_IN) \|\|
2860	(!is_top_level_item() && (!upper_not \|\|
2861	!upper_not->is_top_level_item())) \|\|
2862	first_select->is_part_of_union() \|\|
2863	first_select->group_list.elements \|\|
2864	first_select->order_list.elements \|\|
2865	join->having \|\|
2866	first_select->with_sum_func \|\|
2867	!first_select->leaf_tables.elements\|\|
2868	!join->conds \|\|
2869	with_recursive_reference)
2870	DBUG_RETURN(FALSE);
2871
2872	DBUG_ASSERT(first_select->order_list.elements == `0` &&
2873	first_select->group_list.elements == `0` &&
2874	first_select->having == NULL);
2875
2876	if (find_inner_outer_equalities(&join->conds, eqs))
2877	DBUG_RETURN(FALSE);
2878
2879	DBUG_ASSERT(eqs.elements() != `0`);
2880
2881	save_select= thd->lex->current_select;
2882	thd->lex->current_select= first_select;
2883
2884	/ check that the subquery has only dependencies we are going pull out /
2885	{
2886	List<Item> unused;
2887	Collect_deps_prm prm= {&unused, // parameters
2888	unit->first_select()->nest_level_base, // nest_level_base
2889	`0`, // count
2890	unit->first_select()->nest_level, // nest_level
2891	FALSE // collect
2892	};
2893	walk(&Item::collect_outer_ref_processor, TRUE, &prm);
2894	DBUG_ASSERT(prm.count > `0`);
2895	DBUG_ASSERT(prm.count >= (uint)eqs.elements());
2896	will_be_correlated= prm.count > (uint)eqs.elements();
2897	if (upper_not && will_be_correlated)
2898	goto out;
2899	}
2900
2901	if ((uint)eqs.elements() > (first_select->item_list.elements +
2902	first_select->select_n_reserved))
2903	goto out;
2904	/ It is simple query /
2905	DBUG_ASSERT(first_select->join->all_fields.elements ==
2906	first_select->item_list.elements);
2907
2908	arena= thd->activate_stmt_arena_if_needed(&backup);
2909
2910	while (first_select->item_list.elements > (uint)eqs.elements())
2911	{
2912	first_select->item_list.pop();
2913	first_select->join->all_fields.elements--;
2914	}
2915	{
2916	List_iterator<Item> it(first_select->item_list);
2917
2918	for (uint i= `0`; i < (uint)eqs.elements(); i++)
2919	{
2920	Item *item= it ++;
2921	eq_ref= eqs.at(i).eq_ref;
2922	local_field= eqs.at(i).local_field;
2923	outer_exp= eqs.at(i).outer_exp;
2924	/ Add the field to the SELECT_LIST /
2925	if (item)
2926	it.replace(local_field);
2927	else
2928	{
2929	first_select->item_list.push_back(local_field, thd->mem_root);
2930	first_select->join->all_fields.elements++;
2931	}
2932	first_select->ref_pointer_array [i]= (Item *)local_field;
2933
2934	/ remove the parts from condition /
2935	if (!upper_not \|\| !local_field->maybe_null)
2936	eq_ref= new* (thd->mem_root) Item_int (thd, `1`);
2937	else
2938	{
2939	eq_ref= new* (thd->mem_root)
2940	Item_func_isnotnull (thd,
2941	new (thd->mem_root)
2942	Item_field (thd,
2943	((Item_field*)(local_field->
2944	real_item()))->context,
2945	((Item_field*)(local_field->
2946	real_item()))->field));
2947	if((eq_ref)->fix_fields(thd, (Item *)eq_ref))
2948	{
2949	res= TRUE;
2950	goto out;
2951	}
2952	}
2953	outer_exp->fix_after_pullout(unit->outer_select(), &outer_exp, FALSE);
2954	outer_exp->update_used_tables();
2955	outer.push_back(outer_exp, thd->mem_root);
2956	}
2957	}
2958
2959	join->conds->update_used_tables();
2960
2961	/ make IN SUBQUERY and put outer_exp as left part /
2962	if (eqs.elements() == `1`)
2963	left_exp= outer_exp;
2964	else
2965	{
2966	if (!(left_exp= new (thd->mem_root) Item_row (thd, outer)))
2967	{
2968	res= TRUE;
2969	goto out;
2970	}
2971	}
2972
2973	/ make EXISTS->IN permanet (see Item_subselect::init()) /
2974	set_exists_transformed();
2975
2976	first_select->select_limit= NULL;
2977	if (!(in_subs= new (thd->mem_root) Item_in_subselect (thd, left_exp,
2978	first_select)))
2979	{
2980	res= TRUE;
2981	goto out;
2982	}
2983	in_subs->set_exists_transformed();
2984	optimizer->arguments()[`0`]= left_exp;
2985	optimizer->arguments()[`1`]= in_subs;
2986	in_subs->optimizer= optimizer;
2987	DBUG_ASSERT(is_top_level_item() \|\|
2988	(upper_not && upper_not->is_top_level_item()));
2989	in_subs->top_level_item();
2990	{
2991	SELECT_LEX *current= thd->lex->current_select;
2992	optimizer->reset_cache(); // renew cache, and we will not keep it
2993	thd->lex->current_select= unit->outer_select();
2994	DBUG_ASSERT(optimizer);
2995	if (optimizer->fix_left(thd))
2996	{
2997	res= TRUE;
2998	/*
2999	We should not restore thd->lex->current_select because it will be
3000	reset on exit from this procedure
3001	*/
3002	goto out;
3003	}
3004	/*
3005	As far as Item_ref_in_optimizer do not substitute itself on fix_fields
3006	we can use same item for all selects.
3007	*/
3008	in_subs->expr= new (thd->mem_root)
3009	Item_direct_ref (thd, &first_select->context,
3010	(Item**)optimizer->get_cache(),
3011	(char *)"<no matter>",
3012	&in_left_expr_name);
3013	if (in_subs->fix_fields(thd, optimizer->arguments() + `1`))
3014	{
3015	res= TRUE;
3016	/*
3017	We should not restore thd->lex->current_select because it will be
3018	reset on exit from this procedure
3019	*/
3020	goto out;
3021	}
3022	{
3023	/ Move dependence list /
3024	List_iterator_fast<Ref_to_outside> it(upper_refs);
3025	Ref_to_outside *upper;
3026	while ((upper= it ++))
3027	{
3028	uint i;
3029	for (i= `0`; i < (uint)eqs.elements(); i++)
3030	if (eqs.at(i).outer_exp->
3031	walk(&Item::find_item_processor, TRUE, upper->item))
3032	break;
3033	if (i == (uint)eqs.elements() &&
3034	(in_subs->upper_refs.push_back(upper, thd->stmt_arena->mem_root)))
3035	goto out;
3036	}
3037	}
3038	in_subs->update_used_tables();
3039	/*
3040	The engine of the subquery is fixed so above fix_fields() is not
3041	complete and should be fixed
3042	*/
3043	in_subs->upper_refs = upper_refs;
3044	upper_refs.empty();
3045	thd->lex->current_select= current;
3046	}
3047
3048	DBUG_ASSERT(unit->item == in_subs);
3049	DBUG_ASSERT(join == first_select->join);
3050	/*
3051	Fix dependency info
3052	*/
3053	in_subs->is_correlated= will_be_correlated;
3054	if (!will_be_correlated)
3055	{
3056	first_select->uncacheable&= ~UNCACHEABLE_DEPENDENT_GENERATED;
3057	unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_GENERATED;
3058	}
3059	/*
3060	set possible optimization strategies
3061	*/
3062	in_subs->emb_on_expr_nest= emb_on_expr_nest;
3063	res= check_and_do_in_subquery_rewrites(join);
3064	first_select->join->prepare_stage2();
3065
3066	first_select->fix_prepare_information(thd, &join->conds, &join->having);
3067
3068	if (upper_not)
3069	{
3070	Item *exp;
3071	if (eqs.elements() == `1`)
3072	{
3073	exp= (optimizer->arguments()[`0`]->maybe_null ?
3074	(Item) new* (thd->mem_root)
3075	Item_cond_and (thd,
3076	new (thd->mem_root)
3077	Item_func_isnotnull (thd,
3078	new (thd->mem_root)
3079	Item_direct_ref (thd,
3080	&unit->outer_select()->context,
3081	optimizer->arguments(),
3082	(char *)"<no matter>",
3083	&exists_outer_expr_name)),
3084	optimizer) :
3085	(Item *)optimizer);
3086	}
3087	else
3088	{
3089	List<Item> and_list= new* List<Item>;
3090	if (!and_list)
3091	{
3092	res= TRUE;
3093	goto out;
3094	}
3095	for (size_t i= `0`; i < eqs.elements(); i++)
3096	{
3097	if (optimizer->arguments()[`0`]->maybe_null)
3098	{
3099	and_list->
3100	push_front(new (thd->mem_root)
3101	Item_func_isnotnull (thd,
3102	new (thd->mem_root)
3103	Item_direct_ref (thd,
3104	&unit->outer_select()->context,
3105	optimizer->arguments()[`0`]->addr((int)i),
3106	(char *)"<no matter>",
3107	&exists_outer_expr_name)),
3108	thd->mem_root);
3109	}
3110	}
3111	if (and_list->elements > `0`)
3112	{
3113	and_list->push_front(optimizer, thd->mem_root);
3114	exp= new (thd->mem_root) Item_cond_and (thd, *and_list);
3115	}
3116	else
3117	exp= optimizer;
3118	}
3119	upper_not->arguments()[`0`]= exp;
3120	if (!exp->fixed && exp->fix_fields(thd, upper_not->arguments()))
3121	{
3122	res= TRUE;
3123	goto out;
3124	}
3125	}
3126
3127	out:
3128	thd->lex->current_select= save_select;
3129	if (arena)
3130	thd->restore_active_arena(arena, &backup);
3131	DBUG_RETURN(res);
3132	}
3133
3134
3135	/**
3136	Prepare IN/ALL/ANY/SOME subquery transformation and call the appropriate
3137	transformation function.
3138
3139	@param join JOIN object of transforming subquery
3140
3141	@notes
3142	To decide which transformation procedure (scalar or row) applicable here
3143	we have to call fix_fields() for the left expression to be able to call
3144	cols() method on it. Also this method makes arena management for
3145	underlying transformation methods.
3146
3147	@retval false OK
3148	@retval true Error
3149	*/
3150
3151	bool
3152	Item_in_subselect::select_in_like_transformer(JOIN *join)
3153	{
3154	Query_arena *arena= `0`, backup;
3155	SELECT_LEX *current= thd->lex->current_select;
3156	const char *save_where= thd->where;
3157	bool trans_res= true;
3158	bool result;
3159
3160	DBUG_ENTER("Item_in_subselect::select_in_like_transformer");
3161	DBUG_ASSERT(thd == join->thd);
3162
3163	/*
3164	IN/SOME/ALL/ANY subqueries aren't support LIMIT clause. Without it
3165	ORDER BY clause becomes meaningless thus we drop it here.
3166	*/
3167	for (SELECT_LEX *sl= current->master_unit()->first_select();
3168	sl; sl= sl->next_select())
3169	{
3170	if (sl->join)
3171	{
3172	sl->join->order= `0`;
3173	sl->join->skip_sort_order= `1`;
3174	}
3175	}
3176
3177	thd->where= "IN/ALL/ANY subquery";
3178
3179	/*
3180	In some optimisation cases we will not need this Item_in_optimizer
3181	object, but we can't know it here, but here we need address correct
3182	reference on left expresion.
3183
3184	note: we won't need Item_in_optimizer when handling degenerate cases
3185	like "... IN (SELECT 1)"
3186	*/
3187	arena= thd->activate_stmt_arena_if_needed(&backup);
3188	if (!optimizer)
3189	{
3190	optimizer= new (thd->mem_root) Item_in_optimizer (thd, left_expr_orig, this);
3191	if ((result= !optimizer))
3192	goto out;
3193	}
3194
3195	thd->lex->current_select= current->return_after_parsing();
3196	result= optimizer->fix_left(thd);
3197	thd->lex->current_select= current;
3198
3199	if (changed)
3200	{
3201	trans_res= false;
3202	goto out;
3203	}
3204
3205
3206	if (result)
3207	goto out;
3208
3209	/*
3210	Both transformers call fix_fields() only for Items created inside them,
3211	and all that items do not make permanent changes in current item arena
3212	which allow to us call them with changed arena (if we do not know nature
3213	of Item, we have to call fix_fields() for it only with original arena to
3214	avoid memory leack)
3215	*/
3216	if (left_expr->cols() == `1`)
3217	trans_res= single_value_transformer(join);
3218	else
3219	{
3220	/ we do not support row operation for ALL/ANY/SOME /
3221	if (func != &eq_creator)
3222	{
3223	if (arena)
3224	thd->restore_active_arena(arena, &backup);
3225	my_error(ER_OPERAND_COLUMNS, MYF(`0`), `1`);
3226	DBUG_RETURN(true);
3227	}
3228	trans_res= row_value_transformer(join);
3229	}
3230	out:
3231	if (arena)
3232	thd->restore_active_arena(arena, &backup);
3233	thd->where= save_where;
3234	DBUG_RETURN(trans_res);
3235	}
3236
3237
3238	void Item_in_subselect::print(String *str, enum_query_type query_type)
3239	{
3240	if (test_strategy(SUBS_IN_TO_EXISTS))
3241	str->append(STRING_WITH_LEN("<exists>"));
3242	else
3243	{
3244	left_expr->print(str, query_type);
3245	str->append(STRING_WITH_LEN(" in "));
3246	}
3247	Item_subselect::print(str, query_type);
3248	}
3249
3250	bool Item_exists_subselect::fix_fields(THD thd, Item *ref)
3251	{
3252	DBUG_ENTER("Item_exists_subselect::fix_fields");
3253	if (exists_transformed)
3254	DBUG_RETURN( !( (ref)= new* (thd->mem_root) Item_int (thd, `1`)));
3255	DBUG_RETURN(Item_subselect::fix_fields(thd, ref));
3256	}
3257
3258
3259	bool Item_in_subselect::fix_fields(THD thd_arg, Item *ref)
3260	{
3261	uint outer_cols_num;
3262	List<Item> *inner_cols;
3263	char const *save_where= thd_arg->where;
3264	DBUG_ENTER("Item_in_subselect::fix_fields");
3265
3266	thd= thd_arg;
3267	DBUG_ASSERT(unit->thd == thd);
3268
3269	if (test_strategy(SUBS_SEMI_JOIN))
3270	DBUG_RETURN( !( (ref)= new* (thd->mem_root) Item_int (thd, `1`)) );
3271
3272	thd->where= "IN/ALL/ANY subquery";
3273	/*
3274	Check if the outer and inner IN operands match in those cases when we
3275	will not perform IN=>EXISTS transformation. Currently this is when we
3276	use subquery materialization.
3277
3278	The condition below is true when this method was called recursively from
3279	inside JOIN::prepare for the JOIN object created by the call chain
3280	Item_subselect::fix_fields -> subselect_single_select_engine::prepare,
3281	which creates a JOIN object for the subquery and calls JOIN::prepare for
3282	the JOIN of the subquery.
3283	Notice that in some cases, this doesn't happen, and the check_cols()
3284	test for each Item happens later in
3285	Item_in_subselect::row_value_in_to_exists_transformer.
3286	The reason for this mess is that our JOIN::prepare phase works top-down
3287	instead of bottom-up, so we first do name resoluton and semantic checks
3288	for the outer selects, then for the inner.
3289	*/
3290	if (engine &&
3291	engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE &&
3292	((subselect_single_select_engine*)engine)->join)
3293	{
3294	outer_cols_num= left_expr->cols();
3295
3296	if (unit->is_unit_op())
3297	inner_cols= &(unit->types);
3298	else
3299	inner_cols= &(unit->first_select()->item_list);
3300	if (outer_cols_num != inner_cols->elements)
3301	{
3302	my_error(ER_OPERAND_COLUMNS, MYF(`0`), outer_cols_num);
3303	goto err;
3304	}
3305	if (outer_cols_num > `1`)
3306	{
3307	List_iterator<Item> inner_col_it(*inner_cols);
3308	Item *inner_col;
3309	for (uint i= `0`; i < outer_cols_num; i++)
3310	{
3311	inner_col= inner_col_it ++;
3312	if (inner_col->check_cols(left_expr->element_index(i)->cols()))
3313	goto err;
3314	}
3315	}
3316	}
3317
3318	if (left_expr && !left_expr->fixed &&
3319	left_expr->fix_fields(thd_arg, &left_expr))
3320	goto err;
3321	else
3322	if (Item_subselect::fix_fields(thd_arg, ref))
3323	goto err;
3324	fixed= TRUE;
3325	thd->where= save_where;
3326	DBUG_RETURN(FALSE);
3327
3328	err:
3329	thd->where= save_where;
3330	DBUG_RETURN(TRUE);
3331	}
3332
3333
3334	void Item_in_subselect::fix_after_pullout(st_select_lex *new_parent,
3335	Item *ref, bool* merge)
3336	{
3337	left_expr->fix_after_pullout(new_parent, &left_expr, merge);
3338	Item_subselect::fix_after_pullout(new_parent, ref, merge);
3339	used_tables_cache \|= left_expr->used_tables();
3340	}
3341
3342	void Item_in_subselect::update_used_tables()
3343	{
3344	Item_subselect::update_used_tables();
3345	left_expr->update_used_tables();
3346	//used_tables_cache \|= left_expr->used_tables();
3347	used_tables_cache= Item_subselect::used_tables() \| left_expr->used_tables();
3348	}
3349
3350
3351	/**
3352	Try to create and initialize an engine to compute a subselect via
3353	materialization.
3354
3355	@details
3356	The method creates a new engine for materialized execution, and initializes
3357	the engine. The initialization may fail
3358	- either because it wasn't possible to create the needed temporary table
3359	and its index,
3360	- or because of a memory allocation error,
3361
3362	@returns
3363	@retval TRUE memory allocation error occurred
3364	@retval FALSE an execution method was chosen successfully
3365	*/
3366
3367	bool Item_in_subselect::setup_mat_engine()
3368	{
3369	subselect_hash_sj_engine *mat_engine= NULL;
3370	subselect_single_select_engine *select_engine;
3371
3372	DBUG_ENTER("Item_in_subselect::setup_mat_engine");
3373	DBUG_ASSERT(thd);
3374
3375	/*
3376	The select_engine (that executes transformed IN=>EXISTS subselects) is
3377	pre-created at parse time, and is stored in statment memory (preserved
3378	across PS executions).
3379	*/
3380	DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE);
3381	select_engine= (subselect_single_select_engine*) engine;
3382
3383	/ Create/initialize execution objects. /
3384	if (!(mat_engine= new subselect_hash_sj_engine (thd, this, select_engine)))
3385	DBUG_RETURN(TRUE);
3386
3387	if (mat_engine->prepare(thd) \|\|
3388	mat_engine->init(&select_engine->join->fields_list,
3389	engine->get_identifier()))
3390	DBUG_RETURN(TRUE);
3391
3392	engine= mat_engine;
3393	DBUG_RETURN(FALSE);
3394	}
3395
3396
3397	/**
3398	Initialize the cache of the left operand of the IN predicate.
3399
3400	@note This method has the same purpose as alloc_group_fields(),
3401	but it takes a different kind of collection of items, and the
3402	list we push to is dynamically allocated.
3403
3404	@retval TRUE if a memory allocation error occurred or the cache is
3405	not applicable to the current query
3406	@retval FALSE if success
3407	*/
3408
3409	bool Item_in_subselect::init_left_expr_cache()
3410	{
3411	JOIN *outer_join;
3412	DBUG_ASSERT(thd);
3413
3414	outer_join= unit->outer_select()->join;
3415	/*
3416	An IN predicate might be evaluated in a query for which all tables have
3417	been optimzied away.
3418	*/
3419	if (!outer_join \|\| !outer_join->table_count \|\| !outer_join->tables_list)
3420	return TRUE;
3421
3422	if (!(left_expr_cache= new List<Cached_item>))
3423	return TRUE;
3424
3425	for (uint i= `0`; i < left_expr->cols(); i++)
3426	{
3427	Cached_item *cur_item_cache= new_Cached_item(thd,
3428	left_expr->element_index(i),
3429	FALSE);
3430	if (!cur_item_cache \|\| left_expr_cache->push_front(cur_item_cache,
3431	thd->mem_root))
3432	return TRUE;
3433	}
3434	return FALSE;
3435	}
3436
3437
3438	bool Item_in_subselect::init_cond_guards()
3439	{
3440	DBUG_ASSERT(thd);
3441	uint cols_num= left_expr->cols();
3442	if (!abort_on_null && !pushed_cond_guards &&
3443	(left_expr->maybe_null \|\| cols_num > `1`))
3444	{
3445	if (!(pushed_cond_guards= (bool)thd->alloc(sizeof(bool) cols_num)))
3446	return TRUE;
3447	for (uint i= `0`; i < cols_num; i++)
3448	pushed_cond_guards[i]= TRUE;
3449	}
3450	return FALSE;
3451	}
3452
3453
3454	bool
3455	Item_allany_subselect::select_transformer(JOIN *join)
3456	{
3457	DBUG_ENTER("Item_allany_subselect::select_transformer");
3458	DBUG_ASSERT((in_strategy & ~(SUBS_MAXMIN_INJECTED \| SUBS_MAXMIN_ENGINE \|
3459	SUBS_IN_TO_EXISTS \| SUBS_STRATEGY_CHOSEN)) == `0`);
3460	if (upper_item)
3461	upper_item->show= `1`;
3462	DBUG_RETURN(select_in_like_transformer(join));
3463	}
3464
3465
3466	void Item_allany_subselect::print(String *str, enum_query_type query_type)
3467	{
3468	if (test_strategy(SUBS_IN_TO_EXISTS))
3469	str->append(STRING_WITH_LEN("<exists>"));
3470	else
3471	{
3472	left_expr->print(str, query_type);
3473	str->append(`' '`);
3474	str->append(func->symbol(all));
3475	str->append(all ? " all " : " any ", `5`);
3476	}
3477	Item_subselect::print(str, query_type);
3478	}
3479
3480
3481	void Item_allany_subselect::no_rows_in_result()
3482	{
3483	/*
3484	Subquery predicates outside of the SELECT list must be evaluated in order
3485	to possibly filter the special result row generated for implicit grouping
3486	if the subquery is in the HAVING clause.
3487	If the predicate is constant, we need its actual value in the only result
3488	row for queries with implicit grouping.
3489	*/
3490	if (parsing_place != SELECT_LIST \|\| const_item())
3491	return;
3492	value= `0`;
3493	null_value= `0`;
3494	was_null= `0`;
3495	make_const();
3496	}
3497
3498
3499	void subselect_engine::set_thd(THD *thd_arg)
3500	{
3501	thd= thd_arg;
3502	if (result)
3503	result->set_thd(thd_arg);
3504	}
3505
3506
3507	subselect_single_select_engine::
3508	subselect_single_select_engine(st_select_lex *select,
3509	select_result_interceptor *result_arg,
3510	Item_subselect *item_arg)
3511	:subselect_engine (item_arg, result_arg),
3512	prepared(`0`), executed(`0`),
3513	select_lex(select), join(`0`)
3514	{
3515	select_lex->master_unit()->item= item_arg;
3516	}
3517
3518	int subselect_single_select_engine::get_identifier()
3519	{
3520	return select_lex->select_number;
3521	}
3522
3523	void subselect_single_select_engine::force_reexecution()
3524	{
3525	executed= false;
3526	}
3527
3528	void subselect_single_select_engine::cleanup()
3529	{
3530	DBUG_ENTER("subselect_single_select_engine::cleanup");
3531	prepared= executed= `0`;
3532	join= `0`;
3533	result->cleanup();
3534	select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
3535	DBUG_VOID_RETURN;
3536	}
3537
3538
3539	void subselect_union_engine::cleanup()
3540	{
3541	DBUG_ENTER("subselect_union_engine::cleanup");
3542	unit->reinit_exec_mechanism();
3543	result->cleanup();
3544	unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
3545	for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
3546	sl->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
3547	DBUG_VOID_RETURN;
3548	}
3549
3550
3551	bool subselect_union_engine::is_executed() const
3552	{
3553	return unit->executed;
3554	}
3555
3556	void subselect_union_engine::force_reexecution()
3557	{
3558	unit->executed= false;
3559	}
3560
3561
3562	/*
3563	Check if last execution of the subquery engine produced any rows
3564
3565	SYNOPSIS
3566	subselect_union_engine::no_rows()
3567
3568	DESCRIPTION
3569	Check if last execution of the subquery engine produced any rows. The
3570	return value is undefined if last execution ended in an error.
3571
3572	RETURN
3573	TRUE - Last subselect execution has produced no rows
3574	FALSE - Otherwise
3575	*/
3576
3577	bool subselect_union_engine::no_rows()
3578	{
3579	/ Check if we got any rows when reading UNION result from temp. table: /
3580	if (unit->fake_select_lex)
3581	{
3582	JOIN *join= unit->fake_select_lex->join;
3583	if (join)
3584	return MY_TEST(!join->send_records);
3585	return false;
3586	}
3587	return MY_TEST(!(((select_union_direct *)(unit->get_union_result()))
3588	->send_records));
3589	}
3590
3591
3592	void subselect_uniquesubquery_engine::cleanup()
3593	{
3594	DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
3595	/*
3596	Note for mergers: we don't have to, and actually must not de-initialize
3597	tab->table->file here.
3598	- We don't have to, because free_tmp_table() will call ha_index_or_rnd_end
3599	- We must not do it, because tab->table may be a derived table which
3600	has been already dropped by close_thread_tables(), while we here are
3601	called from cleanup_items()
3602	*/
3603	DBUG_VOID_RETURN;
3604	}
3605
3606
3607	subselect_union_engine::subselect_union_engine(st_select_lex_unit *u,
3608	select_result_interceptor *result_arg,
3609	Item_subselect *item_arg)
3610	:subselect_engine (item_arg, result_arg)
3611	{
3612	unit= u;
3613	unit->item= item_arg;
3614	}
3615
3616
3617	/**
3618	Create and prepare the JOIN object that represents the query execution
3619	plan for the subquery.
3620
3621	@details
3622	This method is called from Item_subselect::fix_fields. For prepared
3623	statements it is called both during the PREPARE and EXECUTE phases in the
3624	following ways:
3625	- During PREPARE the optimizer needs some properties
3626	(join->fields_list.elements) of the JOIN to proceed with preparation of
3627	the remaining query (namely to complete ::fix_fields for the subselect
3628	related classes. In the end of PREPARE the JOIN is deleted.
3629	- When we EXECUTE the query, Item_subselect::fix_fields is called again, and
3630	the JOIN object is re-created again, prepared and executed. In the end of
3631	execution it is deleted.
3632	In all cases the JOIN is created in runtime memory (not in the permanent
3633	memory root).
3634
3635	@todo
3636	Re-check what properties of 'join' are needed during prepare, and see if
3637	we can avoid creating a JOIN during JOIN::prepare of the outer join.
3638
3639	@retval 0 if success
3640	@retval 1 if error
3641	*/
3642
3643	int subselect_single_select_engine::prepare(THD *thd)
3644	{
3645	if (prepared)
3646	return `0`;
3647	set_thd(thd);
3648	if (select_lex->join)
3649	{
3650	select_lex->cleanup();
3651	}
3652	join= new JOIN (thd, select_lex->item_list,
3653	select_lex->options \| SELECT_NO_UNLOCK, result);
3654	if (!join \|\| !result)
3655	return `1`; / Fatal error is set already. /
3656	prepared= `1`;
3657	SELECT_LEX *save_select= thd->lex->current_select;
3658	thd->lex->current_select= select_lex;
3659	if (join->prepare(select_lex->table_list.first,
3660	select_lex->with_wild,
3661	select_lex->where,
3662	select_lex->order_list.elements +
3663	select_lex->group_list.elements,
3664	select_lex->order_list.first,
3665	false,
3666	select_lex->group_list.first,
3667	select_lex->having,
3668	NULL, select_lex,
3669	select_lex->master_unit()))
3670	return `1`;
3671	thd->lex->current_select= save_select;
3672	return `0`;
3673	}
3674
3675	int subselect_union_engine::prepare(THD *thd_arg)
3676	{
3677	set_thd(thd_arg);
3678	return unit->prepare(unit->derived, result, SELECT_NO_UNLOCK);
3679	}
3680
3681	int subselect_uniquesubquery_engine::prepare(THD *)
3682	{
3683	/ Should never be called. /
3684	DBUG_ASSERT(FALSE);
3685	return `1`;
3686	}
3687
3688
3689	/*
3690	Check if last execution of the subquery engine produced any rows
3691
3692	SYNOPSIS
3693	subselect_single_select_engine::no_rows()
3694
3695	DESCRIPTION
3696	Check if last execution of the subquery engine produced any rows. The
3697	return value is undefined if last execution ended in an error.
3698
3699	RETURN
3700	TRUE - Last subselect execution has produced no rows
3701	FALSE - Otherwise
3702	*/
3703
3704	bool subselect_single_select_engine::no_rows()
3705	{
3706	return !item->assigned();
3707	}
3708
3709
3710	/*
3711	makes storage for the output values for the subquery and calcuates
3712	their data and column types and their nullability.
3713	*/
3714	void subselect_engine::set_row(List<Item> &item_list, Item_cache **row)
3715	{
3716	Item *sel_item;
3717	List_iterator_fast<Item> li(item_list);
3718	set_handler(&type_handler_varchar);
3719	for (uint i= `0`; (sel_item= li ++); i++)
3720	{
3721	item->max_length= sel_item->max_length;
3722	set_handler(sel_item->type_handler());
3723	item->decimals= sel_item->decimals;
3724	item->unsigned_flag= sel_item->unsigned_flag;
3725	maybe_null= sel_item->maybe_null;
3726	if (!(row[i]= sel_item->get_cache(thd)))
3727	return;
3728	row[i]->setup(thd, sel_item);
3729	//psergey-backport-timours: row[i]->store(sel_item);
3730	}
3731	if (item_list.elements > `1`)
3732	set_handler(&type_handler_row);
3733	}
3734
3735	void subselect_single_select_engine::fix_length_and_dec(Item_cache **row)
3736	{
3737	DBUG_ASSERT(row \|\| select_lex->item_list.elements==`1`);
3738	set_row(select_lex->item_list, row);
3739	item->collation.set(row[`0`]->collation);
3740	if (cols() != `1`)
3741	maybe_null= `0`;
3742	}
3743
3744	void subselect_union_engine::fix_length_and_dec(Item_cache **row)
3745	{
3746	DBUG_ASSERT(row \|\| unit->first_select()->item_list.elements==`1`);
3747
3748	if (unit->first_select()->item_list.elements == `1`)
3749	{
3750	set_row(unit->types, row);
3751	item->collation.set(row[`0`]->collation);
3752	}
3753	else
3754	{
3755	bool maybe_null_saved= maybe_null;
3756	set_row(unit->types, row);
3757	maybe_null= maybe_null_saved;
3758	}
3759	}
3760
3761	void subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
3762	{
3763	//this never should be called
3764	DBUG_ASSERT(`0`);
3765	}
3766
3767	int read_first_record_seq(JOIN_TAB *tab);
3768	int rr_sequential(READ_RECORD *info);
3769	int join_read_always_key_or_null(JOIN_TAB *tab);
3770	int join_read_next_same_or_null(READ_RECORD *info);
3771
3772	int subselect_single_select_engine::exec()
3773	{
3774	DBUG_ENTER("subselect_single_select_engine::exec");
3775
3776	char const *save_where= thd->where;
3777	SELECT_LEX *save_select= thd->lex->current_select;
3778	thd->lex->current_select= select_lex;
3779
3780	if (join->optimization_state == JOIN::NOT_OPTIMIZED)
3781	{
3782	SELECT_LEX_UNIT *unit= select_lex->master_unit();
3783
3784	unit->set_limit(unit->global_parameters());
3785	if (join->optimize())
3786	{
3787	thd->where= save_where;
3788	executed= `1`;
3789	thd->lex->current_select= save_select;
3790	DBUG_RETURN(join->error ? join->error : `1`);
3791	}
3792	if (!select_lex->uncacheable && thd->lex->describe &&
3793	!(join->select_options & SELECT_DESCRIBE))
3794	{
3795	item->update_used_tables();
3796	if (item->const_item())
3797	{
3798	/*
3799	It's necessary to keep original JOIN table because
3800	create_sort_index() function may overwrite original
3801	JOIN_TAB::type and wrong optimization method can be
3802	selected on re-execution.
3803	*/
3804	select_lex->uncacheable\|= UNCACHEABLE_EXPLAIN;
3805	select_lex->master_unit()->uncacheable\|= UNCACHEABLE_EXPLAIN;
3806	}
3807	}
3808	if (item->engine_changed(this))
3809	{
3810	thd->lex->current_select= save_select;
3811	DBUG_RETURN(`1`);
3812	}
3813	}
3814	if (select_lex->uncacheable &&
3815	select_lex->uncacheable != UNCACHEABLE_EXPLAIN
3816	&& executed)
3817	{
3818	if (join->reinit())
3819	{
3820	thd->where= save_where;
3821	thd->lex->current_select= save_select;
3822	DBUG_RETURN(`1`);
3823	}
3824	item->reset();
3825	item->assigned((executed= `0`));
3826	}
3827	if (!executed)
3828	{
3829	item->reset_value_registration();
3830	JOIN_TAB *changed_tabs[MAX_TABLES];
3831	JOIN_TAB **last_changed_tab= changed_tabs;
3832	if (item->have_guarded_conds())
3833	{
3834	/*
3835	For at least one of the pushed predicates the following is true:
3836	We should not apply optimizations based on the condition that was
3837	pushed down into the subquery. Those optimizations are ref[_or_null]
3838	acceses. Change them to be full table scans.
3839	*/
3840	JOIN_TAB *tab;
3841	for (tab= first_linear_tab(join, WITH_BUSH_ROOTS, WITHOUT_CONST_TABLES);
3842	tab; tab= next_linear_tab(join, tab, WITH_BUSH_ROOTS))
3843	{
3844	if (tab && tab->keyuse)
3845	{
3846	for (uint i= `0`; i < tab->ref.key_parts; i++)
3847	{
3848	bool *cond_guard= tab->ref.cond_guards[i];
3849	if (cond_guard && !*cond_guard)
3850	{
3851	/ Change the access method to full table scan /
3852	tab->save_read_first_record= tab->read_first_record;
3853	tab->save_read_record= tab->read_record.read_record_func;
3854	tab->read_record.read_record_func= rr_sequential;
3855	tab->read_first_record= read_first_record_seq;
3856	tab->read_record.record= tab->table->record[`0`];
3857	tab->read_record.thd= join->thd;
3858	tab->read_record.ref_length= tab->table->file->ref_length;
3859	tab->read_record.unlock_row= rr_unlock_row;
3860	*(last_changed_tab++)= tab;
3861	break;
3862	}
3863	}
3864	}
3865	}
3866	}
3867
3868	join->exec();
3869
3870	/ Enable the optimizations back /
3871	for (JOIN_TAB **ptab= changed_tabs; ptab != last_changed_tab; ptab++)
3872	{
3873	JOIN_TAB tab= ptab;
3874	tab->read_record.record= `0`;
3875	tab->read_record.ref_length= `0`;
3876	tab->read_first_record= tab->save_read_first_record;
3877	tab->read_record.read_record_func= tab->save_read_record;
3878	}
3879	executed= `1`;
3880	if (!(uncacheable() & ~UNCACHEABLE_EXPLAIN) &&
3881	!item->with_recursive_reference)
3882	item->make_const();
3883	thd->where= save_where;
3884	thd->lex->current_select= save_select;
3885	DBUG_RETURN(join->error \|\| thd->is_fatal_error \|\| thd->is_error());
3886	}
3887	thd->where= save_where;
3888	thd->lex->current_select= save_select;
3889	DBUG_RETURN(`0`);
3890	}
3891
3892	int subselect_union_engine::exec()
3893	{
3894	char const *save_where= thd->where;
3895	int res= unit->exec();
3896	thd->where= save_where;
3897	return res;
3898	}
3899
3900
3901	/*
3902	Search for at least one row satisfying select condition
3903
3904	SYNOPSIS
3905	subselect_uniquesubquery_engine::scan_table()
3906
3907	DESCRIPTION
3908	Scan the table using sequential access until we find at least one row
3909	satisfying select condition.
3910
3911	The caller must set this->empty_result_set=FALSE before calling this
3912	function. This function will set it to TRUE if it finds a matching row.
3913
3914	RETURN
3915	FALSE - OK
3916	TRUE - Error
3917	*/
3918
3919	int subselect_uniquesubquery_engine::scan_table()
3920	{
3921	int error;
3922	TABLE *table= tab->table;
3923	DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");
3924
3925	if ((table->file->inited &&
3926	(error= table->file->ha_index_end())) \|\|
3927	(error= table->file->ha_rnd_init(`1`)))
3928	{
3929	(void) report_error(table, error);
3930	DBUG_RETURN(true);
3931	}
3932
3933	table->file->extra_opt(HA_EXTRA_CACHE,
3934	get_thd()->variables.read_buff_size);
3935	table->null_row= `0`;
3936	for (;;)
3937	{
3938	error=table->file->ha_rnd_next(table->record[`0`]);
3939	if (unlikely(error))
3940	{
3941	if (error == HA_ERR_END_OF_FILE)
3942	{
3943	error= `0`;
3944	break;
3945	}
3946	else
3947	{
3948	error= report_error(table, error);
3949	break;
3950	}
3951	}
3952
3953	if (!cond \|\| cond->val_int())
3954	{
3955	empty_result_set= FALSE;
3956	break;
3957	}
3958	}
3959
3960	table->file->ha_rnd_end();
3961	DBUG_RETURN(error != `0`);
3962	}
3963
3964
3965	/**
3966	Copy ref key for index access into the only subquery table.
3967
3968	@details
3969	Copy ref key and check for conversion problems.
3970	If there is an error converting the left IN operand to the column type of
3971	the right IN operand count it as no match. In this case IN has the value of
3972	FALSE. We mark the subquery table cursor as having no more rows (to ensure
3973	that the processing that follows will not find a match) and return FALSE,
3974	so IN is not treated as returning NULL.
3975
3976	@returns
3977	@retval FALSE The outer ref was copied into an index lookup key.
3978	@retval TRUE The outer ref cannot possibly match any row, IN is FALSE.
3979	*/
3980
3981	bool subselect_uniquesubquery_engine::copy_ref_key(bool skip_constants)
3982	{
3983	DBUG_ENTER("subselect_uniquesubquery_engine::copy_ref_key");
3984
3985	for (store_key *copy= tab->ref.key_copy ; copy ; copy++)
3986	{
3987	enum store_key::store_key_result store_res;
3988	if (skip_constants && (*copy)->store_key_is_const())
3989	continue;
3990	store_res= (*copy)->copy();
3991	tab->ref.key_err= store_res;
3992
3993	if (store_res == store_key::STORE_KEY_FATAL)
3994	{
3995	/*
3996	Error converting the left IN operand to the column type of the right
3997	IN operand.
3998	*/
3999	DBUG_RETURN(true);
4000	}
4001	}
4002	DBUG_RETURN(false);
4003	}
4004
4005
4006	/**
4007	Execute subselect via unique index lookup
4008
4009	@details
4010	Find rows corresponding to the ref key using index access.
4011	If some part of the lookup key is NULL, then we're evaluating
4012	NULL IN (SELECT ... )
4013	This is a special case, we don't need to search for NULL in the table,
4014	instead, the result value is
4015	- NULL if select produces empty row set
4016	- FALSE otherwise.
4017
4018	In some cases (IN subselect is a top level item, i.e. abort_on_null==TRUE)
4019	the caller doesn't distinguish between NULL and FALSE result and we just
4020	return FALSE.
4021	Otherwise we make a full table scan to see if there is at least one
4022	matching row.
4023
4024	The result of this function (info about whether a row was found) is
4025	stored in this->empty_result_set.
4026
4027	@returns
4028	@retval 0 OK
4029	@retval 1 notify caller to call Item_subselect::reset(),
4030	in most cases reset() sets the result to NULL
4031	*/
4032
4033	int subselect_uniquesubquery_engine::exec()
4034	{
4035	DBUG_ENTER("subselect_uniquesubquery_engine::exec");
4036	int error;
4037	TABLE *table= tab->table;
4038	empty_result_set= TRUE;
4039	table->status= `0`;
4040	Item_in_subselect in_subs= (Item_in_subselect ) item;
4041
4042	if (!tab->preread_init_done && tab->preread_init())
4043	DBUG_RETURN(`1`);
4044
4045	if (in_subs->left_expr_has_null())
4046	{
4047	/*
4048	The case when all values in left_expr are NULL is handled by
4049	Item_in_optimizer::val_int().
4050	*/
4051	if (in_subs->is_top_level_item())
4052	DBUG_RETURN(`1`); / notify caller to call reset() and set NULL value. /
4053	else
4054	DBUG_RETURN(scan_table());
4055	}
4056
4057	if (copy_ref_key(true))
4058	{
4059	/ We know that there will be no rows even if we scan. /
4060	in_subs->value= `0`;
4061	DBUG_RETURN(`0`);
4062	}
4063
4064	if (!table->file->inited &&
4065	(error= table->file->ha_index_init(tab->ref.key, `0`)))
4066	{
4067	(void) report_error(table, error);
4068	DBUG_RETURN(true);
4069	}
4070
4071	error= table->file->ha_index_read_map(table->record[`0`],
4072	tab->ref.key_buff,
4073	make_prev_keypart_map(tab->
4074	ref.key_parts),
4075	HA_READ_KEY_EXACT);
4076	if (unlikely(error &&
4077	error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE))
4078	error= report_error(table, error);
4079	else
4080	{
4081	error= `0`;
4082	table->null_row= `0`;
4083	if (!table->status && (!cond \|\| cond->val_int()))
4084	{
4085	((Item_in_subselect *) item)->value= `1`;
4086	empty_result_set= FALSE;
4087	}
4088	else
4089	((Item_in_subselect *) item)->value= `0`;
4090	}
4091
4092	DBUG_RETURN(error != `0`);
4093	}
4094
4095
4096	/*
4097	TIMOUR: write comment
4098	*/
4099
4100	int subselect_uniquesubquery_engine::index_lookup()
4101	{
4102	DBUG_ENTER("subselect_uniquesubquery_engine::index_lookup");
4103	int error;
4104	TABLE *table= tab->table;
4105
4106	if (!table->file->inited)
4107	table->file->ha_index_init(tab->ref.key, `0`);
4108	error= table->file->ha_index_read_map(table->record[`0`],
4109	tab->ref.key_buff,
4110	make_prev_keypart_map(tab->
4111	ref.key_parts),
4112	HA_READ_KEY_EXACT);
4113	DBUG_PRINT("info", ("lookup result: %i", error));
4114
4115	if (unlikely(error && error != HA_ERR_KEY_NOT_FOUND &&
4116	error != HA_ERR_END_OF_FILE))
4117	{
4118	/*
4119	TIMOUR: I don't understand at all when do we need to call report_error.
4120	In most places where we access an index, we don't do this. Why here?
4121	*/
4122	error= report_error(table, error);
4123	DBUG_RETURN(error);
4124	}
4125
4126	table->null_row= `0`;
4127	if (!error && (!cond \|\| cond->val_int()))
4128	((Item_in_subselect *) item)->value= `1`;
4129	else
4130	((Item_in_subselect *) item)->value= `0`;
4131
4132	DBUG_RETURN(`0`);
4133	}
4134
4135
4136
4137	subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
4138	{
4139	/ Tell handler we don't need the index anymore /
4140	//psergey-merge-todo: the following was gone in 6.0:
4141	//psergey-merge: don't need this after all: tab->table->file->ha_index_end();
4142	}
4143
4144
4145	/**
4146	Execute subselect via unique index lookup
4147
4148	@details
4149	The engine is used to resolve subqueries in form
4150
4151	oe IN (SELECT key FROM tbl WHERE subq_where)
4152
4153	The value of the predicate is calculated as follows:
4154	1. If oe IS NULL, this is a special case, do a full table scan on
4155	table tbl and search for row that satisfies subq_where. If such
4156	row is found, return NULL, otherwise return FALSE.
4157	2. Make an index lookup via key=oe, search for a row that satisfies
4158	subq_where. If found, return TRUE.
4159	3. If check_null==TRUE, make another lookup via key=NULL, search for a
4160	row that satisfies subq_where. If found, return NULL, otherwise
4161	return FALSE.
4162
4163	@todo
4164	The step #1 can be optimized further when the index has several key
4165	parts. Consider a subquery:
4166
4167	(oe1, oe2) IN (SELECT keypart1, keypart2 FROM tbl WHERE subq_where)
4168
4169	and suppose we need to evaluate it for {oe1, oe2}=={const1, NULL}.
4170	Current code will do a full table scan and obtain correct result. There
4171	is a better option: instead of evaluating
4172
4173	SELECT keypart1, keypart2 FROM tbl WHERE subq_where (1)
4174
4175	and checking if it has produced any matching rows, evaluate
4176
4177	SELECT keypart2 FROM tbl WHERE subq_where AND keypart1=const1 (2)
4178
4179	If this query produces a row, the result is NULL (as we're evaluating
4180	"(const1, NULL) IN { (const1, X), ... }", which has a value of UNKNOWN,
4181	i.e. NULL). If the query produces no rows, the result is FALSE.
4182
4183	We currently evaluate (1) by doing a full table scan. (2) can be
4184	evaluated by doing a "ref" scan on "keypart1=const1", which can be much
4185	cheaper. We can use index statistics to quickly check whether "ref" scan
4186	will be cheaper than full table scan.
4187
4188	@returns
4189	@retval 0 OK
4190	@retval 1 notify caller to call Item_subselect::reset(),
4191	in most cases reset() sets the result to NULL
4192	*/
4193
4194	int subselect_indexsubquery_engine::exec()
4195	{
4196	DBUG_ENTER("subselect_indexsubquery_engine");
4197	int error;
4198	bool null_finding= `0`;
4199	TABLE *table= tab->table;
4200	Item_in_subselect in_subs= (Item_in_subselect ) item;
4201
4202	((Item_in_subselect *) item)->value= `0`;
4203	empty_result_set= TRUE;
4204	table->status= `0`;
4205
4206	if (check_null)
4207	{
4208	/ We need to check for NULL if there wasn't a matching value /
4209	tab->ref.null_ref_key= `0`; // Search first for not null*
4210	((Item_in_subselect *) item)->was_null= `0`;
4211	}
4212
4213	if (!tab->preread_init_done && tab->preread_init())
4214	DBUG_RETURN(`1`);
4215
4216	if (in_subs->left_expr_has_null())
4217	{
4218	/*
4219	The case when all values in left_expr are NULL is handled by
4220	Item_in_optimizer::val_int().
4221	*/
4222	if (in_subs->is_top_level_item())
4223	DBUG_RETURN(`1`); / notify caller to call reset() and set NULL value. /
4224	else
4225	DBUG_RETURN(scan_table());
4226	}
4227
4228	if (copy_ref_key(true))
4229	{
4230	/ We know that there will be no rows even if we scan. /
4231	in_subs->value= `0`;
4232	DBUG_RETURN(`0`);
4233	}
4234
4235	if (!table->file->inited &&
4236	(error= table->file->ha_index_init(tab->ref.key, `1`)))
4237	{
4238	(void) report_error(table, error);
4239	DBUG_RETURN(true);
4240	}
4241
4242	error= table->file->ha_index_read_map(table->record[`0`],
4243	tab->ref.key_buff,
4244	make_prev_keypart_map(tab->
4245	ref.key_parts),
4246	HA_READ_KEY_EXACT);
4247	if (unlikely(error &&
4248	error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE))
4249	error= report_error(table, error);
4250	else
4251	{
4252	for (;;)
4253	{
4254	error= `0`;
4255	table->null_row= `0`;
4256	if (!table->status)
4257	{
4258	if ((!cond \|\| cond->val_int()) && (!having \|\| having->val_int()))
4259	{
4260	empty_result_set= FALSE;
4261	if (null_finding)
4262	((Item_in_subselect *) item)->was_null= `1`;
4263	else
4264	((Item_in_subselect *) item)->value= `1`;
4265	break;
4266	}
4267	error= table->file->ha_index_next_same(table->record[`0`],
4268	tab->ref.key_buff,
4269	tab->ref.key_length);
4270	if (unlikely(error && error != HA_ERR_END_OF_FILE))
4271	{
4272	error= report_error(table, error);
4273	break;
4274	}
4275	}
4276	else
4277	{
4278	if (!check_null \|\| null_finding)
4279	break; / We don't need to check nulls /
4280	*tab->ref.null_ref_key= `1`;
4281	null_finding= `1`;
4282	/ Check if there exists a row with a null value in the index /
4283	if (unlikely((error= (safe_index_read(tab) == `1`))))
4284	break;
4285	}
4286	}
4287	}
4288	DBUG_RETURN(error != `0`);
4289	}
4290
4291
4292	uint subselect_single_select_engine::cols() const
4293	{
4294	//psergey-sj-backport: the following assert was gone in 6.0:
4295	//DBUG_ASSERT(select_lex->join != 0); // should be called after fix_fields()
4296	//return select_lex->join->fields_list.elements;
4297	return select_lex->item_list.elements;
4298	}
4299
4300
4301	uint subselect_union_engine::cols() const
4302	{
4303	DBUG_ASSERT(unit->is_prepared()); // should be called after fix_fields()
4304	return unit->types.elements;
4305	}
4306
4307
4308	uint8 subselect_single_select_engine::uncacheable()
4309	{
4310	return select_lex->uncacheable;
4311	}
4312
4313
4314	uint8 subselect_union_engine::uncacheable()
4315	{
4316	return unit->uncacheable;
4317	}
4318
4319
4320	void subselect_single_select_engine::exclude()
4321	{
4322	select_lex->master_unit()->exclude_level();
4323	}
4324
4325	void subselect_union_engine::exclude()
4326	{
4327	unit->exclude_level();
4328	}
4329
4330
4331	void subselect_uniquesubquery_engine::exclude()
4332	{
4333	//this never should be called
4334	DBUG_ASSERT(`0`);
4335	}
4336
4337
4338	table_map subselect_engine::calc_const_tables(List<TABLE_LIST> &list)
4339	{
4340	table_map map= `0`;
4341	List_iterator<TABLE_LIST> ti(list);
4342	TABLE_LIST *table;
4343	//for (; table; table= table->next_leaf)
4344	while ((table= ti ++))
4345	{
4346	TABLE *tbl= table->table;
4347	if (tbl && tbl->const_table)
4348	map\|= tbl->map;
4349	}
4350	return map;
4351	}
4352
4353
4354	table_map subselect_single_select_engine::upper_select_const_tables()
4355	{
4356	return calc_const_tables(select_lex->outer_select()->leaf_tables);
4357	}
4358
4359
4360	table_map subselect_union_engine::upper_select_const_tables()
4361	{
4362	return calc_const_tables(unit->outer_select()->leaf_tables);
4363	}
4364
4365
4366	void subselect_single_select_engine::print(String *str,
4367	enum_query_type query_type)
4368	{
4369	With_clause* with_clause= select_lex->get_with_clause();
4370	if (with_clause)
4371	with_clause->print(str, query_type);
4372	select_lex->print(get_thd(), str, query_type);
4373	}
4374
4375
4376	void subselect_union_engine::print(String *str, enum_query_type query_type)
4377	{
4378	unit->print(str, query_type);
4379	}
4380
4381
4382	void subselect_uniquesubquery_engine::print(String *str,
4383	enum_query_type query_type)
4384	{
4385	str->append(STRING_WITH_LEN("<primary_index_lookup>("));
4386	tab->ref.items[`0`]->print(str, query_type);
4387	str->append(STRING_WITH_LEN(" in "));
4388	if (tab->table->s->table_category == TABLE_CATEGORY_TEMPORARY)
4389	{
4390	/*
4391	Temporary tables' names change across runs, so they can't be used for
4392	EXPLAIN EXTENDED.
4393	*/
4394	str->append(STRING_WITH_LEN("<temporary table>"));
4395	}
4396	else
4397	str->append(&tab->table->s->table_name);
4398	KEY *key_info= tab->table->key_info+ tab->ref.key;
4399	str->append(STRING_WITH_LEN(" on "));
4400	str->append(&key_info->name);
4401	if (cond)
4402	{
4403	str->append(STRING_WITH_LEN(" where "));
4404	cond->print(str, query_type);
4405	}
4406	str->append(`')'`);
4407	}
4408
4409	/*
4410	TODO:
4411	The above ::print method should be changed as below. Do it after
4412	all other tests pass.
4413
4414	void subselect_uniquesubquery_engine::print(String str)*
4415	{
4416	KEY key_info= tab->table->key_info + tab->ref.key;*
4417	str->append(STRING_WITH_LEN("<primary_index_lookup>("));
4418	for (uint i= 0; i < key_info->user_defined_key_parts; i++)
4419	tab->ref.items[i]->print(str);
4420	str->append(STRING_WITH_LEN(" in "));
4421	str->append(&tab->table->s->table_name);
4422	str->append(STRING_WITH_LEN(" on "));
4423	str->append(&key_info->name);
4424	if (cond)
4425	{
4426	str->append(STRING_WITH_LEN(" where "));
4427	cond->print(str);
4428	}
4429	str->append(')');
4430	}
4431	*/
4432
4433	void subselect_indexsubquery_engine::print(String *str,
4434	enum_query_type query_type)
4435	{
4436	str->append(STRING_WITH_LEN("<index_lookup>("));
4437	tab->ref.items[`0`]->print(str, query_type);
4438	str->append(STRING_WITH_LEN(" in "));
4439	str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
4440	KEY *key_info= tab->table->key_info+ tab->ref.key;
4441	str->append(STRING_WITH_LEN(" on "));
4442	str->append(&key_info->name);
4443	if (check_null)
4444	str->append(STRING_WITH_LEN(" checking NULL"));
4445	if (cond)
4446	{
4447	str->append(STRING_WITH_LEN(" where "));
4448	cond->print(str, query_type);
4449	}
4450	if (having)
4451	{
4452	str->append(STRING_WITH_LEN(" having "));
4453	having->print(str, query_type);
4454	}
4455	str->append(`')'`);
4456	}
4457
4458	/**
4459	change select_result object of engine.
4460
4461	@param si new subselect Item
4462	@param res new select_result object
4463	@param temp temporary assignment
4464
4465	@retval
4466	FALSE OK
4467	@retval
4468	TRUE error
4469	*/
4470
4471	bool
4472	subselect_single_select_engine::change_result(Item_subselect *si,
4473	select_result_interceptor *res,
4474	bool temp)
4475	{
4476	DBUG_ENTER("subselect_single_select_engine::change_result");
4477	item= si;
4478	if (temp)
4479	{
4480	/*
4481	Here we reuse change_item_tree to roll back assignment. It has
4482	nothing special about Item pointer so it is safe conversion. We do*
4483	not change the interface to be compatible with MySQL.
4484	*/
4485	thd->change_item_tree((Item*) &result, (Item)res);
4486	}
4487	else
4488	result= res;
4489
4490	/*
4491	We can't use 'result' below as gcc 4.2.4's alias optimization
4492	assumes that result was not changed by thd->change_item_tree().
4493	I tried to find a solution to make gcc happy, but could not find anything
4494	that would not require a lot of extra code that would be harder to manage
4495	than the current code.
4496	*/
4497	DBUG_RETURN(select_lex->join->change_result(res, NULL));
4498	}
4499
4500
4501	/**
4502	change select_result object of engine.
4503
4504	@param si new subselect Item
4505	@param res new select_result object
4506
4507	@retval
4508	FALSE OK
4509	@retval
4510	TRUE error
4511	*/
4512
4513	bool subselect_union_engine::change_result(Item_subselect *si,
4514	select_result_interceptor *res,
4515	bool temp)
4516	{
4517	item= si;
4518	int rc= unit->change_result(res, result);
4519	if (temp)
4520	thd->change_item_tree((Item*) &result, (Item)res);
4521	else
4522	result= res;
4523	return rc;
4524	}
4525
4526
4527	/**
4528	change select_result emulation, never should be called.
4529
4530	@param si new subselect Item
4531	@param res new select_result object
4532
4533	@retval
4534	FALSE OK
4535	@retval
4536	TRUE error
4537	*/
4538
4539	bool
4540	subselect_uniquesubquery_engine::change_result(Item_subselect *si,
4541	select_result_interceptor *res,
4542	bool temp
4543	__attribute__((unused)))
4544	{
4545	DBUG_ASSERT(`0`);
4546	return TRUE;
4547	}
4548
4549
4550	/**
4551	Report about presence of tables in subquery.
4552
4553	@retval
4554	TRUE there are not tables used in subquery
4555	@retval
4556	FALSE there are some tables in subquery
4557	*/
4558	bool subselect_single_select_engine::no_tables()
4559	{
4560	return(select_lex->table_list.elements == `0`);
4561	}
4562
4563
4564	/*
4565	Check statically whether the subquery can return NULL
4566
4567	SINOPSYS
4568	subselect_single_select_engine::may_be_null()
4569
4570	RETURN
4571	FALSE can guarantee that the subquery never return NULL
4572	TRUE otherwise
4573	*/
4574	bool subselect_single_select_engine::may_be_null()
4575	{
4576	return ((no_tables() && !join->conds && !join->having) ? maybe_null : `1`);
4577	}
4578
4579
4580	/**
4581	Report about presence of tables in subquery.
4582
4583	@retval
4584	TRUE there are not tables used in subquery
4585	@retval
4586	FALSE there are some tables in subquery
4587	*/
4588	bool subselect_union_engine::no_tables()
4589	{
4590	for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
4591	{
4592	if (sl->table_list.elements)
4593	return FALSE;
4594	}
4595	return TRUE;
4596	}
4597
4598
4599	/**
4600	Report about presence of tables in subquery.
4601
4602	@retval
4603	TRUE there are not tables used in subquery
4604	@retval
4605	FALSE there are some tables in subquery
4606	*/
4607
4608	bool subselect_uniquesubquery_engine::no_tables()
4609	{
4610	/ returning value is correct, but this method should never be called /
4611	DBUG_ASSERT(FALSE);
4612	return `0`;
4613	}
4614
4615
4616	/******************************************************************************
4617	WL#1110 - Implementation of class subselect_hash_sj_engine
4618	******************************************************************************/
4619
4620
4621	/**
4622	Check if an IN predicate should be executed via partial matching using
4623	only schema information.
4624
4625	@details
4626	This test essentially has three results:
4627	- partial matching is applicable, but cannot be executed due to a
4628	limitation in the total number of indexes, as a result we can't
4629	use subquery materialization at all.
4630	- partial matching is either applicable or not, and this can be
4631	determined by looking at 'this->max_keys'.
4632	If max_keys > 1, then we need partial matching because there are
4633	more indexes than just the one we use during materialization to
4634	remove duplicates.
4635
4636	@note
4637	TIMOUR: The schema-based analysis for partial matching can be done once for
4638	prepared statement and remembered. It is done here to remove the need to
4639	save/restore all related variables between each re-execution, thus making
4640	the code simpler.
4641
4642	@retval PARTIAL_MATCH if a partial match should be used
4643	@retval COMPLETE_MATCH if a complete match (index lookup) should be used
4644	*/
4645
4646	subselect_hash_sj_engine::exec_strategy
4647	subselect_hash_sj_engine::get_strategy_using_schema()
4648	{
4649	Item_in_subselect item_in= (Item_in_subselect ) item;
4650
4651	if (item_in->is_top_level_item())
4652	return COMPLETE_MATCH;
4653	else
4654	{
4655	List_iterator<Item> inner_col_it(item_in->unit->get_column_types(false*));
4656	Item outer_col, inner_col;
4657
4658	for (uint i= `0`; i < item_in->left_expr->cols(); i++)
4659	{
4660	outer_col= item_in->left_expr->element_index(i);
4661	inner_col= inner_col_it ++;
4662
4663	if (!inner_col->maybe_null && !outer_col->maybe_null)
4664	bitmap_set_bit(&non_null_key_parts, i);
4665	else
4666	{
4667	bitmap_set_bit(&partial_match_key_parts, i);
4668	++count_partial_match_columns;
4669	}
4670	}
4671	}
4672
4673	/ If no column contains NULLs use regular hash index lookups. /
4674	if (count_partial_match_columns)
4675	return PARTIAL_MATCH;
4676	return COMPLETE_MATCH;
4677	}
4678
4679
4680	/**
4681	Test whether an IN predicate must be computed via partial matching
4682	based on the NULL statistics for each column of a materialized subquery.
4683
4684	@details The procedure analyzes column NULL statistics, updates the
4685	matching type of columns that cannot be NULL or that contain only NULLs.
4686	Based on this, the procedure determines the final execution strategy for
4687	the [NOT] IN predicate.
4688
4689	@retval PARTIAL_MATCH if a partial match should be used
4690	@retval COMPLETE_MATCH if a complete match (index lookup) should be used
4691	*/
4692
4693	subselect_hash_sj_engine::exec_strategy
4694	subselect_hash_sj_engine::get_strategy_using_data()
4695	{
4696	Item_in_subselect item_in= (Item_in_subselect ) item;
4697	select_materialize_with_stats *result_sink=
4698	(select_materialize_with_stats *) result;
4699	Item *outer_col;
4700
4701	/*
4702	If we already determined that a complete match is enough based on schema
4703	information, nothing can be better.
4704	*/
4705	if (strategy == COMPLETE_MATCH)
4706	return COMPLETE_MATCH;
4707
4708	for (uint i= `0`; i < item_in->left_expr->cols(); i++)
4709	{
4710	if (!bitmap_is_set(&partial_match_key_parts, i))
4711	continue;
4712	outer_col= item_in->left_expr->element_index(i);
4713	/*
4714	If column 'i' doesn't contain NULLs, and the corresponding outer reference
4715	cannot have a NULL value, then 'i' is a non-nullable column.
4716	*/
4717	if (result_sink->get_null_count_of_col(i) == `0` && !outer_col->maybe_null)
4718	{
4719	bitmap_clear_bit(&partial_match_key_parts, i);
4720	bitmap_set_bit(&non_null_key_parts, i);
4721	--count_partial_match_columns;
4722	}
4723	if (result_sink->get_null_count_of_col(i) == tmp_table->file->stats.records)
4724	++count_null_only_columns;
4725	if (result_sink->get_null_count_of_col(i))
4726	++count_columns_with_nulls;
4727	}
4728
4729	/ If no column contains NULLs use regular hash index lookups. /
4730	if (!count_partial_match_columns)
4731	return COMPLETE_MATCH;
4732	return PARTIAL_MATCH;
4733	}
4734
4735
4736	void
4737	subselect_hash_sj_engine::choose_partial_match_strategy(
4738	bool has_non_null_key, bool has_covering_null_row,
4739	MY_BITMAP *partial_match_key_parts_arg)
4740	{
4741	ulonglong pm_buff_size;
4742
4743	DBUG_ASSERT(strategy == PARTIAL_MATCH);
4744	/*
4745	Choose according to global optimizer switch. If only one of the switches is
4746	'ON', then the remaining strategy is the only possible one. The only cases
4747	when this will be overridden is when the total size of all buffers for the
4748	merge strategy is bigger than the 'rowid_merge_buff_size' system variable,
4749	or if there isn't enough physical memory to allocate the buffers.
4750	*/
4751	if (!optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
4752	optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
4753	strategy= PARTIAL_MATCH_SCAN;
4754	else if
4755	( optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
4756	!optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
4757	strategy= PARTIAL_MATCH_MERGE;
4758
4759	/*
4760	If both switches are ON, or both are OFF, we interpret that as "let the
4761	optimizer decide". Perform a cost based choice between the two partial
4762	matching strategies.
4763	*/
4764	/*
4765	TIMOUR: the above interpretation of the switch values could be changed to:
4766	- if both are ON - let the optimizer decide,
4767	- if both are OFF - do not use partial matching, therefore do not use
4768	materialization in non-top-level predicates.
4769	The problem with this is that we know for sure if we need partial matching
4770	only after the subquery is materialized, and this is too late to revert to
4771	the IN=>EXISTS strategy.
4772	*/
4773	if (strategy == PARTIAL_MATCH)
4774	{
4775	/*
4776	TIMOUR: Currently we use a super simplistic measure. This will be
4777	addressed in a separate task.
4778	*/
4779	if (tmp_table->file->stats.records < `100`)
4780	strategy= PARTIAL_MATCH_SCAN;
4781	else
4782	strategy= PARTIAL_MATCH_MERGE;
4783	}
4784
4785	/ Check if there is enough memory for the rowid merge strategy. /
4786	if (strategy == PARTIAL_MATCH_MERGE)
4787	{
4788	pm_buff_size= rowid_merge_buff_size(has_non_null_key,
4789	has_covering_null_row,
4790	partial_match_key_parts_arg);
4791	if (pm_buff_size > thd->variables.rowid_merge_buff_size)
4792	strategy= PARTIAL_MATCH_SCAN;
4793	}
4794	}
4795
4796
4797	/*
4798	Compute the memory size of all buffers proportional to the number of rows
4799	in tmp_table.
4800
4801	@details
4802	If the result is bigger than thd->variables.rowid_merge_buff_size, partial
4803	matching via merging is not applicable.
4804	*/
4805
4806	ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
4807	bool has_non_null_key, bool has_covering_null_row,
4808	MY_BITMAP *partial_match_key_parts)
4809	{
4810	/ Total size of all buffers used by partial matching. /
4811	ulonglong buff_size;
4812	ha_rows row_count= tmp_table->file->stats.records;
4813	uint rowid_length= tmp_table->file->ref_length;
4814	select_materialize_with_stats *result_sink=
4815	(select_materialize_with_stats *) result;
4816	ha_rows max_null_row;
4817
4818	/ Size of the subselect_rowid_merge_engine::row_num_to_rowid buffer. /
4819	buff_size= row_count * rowid_length * sizeof(uchar);
4820
4821	if (has_non_null_key)
4822	{
4823	/ Add the size of Ordered_key::key_buff of the only non-NULL key. /
4824	buff_size+= row_count * sizeof(rownum_t);
4825	}
4826
4827	if (!has_covering_null_row)
4828	{
4829	for (uint i= `0`; i < partial_match_key_parts->n_bits; i++)
4830	{
4831	if (!bitmap_is_set(partial_match_key_parts, i) \|\|
4832	result_sink->get_null_count_of_col(i) == row_count)
4833	continue; / In these cases we wouldn't construct Ordered keys. /
4834
4835	/ Add the size of Ordered_key::key_buff /
4836	buff_size+= (row_count - result_sink->get_null_count_of_col(i)) *
4837	sizeof(rownum_t);
4838	/ Add the size of Ordered_key::null_key /
4839	max_null_row= result_sink->get_max_null_of_col(i);
4840	if (max_null_row >= UINT_MAX)
4841	{
4842	/*
4843	There can be at most UINT_MAX bits in a MY_BITMAP that is used to
4844	store NULLs in an Ordered_key. Return a number of bytes bigger than
4845	the maximum allowed memory buffer for partial matching to disable
4846	the rowid merge strategy.
4847	*/
4848	return ULONGLONG_MAX;
4849	}
4850	buff_size+= bitmap_buffer_size(max_null_row);
4851	}
4852	}
4853
4854	return buff_size;
4855	}
4856
4857
4858	/*
4859	Initialize a MY_BITMAP with a buffer allocated on the current
4860	memory root.
4861	TIMOUR: move to bitmap C file?
4862	*/
4863
4864	static my_bool
4865	my_bitmap_init_memroot(MY_BITMAP map, uint n_bits, MEM_ROOT mem_root)
4866	{
4867	my_bitmap_map *bitmap_buf;
4868
4869	if (!(bitmap_buf= (my_bitmap_map*) alloc_root(mem_root,
4870	bitmap_buffer_size(n_bits))) \|\|
4871	my_bitmap_init(map, bitmap_buf, n_bits, FALSE))
4872	return TRUE;
4873	bitmap_clear_all(map);
4874	return FALSE;
4875	}
4876
4877
4878	/**
4879	Create all structures needed for IN execution that can live between PS
4880	reexecution.
4881
4882	@param tmp_columns the items that produce the data for the temp table
4883	@param subquery_id subquery's identifier (to make "<subquery%d>" name for
4884	EXPLAIN)
4885
4886	@details
4887	- Create a temporary table to store the result of the IN subquery. The
4888	temporary table has one hash index on all its columns.
4889	- Create a new result sink that sends the result stream of the subquery to
4890	the temporary table,
4891
4892	@notice:
4893	Currently Item_subselect::init() already chooses and creates at parse
4894	time an engine with a corresponding JOIN to execute the subquery.
4895
4896	@retval TRUE if error
4897	@retval FALSE otherwise
4898	*/
4899
4900	bool subselect_hash_sj_engine::init(List<Item> *tmp_columns, uint subquery_id)
4901	{
4902	THD *thd= get_thd();
4903	select_unit *result_sink;
4904	/ Options to create_tmp_table. /
4905	ulonglong tmp_create_options= thd->variables.option_bits \| TMP_TABLE_ALL_COLUMNS;
4906	/ \| TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM /
4907
4908	DBUG_ENTER("subselect_hash_sj_engine::init");
4909
4910	if (my_bitmap_init_memroot(&non_null_key_parts, tmp_columns->elements,
4911	thd->mem_root) \|\|
4912	my_bitmap_init_memroot(&partial_match_key_parts, tmp_columns->elements,
4913	thd->mem_root))
4914	DBUG_RETURN(TRUE);
4915
4916	/*
4917	Create and initialize a select result interceptor that stores the
4918	result stream in a temporary table. The temporary table itself is
4919	managed (created/filled/etc) internally by the interceptor.
4920	*/
4921	/*
4922	TIMOUR:
4923	Select a more efficient result sink when we know there is no need to collect
4924	data statistics.
4925
4926	if (strategy == COMPLETE_MATCH)
4927	{
4928	if (!(result= new select_union))
4929	DBUG_RETURN(TRUE);
4930	}
4931	else if (strategy == PARTIAL_MATCH)
4932	{
4933	if (!(result= new select_materialize_with_stats))
4934	DBUG_RETURN(TRUE);
4935	}
4936	*/
4937	if (!(result_sink= new (thd->mem_root) select_materialize_with_stats (thd)))
4938	DBUG_RETURN(TRUE);
4939
4940	char buf[`32`];
4941	LEX_CSTRING name;
4942	name.length= my_snprintf(buf, sizeof(buf), "<subquery%u>", subquery_id);
4943	if (!(name.str= (char*) thd->memdup(buf, name.length + `1`)))
4944	DBUG_RETURN(TRUE);
4945
4946	result_sink->get_tmp_table_param()->materialized_subquery= true;
4947	if (item->substype() == Item_subselect::IN_SUBS &&
4948	((Item_in_subselect*)item)->is_jtbm_merged)
4949	{
4950	result_sink->get_tmp_table_param()->force_not_null_cols= true;
4951	}
4952	if (result_sink->create_result_table(thd, tmp_columns, TRUE,
4953	tmp_create_options,
4954	&name, TRUE, TRUE, FALSE, `0`))
4955	DBUG_RETURN(TRUE);
4956
4957	tmp_table= result_sink->table;
4958	result= result_sink;
4959
4960	/*
4961	If the subquery has blobs, or the total key length is bigger than
4962	some length, or the total number of key parts is more than the
4963	allowed maximum (currently MAX_REF_PARTS == 32), then the created
4964	index cannot be used for lookups and we can't use hash semi
4965	join. If this is the case, delete the temporary table since it
4966	will not be used, and tell the caller we failed to initialize the
4967	engine.
4968	*/
4969	if (tmp_table->s->keys == `0`)
4970	{
4971	//fprintf(stderr, "Q: %s\n", current_thd->query());
4972	DBUG_ASSERT(`0`);
4973	DBUG_ASSERT(
4974	tmp_table->s->uniques \|\|
4975	tmp_table->key_info->key_length >= tmp_table->file->max_key_length() \|\|
4976	tmp_table->key_info->user_defined_key_parts >
4977	tmp_table->file->max_key_parts());
4978	free_tmp_table(thd, tmp_table);
4979	tmp_table= NULL;
4980	delete result;
4981	result= NULL;
4982	DBUG_RETURN(TRUE);
4983	}
4984
4985	/*
4986	Make sure there is only one index on the temp table, and it doesn't have
4987	the extra key part created when s->uniques > 0.
4988	*/
4989	DBUG_ASSERT(tmp_table->s->keys == `1` &&
4990	((Item_in_subselect *) item)->left_expr->cols() ==
4991	tmp_table->key_info->user_defined_key_parts);
4992
4993	if (make_semi_join_conds() \|\|
4994	/ A unique_engine is used both for complete and partial matching. /
4995	!(lookup_engine= make_unique_engine()))
4996	DBUG_RETURN(TRUE);
4997
4998	/*
4999	Repeat name resolution for 'cond' since cond is not part of any
5000	clause of the query, and it is not 'fixed' during JOIN::prepare.
5001	*/
5002	if (semi_join_conds && !semi_join_conds->fixed &&
5003	semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
5004	DBUG_RETURN(TRUE);
5005	/ Let our engine reuse this query plan for materialization. /
5006	materialize_join= materialize_engine->join;
5007	materialize_join->change_result(result, NULL);
5008
5009	DBUG_RETURN(FALSE);
5010	}
5011
5012
5013	/*
5014	Create an artificial condition to post-filter those rows matched by index
5015	lookups that cannot be distinguished by the index lookup procedure.
5016
5017	@notes
5018	The need for post-filtering may occur e.g. because of
5019	truncation. Prepared statements execution requires that fix_fields is
5020	called for every execution. In order to call fix_fields we need to
5021	create a Name_resolution_context and a corresponding TABLE_LIST for
5022	the temporary table for the subquery, so that all column references
5023	to the materialized subquery table can be resolved correctly.
5024
5025	@returns
5026	@retval TRUE memory allocation error occurred
5027	@retval FALSE the conditions were created and resolved (fixed)
5028	*/
5029
5030	bool subselect_hash_sj_engine::make_semi_join_conds()
5031	{
5032	/*
5033	Table reference for tmp_table that is used to resolve column references
5034	(Item_fields) to columns in tmp_table.
5035	*/
5036	TABLE_LIST *tmp_table_ref;
5037	/ Name resolution context for all tmp_table columns created below. /
5038	Name_resolution_context *context;
5039	Item_in_subselect item_in= (Item_in_subselect ) item;
5040	LEX_CSTRING table_name;
5041	DBUG_ENTER("subselect_hash_sj_engine::make_semi_join_conds");
5042	DBUG_ASSERT(semi_join_conds == NULL);
5043
5044	if (!(semi_join_conds= new (thd->mem_root) Item_cond_and (thd)))
5045	DBUG_RETURN(TRUE);
5046
5047	if (!(tmp_table_ref= (TABLE_LIST) thd->alloc(sizeof*(TABLE_LIST))))
5048	DBUG_RETURN(TRUE);
5049
5050	table_name.str= tmp_table->alias.c_ptr();
5051	table_name.length= tmp_table->alias.length(),
5052	tmp_table_ref->init_one_table(&empty_clex_str, &table_name, NULL, TL_READ);
5053	tmp_table_ref->table= tmp_table;
5054
5055	context= new Name_resolution_context;
5056	context->init();
5057	context->first_name_resolution_table=
5058	context->last_name_resolution_table= tmp_table_ref;
5059	semi_join_conds_context= context;
5060
5061	for (uint i= `0`; i < item_in->left_expr->cols(); i++)
5062	{
5063	/ New equi-join condition for the current column. /
5064	Item_func_eq *eq_cond;
5065	/ Item for the corresponding field from the materialized temp table. /
5066	Item_field *right_col_item;
5067
5068	if (!(right_col_item= new (thd->mem_root)
5069	Item_temptable_field (thd, context, tmp_table->field[i])) \|\|
5070	!(eq_cond= new (thd->mem_root)
5071	Item_func_eq (thd, item_in->left_expr->element_index(i),
5072	right_col_item)) \|\|
5073	(((Item_cond_and*)semi_join_conds)->add(eq_cond, thd->mem_root)))
5074	{
5075	delete semi_join_conds;
5076	semi_join_conds= NULL;
5077	DBUG_RETURN(TRUE);
5078	}
5079	}
5080	if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
5081	DBUG_RETURN(TRUE);
5082
5083	DBUG_RETURN(FALSE);
5084	}
5085
5086
5087	/**
5088	Create a new uniquesubquery engine for the execution of an IN predicate.
5089
5090	@details
5091	Create and initialize a new JOIN_TAB, and Table_ref objects to perform
5092	lookups into the indexed temporary table.
5093
5094	@retval A new subselect_hash_sj_engine object
5095	@retval NULL if a memory allocation error occurs
5096	*/
5097
5098	subselect_uniquesubquery_engine*
5099	subselect_hash_sj_engine::make_unique_engine()
5100	{
5101	Item_in_subselect item_in= (Item_in_subselect ) item;
5102	Item_iterator_row it(item_in->left_expr);
5103	/ The only index on the temporary table. /
5104	KEY *tmp_key= tmp_table->key_info;
5105	JOIN_TAB *tab;
5106
5107	DBUG_ENTER("subselect_hash_sj_engine::make_unique_engine");
5108
5109	/*
5110	Create and initialize the JOIN_TAB that represents an index lookup
5111	plan operator into the materialized subquery result. Notice that:
5112	- this JOIN_TAB has no corresponding JOIN (and doesn't need one), and
5113	- here we initialize only those members that are used by
5114	subselect_uniquesubquery_engine, so these objects are incomplete.
5115	*/
5116	if (!(tab= (JOIN_TAB) thd->alloc(sizeof*(JOIN_TAB))))
5117	DBUG_RETURN(NULL);
5118
5119	tab->table= tmp_table;
5120	tab->preread_init_done= FALSE;
5121	tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
5122
5123	DBUG_RETURN(new subselect_uniquesubquery_engine (thd, tab, item,
5124	semi_join_conds));
5125	}
5126
5127
5128	subselect_hash_sj_engine::~subselect_hash_sj_engine()
5129	{
5130	delete lookup_engine;
5131	delete result;
5132	if (tmp_table)
5133	free_tmp_table(thd, tmp_table);
5134	}
5135
5136
5137	int subselect_hash_sj_engine::prepare(THD *thd_arg)
5138	{
5139	/*
5140	Create and optimize the JOIN that will be used to materialize
5141	the subquery if not yet created.
5142	*/
5143	set_thd(thd_arg);
5144	return materialize_engine->prepare(thd);
5145	}
5146
5147
5148	/**
5149	Cleanup performed after each PS execution.
5150
5151	@details
5152	Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
5153	*/
5154
5155	void subselect_hash_sj_engine::cleanup()
5156	{
5157	enum_engine_type lookup_engine_type= lookup_engine->engine_type();
5158	is_materialized= FALSE;
5159	bitmap_clear_all(&non_null_key_parts);
5160	bitmap_clear_all(&partial_match_key_parts);
5161	count_partial_match_columns= `0`;
5162	count_null_only_columns= `0`;
5163	strategy= UNDEFINED;
5164	materialize_engine->cleanup();
5165	/*
5166	Restore the original Item_in_subselect engine. This engine is created once
5167	at parse time and stored across executions, while all other materialization
5168	related engines are created and chosen for each execution.
5169	*/
5170	((Item_in_subselect *) item)->engine= materialize_engine;
5171	if (lookup_engine_type == TABLE_SCAN_ENGINE \|\|
5172	lookup_engine_type == ROWID_MERGE_ENGINE)
5173	{
5174	subselect_engine *inner_lookup_engine;
5175	inner_lookup_engine=
5176	((subselect_partial_match_engine*) lookup_engine)->lookup_engine;
5177	/*
5178	Partial match engines are recreated for each PS execution inside
5179	subselect_hash_sj_engine::exec().
5180	*/
5181	delete lookup_engine;
5182	lookup_engine= inner_lookup_engine;
5183	}
5184	DBUG_ASSERT(lookup_engine->engine_type() == UNIQUESUBQUERY_ENGINE);
5185	lookup_engine->cleanup();
5186	result->cleanup(); / Resets the temp table as well. /
5187	DBUG_ASSERT(tmp_table);
5188	free_tmp_table(thd, tmp_table);
5189	tmp_table= NULL;
5190	}
5191
5192
5193	/*
5194	Get fanout produced by tables specified in the table_map
5195	*/
5196
5197	double get_fanout_with_deps(JOIN *join, table_map tset)
5198	{
5199	/ Handle the case of "Impossible WHERE" /
5200	if (join->table_count == `0`)
5201	return `0.0`;
5202
5203	/ First, recursively get all tables we depend on /
5204	table_map deps_to_check= tset;
5205	table_map checked_deps= `0`;
5206	table_map further_deps;
5207	do
5208	{
5209	further_deps= `0`;
5210	Table_map_iterator tm_it(deps_to_check);
5211	int tableno;
5212	while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
5213	{
5214	/ get tableno's dependency tables that are not in needed_set /
5215	further_deps \|= join->map2table[tableno]->ref.depend_map & ~checked_deps;
5216	}
5217
5218	checked_deps \|= deps_to_check;
5219	deps_to_check= further_deps;
5220	} while (further_deps != `0`);
5221
5222
5223	/ Now, walk the join order and calculate the fanout /
5224	double fanout= `1`;
5225	for (JOIN_TAB *tab= first_top_level_tab(join, WITHOUT_CONST_TABLES); tab;
5226	tab= next_top_level_tab(join, tab))
5227	{
5228	/*
5229	Ignore SJM nests. They have tab->table==NULL. There is no point to walk
5230	inside them, because GROUP BY clause cannot refer to tables from within
5231	subquery.
5232	*/
5233	if (!tab->is_sjm_nest() && (tab->table->map & checked_deps) &&
5234	!tab->emb_sj_nest &&
5235	tab->records_read != `0`)
5236	{
5237	fanout *= tab->records_read;
5238	}
5239	}
5240	return fanout;
5241	}
5242
5243
5244	#if 0
5245	void check_out_index_stats(JOIN *join)
5246	{
5247	ORDER *order;
5248	uint n_order_items;
5249
5250	/*
5251	First, collect the keys that we can use in each table.
5252	We can use a key if
5253	- all tables refer to it.
5254	*/
5255	key_map key_start_use[MAX_TABLES];
5256	key_map key_infix_use[MAX_TABLES];
5257	table_map key_used=`0`;
5258	table_map non_key_used= `0`;
5259
5260	bzero(&key_start_use, sizeof(key_start_use)); //psergey-todo: safe initialization!
5261	bzero(&key_infix_use, sizeof(key_infix_use));
5262
5263	for (order= join->group_list; order; order= order->next)
5264	{
5265	Item *item= order->item[`0`];
5266
5267	if (item->real_type() == Item::FIELD_ITEM)
5268	{
5269	if (item->used_tables() & OUTER_REF_TABLE_BIT)
5270	continue; / outside references are like constants for us /
5271
5272	Field field= ((Item_field)item->real_item())->field;
5273	uint table_no= field->table->tablenr;
5274	if (!(non_key_used && table_map(`1`) << table_no) &&
5275	!field->part_of_key.is_clear_all())
5276	{
5277	key_map infix_map= field->part_of_key;
5278	infix_map.subtract(field->key_start);
5279	key_start_use[table_no].merge(field->key_start);
5280	key_infix_use[table_no].merge(infix_map);
5281	key_used \|= table_no;
5282	}
5283	continue;
5284	}
5285	/*
5286	Note: the below will cause clauses like GROUP BY YEAR(date) not to be
5287	handled.
5288	*/
5289	non_key_used \|= item->used_tables();
5290	}
5291
5292	Table_map_iterator tm_it(key_used & ~non_key_used);
5293	int tableno;
5294	while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
5295	{
5296	key_map::iterator key_it(key_start_use);
5297	int keyno;
5298	while ((keyno = tm_it.next_bit()) != key_map::iterator::BITMAP_END)
5299	{
5300	for (order= join->group_list; order; order= order->next)
5301	{
5302	Item *item= order->item[`0`];
5303	if (item->used_tables() & (table_map(`1`) << tableno))
5304	{
5305	DBUG_ASSERT(item->real_type() == Item::FIELD_ITEM);
5306	}
5307	}
5308	/*
5309	if (continuation)
5310	{
5311	walk through list and find which key parts are occupied;
5312	// note that the above can't be made any faster.
5313	}
5314	else
5315	use rec_per_key[0];
5316
5317	find out the cardinality.
5318	check if cardinality decreases if we use it;
5319	*/
5320	}
5321	}
5322	}
5323	#endif
5324
5325
5326	/*
5327	Get an estimate of how many records will be produced after the GROUP BY
5328	operation.
5329
5330	@param join Join we're operating on
5331	@param join_op_rows How many records will be produced by the join
5332	operations (this is what join optimizer produces)
5333
5334	@seealso
5335	See also optimize_semijoin_nests(), grep for "Adjust output cardinality
5336	estimates". Very similar code there that is not joined with this one
5337	because we operate on different data structs and too much effort is
5338	needed to abstract them out.
5339
5340	@return
5341	Number of records we expect to get after the GROUP BY operation
5342	*/
5343
5344	double get_post_group_estimate(JOIN* join, double join_op_rows)
5345	{
5346	table_map tables_in_group_list= table_map(`0`);
5347
5348	/ Find out which tables are used in GROUP BY list /
5349	for (ORDER *order= join->group_list_for_estimates; order; order= order->next)
5350	{
5351	Item *item= order->item[`0`];
5352	table_map item_used_tables= item->used_tables();
5353	if (item_used_tables & RAND_TABLE_BIT)
5354	{
5355	/ Each join output record will be in its own group /
5356	return join_op_rows;
5357	}
5358	tables_in_group_list\|= item_used_tables;
5359	}
5360	tables_in_group_list &= ~PSEUDO_TABLE_BITS;
5361
5362	/*
5363	Use join fanouts to calculate the max. number of records in the group-list
5364	*/
5365	double fanout_rows[MAX_KEY];
5366	bzero(&fanout_rows, sizeof(fanout_rows));
5367	double out_rows;
5368
5369	out_rows= get_fanout_with_deps(join, tables_in_group_list);
5370
5371	#if 0
5372	/ The following will be needed when making use of index stats: /
5373	/*
5374	Also generate max. number of records for each of the tables mentioned
5375	in the group-list. We'll use that a baseline number that we'll try to
5376	reduce by using
5377	- #table-records
5378	- index statistics.
5379	*/
5380	Table_map_iterator tm_it(tables_in_group_list);
5381	int tableno;
5382	while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
5383	{
5384	fanout_rows[tableno]= get_fanout_with_deps(join, table_map(`1`) << tableno);
5385	}
5386
5387	/*
5388	Try to bring down estimates using index statistics.
5389	*/
5390	//check_out_index_stats(join);
5391	#endif
5392
5393	return out_rows;
5394	}
5395
5396
5397	/**
5398	Execute a subquery IN predicate via materialization.
5399
5400	@details
5401	If needed materialize the subquery into a temporary table, then
5402	copmpute the predicate via a lookup into this table.
5403
5404	@retval TRUE if error
5405	@retval FALSE otherwise
5406	*/
5407
5408	int subselect_hash_sj_engine::exec()
5409	{
5410	Item_in_subselect item_in= (Item_in_subselect ) item;
5411	SELECT_LEX *save_select= thd->lex->current_select;
5412	subselect_partial_match_engine *pm_engine= NULL;
5413	int res= `0`;
5414
5415	DBUG_ENTER("subselect_hash_sj_engine::exec");
5416
5417	/*
5418	Optimize and materialize the subquery during the first execution of
5419	the subquery predicate.
5420	*/
5421	thd->lex->current_select= materialize_engine->select_lex;
5422	/ The subquery should be optimized, and materialized only once. /
5423	DBUG_ASSERT(materialize_join->optimization_state == JOIN::OPTIMIZATION_DONE &&
5424	!is_materialized);
5425	materialize_join->exec();
5426	if (unlikely((res= MY_TEST(materialize_join->error \|\| thd->is_fatal_error \|\|
5427	thd->is_error()))))
5428	goto err;
5429
5430	/*
5431	TODO:
5432	- Unlock all subquery tables as we don't need them. To implement this
5433	we need to add new functionality to JOIN::join_free that can unlock
5434	all tables in a subquery (and all its subqueries).
5435	- The temp table used for grouping in the subquery can be freed
5436	immediately after materialization (yet it's done together with
5437	unlocking).
5438	*/
5439	is_materialized= TRUE;
5440	/*
5441	If the subquery returned no rows, the temporary table is empty, so we know
5442	directly that the result of IN is FALSE. We first update the table
5443	statistics, then we test if the temporary table for the query result is
5444	empty.
5445	*/
5446	tmp_table->file->info(HA_STATUS_VARIABLE);
5447	if (!tmp_table->file->stats.records)
5448	{
5449	/ The value of IN will not change during this execution. /
5450	item_in->reset();
5451	item_in->make_const();
5452	item_in->set_first_execution();
5453	thd->lex->current_select= save_select;
5454	DBUG_RETURN(FALSE);
5455	}
5456
5457	/*
5458	TIMOUR: The schema-based analysis for partial matching can be done once for
5459	prepared statement and remembered. It is done here to remove the need to
5460	save/restore all related variables between each re-execution, thus making
5461	the code simpler.
5462	*/
5463	strategy= get_strategy_using_schema();
5464	/ This call may discover that we don't need partial matching at all. /
5465	strategy= get_strategy_using_data();
5466	if (strategy == PARTIAL_MATCH)
5467	{
5468	uint count_pm_keys; / Total number of keys needed for partial matching. /
5469	MY_BITMAP nn_key_parts= NULL; /* Key parts of the only non-NULL index. /
5470	uint count_non_null_columns= `0`; / Number of columns in nn_key_parts. /
5471	bool has_covering_null_row;
5472	bool has_covering_null_columns;
5473	select_materialize_with_stats *result_sink=
5474	(select_materialize_with_stats *) result;
5475	uint field_count= tmp_table->s->fields;
5476
5477	if (count_partial_match_columns < field_count)
5478	{
5479	nn_key_parts= &non_null_key_parts;
5480	count_non_null_columns= bitmap_bits_set(nn_key_parts);
5481	}
5482	has_covering_null_row= (result_sink->get_max_nulls_in_row() == field_count);
5483	has_covering_null_columns= (count_non_null_columns +
5484	count_null_only_columns == field_count);
5485
5486	if (has_covering_null_row && has_covering_null_columns)
5487	{
5488	/*
5489	The whole table consist of only NULL values. The result of IN is
5490	a constant UNKNOWN.
5491	*/
5492	DBUG_ASSERT(tmp_table->file->stats.records == `1`);
5493	item_in->value= `0`;
5494	item_in->null_value= `1`;
5495	item_in->make_const();
5496	item_in->set_first_execution();
5497	thd->lex->current_select= save_select;
5498	DBUG_RETURN(FALSE);
5499	}
5500
5501	if (has_covering_null_row)
5502	{
5503	DBUG_ASSERT(count_partial_match_columns == field_count);
5504	count_pm_keys= `0`;
5505	}
5506	else if (has_covering_null_columns)
5507	count_pm_keys= `1`;
5508	else
5509	count_pm_keys= count_partial_match_columns - count_null_only_columns +
5510	(nn_key_parts ? `1` : `0`);
5511
5512	choose_partial_match_strategy(MY_TEST(nn_key_parts),
5513	has_covering_null_row,
5514	&partial_match_key_parts);
5515	DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE \|\|
5516	strategy == PARTIAL_MATCH_SCAN);
5517	if (strategy == PARTIAL_MATCH_MERGE)
5518	{
5519	pm_engine=
5520	new subselect_rowid_merge_engine ((subselect_uniquesubquery_engine*)
5521	lookup_engine, tmp_table,
5522	count_pm_keys,
5523	has_covering_null_row,
5524	has_covering_null_columns,
5525	count_columns_with_nulls,
5526	item, result,
5527	semi_join_conds->argument_list());
5528	if (!pm_engine \|\|
5529	pm_engine->prepare(thd) \|\|
5530	((subselect_rowid_merge_engine*) pm_engine)->
5531	init(nn_key_parts, &partial_match_key_parts))
5532	{
5533	/*
5534	The call to init() would fail if there was not enough memory to allocate
5535	all buffers for the rowid merge strategy. In this case revert to table
5536	scanning which doesn't need any big buffers.
5537	*/
5538	delete pm_engine;
5539	pm_engine= NULL;
5540	strategy= PARTIAL_MATCH_SCAN;
5541	}
5542	}
5543
5544	if (strategy == PARTIAL_MATCH_SCAN)
5545	{
5546	if (!(pm_engine=
5547	new subselect_table_scan_engine ((subselect_uniquesubquery_engine*)
5548	lookup_engine, tmp_table,
5549	item, result,
5550	semi_join_conds->argument_list(),
5551	has_covering_null_row,
5552	has_covering_null_columns,
5553	count_columns_with_nulls)) \|\|
5554	pm_engine->prepare(thd))
5555	{
5556	/ This is an irrecoverable error. /
5557	res= `1`;
5558	goto err;
5559	}
5560	}
5561	}
5562
5563	if (pm_engine)
5564	lookup_engine= pm_engine;
5565	item_in->change_engine(lookup_engine);
5566
5567	err:
5568	thd->lex->current_select= save_select;
5569	DBUG_RETURN(res);
5570	}
5571
5572
5573	/**
5574	Print the state of this engine into a string for debugging and views.
5575	*/
5576
5577	void subselect_hash_sj_engine::print(String *str, enum_query_type query_type)
5578	{
5579	str->append(STRING_WITH_LEN(" <materialize> ("));
5580	materialize_engine->print(str, query_type);
5581	str->append(STRING_WITH_LEN(" ), "));
5582
5583	if (lookup_engine)
5584	lookup_engine->print(str, query_type);
5585	else
5586	str->append(STRING_WITH_LEN(
5587	"<engine selected at execution time>"
5588	));
5589	}
5590
5591	void subselect_hash_sj_engine::fix_length_and_dec(Item_cache** row)
5592	{
5593	DBUG_ASSERT(FALSE);
5594	}
5595
5596	void subselect_hash_sj_engine::exclude()
5597	{
5598	DBUG_ASSERT(FALSE);
5599	}
5600
5601	bool subselect_hash_sj_engine::no_tables()
5602	{
5603	DBUG_ASSERT(FALSE);
5604	return FALSE;
5605	}
5606
5607	bool subselect_hash_sj_engine::change_result(Item_subselect *si,
5608	select_result_interceptor *res,
5609	bool temp __attribute__((unused)))
5610	{
5611	DBUG_ASSERT(FALSE);
5612	return TRUE;
5613	}
5614
5615
5616	Ordered_key::Ordered_key(uint keyid_arg, TABLE tbl_arg, Item search_key_arg,
5617	ha_rows null_count_arg, ha_rows min_null_row_arg,
5618	ha_rows max_null_row_arg, uchar *row_num_to_rowid_arg)
5619	: keyid(keyid_arg), tbl(tbl_arg), search_key(search_key_arg),
5620	row_num_to_rowid(row_num_to_rowid_arg), null_count(null_count_arg)
5621	{
5622	DBUG_ASSERT(tbl->file->stats.records > null_count);
5623	key_buff_elements= tbl->file->stats.records - null_count;
5624	cur_key_idx= HA_POS_ERROR;
5625
5626	DBUG_ASSERT((null_count && min_null_row_arg && max_null_row_arg) \|\|
5627	(!null_count && !min_null_row_arg && !max_null_row_arg));
5628	if (null_count)
5629	{
5630	/ The counters are 1-based, for key access we need 0-based indexes. /
5631	min_null_row= min_null_row_arg - `1`;
5632	max_null_row= max_null_row_arg - `1`;
5633	}
5634	else
5635	min_null_row= max_null_row= `0`;
5636	}
5637
5638
5639	Ordered_key::~Ordered_key()
5640	{
5641	my_free(key_buff);
5642	my_bitmap_free(&null_key);
5643	}
5644
5645
5646	/*
5647	Cleanup that needs to be done for each PS (re)execution.
5648	*/
5649
5650	void Ordered_key::cleanup()
5651	{
5652	/*
5653	Currently these keys are recreated for each PS re-execution, thus
5654	there is nothing to cleanup, the whole object goes away after execution
5655	is over. All handler related initialization/deinitialization is done by
5656	the parent subselect_rowid_merge_engine object.
5657	*/
5658	}
5659
5660
5661	/*
5662	Initialize a multi-column index.
5663	*/
5664
5665	bool Ordered_key::init(MY_BITMAP *columns_to_index)
5666	{
5667	THD *thd= tbl->in_use;
5668	uint cur_key_col= `0`;
5669	Item_field *cur_tmp_field;
5670	Item_func_lt *fn_less_than;
5671
5672	key_column_count= bitmap_bits_set(columns_to_index);
5673	key_columns= (Item_field*) thd->alloc(key_column_count
5674	sizeof(Item_field*));
5675	compare_pred= (Item_func_lt*) thd->alloc(key_column_count
5676	sizeof(Item_func_lt*));
5677
5678	if (!key_columns \|\| !compare_pred)
5679	return TRUE; / Revert to table scan partial match. /
5680
5681	for (uint i= `0`; i < columns_to_index->n_bits; i++)
5682	{
5683	if (!bitmap_is_set(columns_to_index, i))
5684	continue;
5685	cur_tmp_field= new (thd->mem_root) Item_field (thd, tbl->field[i]);
5686	/ Create the predicate (tmp_column[i] < outer_ref[i]). /
5687	fn_less_than= new (thd->mem_root) Item_func_lt (thd, cur_tmp_field,
5688	search_key->element_index(i));
5689	fn_less_than->fix_fields(thd, (Item**) &fn_less_than);
5690	key_columns[cur_key_col]= cur_tmp_field;
5691	compare_pred[cur_key_col]= fn_less_than;
5692	++cur_key_col;
5693	}
5694
5695	if (alloc_keys_buffers())
5696	{
5697	/ TIMOUR revert to partial match via table scan. /
5698	return TRUE;
5699	}
5700	return FALSE;
5701	}
5702
5703
5704	/*
5705	Initialize a single-column index.
5706	*/
5707
5708	bool Ordered_key::init(int col_idx)
5709	{
5710	THD *thd= tbl->in_use;
5711
5712	key_column_count= `1`;
5713
5714	// TIMOUR: check for mem allocation err, revert to scan
5715
5716	key_columns= (Item_field) thd->alloc(sizeof*(Item_field));
5717	compare_pred= (Item_func_lt) thd->alloc(sizeof*(Item_func_lt));
5718
5719	key_columns[`0`]= new (thd->mem_root) Item_field (thd, tbl->field[col_idx]);
5720	/ Create the predicate (tmp_column[i] < outer_ref[i]). /
5721	compare_pred[`0`]= new (thd->mem_root) Item_func_lt (thd, key_columns[`0`],
5722	search_key->element_index(col_idx));
5723	compare_pred[`0`]->fix_fields(thd, (Item**)&compare_pred[`0`]);
5724
5725	if (alloc_keys_buffers())
5726	{
5727	/ TIMOUR revert to partial match via table scan. /
5728	return TRUE;
5729	}
5730	return FALSE;
5731	}
5732
5733
5734	/*
5735	Allocate the buffers for both the row number, and the NULL-bitmap indexes.
5736	*/
5737
5738	bool Ordered_key::alloc_keys_buffers()
5739	{
5740	DBUG_ASSERT(key_buff_elements > `0`);
5741
5742	if (!(key_buff= (rownum_t) my_malloc((size_t)(key_buff_elements
5743	sizeof(rownum_t)), MYF(MY_WME \| MY_THREAD_SPECIFIC))))
5744	return TRUE;
5745
5746	/*
5747	TIMOUR: it is enough to create bitmaps with size
5748	(max_null_row - min_null_row), and then use min_null_row as
5749	lookup offset.
5750	*/
5751	/ Notice that max_null_row is max array index, we need count, so +1. /
5752	if (my_bitmap_init(&null_key, NULL, (uint)(max_null_row + `1`), FALSE))
5753	return TRUE;
5754
5755	cur_key_idx= HA_POS_ERROR;
5756
5757	return FALSE;
5758	}
5759
5760
5761	/*
5762	Quick sort comparison function that compares two rows of the same table
5763	indentfied with their row numbers.
5764
5765	@retval -1
5766	@retval 0
5767	@retval +1
5768	*/
5769
5770	int
5771	Ordered_key::cmp_keys_by_row_data(ha_rows a, ha_rows b)
5772	{
5773	uchar rowid_a, rowid_b;
5774	int __attribute__((unused)) error;
5775	int cmp_res;
5776	/ The length in bytes of the rowids (positions) of tmp_table. /
5777	uint rowid_length= tbl->file->ref_length;
5778
5779	if (a == b)
5780	return `0`;
5781	/ Get the corresponding rowids. /
5782	rowid_a= row_num_to_rowid + a * rowid_length;
5783	rowid_b= row_num_to_rowid + b * rowid_length;
5784	/ Fetch the rows for comparison. /
5785	if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[`0`], rowid_a))))
5786	{
5787	/ purecov: begin inspected /
5788	tbl->file->print_error(error, MYF(ME_FATALERROR)); // Sets fatal_error
5789	return `0`;
5790	/ purecov: end /
5791	}
5792	if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[`1`], rowid_b))))
5793	{
5794	/ purecov: begin inspected /
5795	tbl->file->print_error(error, MYF(ME_FATALERROR)); // Sets fatal_error
5796	return `0`;
5797	/ purecov: end /
5798	}
5799	/*
5800	Compare the two rows by the corresponding values of the indexed
5801	columns.
5802	*/
5803	for (uint i= `0`; i < key_column_count; i++)
5804	{
5805	Field *cur_field= key_columns[i]->field;
5806	if ((cmp_res= cur_field->cmp_offset(tbl->s->rec_buff_length)))
5807	return (cmp_res > `0` ? `1` : -`1`);
5808	}
5809	return `0`;
5810	}
5811
5812
5813	int
5814	Ordered_key::cmp_keys_by_row_data_and_rownum(Ordered_key *key,
5815	rownum_t* a, rownum_t* b)
5816	{
5817	/ The result of comparing the two keys according to their row data. /
5818	int cmp_row_res= key->cmp_keys_by_row_data(a, b);
5819	if (cmp_row_res)
5820	return cmp_row_res;
5821	return (a < b) ? -`1` : (a > b) ? `1` : `0`;
5822	}
5823
5824
5825	void Ordered_key::sort_keys()
5826	{
5827	my_qsort2(key_buff, (size_t) key_buff_elements, sizeof(rownum_t),
5828	(qsort2_cmp) &cmp_keys_by_row_data_and_rownum, (void) this*);
5829	/ Invalidate the current row position. /
5830	cur_key_idx= HA_POS_ERROR;
5831	}
5832
5833
5834	/*
5835	The fraction of rows that do not contain NULL in the columns indexed by
5836	this key.
5837
5838	@retval 1 if there are no NULLs
5839	@retval 0 if only NULLs
5840	*/
5841
5842	double Ordered_key::null_selectivity()
5843	{
5844	/ We should not be processing empty tables. /
5845	DBUG_ASSERT(tbl->file->stats.records);
5846	return (`1` - (double) null_count / (double) tbl->file->stats.records);
5847	}
5848
5849
5850	/*
5851	Compare the value(s) of the current key in 'search_key' with the
5852	data of the current table record.
5853
5854	@notes The comparison result follows from the way compare_pred
5855	is created in Ordered_key::init. Currently compare_pred compares
5856	a field in of the current row with the corresponding Item that
5857	contains the search key.
5858
5859	@param row_num Number of the row (not index in the key_buff array)
5860
5861	@retval -1 if (current row < search_key)
5862	@retval 0 if (current row == search_key)
5863	@retval +1 if (current row > search_key)
5864	*/
5865
5866	int Ordered_key::cmp_key_with_search_key(rownum_t row_num)
5867	{
5868	/ The length in bytes of the rowids (positions) of tmp_table. /
5869	uint rowid_length= tbl->file->ref_length;
5870	uchar cur_rowid= row_num_to_rowid + row_num rowid_length;
5871	int __attribute__((unused)) error;
5872	int cmp_res;
5873
5874	if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[`0`], cur_rowid))))
5875	{
5876	/ purecov: begin inspected /
5877	tbl->file->print_error(error, MYF(ME_FATALERROR)); // Sets fatal_error
5878	return `0`;
5879	/ purecov: end /
5880	}
5881
5882	for (uint i= `0`; i < key_column_count; i++)
5883	{
5884	cmp_res= compare_pred[i]->get_comparator()->compare();
5885	/ Unlike Arg_comparator::compare_row() here there should be no NULLs. /
5886	DBUG_ASSERT(!compare_pred[i]->null_value);
5887	if (cmp_res)
5888	return (cmp_res > `0` ? `1` : -`1`);
5889	}
5890	return `0`;
5891	}
5892
5893
5894	/*
5895	Find a key in a sorted array of keys via binary search.
5896
5897	see create_subq_in_equalities()
5898	*/
5899
5900	bool Ordered_key::lookup()
5901	{
5902	DBUG_ASSERT(key_buff_elements);
5903
5904	ha_rows lo= `0`;
5905	ha_rows hi= key_buff_elements - `1`;
5906	ha_rows mid;
5907	int cmp_res;
5908
5909	while (lo <= hi)
5910	{
5911	mid= lo + (hi - lo) / `2`;
5912	cmp_res= cmp_key_with_search_key(key_buff[mid]);
5913	/*
5914	In order to find the minimum match, check if the pevious element is
5915	equal or smaller than the found one. If equal, we need to search further
5916	to the left.
5917	*/
5918	if (!cmp_res && mid > `0`)
5919	cmp_res= !cmp_key_with_search_key(key_buff[mid - `1`]) ? `1` : `0`;
5920
5921	if (cmp_res == -`1`)
5922	{
5923	/ row[mid] < search_key /
5924	lo= mid + `1`;
5925	}
5926	else if (cmp_res == `1`)
5927	{
5928	/ row[mid] > search_key /
5929	if (!mid)
5930	goto not_found;
5931	hi= mid - `1`;
5932	}
5933	else
5934	{
5935	/ row[mid] == search_key /
5936	cur_key_idx= mid;
5937	return TRUE;
5938	}
5939	}
5940	not_found:
5941	cur_key_idx= HA_POS_ERROR;
5942	return FALSE;
5943	}
5944
5945
5946	/*
5947	Move the current index pointer to the next key with the same column
5948	values as the current key. Since the index is sorted, all such keys
5949	are contiguous.
5950	*/
5951
5952	bool Ordered_key::next_same()
5953	{
5954	DBUG_ASSERT(key_buff_elements);
5955
5956	if (cur_key_idx < key_buff_elements - `1`)
5957	{
5958	/*
5959	TIMOUR:
5960	The below is quite inefficient, since as a result we will fetch every
5961	row (except the last one) twice. There must be a more efficient way,
5962	e.g. swapping record[0] and record[1], and reading only the new record.
5963	*/
5964	if (!cmp_keys_by_row_data(key_buff[cur_key_idx], key_buff[cur_key_idx + `1`]))
5965	{
5966	++cur_key_idx;
5967	return TRUE;
5968	}
5969	}
5970	return FALSE;
5971	}
5972
5973
5974	void Ordered_key::print(String *str)
5975	{
5976	uint i;
5977	str->append("{idx=");
5978	str->qs_append(keyid);
5979	str->append(", (");
5980	for (i= `0`; i < key_column_count - `1`; i++)
5981	{
5982	str->append(&key_columns[i]->field->field_name);
5983	str->append(", ");
5984	}
5985	str->append(&key_columns[i]->field->field_name);
5986	str->append("), ");
5987
5988	str->append("null_bitmap: (bits=");
5989	str->qs_append(null_key.n_bits);
5990	str->append(", nulls= ");
5991	str->qs_append((double)null_count);
5992	str->append(", min_null= ");
5993	str->qs_append((double)min_null_row);
5994	str->append(", max_null= ");
5995	str->qs_append((double)max_null_row);
5996	str->append("), ");
5997
5998	str->append(`'}'`);
5999	}
6000
6001
6002	subselect_partial_match_engine::subselect_partial_match_engine(
6003	subselect_uniquesubquery_engine *engine_arg,
6004	TABLE tmp_table_arg, Item_subselect item_arg,
6005	select_result_interceptor *result_arg,
6006	List<Item> *equi_join_conds_arg,
6007	bool has_covering_null_row_arg,
6008	bool has_covering_null_columns_arg,
6009	uint count_columns_with_nulls_arg)
6010	:subselect_engine (item_arg, result_arg),
6011	tmp_table(tmp_table_arg), lookup_engine(engine_arg),
6012	equi_join_conds(equi_join_conds_arg),
6013	has_covering_null_row(has_covering_null_row_arg),
6014	has_covering_null_columns(has_covering_null_columns_arg),
6015	count_columns_with_nulls(count_columns_with_nulls_arg)
6016	{}
6017
6018
6019	int subselect_partial_match_engine::exec()
6020	{
6021	Item_in_subselect item_in= (Item_in_subselect ) item;
6022	int lookup_res;
6023
6024	DBUG_ASSERT(!(item_in->left_expr_has_null() &&
6025	item_in->is_top_level_item()));
6026
6027	if (!item_in->left_expr_has_null())
6028	{
6029	/ Try to find a matching row by index lookup. /
6030	if (lookup_engine->copy_ref_key(false))
6031	{
6032	/ The result is FALSE based on the outer reference. /
6033	item_in->value= `0`;
6034	item_in->null_value= `0`;
6035	return `0`;
6036	}
6037	else
6038	{
6039	/ Search for a complete match. /
6040	if ((lookup_res= lookup_engine->index_lookup()))
6041	{
6042	/ An error occurred during lookup(). /
6043	item_in->value= `0`;
6044	item_in->null_value= `0`;
6045	return lookup_res;
6046	}
6047	else if (item_in->value \|\| !count_columns_with_nulls)
6048	{
6049	/*
6050	A complete match was found, the result of IN is TRUE.
6051	If no match was found, and there are no NULLs in the materialized
6052	subquery, then the result is guaranteed to be false because this
6053	branch is executed when the outer reference has no NULLs as well.
6054	Notice: (this->item == lookup_engine->item)
6055	*/
6056	return `0`;
6057	}
6058	}
6059	}
6060
6061	if (has_covering_null_row)
6062	{
6063	/*
6064	If there is a NULL-only row that coveres all columns the result of IN
6065	is UNKNOWN.
6066	*/
6067	item_in->value= `0`;
6068	/*
6069	TIMOUR: which one is the right way to propagate an UNKNOWN result?
6070	Should we also set empty_result_set= FALSE; ???
6071	*/
6072	//item_in->was_null= 1;
6073	item_in->null_value= `1`;
6074	return `0`;
6075	}
6076
6077	/*
6078	There is no complete match. Look for a partial match (UNKNOWN result), or
6079	no match (FALSE).
6080	*/
6081	if (tmp_table->file->inited)
6082	tmp_table->file->ha_index_end();
6083
6084	if (partial_match())
6085	{
6086	/ The result of IN is UNKNOWN. /
6087	item_in->value= `0`;
6088	/*
6089	TIMOUR: which one is the right way to propagate an UNKNOWN result?
6090	Should we also set empty_result_set= FALSE; ???
6091	*/
6092	//item_in->was_null= 1;
6093	item_in->null_value= `1`;
6094	}
6095	else
6096	{
6097	/ The result of IN is FALSE. /
6098	item_in->value= `0`;
6099	/*
6100	TIMOUR: which one is the right way to propagate an UNKNOWN result?
6101	Should we also set empty_result_set= FALSE; ???
6102	*/
6103	//item_in->was_null= 0;
6104	item_in->null_value= `0`;
6105	}
6106
6107	return `0`;
6108	}
6109
6110
6111	void subselect_partial_match_engine::print(String *str,
6112	enum_query_type query_type)
6113	{
6114	/*
6115	Should never be called as the actual engine cannot be known at query
6116	optimization time.
6117	DBUG_ASSERT(FALSE);
6118	*/
6119	}
6120
6121
6122	/*
6123	@param non_null_key_parts
6124	@param partial_match_key_parts A union of all single-column NULL key parts.
6125
6126	@retval FALSE the engine was initialized successfully
6127	@retval TRUE there was some (memory allocation) error during initialization,
6128	such errors should be interpreted as revert to other strategy
6129	*/
6130
6131	bool
6132	subselect_rowid_merge_engine::init(MY_BITMAP *non_null_key_parts,
6133	MY_BITMAP *partial_match_key_parts)
6134	{
6135	THD *thd= get_thd();
6136	/ The length in bytes of the rowids (positions) of tmp_table. /
6137	uint rowid_length= tmp_table->file->ref_length;
6138	ha_rows row_count= tmp_table->file->stats.records;
6139	rownum_t cur_rownum= `0`;
6140	select_materialize_with_stats *result_sink=
6141	(select_materialize_with_stats *) result;
6142	uint cur_keyid= `0`;
6143	Item_in_subselect item_in= (Item_in_subselect) item;
6144	int error;
6145
6146	if (merge_keys_count == `0`)
6147	{
6148	DBUG_ASSERT(bitmap_bits_set(partial_match_key_parts) == `0` \|\|
6149	has_covering_null_row);
6150	/ There is nothing to initialize, we will only do regular lookups. /
6151	return FALSE;
6152	}
6153
6154	/*
6155	If all nullable columns contain only NULLs, there must be one index
6156	over all non-null columns.
6157	*/
6158	DBUG_ASSERT(!has_covering_null_columns \|\|
6159	(has_covering_null_columns &&
6160	merge_keys_count == `1` && non_null_key_parts));
6161	/*
6162	Allocate buffers to hold the merged keys and the mapping between rowids and
6163	row numbers. All small buffers are allocated in the runtime memroot. Big
6164	buffers are allocated from the OS via malloc.
6165	*/
6166	if (!(merge_keys= (Ordered_key*) thd->alloc(merge_keys_count
6167	sizeof(Ordered_key*))) \|\|
6168	!(null_bitmaps= (MY_BITMAP*) thd->alloc(merge_keys_count
6169	sizeof(MY_BITMAP*))) \|\|
6170	!(row_num_to_rowid= (uchar) my_malloc((size_t)(row_count rowid_length),
6171	MYF(MY_WME \| MY_THREAD_SPECIFIC))))
6172	return TRUE;
6173
6174	/ Create the only non-NULL key if there is any. /
6175	if (non_null_key_parts)
6176	{
6177	non_null_key= new Ordered_key (cur_keyid, tmp_table, item_in->left_expr,
6178	`0`, `0`, `0`, row_num_to_rowid);
6179	if (non_null_key->init(non_null_key_parts))
6180	return TRUE;
6181	merge_keys[cur_keyid]= non_null_key;
6182	merge_keys[cur_keyid]->first();
6183	++cur_keyid;
6184	}
6185
6186	/*
6187	If all nullable columns contain NULLs, the only key that is needed is the
6188	only non-NULL key that is already created above.
6189	*/
6190	if (!has_covering_null_columns)
6191	{
6192	if (my_bitmap_init_memroot(&matching_keys, merge_keys_count, thd->mem_root) \|\|
6193	my_bitmap_init_memroot(&matching_outer_cols, merge_keys_count, thd->mem_root))
6194	return TRUE;
6195
6196	/*
6197	Create one single-column NULL-key for each column in
6198	partial_match_key_parts.
6199	*/
6200	for (uint i= `0`; i < partial_match_key_parts->n_bits; i++)
6201	{
6202	/ Skip columns that have no NULLs, or contain only NULLs. /
6203	if (!bitmap_is_set(partial_match_key_parts, i) \|\|
6204	result_sink->get_null_count_of_col(i) == row_count)
6205	continue;
6206
6207	merge_keys[cur_keyid]= new Ordered_key (
6208	cur_keyid, tmp_table,
6209	item_in->left_expr->element_index(i),
6210	result_sink->get_null_count_of_col(i),
6211	result_sink->get_min_null_of_col(i),
6212	result_sink->get_max_null_of_col(i),
6213	row_num_to_rowid);
6214	if (merge_keys[cur_keyid]->init(i))
6215	return TRUE;
6216	merge_keys[cur_keyid]->first();
6217	++cur_keyid;
6218	}
6219	}
6220	DBUG_ASSERT(cur_keyid == merge_keys_count);
6221
6222	/ Populate the indexes with data from the temporary table. /
6223	if (unlikely(tmp_table->file->ha_rnd_init_with_error(`1`)))
6224	return TRUE;
6225	tmp_table->file->extra_opt(HA_EXTRA_CACHE,
6226	current_thd->variables.read_buff_size);
6227	tmp_table->null_row= `0`;
6228	while (TRUE)
6229	{
6230	error= tmp_table->file->ha_rnd_next(tmp_table->record[`0`]);
6231	/*
6232	This is a temp table that we fully own, there should be no other
6233	cause to stop the iteration than EOF.
6234	*/
6235	DBUG_ASSERT(!error \|\| error == HA_ERR_END_OF_FILE);
6236	if (unlikely(error == HA_ERR_END_OF_FILE))
6237	{
6238	DBUG_ASSERT(cur_rownum == tmp_table->file->stats.records);
6239	break;
6240	}
6241
6242	/*
6243	Save the position of this record in the row_num -> rowid mapping.
6244	*/
6245	tmp_table->file->position(tmp_table->record[`0`]);
6246	memcpy(row_num_to_rowid + cur_rownum * rowid_length,
6247	tmp_table->file->ref, rowid_length);
6248
6249	/ Add the current row number to the corresponding keys. /
6250	if (non_null_key)
6251	{
6252	/ By definition there are no NULLs in the non-NULL key. /
6253	non_null_key->add_key(cur_rownum);
6254	}
6255
6256	for (uint i= (non_null_key ? `1` : `0`); i < merge_keys_count; i++)
6257	{
6258	/*
6259	Check if the first and only indexed column contains NULL in the curent
6260	row, and add the row number to the corresponding key.
6261	*/
6262	if (merge_keys[i]->get_field(`0`)->is_null())
6263	merge_keys[i]->set_null(cur_rownum);
6264	else
6265	merge_keys[i]->add_key(cur_rownum);
6266	}
6267	++cur_rownum;
6268	}
6269
6270	tmp_table->file->ha_rnd_end();
6271
6272	/ Sort all the keys by their NULL selectivity. /
6273	my_qsort(merge_keys, merge_keys_count, sizeof(Ordered_key*),
6274	(qsort_cmp) cmp_keys_by_null_selectivity);
6275
6276	/ Sort the keys in each of the indexes. /
6277	for (uint i= `0`; i < merge_keys_count; i++)
6278	merge_keys[i]->sort_keys();
6279
6280	if (init_queue(&pq, merge_keys_count, `0`, FALSE,
6281	subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
6282	`0`, `0`))
6283	return TRUE;
6284
6285	return FALSE;
6286	}
6287
6288
6289	subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
6290	{
6291	/ None of the resources below is allocated if there are no ordered keys. /
6292	if (merge_keys_count)
6293	{
6294	my_free(row_num_to_rowid);
6295	for (uint i= `0`; i < merge_keys_count; i++)
6296	delete merge_keys[i];
6297	delete_queue(&pq);
6298	if (tmp_table->file->inited == handler::RND)
6299	tmp_table->file->ha_rnd_end();
6300	}
6301	}
6302
6303
6304	void subselect_rowid_merge_engine::cleanup()
6305	{
6306	}
6307
6308
6309	/*
6310	Quick sort comparison function to compare keys in order of decreasing bitmap
6311	selectivity, so that the most selective keys come first.
6312
6313	@param k1 first key to compare
6314	@param k2 second key to compare
6315
6316	@retval 1 if k1 is less selective than k2
6317	@retval 0 if k1 is equally selective as k2
6318	@retval -1 if k1 is more selective than k2
6319	*/
6320
6321	int
6322	subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
6323	Ordered_key **k2)
6324	{
6325	double k1_sel= (*k1)->null_selectivity();
6326	double k2_sel= (*k2)->null_selectivity();
6327	if (k1_sel < k2_sel)
6328	return `1`;
6329	if (k1_sel > k2_sel)
6330	return -`1`;
6331	return `0`;
6332	}
6333
6334
6335	/*
6336	*/
6337
6338	int
6339	subselect_rowid_merge_engine::cmp_keys_by_cur_rownum(void *arg,
6340	uchar k1, uchar k2)
6341	{
6342	rownum_t r1= ((Ordered_key*) k1)->current();
6343	rownum_t r2= ((Ordered_key*) k2)->current();
6344
6345	return (r1 < r2) ? -`1` : (r1 > r2) ? `1` : `0`;
6346	}
6347
6348
6349	/*
6350	Check if certain table row contains a NULL in all columns for which there is
6351	no match in the corresponding value index.
6352
6353	@note
6354	There is no need to check the columns that contain only NULLs, because
6355	those are guaranteed to match.
6356
6357	@retval TRUE if a NULL row exists
6358	@retval FALSE otherwise
6359	*/
6360
6361	bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num)
6362	{
6363	Ordered_key *cur_key;
6364	for (uint i = `0`; i < merge_keys_count; i++)
6365	{
6366	cur_key= merge_keys[i];
6367	if (bitmap_is_set(&matching_keys, cur_key->get_keyid()))
6368	{
6369	/*
6370	The key 'i' (with id 'cur_keyid') already matches a value in row
6371	'row_num', thus we skip it as it can't possibly match a NULL.
6372	*/
6373	continue;
6374	}
6375	if (!cur_key->is_null(row_num))
6376	return FALSE;
6377	}
6378	return TRUE;
6379	}
6380
6381
6382	/**
6383	Test if a subset of NULL-able columns contains a row of NULLs.
6384	@retval TRUE if such a row exists
6385	@retval FALSE no complementing null row
6386	*/
6387
6388	bool subselect_rowid_merge_engine::
6389	exists_complementing_null_row(MY_BITMAP *keys_to_complement)
6390	{
6391	rownum_t highest_min_row= `0`;
6392	rownum_t lowest_max_row= UINT_MAX;
6393	uint count_null_keys, i;
6394	Ordered_key *cur_key;
6395
6396	if (!count_columns_with_nulls)
6397	{
6398	/*
6399	If there are both NULLs and non-NUll values in the outer reference, and
6400	the subquery contains no NULLs, a complementing NULL row cannot exist.
6401	*/
6402	return FALSE;
6403	}
6404
6405	for (i= (non_null_key ? `1` : `0`), count_null_keys= `0`; i < merge_keys_count; i++)
6406	{
6407	cur_key= merge_keys[i];
6408	if (bitmap_is_set(keys_to_complement, cur_key->get_keyid()))
6409	continue;
6410	if (!cur_key->get_null_count())
6411	{
6412	/ If there is column without NULLs, there cannot be a partial match. /
6413	return FALSE;
6414	}
6415	if (cur_key->get_min_null_row() > highest_min_row)
6416	highest_min_row= cur_key->get_min_null_row();
6417	if (cur_key->get_max_null_row() < lowest_max_row)
6418	lowest_max_row= cur_key->get_max_null_row();
6419	null_bitmaps[count_null_keys++]= cur_key->get_null_key();
6420	}
6421
6422	if (lowest_max_row < highest_min_row)
6423	{
6424	/ The intersection of NULL rows is empty. /
6425	return FALSE;
6426	}
6427
6428	return bitmap_exists_intersection((const MY_BITMAP**) null_bitmaps,
6429	count_null_keys,
6430	(uint)highest_min_row, (uint)lowest_max_row);
6431	}
6432
6433
6434	/*
6435	@retval TRUE there is a partial match (UNKNOWN)
6436	@retval FALSE there is no match at all (FALSE)
6437	*/
6438
6439	bool subselect_rowid_merge_engine::partial_match()
6440	{
6441	Ordered_key min_key; /* Key that contains the current minimum position. /
6442	rownum_t min_row_num; / Current row number of min_key. /
6443	Ordered_key *cur_key;
6444	rownum_t cur_row_num;
6445	uint count_nulls_in_search_key= `0`;
6446	uint max_null_in_any_row=
6447	((select_materialize_with_stats *) result)->get_max_nulls_in_row();
6448	bool res= FALSE;
6449
6450	/ If there is a non-NULL key, it must be the first key in the keys array. /
6451	DBUG_ASSERT(!non_null_key \|\| (non_null_key && merge_keys[`0`] == non_null_key));
6452	/ The prioryty queue for keys must be empty. /
6453	DBUG_ASSERT(!pq.elements);
6454
6455	/ All data accesses during execution are via handler::ha_rnd_pos() /
6456	if (unlikely(tmp_table->file->ha_rnd_init_with_error(`0`)))
6457	{
6458	res= FALSE;
6459	goto end;
6460	}
6461
6462	/ Check if there is a match for the columns of the only non-NULL key. /
6463	if (non_null_key && !non_null_key->lookup())
6464	{
6465	res= FALSE;
6466	goto end;
6467	}
6468
6469	/*
6470	If all nullable columns contain only NULLs, then there is a guranteed
6471	partial match, and we don't need to search for a matching row.
6472	*/
6473	if (has_covering_null_columns)
6474	{
6475	res= TRUE;
6476	goto end;
6477	}
6478
6479	if (non_null_key)
6480	queue_insert(&pq, (uchar *) non_null_key);
6481	/*
6482	Do not add the non_null_key, since it was already processed above.
6483	*/
6484	bitmap_clear_all(&matching_outer_cols);
6485	for (uint i= MY_TEST(non_null_key); i < merge_keys_count; i++)
6486	{
6487	DBUG_ASSERT(merge_keys[i]->get_column_count() == `1`);
6488	if (merge_keys[i]->get_search_key(`0`)->null_value)
6489	{
6490	++count_nulls_in_search_key;
6491	bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
6492	}
6493	else if (merge_keys[i]->lookup())
6494	queue_insert(&pq, (uchar *) merge_keys[i]);
6495	}
6496
6497	/*
6498	If the outer reference consists of only NULLs, or if it has NULLs in all
6499	nullable columns (above we guarantee there is a match for the non-null
6500	coumns), the result is UNKNOWN.
6501	*/
6502	if (count_nulls_in_search_key == merge_keys_count - MY_TEST(non_null_key))
6503	{
6504	res= TRUE;
6505	goto end;
6506	}
6507
6508	/*
6509	If the outer row has NULLs in some columns, and
6510	there is no match for any of the remaining columns, and
6511	there is a subquery row with NULLs in all unmatched columns,
6512	then there is a partial match, otherwise the result is FALSE.
6513	*/
6514	if (count_nulls_in_search_key && !pq.elements)
6515	{
6516	DBUG_ASSERT(!non_null_key);
6517	/*
6518	Check if the intersection of all NULL bitmaps of all keys that
6519	are not in matching_outer_cols is non-empty.
6520	*/
6521	res= exists_complementing_null_row(&matching_outer_cols);
6522	goto end;
6523	}
6524
6525	/*
6526	If there is no NULL (sub)row that covers all NULL columns, and there is no
6527	match for any of the NULL columns, the result is FALSE. Notice that if there
6528	is a non-null key, and there is only one matching key, the non-null key is
6529	the matching key. This is so, because this method returns FALSE if the
6530	non-null key doesn't have a match.
6531	*/
6532	if (!count_nulls_in_search_key &&
6533	(!pq.elements \|\|
6534	(pq.elements == `1` && non_null_key &&
6535	max_null_in_any_row < merge_keys_count-`1`)))
6536	{
6537	if (!pq.elements)
6538	{
6539	DBUG_ASSERT(!non_null_key);
6540	/*
6541	The case of a covering null row is handled by
6542	subselect_partial_match_engine::exec()
6543	*/
6544	DBUG_ASSERT(max_null_in_any_row != tmp_table->s->fields);
6545	}
6546	res= FALSE;
6547	goto end;
6548	}
6549
6550	DBUG_ASSERT(pq.elements);
6551
6552	min_key= (Ordered_key*) queue_remove_top(&pq);
6553	min_row_num= min_key->current();
6554	bitmap_set_bit(&matching_keys, min_key->get_keyid());
6555	bitmap_union(&matching_keys, &matching_outer_cols);
6556	if (min_key->next_same())
6557	queue_insert(&pq, (uchar *) min_key);
6558
6559	if (pq.elements == `0`)
6560	{
6561	/*
6562	Check the only matching row of the only key min_key for NULL matches
6563	in the other columns.
6564	*/
6565	res= test_null_row(min_row_num);
6566	goto end;
6567	}
6568
6569	while (TRUE)
6570	{
6571	cur_key= (Ordered_key*) queue_remove_top(&pq);
6572	cur_row_num= cur_key->current();
6573
6574	if (cur_row_num == min_row_num)
6575	bitmap_set_bit(&matching_keys, cur_key->get_keyid());
6576	else
6577	{
6578	/ Follows from the correct use of priority queue. /
6579	DBUG_ASSERT(cur_row_num > min_row_num);
6580	if (test_null_row(min_row_num))
6581	{
6582	res= TRUE;
6583	goto end;
6584	}
6585	else
6586	{
6587	min_key= cur_key;
6588	min_row_num= cur_row_num;
6589	bitmap_clear_all(&matching_keys);
6590	bitmap_set_bit(&matching_keys, min_key->get_keyid());
6591	bitmap_union(&matching_keys, &matching_outer_cols);
6592	}
6593	}
6594
6595	if (cur_key->next_same())
6596	queue_insert(&pq, (uchar *) cur_key);
6597
6598	if (pq.elements == `0`)
6599	{
6600	/ Check the last row of the last column in PQ for NULL matches. /
6601	res= test_null_row(min_row_num);
6602	goto end;
6603	}
6604	}
6605
6606	/ We should never get here - all branches must be handled explicitly above. /
6607	DBUG_ASSERT(FALSE);
6608
6609	end:
6610	if (!has_covering_null_columns)
6611	bitmap_clear_all(&matching_keys);
6612	queue_remove_all(&pq);
6613	tmp_table->file->ha_rnd_end();
6614	return res;
6615	}
6616
6617
6618	subselect_table_scan_engine::subselect_table_scan_engine(
6619	subselect_uniquesubquery_engine *engine_arg,
6620	TABLE *tmp_table_arg,
6621	Item_subselect *item_arg,
6622	select_result_interceptor *result_arg,
6623	List<Item> *equi_join_conds_arg,
6624	bool has_covering_null_row_arg,
6625	bool has_covering_null_columns_arg,
6626	uint count_columns_with_nulls_arg)
6627	:subselect_partial_match_engine (engine_arg, tmp_table_arg, item_arg,
6628	result_arg, equi_join_conds_arg,
6629	has_covering_null_row_arg,
6630	has_covering_null_columns_arg,
6631	count_columns_with_nulls_arg)
6632	{}
6633
6634
6635	/*
6636	TIMOUR:
6637	This method is based on subselect_uniquesubquery_engine::scan_table().
6638	Consider refactoring somehow, 80% of the code is the same.
6639
6640	for each row_i in tmp_table
6641	{
6642	count_matches= 0;
6643	for each row element row_i[j]
6644	{
6645	if (outer_ref[j] is NULL \|\| row_i[j] is NULL \|\| outer_ref[j] == row_i[j])
6646	++count_matches;
6647	}
6648	if (count_matches == outer_ref.elements)
6649	return TRUE
6650	}
6651	return FALSE
6652	*/
6653
6654	bool subselect_table_scan_engine::partial_match()
6655	{
6656	List_iterator_fast<Item> equality_it(*equi_join_conds);
6657	Item *cur_eq;
6658	uint count_matches;
6659	int error;
6660	bool res;
6661
6662	if (unlikely(tmp_table->file->ha_rnd_init_with_error(`1`)))
6663	{
6664	res= FALSE;
6665	goto end;
6666	}
6667
6668	tmp_table->file->extra_opt(HA_EXTRA_CACHE,
6669	get_thd()->variables.read_buff_size);
6670	for (;;)
6671	{
6672	error= tmp_table->file->ha_rnd_next(tmp_table->record[`0`]);
6673	if (unlikely(error))
6674	{
6675	if (error == HA_ERR_END_OF_FILE)
6676	{
6677	error= `0`;
6678	break;
6679	}
6680	else
6681	{
6682	error= report_error(tmp_table, error);
6683	break;
6684	}
6685	}
6686
6687	equality_it.rewind();
6688	count_matches= `0`;
6689	while ((cur_eq= equality_it ++))
6690	{
6691	DBUG_ASSERT(cur_eq->type() == Item::FUNC_ITEM &&
6692	((Item_func*)cur_eq)->functype() == Item_func::EQ_FUNC);
6693	if (!cur_eq->val_int() && !cur_eq->null_value)
6694	break;
6695	++count_matches;
6696	}
6697	if (count_matches == tmp_table->s->fields)
6698	{
6699	res= TRUE; / Found a matching row. /
6700	goto end;
6701	}
6702	}
6703
6704	res= FALSE;
6705	end:
6706	tmp_table->file->ha_rnd_end();
6707	return res;
6708	}
6709
6710
6711	void subselect_table_scan_engine::cleanup()
6712	{
6713	}
6714
6715
6716	void Item_subselect::register_as_with_rec_ref(With_element *with_elem)
6717	{
6718	with_elem->sq_with_rec_ref.link_in_list(this, &this->next_with_rec_ref);
6719	with_recursive_reference= true;
6720	}
6721
6722
6723	/*
6724	Create an execution tracker for the expression cache we're using for this
6725	subselect; add the tracker to the query plan.
6726	*/
6727
6728	void Item_subselect::init_expr_cache_tracker(THD *thd)
6729	{
6730	if(!expr_cache)
6731	return;
6732
6733	Explain_query *qw= thd->lex->explain;
6734	DBUG_ASSERT(qw);
6735	Explain_node *node= qw->get_node(unit->first_select()->select_number);
6736	if (!node)
6737	return;
6738	DBUG_ASSERT(expr_cache->type() == Item::EXPR_CACHE_ITEM);
6739	node->cache_tracker= ((Item_cache_wrapper *)expr_cache)->init_tracker(qw->mem_root);
6740	}
6741

Browse the source code of MariaDB/sql/item_subselect.cc