- R relation
- I index
- O operator
- B number of pages in buffer
- A attribute
- Npag(R) Number of pages of relation R
- Nrec(R) Number of records of relation R
- Nleaf(I) Number of leaf of index I
- Nkey(I) Number of key of index I
- ψJ join condition
- Sf(ψJ) selectivity factor of ψJ
- CI Cost of accessing the index pages
- CD 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)
| 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) |
| Operator | Cost | Result Size |
|---|---|---|
| Project(O, {Ai}) | C = C(O) | Erec = Erec(O) |
| IndexOnlyScan(R, I, {Ai}) | C = Nleaf(I) | Erec = Nrec(R) |
| 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)) |
| Operator | Cost | Result Size |
|---|---|---|
| Sort(O, {Ai}) | C = C(O) + 2*Npag(O) | Erec = Erec(O) |
| 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)| |
| 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)) |
| 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) | |