Query term tree structure. More...

#include <query_term.h>

Inheritance diagram for Query_term:

Public Member Functions
Query_term *	pushdown_limit_order_by (Query_term_set_op *parent=nullptr)
	Called after contextualization to simplify query, c.f. More...

bool	validate_structure (const Query_term *parent, int depth=0) const
	Return true if structure is too deep, i.e. More...

std::pair< bool, bool >	redundant_order_by (Query_block *block, int level)
	Determine if we have a redundant ORDER BY in block. More...

virtual Query_term_type	term_type () const =0
	Get the node tree type. More...

virtual const char *	operator_string () const =0
	Get the node type description. More...

virtual	~Query_term ()=default
	Node destructor. More...

virtual size_t	child_count () const
	Get the number of children this node has. More...

virtual bool	prepare_query_term (THD thd, Query_expression qe, Change_current_query_block save_query_block, mem_root_deque< Item > insert_field_list, Query_result common_result, ulonglong added_options, ulonglong removed_options, ulonglong create_options)=0
	a) Prepare query blocks, both leaf blocks and blocks reresenting order by/limit in query primaries with parentesized query expression body with order by clause and/or limit/offset clause (unary query terms). More...

virtual bool	optimize_query_term (THD thd, Query_expression qe)=0
	Optimize the non-leaf query blocks. More...

virtual AccessPath *	make_set_op_access_path (THD thd, Query_term_set_op parent, Mem_root_array< AppendPathParameters > *union_all_subpaths, bool calc_found_rows)=0
	Recursively constructs the access path of the set operation, possibly materializing in a tmp table if needed, cf. More...

virtual void	label_children ()=0
	Set the correct value of `Query_term::m_sibling_idx` recursively for set operations. More...

bool	create_tmp_table (THD *thd, ulonglong create_options)
	Create a temporary table for a set operation. More...

virtual VisibleFieldsIterator	types_iterator ()=0
	Abstract over visible column types: if query block, we offer an iterator over visible fields, for binary set operators we offer an iterator over `m_types`, for unary we just call the child's. More...

virtual size_t	visible_column_count () const =0
	Return the number of visible columns of the query term. More...

Query_term_set_op *	parent () const
	Getter for `m_parent`, q.v. More...

void	set_sibling_idx (uint idx)
	Setter for `m_sibling_idx`, q.v. More...

uint	sibling_idx ()
	Getter for `m_sibling_idx`, q.v. More...

virtual void	cleanup (bool full)
	Reset resources used. More...

virtual void	destroy_tree ()=0
	Destroy the query term tree structure. More...

virtual bool	open_result_tables (THD *thd, int level)
	Open tmp tables for the tree of set operation query results, by recursing. More...

virtual mem_root_deque< Item * > *	types_array ()=0

virtual void	debugPrint (int level, std::ostringstream &buf) const =0
	Print the tree rooted at this node to buf. More...

void	printPointers (std::ostringstream &buf) const
	Print the pointer of this node and its parent to buf. More...

virtual Query_block *	query_block () const =0
	The query_block which holds the ORDER BY and LIMIT information for this set operation. More...

void	set_setop_query_result (Query_result *rs)
	Setter for m_setop_query_result, q.v. More...

Query_result *	setop_query_result ()
	Getter for m_setop_query_result, q.v. More...

Query_result_union *	setop_query_result_union ()
	Getter for m_setop_query_result, q.v. Use only if we can down cast. More...

void	cleanup_query_result (bool full)
	Cleanup m_setop_query_result, q.v. More...

void	set_owning_operand ()
	Setter for m_owning_operand, q.v. More...

bool	owning_operand ()
	Getter for m_owning_operand, q.v. More...

void	set_result_table (Table_ref *tl)
	Setter for m_result_table, q.v. More...

Table_ref &	result_table ()
	Getter for m_result_table, q.v. More...

void	set_fields (mem_root_deque< Item * > *fields)

mem_root_deque< Item * > *	fields ()

Static Public Member Functions
static void	indent (int level, std::ostringstream &buf)
	Print blank space indentation (unit: two) to buf according to level. More...

static void	print_order (const THD thd, String str, ORDER *ord, enum_query_type query_type)
	Print into str the order indicated in ord, using standard print_for_order Used by traditional explain. More...

Protected Attributes
Query_term_set_op *	m_parent {nullptr}
	Back pointer to the node whose child we are, or nullptr (root term). More...

uint	m_sibling_idx {0}
	If parent is non-null, this holds the index of the current sibling. More...

Query_result *	m_setop_query_result {nullptr}
	The query result for this term. More...

bool	m_owning_operand {false}
	The operand of a n-ary set operation (that owns the common query result) has this set to true. More...

Table_ref *	m_result_table {nullptr}
	Result temporary table for the set operation, if applicable. More...

mem_root_deque< Item * > *	m_fields {nullptr}
	Used only when streaming, i.e. More...

Detailed Description

Query term tree structure.

There are five node types, cf. Query_term_type. Leaf nodes are Query_block objects. We have three kinds of n-ary set operation nodes corresponding to INTERSECT, UNION and EXCEPT. Finally, we have a "unary" node which essentially adds a ORDER BY/LIMIT over another node.

Query blocks serve a dual purpose: they represent the query specification and table constructors of the query. As such they are the leaf nodes of the query tree. But they also serve as a way to realize ORDER BY and LIMIT for non-leaf nodes, accessed via the function Query_term::query_block(). Therefore, every non-leaf node in the tree has a companion Query_block to hold ORDER BY and LIMIT information. For the leaf nodes, which are themselves query blocks, the query_block() function just returns a pointer to self, i.e. the leaf nodes handle ORDER BY and LIMIT themselves.

Example: ((SELECT * FROM t1 UNION SELECT * FROM t2 UNION ALL SELECT * FROM t3
           ORDER BY a LIMIT 5) INTERSECT
          (((SELECT * FROM t3 ORDER BY a LIMIT 4) ) EXCEPT SELECT * FROM t4)
          ORDER BY a LIMIT 4) ORDER BY -a LIMIT 3;

->
            m_query_term   +------------------+     slave(s)
            +--------------|-Query_expression |------------------+
            |              +------------------+                  |
            V        post_                                       |
+-------------------+processing_ +----------------------+        |
| Query_term_unary  |block()     |Query_block           |        |
|                   |----------->|order by -(`a) limit 3|        |
+-------------------+            +----------------------+        |
 |m_children                                                     |
 | +-----------------------+   +----------------------+          |
 | |Query_term_intersect   |   |Query_block           |          |
 +>|last distinct index: 1 |-->|order by `a` limit 4  |          |
   +-----------------------+   +----------------------+          |
    |m_children                                                  |
    |  +-----------------------+   +----------------------+      |
    |  |Query_term_union       |   |Query_block           |      |
    +->|last distinct index: 1 |-->|order by `a`  limit 5 |      |
    |  +-----------------------+   +----------------------+      |
    |    |m_children                                             |
    |    |   +------------+        SELECT * FROM t1             /
    |    +-->|Query_block |  <---------------------------------+
    |    |   +------------+  ----------------------------------+ next
    |    |                                                      \
    |    |   +------------+        SELECT * FROM t2             /
    |    +-->|Query_block |  <---------------------------------+
    |    |   +------------+  ----------------------------------+ next
    |    |                                                      \
    |    |   +------------+        SELECT * FROM t3             /
    |    +-->|Query_block |  <---------------------------------+
    |        +------------+  ----------------------------------+ next
    |                                                           \
    |  +-----------------------+  +------------+                 |
    |  |Query_term_except      |->|Query_block |                 |
    +->|last distinct index: 1 |  +------------+                 |
       +-----------------------+                                 |
         |m_children                                             |
         |   +----------------------+                            |
         |   |Query_block           |      SELECT * FROM t3      /
         +-->|order by `a`  limit 4 |  <------------------------+
         |   +----------------------+  -------------------------+ next
         |                                                       \
         |   +------------+                SELECT * FROM t4      |
         +-->|Query_block | <------------------------------------+
             +------------+

Note that all leaf query blocks representing the query specifications are linked under Query_expression via their next pointers. The nesting is achieved by the arrows on the left side of the figure, via the nodes' m_children members. The four classes Query_term_unary and Query_term_{union, intersect, except} are modelled via the base class Query_term_set_op which contains a m_children member. Each of these also contain a Query_block which will handle its order by and/or limit clauses. These are similar to the old so-called "fake_query_block" (which is now gone), and are not linked in with "next" pointers.

The is also a back pointer from the children nodes to the parent Query_term object (not shown).

In the simple case of a single query specification (or table value constructor or explicit table), there is no super-structure over the Query_block linked from the Query_expression, i.e. Query_expression's m_query_term member is just a Query_block.

The query blocks (QT_QUERY_BLOCK nodes) corresponding to the query specification (or table value constructors) are prepared and optimized by running over them from the Query_expression via the slave/next pointers as before. There are separate methods which handle prepare and optimization for non-leaves, i.e. nodes of types QT_UNARY, QT_INTERSECT, QT_EXCEPT and QT_UNION.

We also define an iterator class (Query_terms) for iterating over all the nodes in the tree, see also Query_expression::query_terms() for its use. When possible, we access all nodes using iterators.

The built structure can be traced with the debug trace keyword "ast", e.g. as SET SESSION debug = 'd,ast:O,/tmp/mysqld.trace';

Constructor & Destructor Documentation

◆ ~Query_term()

virtual Query_term::~Query_term ( )

virtualdefault

Node destructor.

Member Function Documentation

◆ child_count()

virtual size_t Query_term::child_count ( ) const

inlinevirtual

Get the number of children this node has.

Returns: the number

Reimplemented in Query_term_set_op.

◆ cleanup()

virtual void Query_term::cleanup ( bool full )

inlinevirtual

Reset resources used.

Parameters

full	do full cleanup. Same semantics as for Query_expression's cleanup

Reimplemented in Query_term_set_op, and Query_block.

◆ cleanup_query_result()

void Query_term::cleanup_query_result ( bool full )

Cleanup m_setop_query_result, q.v.

◆ create_tmp_table()

bool Query_term::create_tmp_table	(	THD *	thd,
		ulonglong	create_options
	)

Create a temporary table for a set operation.

Parameters

thd	session context
create_options	create options for create_tmp_table

Returns: false on success, true on error

◆ debugPrint()

virtual void Query_term::debugPrint	(	int	level,
		std::ostringstream &	buf
	)		const

pure virtual

Print the tree rooted at this node to buf.

Call on top level with level==0

Parameters

level	level we are at in tree.
buf	the buffer to format output into

Implemented in Query_term_union, Query_term_intersect, Query_term_except, Query_term_unary, and Query_block.

◆ destroy_tree()

virtual void Query_term::destroy_tree ( )

pure virtual

Destroy the query term tree structure.

Implemented in Query_term_set_op, and Query_block.

◆ fields()

mem_root_deque< Item * > * Query_term::fields ( )

inline

◆ indent()

void Query_term::indent	(	int	level,
		std::ostringstream &	buf
	)

static

Print blank space indentation (unit: two) to buf according to level.

Minion.

Parameters

level	level we are at in tree.
buf	the buffer to format output into

◆ label_children()

virtual void Query_term::label_children ( )

pure virtual

Set the correct value of Query_term::m_sibling_idx recursively for set operations.

For Query_term_unary, this is done in its constructor. A no-op for Query_block. See also set_sibling_idx.

Implemented in Query_term_set_op, and Query_block.

◆ make_set_op_access_path()

virtual AccessPath * Query_term::make_set_op_access_path	(	THD *	thd,
		Query_term_set_op *	parent,
		Mem_root_array< AppendPathParameters > *	union_all_subpaths,
		bool	calc_found_rows
	)

pure virtual

Recursively constructs the access path of the set operation, possibly materializing in a tmp table if needed, cf.

Query_term_set_op::m_is_materialized

Parameters

thd	session context
parent	the parent for which we want to create a materialized access path, or nullptr
union_all_subpaths	if not nullptr, we are part of a UNION all, add constructed access to it.
calc_found_rows	if true, do allow for calculation of number of found rows even in presence of LIMIT.

Returns: access path, if nullptr, this is an error

Implemented in Query_term_set_op, Query_term_unary, and Query_block.

◆ open_result_tables()

virtual bool Query_term::open_result_tables	(	THD *	thd,
		int	level
	)

inlinevirtual

Open tmp tables for the tree of set operation query results, by recursing.

Parameters

thd	session context
level	level in the tree, top should be called with 0.

Returns: true on error

Reimplemented in Query_block, and Query_term_set_op.

◆ operator_string()

virtual const char * Query_term::operator_string ( ) const

pure virtual

Get the node type description.

Returns: descriptive string for each node type.

Implemented in Query_term_union, Query_term_intersect, Query_term_except, Query_term_unary, and Query_block.

◆ optimize_query_term()

virtual bool Query_term::optimize_query_term	(	THD *	thd,
		Query_expression *	qe
	)

pure virtual

Optimize the non-leaf query blocks.

Parameters

thd	session context
qe	owning query expression (of this term)

Returns: true on error, else false

Implemented in Query_block, and Query_term_set_op.

◆ owning_operand()

bool Query_term::owning_operand ( )

inline

Getter for m_owning_operand, q.v.

◆ parent()

Query_term_set_op * Query_term::parent ( ) const

inline

Getter for m_parent, q.v.

◆ prepare_query_term()

virtual bool Query_term::prepare_query_term	(	THD *	thd,
		Query_expression *	qe,
		Change_current_query_block *	save_query_block,
		mem_root_deque< Item * > *	insert_field_list,
		Query_result *	common_result,
		ulonglong	added_options,
		ulonglong	removed_options,
		ulonglong	create_options
	)

pure virtual

a) Prepare query blocks, both leaf blocks and blocks reresenting order by/limit in query primaries with parentesized query expression body with order by clause and/or limit/offset clause (unary query terms).

Establish types for all query terms, and set up tmp table for CTE if present and for any materialized tmp tables for unary query terms.

Types for set operations are calculated bottom-up, so for a unary tmp table, we use the base block's types and names for proper resolution in cases like:

SELECT column_a FROM t1 UNION ( (SELECT column_b FROM t2 ORDER BY column_b LIMIT 3) ORDER BY column_b DESC LIMIT 2 ) ORDER BY column_a;

The second ORDER BY's column_b should resolve to its nested column_b selected from t2. This also means that the second order by operation does sorting using the type of column_b, not using the common type of t1.column_a and t2.column_b.

If the inner SELECT above were a binary set operation, we would order by the joined types of the binary (sub)operation, recursively.

This function constructs the m_types array for each binary set operation query term. Unary terms just use their child's type information.

We have a nested set operation structure where the leaf nodes are inner query blocks, typically SELECT clauses. These are prepared with Query_block::prepare, called by Query_block::prepare_query_term. We also need to prepare the nodes representing the binary set and unary operations. We have already merged nested set operation of the same kind into multi op form, so at any level the child and parent will usually be of another kind(1). We a priori create temporary tables marked with an asterisk below, modulo ALL optimizations, to consolidate the result of each multi set and unary operations. E.g.

               UNION*
                 |
      +----------------+----------+
      |                |          |
 INTERSECT*     UNARY TERM*   EXCEPT*
      |                |          |
  +---+---+            QB      +--+-+
  |   |   |                    |    |
 QB  QB  UNION*                QB   QB
         QB QB

(1) an exception is that we do not merge top level trailing UNION ALL nodes with preceding UNION DISTINCT in order that they can be streamed efficiently.

Note that the Query_result is owned by the first sibling participating in the set operations, so the owning nodes of the above example are actually:

               UNION
                 |
      +----------------+----------+
      |                |          |
 INTERSECT*     UNARY TERM   EXCEPT
      |                |          |
  +---+---+            QB*     +--+-+
  |   |   |                    |    |
 QB* QB  UNION                QB*   QB
         QB* QB

Parameters

thd	session context
qe	query expression query expression directly containing this query term
save_query_block	copy of thd->lex->current_query_block() when Query_expression::prepare was called.
insert_field_list	pointer to field list if INSERT op, NULL otherwise.
common_result	for the top node, this is not used: we use query_result() instead. Otherwise, if it is empty, we create a query result on behalf of this node and its siblings. This node is then the designated owning operand, and is responsible for releasing it after execution. The siblings will see that common_result is not empty and use that.
added_options	these options will be added to the query blocks.
removed_options	options that cannot be used for this query
create_options	options to use for creating tmp table

Returns: false on success, true on error

Implemented in Query_term_set_op, Query_block, and Query_term_unary.

◆ print_order()

void Query_term::print_order	(	const THD *	thd,
		String *	str,
		ORDER *	ord,
		enum_query_type	query_type
	)

static

Print into str the order indicated in ord, using standard print_for_order Used by traditional explain.

Parameters

thd	session state
str	string to accumulate formatted output into
ord	the ORDER to be printed
query_type	controls how printing happens

◆ printPointers()

void Query_term::printPointers ( std::ostringstream & buf ) const

Print the pointer of this node and its parent to buf.

Minion.

Parameters

buf	the buffer to format output into

◆ pushdown_limit_order_by()

Query_term * Query_term::pushdown_limit_order_by ( Query_term_set_op * parent = nullptr )

Called after contextualization to simplify query, c.f.

sql_yacc.yy CONTEXTUALIZE_VIEW. It also sets up the parent pointers.

Parameters

parent parent of this if any

◆ query_block()

virtual Query_block * Query_term::query_block ( ) const

pure virtual

The query_block which holds the ORDER BY and LIMIT information for this set operation.

Note that for the case where the root is a simple query block, this will return self.

Returns: the query block

Implemented in Query_term_set_op, and Query_block.

◆ redundant_order_by()

std::pair< bool, bool > Query_term::redundant_order_by	(	Query_block *	block,
		int	level
	)

Determine if we have a redundant ORDER BY in block.

Used during prepare.

Parameters

block	the query block
level	the current nesting level

Returns: tuple {bool found, bool redundant} redundant==true means ORDER BY of the block is redundant and can be eliminated.

Not very object oriented with this switch, but nice to keep logic in one place.

Logic here presumes that query expressions that only add limit (not order by) will have been pushed down

◆ result_table()

Table_ref & Query_term::result_table ( )

inline

Getter for m_result_table, q.v.

◆ set_fields()

void Query_term::set_fields ( mem_root_deque< Item * > * fields )

inline

◆ set_owning_operand()

void Query_term::set_owning_operand ( )

inline

Setter for m_owning_operand, q.v.

◆ set_result_table()

void Query_term::set_result_table ( Table_ref * tl )

inline

Setter for m_result_table, q.v.

◆ set_setop_query_result()

void Query_term::set_setop_query_result ( Query_result * rs )

inline

Setter for m_setop_query_result, q.v.

◆ set_sibling_idx()

void Query_term::set_sibling_idx ( uint idx )

inline

Setter for m_sibling_idx, q.v.

◆ setop_query_result()

Query_result * Query_term::setop_query_result ( )

inline

Getter for m_setop_query_result, q.v.

◆ setop_query_result_union()

Query_result_union * Query_term::setop_query_result_union ( )

inline

Getter for m_setop_query_result, q.v. Use only if we can down cast.

◆ sibling_idx()

uint Query_term::sibling_idx ( )

inline

Getter for m_sibling_idx, q.v.

◆ term_type()

virtual Query_term_type Query_term::term_type ( ) const

pure virtual

Get the node tree type.

Returns: the tree node type

Implemented in Query_term_union, Query_term_intersect, Query_term_except, Query_term_unary, and Query_block.

◆ types_array()

virtual mem_root_deque< Item * > * Query_term::types_array ( )

pure virtual

Implemented in Query_term_set_op, Query_term_unary, and Query_block.

◆ types_iterator()

virtual VisibleFieldsIterator Query_term::types_iterator ( )

pure virtual

Abstract over visible column types: if query block, we offer an iterator over visible fields, for binary set operators we offer an iterator over m_types, for unary we just call the child's.

See also the accompanying visible_column_count.

Implemented in Query_term_set_op, Query_term_unary, and Query_block.

◆ validate_structure()

bool Query_term::validate_structure	(	const Query_term *	parent,
		int	depth = `0`
	)		const

Return true if structure is too deep, i.e.

more than MAX_SELECT_NESTING. As a side effect is also gives the post processing block a select number, this is done late so as to get numbers higher the leaf blocks, and in inside out order, so that the top set operation block will have the highest number.

Parameters

parent	the real parent in the tree as visited recursively
depth	the current depth in the tree, starting at 0 at the top. It is increased with one for each time we recurse into a child.

Returns: error if too deep structure, else false

◆ visible_column_count()

virtual size_t Query_term::visible_column_count ( ) const

pure virtual

Return the number of visible columns of the query term.

For query blocks this is in general a subset of Query_block::fields

Implemented in Query_term_set_op, Query_term_unary, and Query_block.

Member Data Documentation

◆ m_fields

mem_root_deque<Item *>* Query_term::m_fields {nullptr}

protected

Used only when streaming, i.e.

for a not materialized result set

◆ m_owning_operand

bool Query_term::m_owning_operand {false}

protected

The operand of a n-ary set operation (that owns the common query result) has this set to true.

It is always the first one.

◆ m_parent

Query_term_set_op* Query_term::m_parent {nullptr}

protected

Back pointer to the node whose child we are, or nullptr (root term).

◆ m_result_table

Table_ref* Query_term::m_result_table {nullptr}

protected

Result temporary table for the set operation, if applicable.

◆ m_setop_query_result

Query_result* Query_term::m_setop_query_result {nullptr}

protected

The query result for this term.

Shared between n-ary set operands, the first one holds it, cf. owning_operand. Except at top level, this is always a Query_result_union.

◆ m_sibling_idx

uint Query_term::m_sibling_idx {0}

protected

If parent is non-null, this holds the index of the current sibling.

Used for efficient iterator traversal up and down the tree.

The documentation for this class was generated from the following files:

sql/query_term.h
sql/query_term.cc

Public Member Functions

Static Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~Query_term()

Member Function Documentation

◆ child_count()

◆ cleanup()

◆ cleanup_query_result()

◆ create_tmp_table()

◆ debugPrint()

◆ destroy_tree()

◆ fields()

◆ indent()

◆ label_children()

◆ make_set_op_access_path()

◆ open_result_tables()

◆ operator_string()

◆ optimize_query_term()

◆ owning_operand()

◆ parent()

◆ prepare_query_term()

◆ print_order()

◆ printPointers()

◆ pushdown_limit_order_by()

◆ query_block()

◆ redundant_order_by()

◆ result_table()

◆ set_fields()

◆ set_owning_operand()

◆ set_result_table()

◆ set_setop_query_result()

◆ set_sibling_idx()

◆ setop_query_result()

◆ setop_query_result_union()

◆ sibling_idx()

◆ term_type()

◆ types_array()

◆ types_iterator()

◆ validate_structure()

◆ visible_column_count()

Member Data Documentation

◆ m_fields

◆ m_owning_operand

◆ m_parent

◆ m_result_table

◆ m_setop_query_result

◆ m_sibling_idx