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

1	/*
2	Copyright (c) 2016, 2017 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	#include "mariadb.h"
18	#include "sql_parse.h"
19	#include "sql_select.h"
20	#include "sql_list.h"
21	#include "item_windowfunc.h"
22	#include "filesort.h"
23	#include "sql_base.h"
24	#include "sql_window.h"
25
26
27	bool
28	Window_spec::check_window_names(List_iterator_fast<Window_spec> &it)
29	{
30	if (window_names_are_checked)
31	return false;
32	const char name= this*->name();
33	const char *ref_name= window_reference();
34	it.rewind();
35	Window_spec *win_spec;
36	while((win_spec= it ++) && win_spec != this)
37	{
38	const char *win_spec_name= win_spec->name();
39	if (!win_spec_name)
40	break;
41	if (name && my_strcasecmp(system_charset_info, name, win_spec_name) == `0`)
42	{
43	my_error(ER_DUP_WINDOW_NAME, MYF(`0`), name);
44	return true;
45	}
46	if (ref_name &&
47	my_strcasecmp(system_charset_info, ref_name, win_spec_name) == `0`)
48	{
49	if (partition_list->elements)
50	{
51	my_error(ER_PARTITION_LIST_IN_REFERENCING_WINDOW_SPEC, MYF(`0`),
52	ref_name);
53	return true;
54	}
55	if (win_spec->order_list->elements && order_list->elements)
56	{
57	my_error(ER_ORDER_LIST_IN_REFERENCING_WINDOW_SPEC, MYF(`0`), ref_name);
58	return true;
59	}
60	if (win_spec->window_frame)
61	{
62	my_error(ER_WINDOW_FRAME_IN_REFERENCED_WINDOW_SPEC, MYF(`0`), ref_name);
63	return true;
64	}
65	referenced_win_spec= win_spec;
66	if (partition_list->elements == `0`)
67	partition_list= win_spec->partition_list;
68	if (order_list->elements == `0`)
69	order_list= win_spec->order_list;
70	}
71	}
72	if (ref_name && !referenced_win_spec)
73	{
74	my_error(ER_WRONG_WINDOW_SPEC_NAME, MYF(`0`), ref_name);
75	return true;
76	}
77	window_names_are_checked= true;
78	return false;
79	}
80
81	void
82	Window_spec::print(String *str, enum_query_type query_type)
83	{
84	str->append(`'('`);
85	if (partition_list->first)
86	{
87	str->append(STRING_WITH_LEN(" partition by "));
88	st_select_lex::print_order(str, partition_list->first, query_type);
89	}
90	if (order_list->first)
91	{
92	str->append(STRING_WITH_LEN(" order by "));
93	st_select_lex::print_order(str, order_list->first, query_type);
94	}
95	if (window_frame)
96	window_frame->print(str, query_type);
97	str->append(`')'`);
98	}
99
100	bool
101	Window_frame::check_frame_bounds()
102	{
103	if ((top_bound->is_unbounded() &&
104	top_bound->precedence_type == Window_frame_bound::FOLLOWING) \|\|
105	(bottom_bound->is_unbounded() &&
106	bottom_bound->precedence_type == Window_frame_bound::PRECEDING) \|\|
107	(top_bound->precedence_type == Window_frame_bound::CURRENT &&
108	bottom_bound->precedence_type == Window_frame_bound::PRECEDING) \|\|
109	(bottom_bound->precedence_type == Window_frame_bound::CURRENT &&
110	top_bound->precedence_type == Window_frame_bound::FOLLOWING))
111	{
112	my_error(ER_BAD_COMBINATION_OF_WINDOW_FRAME_BOUND_SPECS, MYF(`0`));
113	return true;
114	}
115
116	return false;
117	}
118
119
120	void
121	Window_frame::print(String *str, enum_query_type query_type)
122	{
123	switch (units) {
124	case UNITS_ROWS:
125	str->append(STRING_WITH_LEN(" rows "));
126	break;
127	case UNITS_RANGE:
128	str->append(STRING_WITH_LEN(" range "));
129	break;
130	default:
131	DBUG_ASSERT(`0`);
132	}
133
134	str->append(STRING_WITH_LEN("between "));
135	top_bound->print(str, query_type);
136	str->append(STRING_WITH_LEN(" and "));
137	bottom_bound->print(str, query_type);
138
139	if (exclusion != EXCL_NONE)
140	{
141	str->append(STRING_WITH_LEN(" exclude "));
142	switch (exclusion) {
143	case EXCL_CURRENT_ROW:
144	str->append(STRING_WITH_LEN(" current row "));
145	break;
146	case EXCL_GROUP:
147	str->append(STRING_WITH_LEN(" group "));
148	break;
149	case EXCL_TIES:
150	str->append(STRING_WITH_LEN(" ties "));
151	break;
152	default:
153	DBUG_ASSERT(`0`);
154	;
155	}
156	}
157	}
158
159
160	void
161	Window_frame_bound::print(String *str, enum_query_type query_type)
162	{
163	if (precedence_type == CURRENT)
164	{
165	str->append(STRING_WITH_LEN(" current row "));
166	return;
167	}
168	if (is_unbounded())
169	str->append(STRING_WITH_LEN(" unbounded "));
170	else
171	offset->print(str ,query_type);
172	switch (precedence_type) {
173	case PRECEDING:
174	str->append(STRING_WITH_LEN(" preceding "));
175	break;
176	case FOLLOWING:
177	str->append(STRING_WITH_LEN(" following "));
178	break;
179	default:
180	DBUG_ASSERT(`0`);
181	}
182	}
183
184	/*
185	Setup window functions in a select
186	*/
187
188	int
189	setup_windows(THD thd, Ref_ptr_array ref_pointer_array, TABLE_LIST tables,
190	List<Item> &fields, List<Item> &all_fields,
191	List<Window_spec> &win_specs, List<Item_window_func> &win_funcs)
192	{
193	Window_spec *win_spec;
194	DBUG_ENTER("setup_windows");
195	List_iterator<Window_spec> it(win_specs);
196
197	/*
198	Move all unnamed specifications after the named ones.
199	We could have avoided it if we had built two separate lists for
200	named and unnamed specifications.
201	*/
202	Query_arena *arena, backup;
203	arena= thd->activate_stmt_arena_if_needed(&backup);
204	uint i = `0`;
205	uint elems= win_specs.elements;
206	while ((win_spec= it ++) && i++ < elems)
207	{
208	if (win_spec->name() == NULL)
209	{
210	it.remove();
211	win_specs.push_back(win_spec);
212	}
213	}
214	if (arena)
215	thd->restore_active_arena(arena, &backup);
216
217	it.rewind();
218
219	List_iterator_fast<Window_spec> itp(win_specs);
220
221	while ((win_spec= it ++))
222	{
223	bool hidden_group_fields;
224	if (win_spec->check_window_names(itp) \|\|
225	setup_group(thd, ref_pointer_array, tables, fields, all_fields,
226	win_spec->partition_list->first, &hidden_group_fields,
227	true) \|\|
228	setup_order(thd, ref_pointer_array, tables, fields, all_fields,
229	win_spec->order_list->first, true) \|\|
230	(win_spec->window_frame &&
231	win_spec->window_frame->check_frame_bounds()))
232	{
233	DBUG_RETURN(`1`);
234	}
235
236	if (win_spec->window_frame &&
237	win_spec->window_frame->exclusion != Window_frame::EXCL_NONE)
238	{
239	my_error(ER_FRAME_EXCLUSION_NOT_SUPPORTED, MYF(`0`));
240	DBUG_RETURN(`1`);
241	}
242	/*
243	For "win_func() OVER (ORDER BY order_list RANGE BETWEEN ...)",
244	- ORDER BY order_list must not be ommitted
245	- the list must have a single element.
246	*/
247	if (win_spec->window_frame &&
248	win_spec->window_frame->units == Window_frame::UNITS_RANGE)
249	{
250	if (win_spec->order_list->elements != `1`)
251	{
252	my_error(ER_RANGE_FRAME_NEEDS_SIMPLE_ORDERBY, MYF(`0`));
253	DBUG_RETURN(`1`);
254	}
255
256	/*
257	"The declared type of SK shall be numeric, datetime, or interval"
258	we don't support datetime or interval, yet.
259	*/
260	Item_result rtype= win_spec->order_list->first->item[`0`]->result_type();
261	if (rtype != REAL_RESULT && rtype != INT_RESULT &&
262	rtype != DECIMAL_RESULT)
263	{
264	my_error(ER_WRONG_TYPE_FOR_RANGE_FRAME, MYF(`0`));
265	DBUG_RETURN(`1`);
266	}
267
268	/*
269	"The declared type of UVS shall be numeric if the declared type of SK
270	is numeric; otherwise, it shall be an interval type that may be added
271	to or subtracted from the declared type of SK"
272	*/
273	Window_frame_bound *bounds[]= {win_spec->window_frame->top_bound,
274	win_spec->window_frame->bottom_bound,
275	NULL};
276	for (Window_frame_bound *pbound= &bounds[`0`]; pbound; pbound++)
277	{
278	if (!(*pbound)->is_unbounded() &&
279	((*pbound)->precedence_type == Window_frame_bound::FOLLOWING \|\|
280	(*pbound)->precedence_type == Window_frame_bound::PRECEDING))
281	{
282	Item_result rtype= (*pbound)->offset->result_type();
283	if (rtype != REAL_RESULT && rtype != INT_RESULT &&
284	rtype != DECIMAL_RESULT)
285	{
286	my_error(ER_WRONG_TYPE_FOR_RANGE_FRAME, MYF(`0`));
287	DBUG_RETURN(`1`);
288	}
289	}
290	}
291	}
292
293	/ "ROWS PRECEDING\|FOLLOWING $n" must have a numeric $n /
294	if (win_spec->window_frame &&
295	win_spec->window_frame->units == Window_frame::UNITS_ROWS)
296	{
297	Window_frame_bound *bounds[]= {win_spec->window_frame->top_bound,
298	win_spec->window_frame->bottom_bound,
299	NULL};
300	for (Window_frame_bound *pbound= &bounds[`0`]; pbound; pbound++)
301	{
302	if (!(*pbound)->is_unbounded() &&
303	((*pbound)->precedence_type == Window_frame_bound::FOLLOWING \|\|
304	(*pbound)->precedence_type == Window_frame_bound::PRECEDING))
305	{
306	Item offset= (pbound)->offset;
307	if (offset->result_type() != INT_RESULT)
308	{
309	my_error(ER_WRONG_TYPE_FOR_ROWS_FRAME, MYF(`0`));
310	DBUG_RETURN(`1`);
311	}
312	}
313	}
314	}
315	}
316
317	List_iterator_fast<Item_window_func> li(win_funcs);
318	while (Item_window_func * win_func_item= li ++)
319	{
320	if (win_func_item->check_result_type_of_order_item())
321	DBUG_RETURN(`1`);
322	}
323	DBUG_RETURN(`0`);
324	}
325
326
327	/**
328	@brief
329	Find fields common for all partition lists used in window functions
330
331	@param thd The thread handle
332
333	@details
334	This function looks for the field references in the partition lists
335	of all window functions used in this select that are common for
336	all the partition lists. The function returns an ORDER list contained
337	all such references.The list either is specially built by the function
338	or is taken directly from the first window specification.
339
340	@retval
341	pointer to the first element of the ORDER list contained field
342	references common for all partition lists
343	0 if no such reference is found.
344	*/
345
346	ORDER st_select_lex::find_common_window_func_partition_fields(THD thd)
347	{
348	ORDER *ord;
349	Item *item;
350	DBUG_ASSERT(window_funcs.elements);
351	List_iterator_fast<Item_window_func> it(window_funcs);
352	Item_window_func *first_wf= it ++;
353	if (!first_wf->window_spec->partition_list)
354	return `0`;
355	List<Item> common_fields;
356	uint first_partition_elements= `0`;
357	for (ord= first_wf->window_spec->partition_list->first; ord; ord= ord->next)
358	{
359	if ((*ord->item)->real_item()->type() == Item::FIELD_ITEM)
360	common_fields.push_back(*ord->item, thd->mem_root);
361	first_partition_elements++;
362	}
363	if (window_specs.elements == `1` &&
364	common_fields.elements == first_partition_elements)
365	return first_wf->window_spec->partition_list->first;
366	List_iterator<Item> li(common_fields);
367	Item_window_func *wf;
368	while (common_fields.elements && (wf= it ++))
369	{
370	if (!wf->window_spec->partition_list)
371	return `0`;
372	while ((item= li ++))
373	{
374	for (ord= wf->window_spec->partition_list->first; ord; ord= ord->next)
375	{
376	if (item->eq(ord->item, false*))
377	break;
378	}
379	if (!ord)
380	li.remove();
381	}
382	li.rewind();
383	}
384	if (!common_fields.elements)
385	return `0`;
386	if (common_fields.elements == first_partition_elements)
387	return first_wf->window_spec->partition_list->first;
388	SQL_I_List<ORDER> res_list;
389	for (ord= first_wf->window_spec->partition_list->first, item= li ++;
390	ord; ord= ord->next)
391	{
392	if (item != *ord->item)
393	continue;
394	if (add_to_list(thd, res_list, item, ord->direction))
395	return `0`;
396	item= li ++;
397	}
398	return res_list.first;
399	}
400
401
402	/////////////////////////////////////////////////////////////////////////////
403	// Sorting window functions to minimize the number of table scans
404	// performed during the computation of these functions
405	/////////////////////////////////////////////////////////////////////////////
406
407	#define CMP_LT -2 // Less than
408	#define CMP_LT_C -1 // Less than and compatible
409	#define CMP_EQ 0 // Equal to
410	#define CMP_GT_C 1 // Greater than and compatible
411	#define CMP_GT 2 // Greater then
412
413	static
414	int compare_order_elements(ORDER ord1, ORDER ord2)
415	{
416	if (ord1->item == ord2->item && ord1->direction == ord2->direction)
417	return CMP_EQ;
418	Item item1= (ord1->item)->real_item();
419	Item item2= (ord2->item)->real_item();
420	DBUG_ASSERT(item1->type() == Item::FIELD_ITEM &&
421	item2->type() == Item::FIELD_ITEM);
422	int cmp= ((Item_field *) item1)->field->field_index -
423	((Item_field *) item2)->field->field_index;
424	if (cmp == `0`)
425	{
426	if (ord1->direction == ord2->direction)
427	return CMP_EQ;
428	return ord1->direction > ord2->direction ? CMP_GT : CMP_LT;
429	}
430	else
431	return cmp > `0` ? CMP_GT : CMP_LT;
432	}
433
434	static
435	int compare_order_lists(SQL_I_List<ORDER> *part_list1,
436	SQL_I_List<ORDER> *part_list2)
437	{
438	if (part_list1 == part_list2)
439	return CMP_EQ;
440	ORDER *elem1= part_list1->first;
441	ORDER *elem2= part_list2->first;
442	for ( ; elem1 && elem2; elem1= elem1->next, elem2= elem2->next)
443	{
444	int cmp;
445	if ((cmp= compare_order_elements(elem1, elem2)))
446	return cmp;
447	}
448	if (elem1)
449	return CMP_GT_C;
450	if (elem2)
451	return CMP_LT_C;
452	return CMP_EQ;
453	}
454
455
456	static
457	int compare_window_frame_bounds(Window_frame_bound *win_frame_bound1,
458	Window_frame_bound *win_frame_bound2,
459	bool is_bottom_bound)
460	{
461	int res;
462	if (win_frame_bound1->precedence_type != win_frame_bound2->precedence_type)
463	{
464	res= win_frame_bound1->precedence_type > win_frame_bound2->precedence_type ?
465	CMP_GT : CMP_LT;
466	if (is_bottom_bound)
467	res= -res;
468	return res;
469	}
470
471	if (win_frame_bound1->is_unbounded() && win_frame_bound2->is_unbounded())
472	return CMP_EQ;
473
474	if (!win_frame_bound1->is_unbounded() && !win_frame_bound2->is_unbounded())
475	{
476	if (win_frame_bound1->offset->eq(win_frame_bound2->offset, true))
477	return CMP_EQ;
478	else
479	{
480	res= strcmp(win_frame_bound1->offset->name.str,
481	win_frame_bound2->offset->name.str);
482	res= res > `0` ? CMP_GT : CMP_LT;
483	if (is_bottom_bound)
484	res= -res;
485	return res;
486	}
487	}
488
489	/*
490	Here we have:
491	win_frame_bound1->is_unbounded() != win_frame_bound1->is_unbounded()
492	*/
493	return is_bottom_bound != win_frame_bound1->is_unbounded() ? CMP_LT : CMP_GT;
494	}
495
496
497	static
498	int compare_window_frames(Window_frame *win_frame1,
499	Window_frame *win_frame2)
500	{
501	int cmp;
502
503	if (win_frame1 == win_frame2)
504	return CMP_EQ;
505
506	if (!win_frame1)
507	return CMP_LT;
508
509	if (!win_frame2)
510	return CMP_GT;
511
512	if (win_frame1->units != win_frame2->units)
513	return win_frame1->units > win_frame2->units ? CMP_GT : CMP_LT;
514
515	cmp= compare_window_frame_bounds(win_frame1->top_bound,
516	win_frame2->top_bound,
517	false);
518	if (cmp)
519	return cmp;
520
521	cmp= compare_window_frame_bounds(win_frame1->bottom_bound,
522	win_frame2->bottom_bound,
523	true);
524	if (cmp)
525	return cmp;
526
527	if (win_frame1->exclusion != win_frame2->exclusion)
528	return win_frame1->exclusion > win_frame2->exclusion ? CMP_GT_C : CMP_LT_C;
529
530	return CMP_EQ;
531	}
532
533	static
534	int compare_window_spec_joined_lists(Window_spec *win_spec1,
535	Window_spec *win_spec2)
536	{
537	win_spec1->join_partition_and_order_lists();
538	win_spec2->join_partition_and_order_lists();
539	int cmp= compare_order_lists(win_spec1->partition_list,
540	win_spec2->partition_list);
541	win_spec1->disjoin_partition_and_order_lists();
542	win_spec2->disjoin_partition_and_order_lists();
543	return cmp;
544	}
545
546
547	static
548	int compare_window_funcs_by_window_specs(Item_window_func *win_func1,
549	Item_window_func *win_func2,
550	void *arg)
551	{
552	int cmp;
553	Window_spec *win_spec1= win_func1->window_spec;
554	Window_spec *win_spec2= win_func2->window_spec;
555	if (win_spec1 == win_spec2)
556	return CMP_EQ;
557	cmp= compare_order_lists(win_spec1->partition_list,
558	win_spec2->partition_list);
559	if (cmp == CMP_EQ)
560	{
561	/*
562	Partition lists contain the same elements.
563	Let's use only one of the lists.
564	*/
565	if (!win_spec1->name() && win_spec2->name())
566	win_spec1->partition_list= win_spec2->partition_list;
567	else
568	win_spec2->partition_list= win_spec1->partition_list;
569
570	cmp= compare_order_lists(win_spec1->order_list,
571	win_spec2->order_list);
572
573	if (cmp != CMP_EQ)
574	return cmp;
575
576	/*
577	Order lists contain the same elements.
578	Let's use only one of the lists.
579	*/
580	if (!win_spec1->name() && win_spec2->name())
581	win_spec1->order_list= win_spec2->order_list;
582	else
583	win_spec2->order_list= win_spec1->order_list;
584
585	cmp= compare_window_frames(win_spec1->window_frame,
586	win_spec2->window_frame);
587
588	if (cmp != CMP_EQ)
589	return cmp;
590
591	/ Window frames are equal. Let's use only one of them. /
592	if (!win_spec1->name() && win_spec2->name())
593	win_spec1->window_frame= win_spec2->window_frame;
594	else
595	win_spec2->window_frame= win_spec1->window_frame;
596
597	return CMP_EQ;
598	}
599
600	if (cmp == CMP_GT \|\| cmp == CMP_LT)
601	return cmp;
602
603	/ one of the partitions lists is the proper beginning of the another /
604	cmp= compare_window_spec_joined_lists(win_spec1, win_spec2);
605
606	if (CMP_LT_C <= cmp && cmp <= CMP_GT_C)
607	cmp= win_spec1->partition_list->elements <
608	win_spec2->partition_list->elements ? CMP_GT_C : CMP_LT_C;
609
610	return cmp;
611	}
612
613
614	#define SORTORDER_CHANGE_FLAG 1
615	#define PARTITION_CHANGE_FLAG 2
616	#define FRAME_CHANGE_FLAG 4
617
618	typedef int (Item_window_func_cmp)(Item_window_func f1,
619	Item_window_func *f2,
620	void *arg);
621	/*
622	@brief
623	Sort window functions so that those that can be computed together are
624	adjacent.
625
626	@detail
627	Sort window functions by their
628	- required sorting order,
629	- partition list,
630	- window frame compatibility.
631
632	The changes between the groups are marked by setting item_window_func->marker.
633	*/
634
635	static
636	void order_window_funcs_by_window_specs(List<Item_window_func> *win_func_list)
637	{
638	if (win_func_list->elements == `0`)
639	return;
640
641	bubble_sort<Item_window_func>(win_func_list,
642	compare_window_funcs_by_window_specs,
643	NULL);
644
645	List_iterator_fast<Item_window_func> it(*win_func_list);
646	Item_window_func *prev= it ++;
647	prev->marker= SORTORDER_CHANGE_FLAG \|
648	PARTITION_CHANGE_FLAG \|
649	FRAME_CHANGE_FLAG;
650	Item_window_func *curr;
651	while ((curr= it ++))
652	{
653	Window_spec *win_spec_prev= prev->window_spec;
654	Window_spec *win_spec_curr= curr->window_spec;
655	curr->marker= `0`;
656	if (!(win_spec_prev->partition_list == win_spec_curr->partition_list &&
657	win_spec_prev->order_list == win_spec_curr->order_list))
658	{
659	int cmp;
660	if (win_spec_prev->partition_list == win_spec_curr->partition_list)
661	cmp= compare_order_lists(win_spec_prev->order_list,
662	win_spec_curr->order_list);
663	else
664	cmp= compare_window_spec_joined_lists(win_spec_prev, win_spec_curr);
665	if (!(CMP_LT_C <= cmp && cmp <= CMP_GT_C))
666	{
667	curr->marker= SORTORDER_CHANGE_FLAG \|
668	PARTITION_CHANGE_FLAG \|
669	FRAME_CHANGE_FLAG;
670	}
671	else if (win_spec_prev->partition_list != win_spec_curr->partition_list)
672	{
673	curr->marker\|= PARTITION_CHANGE_FLAG \| FRAME_CHANGE_FLAG;
674	}
675	}
676	else if (win_spec_prev->window_frame != win_spec_curr->window_frame)
677	curr->marker\|= FRAME_CHANGE_FLAG;
678
679	prev= curr;
680	}
681	}
682
683
684	/////////////////////////////////////////////////////////////////////////////
685
686
687	/////////////////////////////////////////////////////////////////////////////
688	// Window Frames support
689	/////////////////////////////////////////////////////////////////////////////
690
691	// note: make rr_from_pointers static again when not need it here anymore
692	int rr_from_pointers(READ_RECORD *info);
693
694
695	/////////////////////////////////////////////////////////////////////////////
696
697
698	/*
699	A cursor over a sequence of rowids. One can
700	- Move to next rowid
701	- jump to given number in the sequence
702	- Know the number of the current rowid (i.e. how many rowids have been read)
703	*/
704
705	class Rowid_seq_cursor
706	{
707	public:
708	Rowid_seq_cursor() : io_cache(NULL), ref_buffer(`0`) {}
709	virtual ~Rowid_seq_cursor()
710	{
711	if (ref_buffer)
712	my_free(ref_buffer);
713	if (io_cache)
714	{
715	end_slave_io_cache(io_cache);
716	my_free(io_cache);
717	io_cache= NULL;
718	}
719	}
720
721	private:
722	/ Length of one rowid element /
723	size_t ref_length;
724
725	/ If io_cache=!NULL, use it /
726	IO_CACHE *io_cache;
727	uchar ref_buffer; /* Buffer for the last returned rowid /
728	ha_rows rownum; / Number of the rowid that is about to be returned /
729	ha_rows current_ref_buffer_rownum;
730	bool ref_buffer_valid;
731
732	/ The following are used when we are reading from an array of pointers /
733	uchar *cache_start;
734	uchar *cache_pos;
735	uchar *cache_end;
736	public:
737
738	void init(READ_RECORD *info)
739	{
740	ref_length= info->ref_length;
741	if (info->read_record_func == rr_from_pointers)
742	{
743	io_cache= NULL;
744	cache_start= info->cache_pos;
745	cache_pos= info->cache_pos;
746	cache_end= info->cache_end;
747	}
748	else
749	{
750	//DBUG_ASSERT(info->read_record == rr_from_tempfile);
751	rownum= `0`;
752	io_cache= (IO_CACHE)my_malloc(sizeof*(IO_CACHE), MYF(`0`));
753	init_slave_io_cache(info->io_cache, io_cache);
754
755	ref_buffer= (uchar*)my_malloc(ref_length, MYF(`0`));
756	ref_buffer_valid= false;
757	}
758	}
759
760	virtual int next()
761	{
762	/ Allow multiple next() calls in EOF state. /
763	if (at_eof())
764	return -`1`;
765
766	if (io_cache)
767	{
768	rownum++;
769	}
770	else
771	{
772	cache_pos+= ref_length;
773	DBUG_ASSERT(cache_pos <= cache_end);
774	}
775	return `0`;
776	}
777
778	virtual int prev()
779	{
780	if (io_cache)
781	{
782	if (rownum == `0`)
783	return -`1`;
784
785	rownum--;
786	return `0`;
787	}
788	else
789	{
790	/ Allow multiple prev() calls when positioned at the start. /
791	if (cache_pos == cache_start)
792	return -`1`;
793	cache_pos-= ref_length;
794	DBUG_ASSERT(cache_pos >= cache_start);
795	return `0`;
796	}
797	}
798
799	ha_rows get_rownum() const
800	{
801	if (io_cache)
802	return rownum;
803	else
804	return (cache_pos - cache_start) / ref_length;
805	}
806
807	void move_to(ha_rows row_number)
808	{
809	if (io_cache)
810	{
811	rownum= row_number;
812	}
813	else
814	{
815	cache_pos= MY_MIN(cache_end, cache_start + row_number * ref_length);
816	DBUG_ASSERT(cache_pos <= cache_end);
817	}
818	}
819
820	protected:
821	bool at_eof()
822	{
823	if (io_cache)
824	{
825	return rownum * ref_length >= io_cache->end_of_file;
826	}
827	else
828	return (cache_pos == cache_end);
829	}
830
831	bool get_curr_rowid(uchar **row_id)
832	{
833	if (io_cache)
834	{
835	DBUG_ASSERT(!at_eof());
836	if (!ref_buffer_valid \|\| current_ref_buffer_rownum != rownum)
837	{
838	seek_io_cache(io_cache, rownum * ref_length);
839	if (my_b_read(io_cache,ref_buffer,ref_length))
840	{
841	/ Error reading from file. /
842	return true;
843	}
844	ref_buffer_valid= true;
845	current_ref_buffer_rownum = rownum;
846	}
847	*row_id = ref_buffer;
848	return false;
849	}
850	else
851	{
852	*row_id= cache_pos;
853	return false;
854	}
855	}
856	};
857
858
859	/*
860	Cursor which reads from rowid sequence and also retrieves table rows.
861	*/
862
863	class Table_read_cursor : public Rowid_seq_cursor
864	{
865	public:
866	virtual ~Table_read_cursor() {}
867
868	void init(READ_RECORD *info)
869	{
870	Rowid_seq_cursor::init(info);
871	table= info->table;
872	record= info->record;
873	}
874
875	virtual int fetch()
876	{
877	if (at_eof())
878	return -`1`;
879
880	uchar* curr_rowid;
881	if (get_curr_rowid(&curr_rowid))
882	return -`1`;
883	return table->file->ha_rnd_pos(record, curr_rowid);
884	}
885
886	private:
887	/ The table that is acccesed by this cursor. /
888	TABLE *table;
889	/ Buffer where to store the table's record data. /
890	uchar *record;
891
892	// TODO(spetrunia): should move_to() also read row here?
893	};
894
895
896	/*
897	A cursor which only moves within a partition. The scan stops at the partition
898	end, and it needs an explicit command to move to the next partition.
899
900	This cursor can not move backwards.
901	*/
902
903	class Partition_read_cursor : public Table_read_cursor
904	{
905	public:
906	Partition_read_cursor(THD thd, SQL_I_List<ORDER> partition_list) :
907	bound_tracker (thd, partition_list) {}
908
909	void init(READ_RECORD *info)
910	{
911	Table_read_cursor::init(info);
912	bound_tracker.init();
913	end_of_partition= false;
914	}
915
916	/*
917	Informs the cursor that we need to move into the next partition.
918	The next partition is provided in two ways:
919	- in table->record[0]..
920	- rownum parameter has the row number.
921	*/
922	void on_next_partition(ha_rows rownum)
923	{
924	/ Remember the sort key value from the new partition /
925	move_to(rownum);
926	bound_tracker.check_if_next_group();
927	end_of_partition= false;
928
929	}
930
931	/*
932	This returns -1 when end of partition was reached.
933	*/
934	int next()
935	{
936	int res;
937	if (end_of_partition)
938	return -`1`;
939
940	if ((res= Table_read_cursor::next()) \|\|
941	(res= fetch()))
942	{
943	/ TODO(cvicentiu) This does not consider table read failures.*
944	Perhaps assuming end of table like this is fine in that case. /*
945
946	/ This row is the final row in the table. To maintain semantics*
947	that cursors always point to the last valid row, move back one step,
948	but mark end_of_partition as true. /*
949	Table_read_cursor::prev();
950	end_of_partition= true;
951	return res;
952	}
953
954	if (bound_tracker.compare_with_cache())
955	{
956	/ This row is part of a new partition, don't move*
957	forward any more untill we get informed of a new partition. /*
958	Table_read_cursor::prev();
959	end_of_partition= true;
960	return -`1`;
961	}
962	return `0`;
963	}
964
965	private:
966	Group_bound_tracker bound_tracker;
967	bool end_of_partition;
968	};
969
970
971
972	/////////////////////////////////////////////////////////////////////////////
973
974	/*
975	Window frame bound cursor. Abstract interface.
976
977	@detail
978	The cursor moves within the partition that the current row is in.
979	It may be ahead or behind the current row.
980
981	The cursor also assumes that the current row moves forward through the
982	partition and will move to the next adjacent partition after this one.
983
984	List of all cursor classes:
985	Frame_cursor
986	Frame_range_n_top
987	Frame_range_n_bottom
988
989	Frame_range_current_row_top
990	Frame_range_current_row_bottom
991
992	Frame_n_rows_preceding
993	Frame_n_rows_following
994
995	Frame_rows_current_row_top = Frame_n_rows_preceding(0)
996	Frame_rows_current_row_bottom
997
998	// These handle both RANGE and ROWS-type bounds
999	Frame_unbounded_preceding
1000	Frame_unbounded_following
1001
1002	// This is not used as a frame bound, it counts rows in the partition:
1003	Frame_unbounded_following_set_count : public Frame_unbounded_following
1004
1005	@todo
1006	- if we want to allocate this on the MEM_ROOT we should make sure
1007	it is not re-allocated for every subquery execution.
1008	*/
1009
1010	class Frame_cursor : public Sql_alloc
1011	{
1012	public:
1013	Frame_cursor() : sum_functions (), perform_no_action(false) {}
1014
1015	virtual void init(READ_RECORD *info) {};
1016
1017	bool add_sum_func(Item_sum* item)
1018	{
1019	return sum_functions.push_back(item);
1020	}
1021	/*
1022	Current row has moved to the next partition and is positioned on the first
1023	row there. Position the frame bound accordingly.
1024
1025	@param first - TRUE means this is the first partition
1026	@param item - Put or remove rows from there.
1027
1028	@detail
1029	- if first==false, the caller guarantees that tbl->record[0] points at the
1030	first row in the new partition.
1031	- if first==true, we are just starting in the first partition and no such
1032	guarantee is provided.
1033
1034	- The callee may move tbl->file and tbl->record[0] to point to some other
1035	row.
1036	*/
1037	virtual void pre_next_partition(ha_rows rownum) {};
1038	virtual void next_partition(ha_rows rownum)=`0`;
1039
1040	/*
1041	The current row has moved one row forward.
1042	Move this frame bound accordingly, and update the value of aggregate
1043	function as necessary.
1044	*/
1045	virtual void pre_next_row() {};
1046	virtual void next_row()=`0`;
1047
1048	virtual bool is_outside_computation_bounds() const { return false; };
1049
1050	virtual ~Frame_cursor() {}
1051
1052	/*
1053	Regular frame cursors add or remove values from the sum functions they
1054	manage. By calling this method, they will only perform the required
1055	movement within the table, but no adding/removing will happen.
1056	*/
1057	void set_no_action()
1058	{
1059	perform_no_action= true;
1060	}
1061
1062	/ Retrieves the row number that this cursor currently points at. /
1063	virtual ha_rows get_curr_rownum() const= `0`;
1064
1065	protected:
1066	inline void add_value_to_items()
1067	{
1068	if (perform_no_action)
1069	return;
1070
1071	List_iterator_fast<Item_sum> it(sum_functions);
1072	Item_sum *item_sum;
1073	while ((item_sum= it ++))
1074	{
1075	item_sum->add();
1076	}
1077	}
1078
1079	inline void remove_value_from_items()
1080	{
1081	if (perform_no_action)
1082	return;
1083
1084	List_iterator_fast<Item_sum> it(sum_functions);
1085	Item_sum *item_sum;
1086	while ((item_sum= it ++))
1087	{
1088	item_sum->remove();
1089	}
1090	}
1091
1092	/ Clear all sum functions handled by this cursor. /
1093	void clear_sum_functions()
1094	{
1095	List_iterator_fast<Item_sum> iter_sum_func(sum_functions);
1096	Item_sum *sum_func;
1097	while ((sum_func= iter_sum_func ++))
1098	{
1099	sum_func->clear();
1100	}
1101	}
1102
1103	/ Sum functions that this cursor handles. /
1104	List<Item_sum> sum_functions;
1105
1106	private:
1107	bool perform_no_action;
1108	};
1109
1110	/*
1111	A class that owns cursor objects associated with a specific window function.
1112	*/
1113	class Cursor_manager
1114	{
1115	public:
1116	bool add_cursor(Frame_cursor *cursor)
1117	{
1118	return cursors.push_back(cursor);
1119	}
1120
1121	void initialize_cursors(READ_RECORD *info)
1122	{
1123	List_iterator_fast<Frame_cursor> iter(cursors);
1124	Frame_cursor *fc;
1125	while ((fc= iter ++))
1126	fc->init(info);
1127	}
1128
1129	void notify_cursors_partition_changed(ha_rows rownum)
1130	{
1131	List_iterator_fast<Frame_cursor> iter(cursors);
1132	Frame_cursor *cursor;
1133	while ((cursor= iter ++))
1134	cursor->pre_next_partition(rownum);
1135
1136	iter.rewind();
1137	while ((cursor= iter ++))
1138	cursor->next_partition(rownum);
1139	}
1140
1141	void notify_cursors_next_row()
1142	{
1143	List_iterator_fast<Frame_cursor> iter(cursors);
1144	Frame_cursor *cursor;
1145	while ((cursor= iter ++))
1146	cursor->pre_next_row();
1147
1148	iter.rewind();
1149	while ((cursor= iter ++))
1150	cursor->next_row();
1151	}
1152
1153	~Cursor_manager() { cursors.delete_elements(); }
1154
1155	private:
1156	/ List of the cursors that this manager owns. /
1157	List<Frame_cursor> cursors;
1158	};
1159
1160
1161
1162	//////////////////////////////////////////////////////////////////////////////
1163	// RANGE-type frames
1164	//////////////////////////////////////////////////////////////////////////////
1165
1166	/*
1167	Frame_range_n_top handles the top end of RANGE-type frame.
1168
1169	That is, it handles:
1170	RANGE BETWEEN n PRECEDING AND ...
1171	RANGE BETWEEN n FOLLOWING AND ...
1172
1173	Top of the frame doesn't need to check for partition end, since bottom will
1174	reach it before.
1175	*/
1176
1177	class Frame_range_n_top : public Frame_cursor
1178	{
1179	Partition_read_cursor cursor;
1180
1181	Cached_item_item *range_expr;
1182
1183	Item *n_val;
1184	Item *item_add;
1185
1186	const bool is_preceding;
1187
1188	bool end_of_partition;
1189
1190	/*
1191	1 when order_list uses ASC ordering
1192	-1 when order_list uses DESC ordering
1193	*/
1194	int order_direction;
1195	public:
1196	Frame_range_n_top(THD *thd,
1197	SQL_I_List<ORDER> *partition_list,
1198	SQL_I_List<ORDER> *order_list,
1199	bool is_preceding_arg, Item *n_val_arg) :
1200	cursor (thd, partition_list), n_val(n_val_arg), item_add(NULL),
1201	is_preceding(is_preceding_arg)
1202	{
1203	DBUG_ASSERT(order_list->elements == `1`);
1204	Item *src_expr= order_list->first->item[`0`];
1205	if (order_list->first->direction == ORDER::ORDER_ASC)
1206	order_direction= `1`;
1207	else
1208	order_direction= -`1`;
1209
1210	range_expr= (Cached_item_item*) new_Cached_item(thd, src_expr, FALSE);
1211
1212	bool use_minus= is_preceding;
1213	if (order_direction == -`1`)
1214	use_minus= !use_minus;
1215
1216	if (use_minus)
1217	item_add= new (thd->mem_root) Item_func_minus (thd, src_expr, n_val);
1218	else
1219	item_add= new (thd->mem_root) Item_func_plus (thd, src_expr, n_val);
1220
1221	item_add->fix_fields(thd, &item_add);
1222	}
1223
1224	void init(READ_RECORD *info)
1225	{
1226	cursor.init(info);
1227	}
1228
1229	void pre_next_partition(ha_rows rownum)
1230	{
1231	// Save the value of FUNC(current_row)
1232	range_expr->fetch_value_from(item_add);
1233
1234	cursor.on_next_partition(rownum);
1235	end_of_partition= false;
1236	}
1237
1238	void next_partition(ha_rows rownum)
1239	{
1240	walk_till_non_peer();
1241	}
1242
1243	void pre_next_row()
1244	{
1245	if (end_of_partition)
1246	return;
1247	range_expr->fetch_value_from(item_add);
1248	}
1249
1250	void next_row()
1251	{
1252	if (end_of_partition)
1253	return;
1254	/*
1255	Ok, our cursor is at the first row R where
1256	(prev_row + n) >= R
1257	We need to check about the current row.
1258	*/
1259	walk_till_non_peer();
1260	}
1261
1262	ha_rows get_curr_rownum() const
1263	{
1264	return cursor.get_rownum();
1265	}
1266
1267	bool is_outside_computation_bounds() const
1268	{
1269	if (end_of_partition)
1270	return true;
1271	return false;
1272	}
1273
1274	private:
1275	void walk_till_non_peer()
1276	{
1277	if (cursor.fetch()) // ERROR
1278	return;
1279	// Current row is not a peer.
1280	if (order_direction * range_expr->cmp_read_only() <= `0`)
1281	return;
1282	remove_value_from_items();
1283
1284	int res;
1285	while (!(res= cursor.next()))
1286	{
1287	/ Note, no need to fetch the value explicitly here. The partition*
1288	read cursor will fetch it to check if the partition has changed.
1289	TODO(cvicentiu) make this piece of information not necessary by
1290	reimplementing Partition_read_cursor.
1291	*/
1292	if (order_direction * range_expr->cmp_read_only() <= `0`)
1293	break;
1294	remove_value_from_items();
1295	}
1296	if (res)
1297	end_of_partition= true;
1298	}
1299
1300	};
1301
1302
1303	/*
1304	Frame_range_n_bottom handles bottom end of RANGE-type frame.
1305
1306	That is, it handles frame bounds in form:
1307	RANGE BETWEEN ... AND n PRECEDING
1308	RANGE BETWEEN ... AND n FOLLOWING
1309
1310	Bottom end moves first so it needs to check for partition end
1311	(todo: unless it's PRECEDING and in that case it doesnt)
1312	(todo: factor out common parts with Frame_range_n_top into
1313	a common ancestor)
1314	*/
1315
1316	class Frame_range_n_bottom: public Frame_cursor
1317	{
1318	Partition_read_cursor cursor;
1319
1320	Cached_item_item *range_expr;
1321
1322	Item *n_val;
1323	Item *item_add;
1324
1325	const bool is_preceding;
1326
1327	bool end_of_partition;
1328
1329	/*
1330	1 when order_list uses ASC ordering
1331	-1 when order_list uses DESC ordering
1332	*/
1333	int order_direction;
1334	public:
1335	Frame_range_n_bottom(THD *thd,
1336	SQL_I_List<ORDER> *partition_list,
1337	SQL_I_List<ORDER> *order_list,
1338	bool is_preceding_arg, Item *n_val_arg) :
1339	cursor (thd, partition_list), n_val(n_val_arg), item_add(NULL),
1340	is_preceding(is_preceding_arg), added_values(false)
1341	{
1342	DBUG_ASSERT(order_list->elements == `1`);
1343	Item *src_expr= order_list->first->item[`0`];
1344
1345	if (order_list->first->direction == ORDER::ORDER_ASC)
1346	order_direction= `1`;
1347	else
1348	order_direction= -`1`;
1349
1350	range_expr= (Cached_item_item*) new_Cached_item(thd, src_expr, FALSE);
1351
1352	bool use_minus= is_preceding;
1353	if (order_direction == -`1`)
1354	use_minus= !use_minus;
1355
1356	if (use_minus)
1357	item_add= new (thd->mem_root) Item_func_minus (thd, src_expr, n_val);
1358	else
1359	item_add= new (thd->mem_root) Item_func_plus (thd, src_expr, n_val);
1360
1361	item_add->fix_fields(thd, &item_add);
1362	}
1363
1364	void init(READ_RECORD *info)
1365	{
1366	cursor.init(info);
1367	}
1368
1369	void pre_next_partition(ha_rows rownum)
1370	{
1371	// Save the value of FUNC(current_row)
1372	range_expr->fetch_value_from(item_add);
1373
1374	cursor.on_next_partition(rownum);
1375	end_of_partition= false;
1376	added_values= false;
1377	}
1378
1379	void next_partition(ha_rows rownum)
1380	{
1381	cursor.move_to(rownum);
1382	walk_till_non_peer();
1383	}
1384
1385	void pre_next_row()
1386	{
1387	if (end_of_partition)
1388	return;
1389	range_expr->fetch_value_from(item_add);
1390	}
1391
1392	void next_row()
1393	{
1394	if (end_of_partition)
1395	return;
1396	/*
1397	Ok, our cursor is at the first row R where
1398	(prev_row + n) >= R
1399	We need to check about the current row.
1400	*/
1401	walk_till_non_peer();
1402	}
1403
1404	bool is_outside_computation_bounds() const
1405	{
1406	if (!added_values)
1407	return true;
1408	return false;
1409	}
1410
1411	ha_rows get_curr_rownum() const
1412	{
1413	if (end_of_partition)
1414	return cursor.get_rownum(); // Cursor does not pass over partition bound.
1415	else
1416	return cursor.get_rownum() - `1`; // Cursor is placed on first non peer.
1417	}
1418
1419	private:
1420	bool added_values;
1421
1422	void walk_till_non_peer()
1423	{
1424	cursor.fetch();
1425	// Current row is not a peer.
1426	if (order_direction * range_expr->cmp_read_only() < `0`)
1427	return;
1428
1429	add_value_to_items(); // Add current row.
1430	added_values= true;
1431	int res;
1432	while (!(res= cursor.next()))
1433	{
1434	if (order_direction * range_expr->cmp_read_only() < `0`)
1435	break;
1436	add_value_to_items();
1437	}
1438	if (res)
1439	end_of_partition= true;
1440	}
1441	};
1442
1443
1444	/*
1445	RANGE BETWEEN ... AND CURRENT ROW, bottom frame bound for CURRENT ROW
1446	...
1447	\| peer1
1448	\| peer2 <----- current_row
1449	\| peer3
1450	+-peer4 <----- the cursor points here. peer4 itself is included.
1451	nonpeer1
1452	nonpeer2
1453
1454	This bound moves in front of the current_row. It should be a the first row
1455	that is still a peer of the current row.
1456	*/
1457
1458	class Frame_range_current_row_bottom: public Frame_cursor
1459	{
1460	Partition_read_cursor cursor;
1461
1462	Group_bound_tracker peer_tracker;
1463
1464	bool dont_move;
1465	public:
1466	Frame_range_current_row_bottom(THD *thd,
1467	SQL_I_List<ORDER> *partition_list,
1468	SQL_I_List<ORDER> *order_list) :
1469	cursor (thd, partition_list), peer_tracker (thd, order_list)
1470	{
1471	}
1472
1473	void init(READ_RECORD *info)
1474	{
1475	cursor.init(info);
1476	peer_tracker.init();
1477	}
1478
1479	void pre_next_partition(ha_rows rownum)
1480	{
1481	// Save the value of the current_row
1482	peer_tracker.check_if_next_group();
1483	cursor.on_next_partition(rownum);
1484	// Add the current row now because our cursor has already seen it
1485	add_value_to_items();
1486	}
1487
1488	void next_partition(ha_rows rownum)
1489	{
1490	walk_till_non_peer();
1491	}
1492
1493	void pre_next_row()
1494	{
1495	dont_move= !peer_tracker.check_if_next_group();
1496	}
1497
1498	void next_row()
1499	{
1500	// Check if our cursor is pointing at a peer of the current row.
1501	// If not, move forward until that becomes true
1502	if (dont_move)
1503	{
1504	/*
1505	Our current is not a peer of the current row.
1506	No need to move the bound.
1507	*/
1508	return;
1509	}
1510	walk_till_non_peer();
1511	}
1512
1513	ha_rows get_curr_rownum() const
1514	{
1515	return cursor.get_rownum();
1516	}
1517
1518	private:
1519	void walk_till_non_peer()
1520	{
1521	/*
1522	Walk forward until we've met first row that's not a peer of the current
1523	row
1524	*/
1525	while (!cursor.next())
1526	{
1527	if (peer_tracker.compare_with_cache())
1528	{
1529	cursor.prev(); // Move to our peer.
1530	break;
1531	}
1532
1533	add_value_to_items();
1534	}
1535	}
1536	};
1537
1538
1539	/*
1540	RANGE BETWEEN CURRENT ROW AND .... Top CURRENT ROW, RANGE-type frame bound
1541
1542	nonpeer1
1543	nonpeer2
1544	+-peer1 <----- the cursor points here. peer1 itself is included.
1545	\| peer2
1546	\| peer3 <----- current_row
1547	\| peer4
1548	...
1549
1550	It moves behind the current_row. It is located right after the first peer of
1551	the current_row.
1552	*/
1553
1554	class Frame_range_current_row_top : public Frame_cursor
1555	{
1556	Group_bound_tracker bound_tracker;
1557
1558	Table_read_cursor cursor;
1559	Group_bound_tracker peer_tracker;
1560
1561	bool move;
1562	public:
1563	Frame_range_current_row_top(THD *thd,
1564	SQL_I_List<ORDER> *partition_list,
1565	SQL_I_List<ORDER> *order_list) :
1566	bound_tracker (thd, partition_list), cursor (), peer_tracker (thd, order_list),
1567	move(false)
1568	{}
1569
1570	void init(READ_RECORD *info)
1571	{
1572	bound_tracker.init();
1573
1574	cursor.init(info);
1575	peer_tracker.init();
1576	}
1577
1578	void pre_next_partition(ha_rows rownum)
1579	{
1580	// Fetch the value from the first row
1581	peer_tracker.check_if_next_group();
1582	cursor.move_to(rownum);
1583	}
1584
1585	void next_partition(ha_rows rownum) {}
1586
1587	void pre_next_row()
1588	{
1589	// Check if the new current_row is a peer of the row that our cursor is
1590	// pointing to.
1591	move= peer_tracker.check_if_next_group();
1592	}
1593
1594	void next_row()
1595	{
1596	if (move)
1597	{
1598	/*
1599	Our cursor is pointing at the first row that was a peer of the previous
1600	current row. Or, it was the first row in the partition.
1601	*/
1602	if (cursor.fetch())
1603	return;
1604
1605	// todo: need the following check ?
1606	if (!peer_tracker.compare_with_cache())
1607	return;
1608	remove_value_from_items();
1609
1610	do
1611	{
1612	if (cursor.next() \|\| cursor.fetch())
1613	return;
1614	if (!peer_tracker.compare_with_cache())
1615	return;
1616	remove_value_from_items();
1617	}
1618	while (`1`);
1619	}
1620	}
1621
1622	ha_rows get_curr_rownum() const
1623	{
1624	return cursor.get_rownum();
1625	}
1626	};
1627
1628
1629	/////////////////////////////////////////////////////////////////////////////
1630	// UNBOUNDED frame bounds (shared between RANGE and ROWS)
1631	/////////////////////////////////////////////////////////////////////////////
1632
1633	/*
1634	UNBOUNDED PRECEDING frame bound
1635	*/
1636	class Frame_unbounded_preceding : public Frame_cursor
1637	{
1638	public:
1639	Frame_unbounded_preceding(THD *thd,
1640	SQL_I_List<ORDER> *partition_list,
1641	SQL_I_List<ORDER> *order_list)
1642	{}
1643
1644	void init(READ_RECORD *info) {}
1645
1646	void next_partition(ha_rows rownum)
1647	{
1648	/*
1649	UNBOUNDED PRECEDING frame end just stays on the first row of the
1650	partition. We are top of the frame, so we don't need to update the sum
1651	function.
1652	*/
1653	curr_rownum= rownum;
1654	}
1655
1656	void next_row()
1657	{
1658	/ Do nothing, UNBOUNDED PRECEDING frame end doesn't move. /
1659	}
1660
1661	ha_rows get_curr_rownum() const
1662	{
1663	return curr_rownum;
1664	}
1665
1666	private:
1667	ha_rows curr_rownum;
1668	};
1669
1670
1671	/*
1672	UNBOUNDED FOLLOWING frame bound
1673	*/
1674
1675	class Frame_unbounded_following : public Frame_cursor
1676	{
1677	protected:
1678	Partition_read_cursor cursor;
1679
1680	public:
1681	Frame_unbounded_following(THD *thd,
1682	SQL_I_List<ORDER> *partition_list,
1683	SQL_I_List<ORDER> *order_list) :
1684	cursor (thd, partition_list) {}
1685
1686	void init(READ_RECORD *info)
1687	{
1688	cursor.init(info);
1689	}
1690
1691	void pre_next_partition(ha_rows rownum)
1692	{
1693	cursor.on_next_partition(rownum);
1694	}
1695
1696	void next_partition(ha_rows rownum)
1697	{
1698	/ Activate the first row /
1699	cursor.fetch();
1700	add_value_to_items();
1701
1702	/ Walk to the end of the partition, updating the SUM function /
1703	while (!cursor.next())
1704	{
1705	add_value_to_items();
1706	}
1707	}
1708
1709	void next_row()
1710	{
1711	/ Do nothing, UNBOUNDED FOLLOWING frame end doesn't move /
1712	}
1713
1714	ha_rows get_curr_rownum() const
1715	{
1716	return cursor.get_rownum();
1717	}
1718	};
1719
1720
1721	class Frame_unbounded_following_set_count : public Frame_unbounded_following
1722	{
1723	public:
1724	Frame_unbounded_following_set_count(
1725	THD *thd,
1726	SQL_I_List<ORDER> partition_list, SQL_I_List<ORDER> order_list) :
1727	Frame_unbounded_following (thd, partition_list, order_list) {}
1728
1729	void next_partition(ha_rows rownum)
1730	{
1731	ha_rows num_rows_in_partition= `0`;
1732	if (cursor.fetch())
1733	return;
1734	num_rows_in_partition++;
1735
1736	/ Walk to the end of the partition, find how many rows there are. /
1737	while (!cursor.next())
1738	num_rows_in_partition++;
1739	set_win_funcs_row_count(num_rows_in_partition);
1740	}
1741
1742	ha_rows get_curr_rownum() const
1743	{
1744	return cursor.get_rownum();
1745	}
1746
1747	protected:
1748	void set_win_funcs_row_count(ha_rows num_rows_in_partition)
1749	{
1750	List_iterator_fast<Item_sum> it(sum_functions);
1751	Item_sum* item;
1752	while ((item= it ++))
1753	{
1754	Item_sum_window_with_row_count* item_with_row_count =
1755	static_cast<Item_sum_window_with_row_count *>(item);
1756	item_with_row_count->set_row_count(num_rows_in_partition);
1757	}
1758	}
1759	};
1760
1761	class Frame_unbounded_following_set_count_no_nulls:
1762	public Frame_unbounded_following_set_count
1763	{
1764
1765	public:
1766	Frame_unbounded_following_set_count_no_nulls(THD *thd,
1767	SQL_I_List<ORDER> *partition_list,
1768	SQL_I_List<ORDER> *order_list) :
1769	Frame_unbounded_following_set_count (thd,partition_list, order_list)
1770	{
1771	order_item= order_list->first->item[`0`];
1772	}
1773	void next_partition(ha_rows rownum)
1774	{
1775	ha_rows num_rows_in_partition= `0`;
1776	if (cursor.fetch())
1777	return;
1778
1779	/ Walk to the end of the partition, find how many rows there are. /
1780	do
1781	{
1782	if (!order_item->is_null())
1783	num_rows_in_partition++;
1784	} while (!cursor.next());
1785
1786	set_win_funcs_row_count(num_rows_in_partition);
1787	}
1788
1789	ha_rows get_curr_rownum() const
1790	{
1791	return cursor.get_rownum();
1792	}
1793
1794	private:
1795	Item* order_item;
1796	};
1797
1798	/////////////////////////////////////////////////////////////////////////////
1799	// ROWS-type frame bounds
1800	/////////////////////////////////////////////////////////////////////////////
1801	/*
1802	ROWS $n PRECEDING frame bound
1803
1804	*/
1805	class Frame_n_rows_preceding : public Frame_cursor
1806	{
1807	/ Whether this is top of the frame or bottom /
1808	const bool is_top_bound;
1809	const ha_rows n_rows;
1810
1811	/ Number of rows that we need to skip before our cursor starts moving /
1812	ha_rows n_rows_behind;
1813
1814	Table_read_cursor cursor;
1815	public:
1816	Frame_n_rows_preceding(bool is_top_bound_arg, ha_rows n_rows_arg) :
1817	is_top_bound(is_top_bound_arg), n_rows(n_rows_arg), n_rows_behind(`0`)
1818	{}
1819
1820	void init(READ_RECORD *info)
1821	{
1822	cursor.init(info);
1823	}
1824
1825	void next_partition(ha_rows rownum)
1826	{
1827	/*
1828	Position our cursor to point at the first row in the new partition
1829	(for rownum=0, it is already there, otherwise, it lags behind)
1830	*/
1831	cursor.move_to(rownum);
1832	/ Cursor is in the same spot as current row. /
1833	n_rows_behind= `0`;
1834
1835	/*
1836	Suppose the bound is ROWS 2 PRECEDING, and current row is row#n:
1837	...
1838	n-3
1839	n-2 --- bound row
1840	n-1
1841	n --- current_row
1842	...
1843	The bound should point at row #(n-2). Bounds are inclusive, so
1844	- bottom bound should add row #(n-2) into the window function
1845	- top bound should remove row (#n-3) from the window function.
1846	*/
1847	move_cursor_if_possible();
1848
1849	}
1850
1851	void next_row()
1852	{
1853	n_rows_behind++;
1854	move_cursor_if_possible();
1855	}
1856
1857	bool is_outside_computation_bounds() const
1858	{
1859	/ As a bottom boundary, rows have not yet been added. /
1860	if (!is_top_bound && n_rows - n_rows_behind)
1861	return true;
1862	return false;
1863	}
1864
1865	ha_rows get_curr_rownum() const
1866	{
1867	return cursor.get_rownum();
1868	}
1869
1870	private:
1871	void move_cursor_if_possible()
1872	{
1873	longlong rows_difference= n_rows - n_rows_behind;
1874	if (rows_difference > `0`) / We still have to wait. /
1875	return;
1876
1877	/ The cursor points to the first row in the frame. /
1878	if (rows_difference == `0`)
1879	{
1880	if (!is_top_bound)
1881	{
1882	cursor.fetch();
1883	add_value_to_items();
1884	}
1885	/ For top bound we don't have to remove anything as nothing was added. /
1886	return;
1887	}
1888
1889	/ We need to catch up by one row. /
1890	DBUG_ASSERT(rows_difference == -`1`);
1891
1892	if (is_top_bound)
1893	{
1894	cursor.fetch();
1895	remove_value_from_items();
1896	cursor.next();
1897	}
1898	else
1899	{
1900	cursor.next();
1901	cursor.fetch();
1902	add_value_to_items();
1903	}
1904	/ We've advanced one row. We are no longer behind. /
1905	n_rows_behind--;
1906	}
1907	};
1908
1909
1910	/*
1911	ROWS ... CURRENT ROW, Bottom bound.
1912
1913	This case is moved to separate class because here we don't need to maintain
1914	our own cursor, or check for partition bound.
1915	*/
1916
1917	class Frame_rows_current_row_bottom : public Frame_cursor
1918	{
1919	public:
1920
1921	Frame_rows_current_row_bottom() : curr_rownum(`0`) {}
1922
1923	void pre_next_partition(ha_rows rownum)
1924	{
1925	add_value_to_items();
1926	curr_rownum= rownum;
1927	}
1928
1929	void next_partition(ha_rows rownum) {}
1930
1931	void pre_next_row()
1932	{
1933	/ Temp table's current row is current_row. Add it to the window func /
1934	add_value_to_items();
1935	}
1936
1937	void next_row()
1938	{
1939	curr_rownum++;
1940	};
1941
1942	ha_rows get_curr_rownum() const
1943	{
1944	return curr_rownum;
1945	}
1946
1947	private:
1948	ha_rows curr_rownum;
1949	};
1950
1951
1952	/*
1953	ROWS-type CURRENT ROW, top bound.
1954
1955	This serves for processing "ROWS BETWEEN CURRENT ROW AND ..." frames.
1956
1957	n-1
1958	n --+ --- current_row, and top frame bound
1959	n+1 \|
1960	... \|
1961
1962	when the current_row moves to row #n, this frame bound should remove the
1963	row #(n-1) from the window function.
1964
1965	In other words, we need what "ROWS PRECEDING 0" provides.
1966	*/
1967	class Frame_rows_current_row_top: public Frame_n_rows_preceding
1968
1969	{
1970	public:
1971	Frame_rows_current_row_top() :
1972	Frame_n_rows_preceding (true /top/, `0` / n_rows /)
1973	{}
1974	};
1975
1976
1977	/*
1978	ROWS $n FOLLOWING frame bound.
1979	*/
1980
1981	class Frame_n_rows_following : public Frame_cursor
1982	{
1983	/ Whether this is top of the frame or bottom /
1984	const bool is_top_bound;
1985	const ha_rows n_rows;
1986
1987	Partition_read_cursor cursor;
1988	bool at_partition_end;
1989	public:
1990	Frame_n_rows_following(THD *thd,
1991	SQL_I_List<ORDER> *partition_list,
1992	SQL_I_List<ORDER> *order_list,
1993	bool is_top_bound_arg, ha_rows n_rows_arg) :
1994	is_top_bound(is_top_bound_arg), n_rows(n_rows_arg),
1995	cursor (thd, partition_list)
1996	{
1997	}
1998
1999	void init(READ_RECORD *info)
2000	{
2001	cursor.init(info);
2002	at_partition_end= false;
2003	}
2004
2005	void pre_next_partition(ha_rows rownum)
2006	{
2007	at_partition_end= false;
2008
2009	cursor.on_next_partition(rownum);
2010	}
2011
2012	/ Move our cursor to be n_rows ahead. /
2013	void next_partition(ha_rows rownum)
2014	{
2015	if (is_top_bound)
2016	next_part_top(rownum);
2017	else
2018	next_part_bottom(rownum);
2019	}
2020
2021	void next_row()
2022	{
2023	if (is_top_bound)
2024	next_row_top();
2025	else
2026	next_row_bottom();
2027	}
2028
2029	bool is_outside_computation_bounds() const
2030	{
2031	/*
2032	The top bound can go over the current partition. In this case,
2033	the sum function has 0 values added to it.
2034	*/
2035	if (at_partition_end && is_top_bound)
2036	return true;
2037	return false;
2038	}
2039
2040	ha_rows get_curr_rownum() const
2041	{
2042	return cursor.get_rownum();
2043	}
2044
2045	private:
2046	void next_part_top(ha_rows rownum)
2047	{
2048	for (ha_rows i= `0`; i < n_rows; i++)
2049	{
2050	if (cursor.fetch())
2051	break;
2052	remove_value_from_items();
2053	if (cursor.next())
2054	at_partition_end= true;
2055	}
2056	}
2057
2058	void next_part_bottom(ha_rows rownum)
2059	{
2060	if (cursor.fetch())
2061	return;
2062	add_value_to_items();
2063
2064	for (ha_rows i= `0`; i < n_rows; i++)
2065	{
2066	if (cursor.next())
2067	{
2068	at_partition_end= true;
2069	break;
2070	}
2071	add_value_to_items();
2072	}
2073	return;
2074	}
2075
2076	void next_row_top()
2077	{
2078	if (cursor.fetch()) // PART END OR FAILURE
2079	{
2080	at_partition_end= true;
2081	return;
2082	}
2083	remove_value_from_items();
2084	if (cursor.next())
2085	{
2086	at_partition_end= true;
2087	return;
2088	}
2089	}
2090
2091	void next_row_bottom()
2092	{
2093	if (at_partition_end)
2094	return;
2095
2096	if (cursor.next())
2097	{
2098	at_partition_end= true;
2099	return;
2100	}
2101
2102	add_value_to_items();
2103
2104	}
2105	};
2106
2107	/*
2108	A cursor that performs a table scan between two indices. The indices
2109	are provided by the two cursors representing the top and bottom bound
2110	of the window function's frame definition.
2111
2112	Each scan clears the sum function.
2113
2114	NOTE:
2115	The cursor does not alter the top and bottom cursors.
2116	This type of cursor is expensive computational wise. This is only to be
2117	used when the sum functions do not support removal.
2118	*/
2119	class Frame_scan_cursor : public Frame_cursor
2120	{
2121	public:
2122	Frame_scan_cursor(const Frame_cursor &top_bound,
2123	const Frame_cursor &bottom_bound) :
2124	top_bound(top_bound), bottom_bound(bottom_bound) {}
2125
2126	void init(READ_RECORD *info)
2127	{
2128	cursor.init(info);
2129	}
2130
2131	void pre_next_partition(ha_rows rownum)
2132	{
2133	/ TODO(cvicentiu) Sum functions get cleared on next partition anyway during*
2134	the window function computation algorithm. Either perform this only in
2135	cursors, or remove it from pre_next_partition.
2136	*/
2137	curr_rownum= rownum;
2138	clear_sum_functions();
2139	}
2140
2141	void next_partition(ha_rows rownum)
2142	{
2143	compute_values_for_current_row();
2144	}
2145
2146	void pre_next_row()
2147	{
2148	clear_sum_functions();
2149	}
2150
2151	void next_row()
2152	{
2153	curr_rownum++;
2154	compute_values_for_current_row();
2155	}
2156
2157	ha_rows get_curr_rownum() const
2158	{
2159	return curr_rownum;
2160	}
2161
2162	private:
2163	const Frame_cursor &top_bound;
2164	const Frame_cursor &bottom_bound;
2165	Table_read_cursor cursor;
2166	ha_rows curr_rownum;
2167
2168	/ Scan the rows between the top bound and bottom bound. Add all the values*
2169	between them, top bound row and bottom bound row inclusive. /*
2170	void compute_values_for_current_row()
2171	{
2172	if (top_bound.is_outside_computation_bounds() \|\|
2173	bottom_bound.is_outside_computation_bounds())
2174	return;
2175
2176	ha_rows start_rownum= top_bound.get_curr_rownum();
2177	ha_rows bottom_rownum= bottom_bound.get_curr_rownum();
2178	DBUG_PRINT("info", ("COMPUTING (%llu %llu)", start_rownum, bottom_rownum));
2179
2180	cursor.move_to(start_rownum);
2181
2182	for (ha_rows idx= start_rownum; idx <= bottom_rownum; idx++)
2183	{
2184	if (cursor.fetch()) //EOF
2185	break;
2186	add_value_to_items();
2187	if (cursor.next()) // EOF
2188	break;
2189	}
2190	}
2191	};
2192
2193	/ A cursor that follows a target cursor. Each time a new row is added,*
2194	the window functions are cleared and only have the row at which the target
2195	is point at added to them.
2196
2197	The window functions are cleared if the bounds or the position cursors are
2198	outside computational bounds.
2199	*/
2200	class Frame_positional_cursor : public Frame_cursor
2201	{
2202	public:
2203	Frame_positional_cursor(const Frame_cursor &position_cursor) :
2204	position_cursor(position_cursor), top_bound(NULL),
2205	bottom_bound(NULL), offset(NULL), overflowed(false),
2206	negative_offset(false) {}
2207
2208	Frame_positional_cursor(const Frame_cursor &position_cursor,
2209	const Frame_cursor &top_bound,
2210	const Frame_cursor &bottom_bound,
2211	Item &offset,
2212	bool negative_offset) :
2213	position_cursor(position_cursor), top_bound(&top_bound),
2214	bottom_bound(&bottom_bound), offset(&offset),
2215	negative_offset(negative_offset) {}
2216
2217	void init(READ_RECORD *info)
2218	{
2219	cursor.init(info);
2220	}
2221
2222	void pre_next_partition(ha_rows rownum)
2223	{
2224	/ The offset is dependant on the current row values. We can only get*
2225	* it here accurately. When fetching other rows, it changes. */
2226	save_offset_value();
2227	}
2228
2229	void next_partition(ha_rows rownum)
2230	{
2231	save_positional_value();
2232	}
2233
2234	void pre_next_row()
2235	{
2236	/ The offset is dependant on the current row values. We can only get*
2237	* it here accurately. When fetching other rows, it changes. */
2238	save_offset_value();
2239	}
2240
2241	void next_row()
2242	{
2243	save_positional_value();
2244	}
2245
2246	ha_rows get_curr_rownum() const
2247	{
2248	return position_cursor.get_curr_rownum();
2249	}
2250
2251	private:
2252	/ Check if a our position is within bounds.*
2253	* The position is passed as a parameter to avoid recalculating it. */
2254	bool position_is_within_bounds()
2255	{
2256	if (!offset)
2257	return !position_cursor.is_outside_computation_bounds();
2258
2259	if (overflowed)
2260	return false;
2261
2262	/ No valid bound to compare to. /
2263	if (position_cursor.is_outside_computation_bounds() \|\|
2264	top_bound->is_outside_computation_bounds() \|\|
2265	bottom_bound->is_outside_computation_bounds())
2266	return false;
2267
2268	/ We are over the bound. /
2269	if (position < top_bound->get_curr_rownum())
2270	return false;
2271	if (position > bottom_bound->get_curr_rownum())
2272	return false;
2273
2274	return true;
2275	}
2276
2277	/ Get the current position, accounting for the offset value, if present.*
2278	NOTE: This function does not check over/underflow.
2279	*/
2280	void get_current_position()
2281	{
2282	position = position_cursor.get_curr_rownum();
2283	overflowed= false;
2284	if (offset)
2285	{
2286	if (offset_value < `0` &&
2287	position + offset_value > position)
2288	{
2289	overflowed= true;
2290	}
2291	if (offset_value > `0` &&
2292	position + offset_value < position)
2293	{
2294	overflowed= true;
2295	}
2296	position += offset_value;
2297	}
2298	}
2299
2300	void save_offset_value()
2301	{
2302	if (offset)
2303	offset_value= offset->val_int() * (negative_offset ? -`1` : `1`);
2304	else
2305	offset_value= `0`;
2306	}
2307
2308	void save_positional_value()
2309	{
2310	get_current_position();
2311	if (!position_is_within_bounds())
2312	clear_sum_functions();
2313	else
2314	{
2315	cursor.move_to(position);
2316	cursor.fetch();
2317	add_value_to_items();
2318	}
2319	}
2320
2321	const Frame_cursor &position_cursor;
2322	const Frame_cursor *top_bound;
2323	const Frame_cursor *bottom_bound;
2324	Item *offset;
2325	Table_read_cursor cursor;
2326	ha_rows position;
2327	longlong offset_value;
2328	bool overflowed;
2329
2330	bool negative_offset;
2331	};
2332
2333
2334	/*
2335	Get a Frame_cursor for a frame bound. This is a "factory function".
2336	*/
2337	Frame_cursor get_frame_cursor(THD thd, Window_spec spec, bool* is_top_bound)
2338	{
2339	Window_frame *frame= spec->window_frame;
2340	if (!frame)
2341	{
2342	/*
2343	The docs say this about the lack of frame clause:
2344
2345	Let WD be a window structure descriptor.
2346	...
2347	If WD has no window framing clause, then
2348	Case:
2349	i) If the window ordering clause of WD is not present, then WF is the
2350	window partition of R.
2351	ii) Otherwise, WF consists of all rows of the partition of R that
2352	precede R or are peers of R in the window ordering of the window
2353	partition defined by the window ordering clause.
2354
2355	For case #ii, the frame bounds essentially are "RANGE BETWEEN UNBOUNDED
2356	PRECEDING AND CURRENT ROW".
2357	For the case #i, without ordering clause all rows are considered peers,
2358	so again the same frame bounds can be used.
2359	*/
2360	if (is_top_bound)
2361	return new Frame_unbounded_preceding (thd,
2362	spec->partition_list,
2363	spec->order_list);
2364	else
2365	return new Frame_range_current_row_bottom (thd,
2366	spec->partition_list,
2367	spec->order_list);
2368	}
2369
2370	Window_frame_bound *bound= is_top_bound? frame->top_bound :
2371	frame->bottom_bound;
2372
2373	if (bound->precedence_type == Window_frame_bound::PRECEDING \|\|
2374	bound->precedence_type == Window_frame_bound::FOLLOWING)
2375	{
2376	bool is_preceding= (bound->precedence_type ==
2377	Window_frame_bound::PRECEDING);
2378
2379	if (bound->offset == NULL) / this is UNBOUNDED /
2380	{
2381	/ The following serve both RANGE and ROWS: /
2382	if (is_preceding)
2383	return new Frame_unbounded_preceding (thd,
2384	spec->partition_list,
2385	spec->order_list);
2386
2387	return new Frame_unbounded_following (thd,
2388	spec->partition_list,
2389	spec->order_list);
2390	}
2391
2392	if (frame->units == Window_frame::UNITS_ROWS)
2393	{
2394	ha_rows n_rows= bound->offset->val_int();
2395	/ These should be handled in the parser /
2396	DBUG_ASSERT(!bound->offset->null_value);
2397	DBUG_ASSERT((longlong) n_rows >= `0`);
2398	if (is_preceding)
2399	return new Frame_n_rows_preceding (is_top_bound, n_rows);
2400
2401	return new Frame_n_rows_following (
2402	thd, spec->partition_list, spec->order_list,
2403	is_top_bound, n_rows);
2404	}
2405	else
2406	{
2407	if (is_top_bound)
2408	return new Frame_range_n_top (
2409	thd, spec->partition_list, spec->order_list,
2410	is_preceding, bound->offset);
2411
2412	return new Frame_range_n_bottom (thd,
2413	spec->partition_list, spec->order_list,
2414	is_preceding, bound->offset);
2415	}
2416	}
2417
2418	if (bound->precedence_type == Window_frame_bound::CURRENT)
2419	{
2420	if (frame->units == Window_frame::UNITS_ROWS)
2421	{
2422	if (is_top_bound)
2423	return new Frame_rows_current_row_top;
2424
2425	return new Frame_rows_current_row_bottom;
2426	}
2427	else
2428	{
2429	if (is_top_bound)
2430	return new Frame_range_current_row_top (
2431	thd, spec->partition_list, spec->order_list);
2432
2433	return new Frame_range_current_row_bottom (
2434	thd, spec->partition_list, spec->order_list);
2435	}
2436	}
2437	return NULL;
2438	}
2439
2440	static
2441	void add_special_frame_cursors(THD thd, Cursor_manager cursor_manager,
2442	Item_window_func *window_func)
2443	{
2444	Window_spec *spec= window_func->window_spec;
2445	Item_sum *item_sum= window_func->window_func();
2446	DBUG_PRINT("info", ("Get arg count: %d", item_sum->get_arg_count()));
2447	Frame_cursor *fc;
2448	switch (item_sum->sum_func())
2449	{
2450	case Item_sum::CUME_DIST_FUNC:
2451	fc= new Frame_unbounded_preceding (thd,
2452	spec->partition_list,
2453	spec->order_list);
2454	fc->add_sum_func(item_sum);
2455	cursor_manager->add_cursor(fc);
2456	fc= new Frame_range_current_row_bottom (thd,
2457	spec->partition_list,
2458	spec->order_list);
2459	fc->add_sum_func(item_sum);
2460	cursor_manager->add_cursor(fc);
2461	break;
2462	case Item_sum::LEAD_FUNC:
2463	case Item_sum::LAG_FUNC:
2464	{
2465	Frame_cursor bottom_bound= new* Frame_unbounded_following (thd,
2466	spec->partition_list,
2467	spec->order_list);
2468	Frame_cursor top_bound= new* Frame_unbounded_preceding (thd,
2469	spec->partition_list,
2470	spec->order_list);
2471	Frame_cursor current_row_pos= new* Frame_rows_current_row_bottom;
2472	cursor_manager->add_cursor(bottom_bound);
2473	cursor_manager->add_cursor(top_bound);
2474	cursor_manager->add_cursor(current_row_pos);
2475	DBUG_ASSERT(item_sum->fixed);
2476	bool negative_offset= item_sum->sum_func() == Item_sum::LAG_FUNC;
2477	fc= new Frame_positional_cursor (*current_row_pos,
2478	top_bound, bottom_bound,
2479	*item_sum->get_arg(`1`),
2480	negative_offset);
2481	fc->add_sum_func(item_sum);
2482	cursor_manager->add_cursor(fc);
2483	break;
2484	}
2485	case Item_sum::FIRST_VALUE_FUNC:
2486	{
2487	Frame_cursor bottom_bound= get_frame_cursor(thd, spec, false*);
2488	Frame_cursor top_bound= get_frame_cursor(thd, spec, true*);
2489	cursor_manager->add_cursor(bottom_bound);
2490	cursor_manager->add_cursor(top_bound);
2491	DBUG_ASSERT(item_sum->fixed);
2492	Item offset_item= new* (thd->mem_root) Item_int (thd, `0`);
2493	offset_item->fix_fields(thd, &offset_item);
2494	fc= new Frame_positional_cursor (*top_bound,
2495	top_bound, bottom_bound,
2496	offset_item, false*);
2497	fc->add_sum_func(item_sum);
2498	cursor_manager->add_cursor(fc);
2499	break;
2500	}
2501	case Item_sum::LAST_VALUE_FUNC:
2502	{
2503	Frame_cursor bottom_bound= get_frame_cursor(thd, spec, false*);
2504	Frame_cursor top_bound= get_frame_cursor(thd, spec, true*);
2505	cursor_manager->add_cursor(bottom_bound);
2506	cursor_manager->add_cursor(top_bound);
2507	DBUG_ASSERT(item_sum->fixed);
2508	Item offset_item= new* (thd->mem_root) Item_int (thd, `0`);
2509	offset_item->fix_fields(thd, &offset_item);
2510	fc= new Frame_positional_cursor (*bottom_bound,
2511	top_bound, bottom_bound,
2512	offset_item, false*);
2513	fc->add_sum_func(item_sum);
2514	cursor_manager->add_cursor(fc);
2515	break;
2516	}
2517	case Item_sum::NTH_VALUE_FUNC:
2518	{
2519	Frame_cursor bottom_bound= get_frame_cursor(thd, spec, false*);
2520	Frame_cursor top_bound= get_frame_cursor(thd, spec, true*);
2521	cursor_manager->add_cursor(bottom_bound);
2522	cursor_manager->add_cursor(top_bound);
2523	DBUG_ASSERT(item_sum->fixed);
2524	Item int_item= new* (thd->mem_root) Item_int (thd, `1`);
2525	Item offset_func= new* (thd->mem_root)
2526	Item_func_minus (thd, item_sum->get_arg(`1`),
2527	int_item);
2528	offset_func->fix_fields(thd, &offset_func);
2529	fc= new Frame_positional_cursor (*top_bound,
2530	top_bound, bottom_bound,
2531	offset_func, false*);
2532	fc->add_sum_func(item_sum);
2533	cursor_manager->add_cursor(fc);
2534	break;
2535	}
2536	case Item_sum::PERCENTILE_CONT_FUNC:
2537	case Item_sum::PERCENTILE_DISC_FUNC:
2538	{
2539	fc= new Frame_unbounded_preceding (thd,
2540	spec->partition_list,
2541	spec->order_list);
2542	fc->add_sum_func(item_sum);
2543	cursor_manager->add_cursor(fc);
2544	fc= new Frame_unbounded_following (thd,
2545	spec->partition_list,
2546	spec->order_list);
2547	fc->add_sum_func(item_sum);
2548	cursor_manager->add_cursor(fc);
2549	break;
2550	}
2551	default:
2552	fc= new Frame_unbounded_preceding (
2553	thd, spec->partition_list, spec->order_list);
2554	fc->add_sum_func(item_sum);
2555	cursor_manager->add_cursor(fc);
2556
2557	fc= new Frame_rows_current_row_bottom;
2558	fc->add_sum_func(item_sum);
2559	cursor_manager->add_cursor(fc);
2560	}
2561	}
2562
2563
2564	static bool is_computed_with_remove(Item_sum::Sumfunctype sum_func)
2565	{
2566	switch (sum_func)
2567	{
2568	case Item_sum::CUME_DIST_FUNC:
2569	case Item_sum::ROW_NUMBER_FUNC:
2570	case Item_sum::RANK_FUNC:
2571	case Item_sum::DENSE_RANK_FUNC:
2572	case Item_sum::NTILE_FUNC:
2573	case Item_sum::FIRST_VALUE_FUNC:
2574	case Item_sum::LAST_VALUE_FUNC:
2575	case Item_sum::PERCENTILE_CONT_FUNC:
2576	case Item_sum::PERCENTILE_DISC_FUNC:
2577	return false;
2578	default:
2579	return true;
2580	}
2581	}
2582	/*
2583	Create required frame cursors for the list of window functions.
2584	Register all functions to their appropriate cursors.
2585	If the window functions share the same frame specification,
2586	those window functions will be registered to the same cursor.
2587	*/
2588	void get_window_functions_required_cursors(
2589	THD *thd,
2590	List<Item_window_func>& window_functions,
2591	List<Cursor_manager> *cursor_managers)
2592	{
2593	List_iterator_fast<Item_window_func> it(window_functions);
2594	Item_window_func* item_win_func;
2595	Item_sum *sum_func;
2596	while ((item_win_func= it ++))
2597	{
2598	Cursor_manager cursor_manager = new* Cursor_manager ();
2599	sum_func = item_win_func->window_func();
2600	Frame_cursor *fc;
2601	/*
2602	Some window functions require the partition size for computing values.
2603	Add a cursor that retrieves it as the first one in the list if necessary.
2604	*/
2605	if (item_win_func->requires_partition_size())
2606	{
2607	if (item_win_func->only_single_element_order_list())
2608	{
2609	fc= new Frame_unbounded_following_set_count_no_nulls (thd,
2610	item_win_func->window_spec->partition_list,
2611	item_win_func->window_spec->order_list);
2612	}
2613	else
2614	{
2615	fc= new Frame_unbounded_following_set_count (thd,
2616	item_win_func->window_spec->partition_list,
2617	item_win_func->window_spec->order_list);
2618	}
2619	fc->add_sum_func(sum_func);
2620	cursor_manager->add_cursor(fc);
2621	}
2622
2623	/*
2624	If it is not a regular window function that follows frame specifications,
2625	and/or specific cursors are required. ROW_NUM, RANK, NTILE and others
2626	follow such rules. Check is_frame_prohibited check for the full list.
2627
2628	TODO(cvicentiu) This approach is messy. Every time a function allows
2629	computation in a certain way, we have to add an extra method to this
2630	factory function. It is better to have window functions output
2631	their own cursors, as needed. This way, the logic is bound
2632	only to the implementation of said window function. Regular aggregate
2633	functions can keep the default frame generating code, overwrite it or
2634	add to it.
2635	*/
2636	if (item_win_func->is_frame_prohibited() \|\|
2637	item_win_func->requires_special_cursors())
2638	{
2639	add_special_frame_cursors(thd, cursor_manager, item_win_func);
2640	cursor_managers->push_back(cursor_manager);
2641	continue;
2642	}
2643
2644	Frame_cursor *frame_bottom= get_frame_cursor(thd,
2645	item_win_func->window_spec, false);
2646	Frame_cursor *frame_top= get_frame_cursor(thd,
2647	item_win_func->window_spec, true);
2648
2649	frame_bottom->add_sum_func(sum_func);
2650	frame_top->add_sum_func(sum_func);
2651
2652	/*
2653	The order of these cursors is important. A sum function
2654	must first add values (via frame_bottom) then remove them via
2655	frame_top. Removing items first doesn't make sense in the case of all
2656	window functions.
2657	*/
2658	cursor_manager->add_cursor(frame_bottom);
2659	cursor_manager->add_cursor(frame_top);
2660	if (is_computed_with_remove(sum_func->sum_func()) &&
2661	!sum_func->supports_removal())
2662	{
2663	frame_bottom->set_no_action();
2664	frame_top->set_no_action();
2665	Frame_cursor scan_cursor= new* Frame_scan_cursor (*frame_top,
2666	*frame_bottom);
2667	scan_cursor->add_sum_func(sum_func);
2668	cursor_manager->add_cursor(scan_cursor);
2669
2670	}
2671	cursor_managers->push_back(cursor_manager);
2672	}
2673	}
2674
2675	/**
2676	Helper function that takes a list of window functions and writes
2677	their values in the current table record.
2678	*/
2679	static
2680	bool save_window_function_values(List<Item_window_func>& window_functions,
2681	TABLE tbl, uchar rowid_buf)
2682	{
2683	List_iterator_fast<Item_window_func> iter(window_functions);
2684	tbl->file->ha_rnd_pos(tbl->record[`0`], rowid_buf);
2685	store_record(tbl, record[`1`]);
2686	while (Item_window_func *item_win= iter ++)
2687	item_win->save_in_field(item_win->result_field, true);
2688
2689	int err= tbl->file->ha_update_row(tbl->record[`1`], tbl->record[`0`]);
2690	if (err && err != HA_ERR_RECORD_IS_THE_SAME)
2691	return true;
2692
2693	return false;
2694	}
2695
2696	/*
2697	TODO(cvicentiu) update this comment to reflect the new execution.
2698
2699	Streamed window function computation with window frames.
2700
2701	We make a single pass over the ordered temp.table, but we're using three
2702	cursors:
2703	- current row - the row that we're computing window func value for)
2704	- start_bound - the start of the frame
2705	- bottom_bound - the end of the frame
2706
2707	All three cursors move together.
2708
2709	@todo
2710	Provided bounds have their 'cursors'... is it better to re-clone their
2711	cursors or re-position them onto the current row?
2712
2713	@detail
2714	ROWS BETWEEN 3 PRECEDING -- frame start
2715	AND 3 FOLLOWING -- frame end
2716
2717	/------ frame end (aka BOTTOM)
2718	Dataset start \|
2719	--------===========[]================-------->> dataset end*
2720	\| \
2721	\| +-------- current row
2722	\|
2723	\-------- frame start ("TOP")
2724
2725	- frame_end moves forward and adds rows into the aggregate function.
2726	- frame_start follows behind and removes rows from the aggregate function.
2727	- current_row is the row where the value of aggregate function is stored.
2728
2729	@TODO: Only the first cursor needs to check for run-out-of-partition
2730	condition (Others can catch up by counting rows?)
2731
2732	*/
2733	bool compute_window_func(THD *thd,
2734	List<Item_window_func>& window_functions,
2735	List<Cursor_manager>& cursor_managers,
2736	TABLE *tbl,
2737	SORT_INFO *filesort_result)
2738	{
2739	List_iterator_fast<Item_window_func> iter_win_funcs(window_functions);
2740	List_iterator_fast<Cursor_manager> iter_cursor_managers(cursor_managers);
2741	uint err;
2742
2743	READ_RECORD info;
2744
2745	if (init_read_record(&info, current_thd, tbl, NULL/select/, filesort_result,
2746	`0`, `1`, FALSE))
2747	return true;
2748
2749	Cursor_manager *cursor_manager;
2750	while ((cursor_manager= iter_cursor_managers ++))
2751	cursor_manager->initialize_cursors(&info);
2752
2753	/ One partition tracker for each window function. /
2754	List<Group_bound_tracker> partition_trackers;
2755	Item_window_func *win_func;
2756	while ((win_func= iter_win_funcs ++))
2757	{
2758	Group_bound_tracker tracker= new* Group_bound_tracker (thd,
2759	win_func->window_spec->partition_list);
2760	// TODO(cvicentiu) This should be removed and placed in constructor.
2761	tracker->init();
2762	partition_trackers.push_back(tracker);
2763	}
2764
2765	List_iterator_fast<Group_bound_tracker> iter_part_trackers(partition_trackers);
2766	ha_rows rownum= `0`;
2767	uchar rowid_buf= (uchar) my_malloc(tbl->file->ref_length, MYF(`0`));
2768
2769	while (true)
2770	{
2771	if ((err= info.read_record()))
2772	break; // End of file.
2773
2774	/ Remember current row so that we can restore it before computing*
2775	each window function. /*
2776	tbl->file->position(tbl->record[`0`]);
2777	memcpy(rowid_buf, tbl->file->ref, tbl->file->ref_length);
2778
2779	iter_win_funcs.rewind();
2780	iter_part_trackers.rewind();
2781	iter_cursor_managers.rewind();
2782
2783	Group_bound_tracker *tracker;
2784	while ((win_func= iter_win_funcs ++) &&
2785	(tracker= iter_part_trackers ++) &&
2786	(cursor_manager= iter_cursor_managers ++))
2787	{
2788	if (tracker->check_if_next_group() \|\| (rownum == `0`))
2789	{
2790	/ TODO(cvicentiu)*
2791	Clearing window functions should happen through cursors. /*
2792	win_func->window_func()->clear();
2793	cursor_manager->notify_cursors_partition_changed(rownum);
2794	}
2795	else
2796	{
2797	cursor_manager->notify_cursors_next_row();
2798	}
2799
2800	/ Check if we found any error in the window function while adding values*
2801	through cursors. /*
2802	if (unlikely(thd->is_error() \|\| thd->is_killed()))
2803	break;
2804
2805
2806	/ Return to current row after notifying cursors for each window*
2807	function. /*
2808	tbl->file->ha_rnd_pos(tbl->record[`0`], rowid_buf);
2809	}
2810
2811	/ We now have computed values for each window function. They can now*
2812	be saved in the current row. /*
2813	save_window_function_values(window_functions, tbl, rowid_buf);
2814
2815	rownum++;
2816	}
2817
2818	my_free(rowid_buf);
2819	partition_trackers.delete_elements();
2820	end_read_record(&info);
2821
2822	return false;
2823	}
2824
2825	/ Make a list that is a concation of two lists of ORDER elements /
2826
2827	static ORDER* concat_order_lists(MEM_ROOT mem_root, ORDER list1, ORDER *list2)
2828	{
2829	if (!list1)
2830	{
2831	list1= list2;
2832	list2= NULL;
2833	}
2834
2835	ORDER res= NULL; // first element in the new list*
2836	ORDER prev= NULL; // last element in the new list*
2837	ORDER cur_list= list1; // this goes through list1, list2*
2838	while (cur_list)
2839	{
2840	for (ORDER *cur= cur_list; cur; cur= cur->next)
2841	{
2842	ORDER copy= (ORDER)alloc_root(mem_root, sizeof(ORDER));
2843	memcpy(copy, cur, sizeof(ORDER));
2844	if (prev)
2845	prev->next= copy;
2846	prev= copy;
2847	if (!res)
2848	res= copy;
2849	}
2850
2851	cur_list= (cur_list == list1)? list2: NULL;
2852	}
2853
2854	if (prev)
2855	prev->next= NULL;
2856
2857	return res;
2858	}
2859
2860	bool Window_func_runner::add_function_to_run(Item_window_func *win_func)
2861	{
2862
2863	Item_sum *sum_func= win_func->window_func();
2864	sum_func->setup_window_func(current_thd, win_func->window_spec);
2865
2866	Item_sum::Sumfunctype type= win_func->window_func()->sum_func();
2867
2868	switch (type)
2869	{
2870	/ Distinct is not yet supported. /
2871	case Item_sum::GROUP_CONCAT_FUNC:
2872	my_error(ER_NOT_SUPPORTED_YET, MYF(`0`),
2873	"GROUP_CONCAT() aggregate as window function");
2874	return true;
2875	case Item_sum::SUM_DISTINCT_FUNC:
2876	my_error(ER_NOT_SUPPORTED_YET, MYF(`0`),
2877	"SUM(DISTINCT) aggregate as window function");
2878	return true;
2879	case Item_sum::AVG_DISTINCT_FUNC:
2880	my_error(ER_NOT_SUPPORTED_YET, MYF(`0`),
2881	"AVG(DISTINCT) aggregate as window function");
2882	return true;
2883	case Item_sum::COUNT_DISTINCT_FUNC:
2884	my_error(ER_NOT_SUPPORTED_YET, MYF(`0`),
2885	"COUNT(DISTINCT) aggregate as window function");
2886	return true;
2887	default:
2888	break;
2889	}
2890
2891	return window_functions.push_back(win_func);
2892	}
2893
2894
2895	/*
2896	Compute the value of window function for all rows.
2897	*/
2898	bool Window_func_runner::exec(THD thd, TABLE tbl, SORT_INFO *filesort_result)
2899	{
2900	List_iterator_fast<Item_window_func> it(window_functions);
2901	Item_window_func *win_func;
2902	while ((win_func= it ++))
2903	{
2904	win_func->set_phase_to_computation();
2905	// TODO(cvicentiu) Setting the aggregator should probably be done during
2906	// setup of Window_funcs_sort.
2907	win_func->window_func()->set_aggregator(Aggregator::SIMPLE_AGGREGATOR);
2908	}
2909	it.rewind();
2910
2911	List<Cursor_manager> cursor_managers;
2912	get_window_functions_required_cursors(thd, window_functions,
2913	&cursor_managers);
2914
2915	/ Go through the sorted array and compute the window function /
2916	bool is_error= compute_window_func(thd,
2917	window_functions,
2918	cursor_managers,
2919	tbl, filesort_result);
2920	while ((win_func= it ++))
2921	{
2922	win_func->set_phase_to_retrieval();
2923	}
2924
2925	cursor_managers.delete_elements();
2926
2927	return is_error;
2928	}
2929
2930
2931	bool Window_funcs_sort::exec(JOIN *join)
2932	{
2933	THD *thd= join->thd;
2934	JOIN_TAB *join_tab= join->join_tab + join->total_join_tab_cnt();
2935
2936	/ Sort the table based on the most specific sorting criteria of*
2937	the window functions. /*
2938	if (create_sort_index(thd, join, join_tab, filesort))
2939	return true;
2940
2941	TABLE *tbl= join_tab->table;
2942	SORT_INFO *filesort_result= join_tab->filesort_result;
2943
2944	bool is_error= runner.exec(thd, tbl, filesort_result);
2945
2946	delete join_tab->filesort_result;
2947	join_tab->filesort_result= NULL;
2948	return is_error;
2949	}
2950
2951
2952	bool Window_funcs_sort::setup(THD thd, SQL_SELECT sel,
2953	List_iterator<Item_window_func> &it,
2954	JOIN_TAB *join_tab)
2955	{
2956	Window_spec *spec;
2957	Item_window_func *win_func= it.peek();
2958	Item_window_func *win_func_with_longest_order= NULL;
2959	int longest_order_elements= -`1`;
2960
2961	/ The iterator should point to a valid function at the start of execution. /
2962	DBUG_ASSERT(win_func);
2963	do
2964	{
2965	spec= win_func->window_spec;
2966	int win_func_order_elements= spec->partition_list->elements +
2967	spec->order_list->elements;
2968	if (win_func_order_elements > longest_order_elements)
2969	{
2970	win_func_with_longest_order= win_func;
2971	longest_order_elements= win_func_order_elements;
2972	}
2973	if (runner.add_function_to_run(win_func))
2974	return true;
2975	it ++;
2976	win_func= it.peek();
2977	} while (win_func && !(win_func->marker & SORTORDER_CHANGE_FLAG));
2978
2979	/*
2980	The sort criteria must be taken from the last win_func in the group of
2981	adjacent win_funcs that do not have SORTORDER_CHANGE_FLAG. This is
2982	because the sort order must be the most specific sorting criteria defined
2983	within the window function group. This ensures that we sort the table
2984	in a way that the result is valid for all window functions belonging to
2985	this Window_funcs_sort.
2986	*/
2987	spec= win_func_with_longest_order->window_spec;
2988
2989	ORDER* sort_order= concat_order_lists(thd->mem_root,
2990	spec->partition_list->first,
2991	spec->order_list->first);
2992	if (sort_order == NULL) // No partition or order by clause.
2993	{
2994	/ TODO(cvicentiu) This is used as a way to allow an empty OVER ()*
2995	clause for window functions. However, a better approach is
2996	to not call Filesort at all in this case and just read whatever order
2997	the temporary table has.
2998	Due to cursors not working for out_of_memory cases (yet!), we have to run
2999	filesort to generate a sort buffer of the results.
3000	In this case we sort by the first field of the temporary table.
3001	We should have this field available, even if it is a window_function
3002	field. We don't care of the particular sorting result in this case.
3003	*/
3004	ORDER order= (ORDER )alloc_root(thd->mem_root, sizeof(ORDER));
3005	memset(order, `0`, sizeof(*order));
3006	Item item= new* (thd->mem_root) Item_field (thd, join_tab->table->field[`0`]);
3007	order->item= (Item *)alloc_root(thd->mem_root, `2` sizeof(Item *));
3008	order->item[`1`]= NULL;
3009	order->item[`0`]= item;
3010	order->field= join_tab->table->field[`0`];
3011	sort_order= order;
3012	}
3013	filesort= new (thd->mem_root) Filesort (sort_order, HA_POS_ERROR, true, NULL);
3014
3015	/ Apply the same condition that the subsequent sort has. /
3016	filesort->select= sel;
3017
3018	return false;
3019	}
3020
3021
3022	bool Window_funcs_computation::setup(THD *thd,
3023	List<Item_window_func> *window_funcs,
3024	JOIN_TAB *tab)
3025	{
3026	order_window_funcs_by_window_specs(window_funcs);
3027
3028	SQL_SELECT *sel= NULL;
3029	/*
3030	If the tmp table is filtered during sorting
3031	(ex: SELECT with HAVING && ORDER BY), we must make sure to keep the
3032	filtering conditions when we perform sorting for window function
3033	computation.
3034	*/
3035	if (tab->filesort && tab->filesort->select)
3036	{
3037	sel= tab->filesort->select;
3038	DBUG_ASSERT(!sel->quick);
3039	}
3040
3041	Window_funcs_sort *srt;
3042	List_iterator<Item_window_func> iter(*window_funcs);
3043	while (iter.peek())
3044	{
3045	if (!(srt= new Window_funcs_sort ()) \|\|
3046	srt->setup(thd, sel, iter, tab))
3047	{
3048	return true;
3049	}
3050	win_func_sorts.push_back(srt, thd->mem_root);
3051	}
3052	return false;
3053	}
3054
3055
3056	bool Window_funcs_computation::exec(JOIN *join)
3057	{
3058	List_iterator<Window_funcs_sort> it(win_func_sorts);
3059	Window_funcs_sort *srt;
3060	/ Execute each sort /
3061	while ((srt = it ++))
3062	{
3063	if (srt->exec(join))
3064	return true;
3065	}
3066	return false;
3067	}
3068
3069
3070	void Window_funcs_computation::cleanup()
3071	{
3072	List_iterator<Window_funcs_sort> it(win_func_sorts);
3073	Window_funcs_sort *srt;
3074	while ((srt = it ++))
3075	{
3076	srt->cleanup();
3077	delete srt;
3078	}
3079	}
3080
3081
3082	Explain_aggr_window_funcs*
3083	Window_funcs_computation::save_explain_plan(MEM_ROOT *mem_root,
3084	bool is_analyze)
3085	{
3086	Explain_aggr_window_funcs xpl= new* Explain_aggr_window_funcs;
3087	List_iterator<Window_funcs_sort> it(win_func_sorts);
3088	Window_funcs_sort *srt;
3089	if (!xpl)
3090	return `0`;
3091	while ((srt = it ++))
3092	{
3093	Explain_aggr_filesort *eaf=
3094	new Explain_aggr_filesort (mem_root, is_analyze, srt->filesort);
3095	if (!eaf)
3096	return `0`;
3097	xpl->sorts.push_back(eaf, mem_root);
3098	}
3099	return xpl;
3100	}
3101
3102	/////////////////////////////////////////////////////////////////////////////
3103	// Unneeded comments (will be removed when we develop a replacement for
3104	// the feature that was attempted here
3105	/////////////////////////////////////////////////////////////////////////////
3106	/*
3107	TODO Get this code to set can_compute_window_function during preparation,
3108	not during execution.
3109
3110	The reason for this is the following:
3111	Our single scan optimization for window functions without tmp table,
3112	is valid, if and only if, we only need to perform one sorting operation,
3113	via filesort. The cases where we need to perform one sorting operation only:
3114
3115	* A select with only one window function.
3116	* A select with multiple window functions, but they must have their
3117	partition and order by clauses compatible. This means that one ordering
3118	is acceptable for both window functions.
3119
3120	For example:
3121	partition by a, b, c; order by d, e results in sorting by a b c d e.
3122	partition by a; order by d results in sorting by a d.
3123
3124	This kind of sorting is compatible. The less specific partition does
3125	not care for the order of b and c columns so it is valid if we sort
3126	by those in case of equality over a.
3127
3128	partition by a, b; order by d, e results in sorting by a b d e
3129	partition by a; order by e results in sorting by a e
3130
3131	This sorting is incompatible due to the order by clause. The partition by
3132	clause is compatible, (partition by a) is a prefix for (partition by a, b)
3133	However, order by e is not a prefix for order by d, e, thus it is not
3134	compatible.
3135
3136	The rule for having compatible sorting is thus:
3137	Each partition order must contain the other window functions partitions
3138	prefixes, or be a prefix itself. This must hold true for all partitions.
3139	Analog for the order by clause.
3140	*/
3141	#if 0
3142	List<Item_window_func> window_functions;
3143	SQL_I_List<ORDER> largest_partition;
3144	SQL_I_List<ORDER> largest_order_by;
3145	bool can_compute_window_live = !need_tmp;
3146	// Construct the window_functions item list and check if they can be
3147	// computed using only one sorting.
3148	//
3149	// TODO: Perhaps group functions into compatible sorting bins
3150	// to minimize the number of sorting passes required to compute all of them.
3151	while ((item= it++))
3152	{
3153	if (item->type() == Item::WINDOW_FUNC_ITEM)
3154	{
3155	Item_window_func item_win = (Item_window_func ) item;
3156	window_functions.push_back(item_win);
3157	if (!can_compute_window_live)
3158	continue; // No point checking since we have to perform multiple sorts.
3159	Window_spec *spec = item_win->window_spec;
3160	// Having an empty partition list on one window function and a
3161	// not empty list on a separate window function causes the sorting
3162	// to be incompatible.
3163	//
3164	// Example:
3165	// over (partition by a, order by x) && over (order by x).
3166	//
3167	// The first function requires an ordering by a first and then by x,
3168	// while the seond function requires an ordering by x first.
3169	// The same restriction is not required for the order by clause.
3170	if (largest_partition.elements && !spec->partition_list.elements)
3171	{
3172	can_compute_window_live= FALSE;
3173	continue;
3174	}
3175	can_compute_window_live= test_if_order_compatible(largest_partition,
3176	spec->partition_list);
3177	if (!can_compute_window_live)
3178	continue;
3179
3180	can_compute_window_live= test_if_order_compatible(largest_order_by,
3181	spec->order_list);
3182	if (!can_compute_window_live)
3183	continue;
3184
3185	if (largest_partition.elements < spec->partition_list.elements)
3186	largest_partition = spec->partition_list;
3187	if (largest_order_by.elements < spec->order_list.elements)
3188	largest_order_by = spec->order_list;
3189	}
3190	}
3191	if (can_compute_window_live && window_functions.elements && table_count == `1`)
3192	{
3193	ha_rows examined_rows = `0`;
3194	ha_rows found_rows = `0`;
3195	ha_rows filesort_retval;
3196	SORT_FIELD s_order= (SORT_FIELD ) my_malloc(sizeof(SORT_FIELD) *
3197	(largest_partition.elements + largest_order_by.elements) + `1`,
3198	MYF(MY_WME \| MY_ZEROFILL \| MY_THREAD_SPECIFIC));
3199
3200	size_t pos= `0`;
3201	for (ORDER* curr = largest_partition.first; curr; curr=curr->next, pos++)
3202	s_order[pos].item = *curr->item;
3203
3204	for (ORDER* curr = largest_order_by.first; curr; curr=curr->next, pos++)
3205	s_order[pos].item = *curr->item;
3206
3207	table[`0`]->sort.io_cache=(IO_CACHE) my_malloc(sizeof*(IO_CACHE),
3208	MYF(MY_WME \| MY_ZEROFILL\|
3209	MY_THREAD_SPECIFIC));
3210
3211
3212	filesort_retval= filesort(thd, table[`0`], s_order,
3213	(largest_partition.elements + largest_order_by.elements),
3214	this->select, HA_POS_ERROR, FALSE,
3215	&examined_rows, &found_rows,
3216	this->explain->ops_tracker.report_sorting(thd));
3217	table[`0`]->sort.found_records= filesort_retval;
3218
3219	join_tab->read_first_record = join_init_read_record;
3220	join_tab->records= found_rows;
3221
3222	my_free(s_order);
3223	}
3224	else
3225	#endif
3226

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