Deriving high-speed search conditions

A high-speed search condition refers to a condition derived from a WHERE clause search condition or an ON search condition in a FROM clause by CNF conversion or condition shifting. When high-speed search conditions are derived, the retrieval performance improves because the rows to be retrieved can be narrowed at an earlier stage.

When HiRDB derives high-speed search conditions, it retains the original search conditions used in the derivation. HiRDB can therefore generate just those derived conditions that are optimal conditions without generating derived conditions that cannot be used to narrow the search.

When HiRDB derives high-speed search conditions, it optimizes the search by considering the new derived conditions when it determines the access path (including the table retrieval method, join method, and join sequence). Therefore, when HiRDB derives high-speed search conditions, the access paths may change as described as follows:

HiRDB determines that the rows to be retrieved can be narrowed down at an early stage, and retrievals with an index become easier to select.
If OR is specified in a join condition, and the CNF conversion and OR reduction operations extract the join condition outside OR, then nested-loops-join, merge join, and hash join can be applied outside direct products.
If a limiting condition is specified for only one of the tables to be joined, nested-loops join becomes easier to select. If limiting conditions are specified for both tables, merge join and hash join become easier to select.

When high-speed search conditions are derived from complex conditions, it takes longer to generate the high-speed search conditions and to evaluate the conditions when the search is executed. Therefore, depending on the SQL statements involved, the performance may actually drop instead of improve.

Organization of this subsection: (1) Application scope of high-speed search conditions; (2) Deriving high-speed search conditions by CNF conversion; (3) Deriving high-speed search conditions by condition shifting

(1) Application scope of high-speed search conditions

Whether or not HiRDB derives high-speed search conditions depends on the specification values of the SQL optimization and SQL extension optimizing options. The following table shows the relationships between the SQL optimization and SQL extension optimizing options and deriving high-speed search conditions.

Table 4-18 Relationships between the SQL optimization and SQL extension optimizing options and deriving high-speed search conditions

Type	Derivation source condition	Derived condition	Specified SQL optimization option or SQL extension optimizing option
Type	Derivation source condition	Derived condition	Do not derive	Derive^#¹
CNF conversion	OR condition for one table	One-table condition	--	--
	OR condition extending across two or more tables	One-table condition	G^#²	G
		Join condition (column=column) is extracted by OR reduction	G^#²	G
		Other condition for two or more tables	--	--
Condition shifting	Join condition for tables A and B, and condition for table A	One-table condition for table B	--	G
Condition shifting	Join condition for tables A and B, and join condition for tables A and C	Join condition for tables B and C	--	--

Legend:: G: HiRDB generates high-speed search conditions.; --: HiRDB does not generate high-speed search conditions.

#1: Specify the value for deriving high-speed search conditions in the SQL optimization options.

#2: If a direct product is specified in the search at the derivation source of high-speed search conditions, high-speed search conditions are generated depending on the conditions described below. The following table describes whether high-speed search conditions are derived, and the derivation condition.

Search at the derivation source		Derivation condition		High-speed search conditions that are derived	Whether derived or not
Two-table search	Direct product	Join condition (column=column) cannot be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	--
			--	Other two-table condition	N
		Join condition (column=column) can be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	Y
			--	Other two-table condition	N
	No direct product	--			N
Search in three or more tables	All direct product	Join condition (column=column) cannot be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	--
			--	Other two-table condition	N
		Join condition (column=column) can be extracted partially by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	Y
			--	Other two-table condition	N
		Join condition (column=column) can be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	Y
			--	Other two-table condition	N
	Partially direct product	Join condition (column=column) cannot be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	--
			--	Other two-table condition	N
		Join condition (column=column) can be extracted partially by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the one-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the one-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	Y
			--	Other two-table condition	N
		Join condition (column=column) can be extracted by OR reduction.	The search condition of the derivation source includes a one-table condition for the same table as for the two-table condition to be derived.	None	N
			The search condition of the derivation source does not include a one-table condition for the same table as for the two-table condition to be derived.	One-table condition	Y
			--	Join condition (column=column)	Y
			--	Other two-table condition	N
	No direct product	--			N

Legend:: Y: Derived; N: Not derived; --: Not applicable

(2) Deriving high-speed search conditions by CNF conversion

CNF conversion refers to converting conditions joined with OR (disjunctive normal form (DNF) format) into equivalent conditions joined with AND (conjunctive normal form (CNF) format). High-speed search conditions can be derived by applying CNF conversion to WHERE clause search conditions or to ON search conditions in FROM clauses.

(a) Search conditions derived by CNF conversion

The following search conditions are derived by CNF conversion:

If CNF conversion can generate a one-table condition from a condition that extends across two or more tables joined with OR, HiRDB derives the one-table condition as a high-speed search condition. By deriving the one-table condition, HiRDB can narrow the number of items to be joined.
If all conditions joined with OR are included in the same join condition (column=column only) for two tables, HiRDB can derive (join-condition OR ... OR join-condition) by applying CNF conversion to that condition. Then if the same condition can be used to execute duplicate elimination on all join conditions joined with OR (OR reduction), HiRDB derives the join conditions as high-speed search conditions. By deriving the join conditions, HiRDB can eliminate direct product processing and improve the performance.

Furthermore, the specifications for the SQL optimization options and SQL extension optimizing options determine whether HiRDB derives high-speed search conditions. For details about the relationships between SQL optimization options and SQL extension optimizing options, and deriving of high-speed search conditions, see (1) Application scope of high-speed search conditions.

(b) Conditions when CNF conversion is not executed

High-speed search conditions are not derived by CNF conversion if any one of the following conditions applies:

A derived search condition would include a subquery.
Deriving the derivation-source conditions specified in the ON search condition of an outer join would produce conditions that are confined to the outer table.
Deriving the derivation-source conditions specified in the WHERE clause of an outer join would produce conditions that are confined to the inner table.
Deriving the derivation-source conditions specified in the WHERE clause of an outer join would produce conditions for two or more tables.
If HiRDB derived high-speed search conditions, the maximum nest count of the Boolean operations would exceed 255.
A search condition is specified in a HAVING clause.
A derived search condition would be a join condition resulting from direct product.

(3) Deriving high-speed search conditions by condition shifting

Condition shifting refers to deriving a new condition from two or more conditions.

The methods of deriving search conditions by condition shifting are described as follows.

Deriving high-speed search conditions by shifting a one-table condition through a join condition
Deriving high-speed search conditions by shifting join conditions (applicable to the UNIX edition only)

(a) Deriving high-speed search conditions by shifting a one-table condition through a join condition

If the search conditions consist of a two-table join condition (column=column only) and a one-table condition that includes the join column, HiRDB derives a one-table condition for the column in the table to be joined. An example is shown as follows:

 
T1.C1 = T2.C1 AND T1.C1 > 10
T1.C1 = T2.C1 AND T1.C1 > 10 AND T2.C1 > 10

The underlined section becomes the derived high-speed search condition.

One-table conditions that are targets for condition shifting
The one-table conditions that are targets for condition shifting are listed as follows:
- column-specification comparison operator {value-specification|reference-column-to-outside}
  Condition shifting is executed even when the left and right sides of the comparison operator (=, <>, ^=, !=, <, <=, >, or >=) are switched.
- column-specification IS [NOT] NULL
- column-specification [NOT] IN (value-specification[,value-specification]...)
- column-specification [NOT] LIKE pattern-character-string [ESCAPE escape-character]
  If the join columns have different data lengths, condition shifting is executed only when the pattern character string is a literal and forward matching is applied.
- column-specification [NOT] XLIKE pattern-character-string [ESCAPE escape-character]
  If the join columns have different data lengths, condition shifting is not executed.
- column-specification BETWEEN {value-specification|reference-column-to-outside} AND {value-specification|reference-column-to-outside}
- column-specification [NOT] SIMILAR TO pattern-character-string [ESCAPE escape-character]
  If the join columns have different data lengths, condition shifting is executed only when the pattern character string is a literal and forward matching that produces a LIKE-predicate equivalent is applied.
Conditions when condition shifting is not executed
Condition shifting is not executed if any one of the following conditions applies:
- The join condition is an outer join.
- The join condition is an inner join, and condition shifting would take place between a WHERE clause search condition and an ON search condition in a FROM clause. (For an inner join involving three or more tables, HiRDB executes condition shifting between multiple ON search conditions.)
- The data type of the join columns is a comparison of fixed length and variable length.
- The data type of the join columns is FLOAT or SMALLFLT.
- If HiRDB derived high-speed search conditions, the maximum nest count of the Boolean operations would exceed 255.
- A search condition is specified in a HAVING clause.

(b) Deriving high-speed search conditions by shifting join conditions (applicable to the UNIX edition only)

If the search conditions consist of a two-table join condition (column=column only) and a join condition (column=column only) between a column in one of the two tables and a column in a separate third table, HiRDB derives a new join condition from the remaining two columns that are not linked by a join condition. If correlation names are specified, the tables are viewed as separate tables if the correlation names are different. An example is shown as follows:

 
T1.C1 = T2.C1 AND T2.C1 = T3.C1
T1.C1 = T2.C1 AND T2.C1 = T3.C1 AND T1.C1 = T3.C1

The underlined section is the rapid search condition that was derived.

Conditions when the join condition is not shifted
The join condition is not shifted if any one of the following conditions applies:
- The join condition is an outer join.
- The join condition is an inner join, and condition shifting would take place between a WHERE clause search condition and an ON search condition in a FROM clause. (For an inner join involving three or more tables, HiRDB executes condition shifting between multiple ON search conditions.)
- The data type of the join columns is a comparison of fixed length and variable length.
- The data type of the join columns is FLOAT or SMALLFLT.
- If HiRDB derived high-speed search conditions, the maximum nest count of the Boolean operations would exceed 255.
- A search condition is specified in a HAVING clause.