Shulou(Shulou.com)06/01 Report--

The last section introduced the implementation logic of the subfunction subfunction build_base_rel_tlists/find_placeholders_in_jointree/find_lateral_references in the function query_planner. This section introduces the mathematical knowledge involved in the next subfunction deconstruct_jointree function: the equivalent class and the application example of the equivalent class in PG.

I. the basis of mathematics

Equivalence relation

Equivalence relation (equivalence relation) is to say that R is a binary relation on a set A. If R satisfies the following conditions:

1. Reflexivity: ∀ x ∈ Ajie XRx

two。 Symmetry: ∀ XMagi y ∈ AMagi XRy ⇒ yRx

3. Transitivity: ∀ XJI YJI z ∈ A, (xRy ∧ yRz) ⇒ xRz

Then R is said to be an equivalent relation defined on A. It is customary to rewrite the symbol of equivalence relation from R to ∼

For detailed instructions and examples, see Wikipedia.

Equivalence class

Suppose an equivalence relation (represented by ∼) is defined on a set A, then the equivalence class of an element x in An is a subset of all elements equivalent to x in A.

[X] = {y ∈ AJ y ∼ x}

For detailed instructions and examples, see Wikipedia.

II. Application

PG scans the constraint clause (qual clauses) in the function deconstruct_jointree and may find an equality in a non-externally joined condition, such as axib, where an equivalence class is created (marked as {Aline B}). If another equation, such as BeverC, is found later, then C is added to the existing equivalence class {Ameng B}, that is, {Ameng Breco C}. Through this step, some equivalence classes are generated, and the equivalence relation of any pair of members of these equivalence classes can be used as a constraint or connection condition.

The advantage of this is that through such simplification, only some equivalence conditions need to be verified, but not all equivalence conditions, and some redundant equivalence class conditions can be removed; second, considering from the opposite direction, when the optimizer prepares a list of constraints or join conditions, it checks whether each equivalence class can derive new implicit conditions that satisfy the current constraint or join. For example, in the above example, the optimizer can try to explore new optimal connection paths based on the condition that an Achievement C can be generated according to the equivalence class {A _ Magi B ~ C}.

Example 1:

Testdb=# explain verbose select t1.dwbhmemt 2.grbhtestdb from t_dwxx # grmgxx t2testdb-# where t1.dwbh = t2.dwbh and t1.dwbh = '1001' QUERY PLAN-Nested Loop (cost=0.00..16.06 rows=2 width=76) Output: t1.dwbh T2.grbh-Connect without filter operation-> Seq Scan on public.t_dwxx T1 (cost=0.00..1.04 rows=1 width=38) Output: t1.dwmc, t1.dwbh, t1.dwdz Filter: (t1.dwbh):: text = '1001'::text)-- complete the selection operation before connecting-> Seq Scan on public.t_grxx T2 (cost=0.00..15.00 rows=2 width=76) Output: t2.dwbh T2.grbh, t2.xm, t2.xb, t2.nl Filter: (t2.dwbh):: text = '1001'::text)-- complete the selection operation before connecting (8 rows)

Constraints: t1.dwbh = t2.dwbh and t1.dwbhexamples 1001', its corresponding equivalence class can be briefly understood as: {t1.dwbhjournal t2.dwbhjournal 1001'}, according to transitivity, then we can deduce the implicit constraint condition: t2.dwbhexamples 1001". Before joining, the predicates t1.dwbhexamples 1001' and t2.dwbhexamples 1002' are pushed down to the base table scan to reduce the number of joined tuples, thus achieving query optimization. From the point of view of the query plan, PG actually handles it in the same way.

The following SQL statement does not have the above conditions, so you also need to execute join filter. Exe during the connection.

Testdb=# explain verbose select t1.dwbhmemt 2.grbhtestdb from t_dwxx # grmgxx t2testdb-# where t1.dwbh = t2.dwbh and t1.dwdz like 'Guangdong%' QUERY PLAN-Nested Loop (cost=0.00..20.04 rows=2 width=76) Output: t1.dwbh T2.grbh Join Filter: (t1.dwbh):: text = (t2.dwbh):: text)-> Seq Scan on public.t_dwxx T1 (cost=0.00..1.04 rows=1 width=38) Output: t1.dwmc, t1.dwbh T1.dwdz Filter: (t1.dwdz):: text ~ 'Guangdong%':: text)-> Seq Scan on public.t_grxx T2 (cost=0.00..14.00 rows=400 width=76) Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl (8 rows)

Example 2:

The test script is as follows:

Testdb=# explain verbose select t1.dwbh. t_dwxx t2.grbhfrom dwbhj1reel tweak grxx t2where t1.dwbh = t2.dwbh order by t2.dwbh. QUERY PLAN -Sort (cost=20.18..20.19 rows=6 width=114) Output: t1.dwbh T2.grbh, t2.dwbh Sort Key: t1.dwbh-> Hash Join (cost=1.07..20.10 rows=6 width=114) Output: t1.dwbh, t2.grbh, t2.dwbh Inner Unique: true Hash Cond: (t2.dwbh):: text = (t1.dwbh):: text)-> Seq Scan on public.t_grxx T2 (cost=0.00..14.00 rows=400 width=76) Output: t2.dwbh, t2.grbh T2.xm, t2.xb, t2.nl-> Hash (cost=1.03..1.03 rows=3 width=38) Output: t1.dwbh-> Seq Scan on public.t_dwxx T1 (cost=0.00..1.03 rows=3 width=38) Output: t1.dwbh (13 rows)

In terms of the execution plan, although it is explicitly specified to sort by t2.dwbh, it is actually sorted by t1.dwbh. The reason is that there is an equivalent class {t1.dwbhjournal t2.dwbh}, whether sorted on t1.dwbh or t2.dwbh, the result is the same, but sorted on t1.dwbh, the cost is lower, so this Key is preferred.

It is worth noting that the equivalence class of PG is generated only when there are equality conditions (excluding outer joins) and ordering. As a direction of optimization, the predicate can be pushed down when there is an inequality.

Testdb=# explain verbose select t1.dwbh. t_dwxx t2.grbhfrom dwbhredgxx t2where t1.dwbh = t2.dwbh and t1.dwbh > '1001' QUERY PLAN-Nested Loop (cost=0.00..20.04 rows=2 width=76) Output: t1.dwbh T2.grbh Join Filter: (t1.dwbh):: text = (t2.dwbh):: text)-- this step is necessary-> Seq Scan on public.t_dwxx T1 (cost=0.00..1.04 rows=1 width=38) Output: t1.dwmc, t1.dwbh T1.dwdz Filter: (t1.dwbh):: text > '1001'::text)-- Filter filtering-> Seq Scan on public.t_grxx T2 (cost=0.00..14.00 rows=400 width=76) Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl-full table scan, you can consider adding Filter (8 rows) 3.

Equivalence relation

Equivalence class

Relational algebra

Basis of query optimization

Attached: code snippet in query_planner

/ /... / * * Examine the targetlist and join tree, adding entries to baserel * targetlists for all referenced Vars, and generating PlaceHolderInfo * entries for all referenced PlaceHolderVars. Restrict and join clauses * are added to appropriate lists belonging to the mentioned relations. We * also build EquivalenceClasses for provably equivalent expressions. The * SpecialJoinInfo list is also built to hold information about join order * restrictions. Finally, we form a target joinlist for make_one_rel () to * work from. * / build_base_rel_tlists (root, tlist); / / construct the projection column find_placeholders_in_jointree (root) of "base rels"; / / deal with PHI find_lateral_references (root) in jointree; / / deal with Lateral dependency joinlist = deconstruct_jointree (root) in jointree; / / decompose jointree / * * Reconsider any postponed outer-join quals now that we have built up * equivalence classes. (This could result in further additions or * mergings of classes.) * / reconsider_outer_join_clauses (root); / / if the equivalence class has been created, you need to reconsider the outer join expression / * * If we formed any equivalence classes, generate additional restriction * clauses as appropriate. (Implied join clauses are formed on-the-fly * later.) * / generate_base_implied_equalities (root); / / after the equivalence class is built, the additional constraint statement / / is generated.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.