CS计算机代考程序代写 database compiler algorithm data structure SQL 2021/4/28 Query Optimisation

程序代写 CS代考 / Algorithm算法代写代考, compiler, data structure, database, SQL代写代考

2021/4/28 Query Optimisation
Query Optimisation
Query Optimisation
Approaches to Optimisation Cost-based Query Optimiser
Cost Models and Analysis Choosing Access Methods (RelOps) PostgreSQL Query Optimization
>>
COMP9315 21T1 ♢ Query Optimisation ♢ [0/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 1/16

2021/4/28 Query Optimisation
∧ >>
❖ Query Optimisation
Queryoptimiser: RAexpression→efcientevaluation
plan
COMP9315 21T1 ♢ Query Optimisation ♢ [1/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 2/16

2021/4/28 Query Optimisation
❖ Query Optimisation (cont)
Query optimisation is a critical step in query evaluation. The query optimiser
takes relational algebra expression from SQL compiler
produces sequence of RelOps to evaluate the expression
query execution plan should provide efcient evaluation
“Optimisation” is a misnomer since query optimisers aim to nd a good plan … but maybe not optimal
Observed Query Time = Planning time + Evaluation time
COMP9315 21T1 ♢ Query Optimisation ♢ [2/14]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 3/16

2021/4/28 Query Optimisation
❖ Query Optimisation (cont)
Why do we not generate optimal query execution plans? Finding an optimal query plan …
requires exhaustive search of a space of possible plans for each possible plan, need to estimate cost (not cheap)
Even for relatively small query, search space is very large. Compromise:
dolimitedsearchofqueryplanspace (guidedby heuristics)
quickly choose a reasonably efcient execution plan
COMP9315 21T1 ♢ Query Optimisation ♢ [3/14]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 4/16

2021/4/28 Query Optimisation
<< ∧ >>
❖ Approaches to Optimisation Three main classes of techniques developed:
(equivalences, rewriting, heuristics) (execution costs, search-based)
(application properties, heuristics)
All driven by aim of minimising (or at least reducing) “cost”.
Real query optimisers use a combination of algrebraic+physical.
Semantic QO is good idea, but expensive/difcult to implement.
COMP9315 21T1 ♢ Query Optimisation ♢ [4/14]
algebraic physical semantic
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 5/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ Approaches to Optimisation (cont)
Example of optimisation transformations:
For join, may also consider sort/merge join and hash join.
COMP9315 21T1 ♢ Query Optimisation ♢ [5/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 6/16

2021/4/28 Query Optimisation
<< ∧ >>
❖ Cost-based Query Optimiser Approximate algorithm for cost-based optimisation:
translate SQL query to RAexp
for enough transformations RA’ of RAexp {
while (more choices for RelOps) { Plan={}; i=0; cost=0
for each node e of RA’ (recursively) {
ROp = select RelOp method for e Plan = Plan ∪ ROp
cost += Cost(ROp) // using child info
}
if (cost < MinCost) { MinCost = cost; BestPlan = Plan } } } Heuristics: push selections down, consider only left-deep join trees. COMP9315 21T1 ♢ Query Optimisation ♢ [6/14] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 7/16 2021/4/28 Query Optimisation << ∧ >>
❖ Cost Models and Analysis
The cost of evaluating a query is determined by:
sizeofrelations (databaserelationsandtemporaryrelations)
accessmechanisms (indexing,hashing,sorting,join algorithms)
size/numberofmainmemorybuffers (andreplacement strategy)
Analysis of costs involves estimating: size of intermediate results number of disk reads/writes
COMP9315 21T1 ♢ Query Optimisation ♢ [7/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 8/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ Choosing Access Methods (RelOps)
Performed for each node in RA expression tree … Inputs:
asingleRAoperation (σ, π, ⨝)
information about le organisation, data distribution,
…
list of operations available in the database engine
Output:
specic DBMS operation to implement this RA operation
COMP9315 21T1 ♢ Query Optimisation ♢ [8/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 9/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ Choosing Access Methods (RelOps) (cont)
Example:
RA operation: Sel[name=’John’ ∧ age>21](Student)
Student relation has B-tree index on name
database engine (obviously) has B-tree search method
giving
tmp[i] := BtreeSearch[name=’John’](Student)
tmp[i+1] := LinearSearch[age>21](tmp[i])
Where possible, use pipelining to avoid storing tmp[i] on disk.
COMP9315 21T1 ♢ Query Optimisation ♢ [9/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 10/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ Choosing Access Methods (RelOps) (cont)
Rules for choosing σ access methods: σA=c(R)andRhasindexonA ⇒ indexSearch[A=c]
(R)
σA=c(R)andRishashedonA ⇒ hashSearch[A=c](R)
σA=c(R)andRissortedonA ⇒ binarySearch[A=c] (R)
σA ≥ c(R) and R has clustered index on A
⇒ indexSearch[A=c](R)thenscan
σA≥c(R)andRishashedonA
⇒ linearSearch[A>=c](R)
COMP9315 21T1 ♢ Query Optimisation ♢ [10/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 11/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ Choosing Access Methods (RelOps) (cont)
Rules for choosing ⨝ access methods:
R⨝SandRtsinmemorybuffers ⇒ bnlJoin(R,S) R⨝SandStsinmemorybuffers ⇒ bnlJoin(S,R) R⨝SandR,Ssortedonjoinattr ⇒ smJoin(R,S) R⨝SandRhasindexonjoinattr ⇒ inlJoin(S,R) R⨝Sandnoindexes,nosorting ⇒ hashJoin(R,S)
(bnl=blocknestedloop; inl=indexnestedloop; sm=sortmerge)
COMP9315 21T1 ♢ Query Optimisation ♢ [11/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 12/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ PostgreSQL Query Optimization
Input: tree of Query nodes returned by parser Output: tree of Plan nodes used by query executor
wrapped in a PlannedStmt node containing state info Intermediate data structures are trees of Path nodes
a path tree represents one evaluation order for a query
All Node types are dened in include/nodes/*.h
COMP9315 21T1 ♢ Query Optimisation ♢ [12/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 13/16

2021/4/28 Query Optimisation
<< ∧ >> ❖ PostgreSQL Query Optimization (cont)
Query optimisation proceeds in two stages (after parsing)…
Rewriting:
uses PostgreSQL’s rule system
query tree is expanded to include e.g. view denitions
Planning and optimisation:
using cost-based analysis of generated paths
via one of two different path generators
chooses least-cost path from all those considered
Then produces a Plan tree from the selected path. COMP9315 21T1 ♢ Query Optimisation ♢ [13/14]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 14/16

2021/4/28 Query Optimisation
<< ∧ ❖ PostgreSQL Query Optimization (cont) COMP9315 21T1 ♢ Query Optimisation ♢ [14/14] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 15/16 2021/4/28 Query Optimisation Produced: 5 Apr 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/qry-optimisation/slides.html 16/16

Related Posts