Advance Databases

Physical Operators Cost and Result Size

• R relation
• I index
• O operator
• B number of pages in buffer
• A attribute
• N_pag(R) Number of pages of relation R
• N_rec(R) Number of records of relation R
• N_leaf(I) Number of leaf of index I
• N_key(I) Number of key of index I
• ψ_J join condition
• S_f(ψ_J) selectivity factor of ψ_J
• C_I Cost of accessing the index pages
• C_D Cost of accessing the data pages containing the records
• Φ(k, n) ~ min(k, n) Cardenas formula (estimate of the number of pages, in a file of n pages, that contain at least one of the k records to be retrieved using a sorted rid-list)

Relation (R)

Operator	Cost	Result Size
TableScan(R)	C = Npag(R)	Erec = Nrec(R)
IndexScan(R, I) clustered	C = Nleaf(I) + Npag(R)	Erec = Nrec(R)
IndexScan(R, I) on key	C = Nleaf(I) + Nrec(R)	Erec = Nrec(R)
IndexScan(R, I) otherwise	C = Nleaf(I) + Nkey(R) * Φ(Nrec(R)/Nkey(R), Npag(R))	Erec = Nrec(R)
IndexSequentialScan(R, I)	C = Nleaf(I)	Erec = Nrec(R)
SortScan(R, I)	C = 3*Npag(R)	Erec = Nrec(R)

Projection (π)

Operator	Cost	Result Size
Project(O, {Ai})	C = C(O)	Erec = Erec(O)
IndexOnlyScan(R, I, {Ai})	C = Nleaf(I)	Erec = Nrec(R)

Duplicate elimination (δ)

Operator	Cost	Result Size
Distinct(O, {Ai})	C = C(O)	Erec = min(Erec(O)/2, Π Nkey(Ai))
HashDistinct(O, {Ai})	C = C(O) + 2*Npag(O)	Erec = min(Erec(O)/2, Π Nkey(Ai))

Sort (τ)

Operator	Cost	Result Size
Sort(O, {Ai})	C = C(O) + 2*Npag(O)	Erec = Erec(O)

Selection (σ)

Operator	Cost	Result Size
Filter(O, ψ)	C = C(O)	Erec = |Sf(ψ) * Erec(O)|
IndexFilter(R, I, ψ) clustered	C = |Sf(ψ) * (Nleaf(I) + Npag(R))|	Erec = |Sf(ψ) * Nrec(R)|
IndexFilter(R, I, ψ) unclustered	C = |Sf(ψ) * (Nleaf(I) + Nkey(R) * Φ(Nrec(R)/Nkey(R), Npag(R)))|	Erec = |Sf(ψ) * Nrec(R)|
IndexFilter(R, I, ψ) on key	C = |Sf(ψ) * (Nleaf(I) + Nrec(R))|	Erec = |Sf(ψ) * Nrec(R)|
IndexSequentialFilter(R, I, ψ)	C = |Sf(ψ) * Nleaf(I)|	Erec = |Sf(ψ) * Nrec(R)|
IndexOnlyFilter(R, I, {Ai}, ψ)	C = |Sf(ψ) * Nleaf(I)|	Erec = |Sf(ψ) * Nrec(R)|
OrIndexFilter(R, I, {Ai}, ψ)	C = |Σ CIK | + |Φ(Erec, Npag(R))|	Erec = |Sf(ψ) * Nrec(R)|
AndIndexFilter(R, I, {Ai}, ψ)	C = |Σ CIK | + |Φ(Erec, Npag(R))|	Erec = |Sf(ψ) * Nrec(R)|

Grouping (γ)

Operator	Cost	Result Size
GroupBy(O, {Ai}, {fi})	C = C(O)	Erec = min(Erec(O)/2, Π Nkey(Ai))
HashGroupBy(O, {Ai}, {fi})	C = C(O) + 2*Npag(O)	Erec = min(Erec(O)/2, Π Nkey(Ai))

Join (⋈)

Operator	Cost	Result Size
NestedLoop(OE, OI, ψJ)	C = C(OE) + Erec(OE) * C(OI)	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |
PageNestedLoop(OE, OI, ψJ)	C = C(OE) + Npag(OE) * C(OI)	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |
BlockNestedLoop(OE, OI, ψJ)	C = C(OE) + Npag(OE)/B * C(OI)	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |
IndexNestedLoop(OE, OI, ψJ)	C = C(OE) + Erec(OE) * (CI + CD)	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |
MergeJoin(OE, OI, ψJ)	C = C(OE) + C(OI)	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |
HashJoin(OE, OI, ψJ)	C = C(OE) + 2*(Npag(OE) + Npag(OI))	Erec = | Sf(ψJ) * Erec(OE) * Erec(OI) |