ADBMS Flow

ADBMS formulas

2. Basic Cost Estimation:

   $b\ast t_T+S\ast 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)

3. Linear Search (A1) - General Case:

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

4. Linear Search (A1) - Selection on Key Attribute:

   Cost = $(b_r/2)+1$

5. Primary Index, Equality on Key (A2):

   Cost = $(h_i+1)\ast (t_T+t_S)$ (where $h_i$ is the height of the index)

6. Primary Index, Equality on Nonkey (A3):

   Cost = $h_i\ast (t_T+t_S)+t_S+t_T\ast b$ (where b is the number of blocks containing matching records)

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

   Cost = $(h_i+1)\ast (t_T+t_S)$

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

   Cost = $(h_i+n)\ast (t_T+t_S)$ (where n is the number of matching records)

9. Number of Merge Passes (External Sort-Merge):

   $\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil$ (where M is memory size, $b_b$ is buffer block per run and $b_r$ blocks for relation r)

10. Total Block Transfers (External Sort-Merge):

    $b_r\ast (2\ast \lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil +1)$

11. Total Number of Seeks (External Sort-Merge):

    $2\lceil b_r/M\rceil +\lceil b_r/b_b\rceil \ast (2\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_r/M)\rceil -1)$

12. Nested-Loop Join (Worst Case Block Transfers):

    $n_r\ast 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)

13. Nested-Loop Join (Worst Case Seeks):

    $n_r+b_r$

14. Nested-Loop Join (Smaller Relation in Memory):

    $b_r+b_s$ (block transfers and 2 seeks)

15. Block Nested-Loop Join (Worst Case):

    $b_r\ast b_s+b_r$ (block transfers) + $2\ast b_r$ (seeks)

16. Block Nested-Loop Join (Best Case):

    $b_r+b_s$ (block transfers) + 2 (seeks)

17. Improved Block Nested-Loop Join:

    Cost = $\lceil b_r/(M-2)\rceil \ast b_s+b_r$ (block transfers) + $2\lceil b_r/(M-2)\rceil$ (seeks)

18. Indexed Nested-Loop Join:

    Cost = $b_r\ast (t_T+t_S)+n_r\ast c$ (where c is the cost of traversing the index and fetching matching tuples)

19. Merge-Join Cost:

    $b_r+b_s$ (block transfers) + $\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil$ (seeks) + (cost of sorting if relations are unsorted)

20. Hash function mapping

    $h$ maps $JoinAttrs$ values to $\{0,1,...,n\}$

21. Partitioning tuples Each tuple $t_r\in r$ is put in partition $r_i$ where $i=h(t_r[JoinAttrs])$. Each tuple $t_s\in s$ is put in partition $s_i$, where $i=h(t_s[JoinAttrs])$.

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

    $n=\lceil b_s/M\rceil \ast f$ (where f is a fudge factor, typically around 1.2)

23. Number of Passes for Recursive Partitioning (Hash-Join): $\lceil lo{g}_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil$

24. Cost of Hash-Join (No Recursive Partitioning):

    $3(b_r+b_s)+4\ast n_h$ (block transfers) + $2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )$ (seeks)

25. Cost of Hash-Join (With Recursive Partitioning):

    $2(b_r+b_s)\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil +b_r+b_s$ (block transfers) + $2(\lceil b_r/b_b\rceil +\lceil b_s/b_b\rceil )\lceil {\log }_{\lfloor M/b_b\rfloor -1}(b_s/M)\rceil$ (seeks)

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

    $b_r+b_s$

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

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

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

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

Link to original

[[8. Query Processing.pdf#page=24&rect=58,141,533,626|]]

8. Query Processing, p.4

Questions

15, p.1

15, p.2

15, p.2

15, p.4

16, p.4

16, p.5

8. Query Processing, p.10