ADBMS formulas

Basic Cost Estimation:

$b * t_{T} + S * t_{S}$ (where b is the number of block transfers, $t_{T}$ is the time to transfer one block, S is the number of seeks, and $t_{S}$ is the time for one seek)

Linear Search (A1) - General Case:

Cost = $b_{r} + 1$ (where $b_{r}$ is the number of blocks in relation r)

Linear Search (A1) - Selection on Key Attribute:

Cost = $(b_{r} /2) + 1$

Primary Index, Equality on Key (A2):

Cost = $(h_{i} + 1) * (t_{T} + t_{S})$ (where $h_{i}$ is the height of the index)

Primary Index, Equality on Nonkey (A3):

Cost = $h_{i} * (t_{T} + t_{S}) + t_{S} + t_{T} * b$ (where b is the number of blocks containing matching records)

Secondary Index, Equality on Nonkey (A4) - Single Record (Candidate Key):

Cost = $(h_{i} + 1) * (t_{T} + t_{S})$

Secondary Index, Equality on Nonkey (A4) - Multiple Records:

Cost = $(h_{i} + n) * (t_{T} + t_{S})$ (where n is the number of matching records)

Number of Merge Passes (External Sort-Merge):

$⌈ lo g_{⌊ M / b_{b} ⌋ - 1} (b_{r} / M)⌉$ (where M is memory size, $b_{b}$ is buffer block per run and $b_{r}$ blocks for relation r)

Total Block Transfers (External Sort-Merge):

$b_{r} * (2 * ⌈ lo g_{⌊ M / b_{b} ⌋ - 1} (b_{r} / M)⌉ + 1)$

Total Number of Seeks (External Sort-Merge):

$2 ⌈ b_{r} / M ⌉ + ⌈ b_{r} / b_{b} ⌉ * (2 ⌈ lo g_{⌊ M / b_{b} ⌋ - 1} (b_{r} / M)⌉ - 1)$

Nested-Loop Join (Worst Case Block Transfers):

$n_{r} * b_{s} + b_{r}$ (where $n_{r}$ is the number of tuples in r, $b_{s}$ is the number of blocks in s, and $b_{r}$ is number of blocks in r)

Nested-Loop Join (Worst Case Seeks):

$n_{r} + b_{r}$

Nested-Loop Join (Smaller Relation in Memory):

$b_{r} + b_{s}$ (block transfers and 2 seeks)

Block Nested-Loop Join (Worst Case):

$b_{r} * b_{s} + b_{r}$ (block transfers) + $2 * b_{r}$ (seeks)

Block Nested-Loop Join (Best Case):

$b_{r} + b_{s}$ (block transfers) + 2 (seeks)

Improved Block Nested-Loop Join:

Cost = $⌈ b_{r} / (M - 2)⌉ * b_{s} + b_{r}$ (block transfers) + $2 ⌈ b_{r} / (M - 2)⌉$ (seeks)

Indexed Nested-Loop Join:

Cost = $b_{r} * (t_{T} + t_{S}) + n_{r} * c$ (where c is the cost of traversing the index and fetching matching tuples)

Merge-Join Cost:

$b_{r} + b_{s}$ (block transfers) + $⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉$ (seeks) + (cost of sorting if relations are unsorted)

Hash function mapping

$h$ maps $J o in A tt rs$ values to ${0, 1, ..., n}$

Partitioning tuples Each tuple $t_{r} \in r$ is put in partition $r_{i}$ where $i = h (t_{r} [J o in A tt rs])$ . Each tuple $t_{s} \in s$ is put in partition $s_{i}$ , where $i = h (t_{s} [J o in A tt rs])$ .

Number of Partitions (Hash-Join, Fudge Factor):

$n = ⌈ b_{s} / M ⌉ * f$ (where f is a fudge factor, typically around 1.2)

Number of Passes for Recursive Partitioning (Hash-Join): $⌈ l o g_{⌊ M / b_{b} ⌋ - 1} (b_{s} / M)⌉$

Cost of Hash-Join (No Recursive Partitioning):

$3 (b_{r} + b_{s}) + 4 * n_{h}$ (block transfers) + $2 (⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉)$ (seeks)

Cost of Hash-Join (With Recursive Partitioning):

$2 (b_{r} + b_{s}) ⌈ lo g_{⌊ M / b_{b} ⌋ - 1} (b_{s} / M)⌉ + b_{r} + b_{s}$ (block transfers) + $2 (⌈ b_{r} / b_{b} ⌉ + ⌈ b_{s} / b_{b} ⌉) ⌈ lo g_{⌊ M / b_{b} ⌋ - 1} (b_{s} / M)⌉$ (seeks)

Cost of Hash-Join (Build Input in Memory):

$b_{r} + b_{s}$

B+-Tree Properties (Children): 1. Each node that is not a root or a leaf has between $⌈ n /2 ⌉$ and $n$ children.

B+-Tree Properties (Leaf Node Values): 1. A leaf node has between $⌈(n - 1) /2 ⌉$ and $n - 1$ values.

B+-Tree Properties (Root - Non-Leaf): 1. If the root is not a leaf, it has at least 2 children.

B+-Tree Properties (Root - Leaf): 1. If the root is a leaf, it can have between 0 and $(n - 1)$ values.

Link to original