Title: Theory / Important / CS / Algo / Database / Database System Concept 6 - McGraw Hill+27{ / 12 Query processing

Name: A secondary index
Definition: A way to quickly access data that is not the primary key
Page: https://aws.amazon.com/getting-started/hands-on/purpose-built-databases/dynamodb/
Context: AWS DynamoDB
Extra: Not to confound with Search Key

Name: Query processing
Definition: Parsing
Page: 537
Chapter: 12
Definition2: Translation
Conjdef: In this order
Definition3: optimization
Intuition: the range of activities involved in extracting data from a database
Definition4: evaluation

Name: An evaluation primitive
Definition: A relational-algebra operation annotated with instructions on how to evaluate
Page: 539
Chapter: 12

Name: Query execution plan for Q
Definition: A sequence of primitive operations that can be used to evaluate the query Q
Page: 539
Chapter: 12
Variables: Q
Name2: Query evaluation plan for Q

Name: The query-execution engine
Definition: A software executing query execution plan
Page: 539
Chapter: 12

Name: Query optimization
Definition: The process ensuring that queries are executed as efficiently as possible
Page: 539
Chapter: 12

Name: A pipeline
Definition: A process where the output of an operation is not stored but directly used as the input of the next operation
Page: 539
Chapter: 12
Context: query evaluation

Question: How to measure cost of a query evaluation
Answer: number of block transfer
Page: 540
Chapter: 12
Context: query evaluation
Answer2: number of disk seeks

Name: The response time of P
Definition: The time it takes from emitting the query up to receiving its answer
Page: 541
Chapter: 12
Variables: Q a query
P an evaluation plan for Q

Name: The resource consumption of P
Definition: How much resource of each kind (bandwidth, seek) P takes
Page: 541
Chapter: 12
Variables: Q a query
P an evaluation plan for Q

Name: Primary index
Definition: an index that allows the records of a file to be read in an order that corresponds
to the physical order in the file
Page: 542
Chapter: 12
Section: 3.1
Context: query processing
Notation: A1
Name2: Clustering index

Name: Access paths
Definition: a path
through which data can be located and accessed
Page: 542
Chapter: 12
Section: 3.1
Context: query processing
Name2: Index structures

Name: Index scan
Definition: Search algorithms that use an index
Page: 542
Chapter: 12
Section: 3.1
Context: query processing

Page: 542
Implementation: Direct access using the path, when the constraint uses an equality on a primary key
Section: 3.1
Chapter: 12
Name: Primary index, equality on key
Time complexity: (height of the index + 1)(\(t_\tau + t_S\))
Context: query processing
Abbreviation: A2

Name: Time for a block transfer
Page: 540
Chapter: 12
Section: 3.1
Context: query processing
Notation: \(t_T\)

Name: Time for a disk seek
Page: 540
Chapter: 12
Section: 3.1
Context: query processing
Notation: \(t_S\)

Page: 540
Implementation: the system scans each file block and tests all records to see whether they satisfy the selection condition
Section: 3.1
Chapter: 12
Name: Linear search
Time complexity: Worst case \(t_S+\mathtt{number of block in file}\times t_T\)
If equality on a key, then it halts as soon as one result is found, which divide average search time by two
Context: query processing
Abbreviation: A1

Page: 540
Section: 3.1
Chapter: 12
Name: Primary index, equality on nonkey
Time complexity: \(\text{height of the index} \times (t_T+t_S) + b\times t_T\)
Context: query processing
Abbreviation: A3

Page: 540
Section: 3.1
Chapter: 12
Name: Secondary index, equality
Time complexity: \((\text{height of the index}+1) \times (t_T+t_S)\)
Context: query processing
Abbreviation: A4

Page: 544
Section: 3.1
Chapter: 12
Name: primary index, comparison
Time complexity: \(\text{height of the index} \times (t_T+t_S) + b\times t_T\)
Context: query processing
Abbreviation: A5

Page: 545
Implementation: Seach if one or multiple conjunct uses selectiong according to an index. If so uses the cheapest algorithm used for one of those index, then filter according to other conjuncts
Section: 3.3
Chapter: 12
Name: conjunctive selection using one index
Time complexity: Same complexity as the underlying algorithm
Context: query processing
Abbreviation: A7

Page: 545
Implementation: check whether there is some conjunct taken together specify one of the index of the table. If so, query with A2, A3 or A4 on this index, then filter
Section: 3.3
Chapter: 12
Name: conjunctive selection using composite index
Time complexity: Same complexity as the underlying algorithm
Context: query processing
Abbreviation: A8

Page: 546
Implementation: todo
Section: 3.3
Chapter: 12
Name: conjunctive selection by intersection of identifiers
Time complexity: sume of the costs of the individual index scans plus the cost of retrieving the records in the intersection of the retrieved lists of pointers
Context: query processing
Abbreviation: A9

Page: 546
Implementation: each index is scanned
for pointers to tuples that satisfy the individual condition. The union of all
the retrieved pointers yields the set of pointers to all tuples that satisfy the
disjunctive condition. We then use the pointers to retrieve the actual records.
Section: 3.3
Chapter: 12
Name: disjunctive selection by union of identifiers
Context: query processing
Assuming: access paths are available on all the conditions of a disjunctive selection
Abbreviation: A10

Name: External sorting
Definition: Sorting of relations that do not fit in memory
Page: 547
Chapter: 12
Section: 4.1
Context: query processing

Page: 547
Implementation: Iterate over all data on disk. Put as much data in memory as possible, sort it, write it to file.
Section: 4.1
Chapter: 12
Variables: B the number of blocks to sort
M the number of blocks in the main-memory buffer available for sorting
N=M/B
Name: external sort–merge
Context: query processing
Implementation2: Do a N-merge of the sorted block

Page: 547
Implementation: merge all sorted lists, by iterating over all of them to find the smallest input not yet sorted (uses a priority queue for this) and output this smallest element in file
Section: 4.1
Chapter: 12
Variables: M the number of blocks in the main-memory buffer available for sorting
Name: N-way merge
Returns: the union of the input, sorted
Context: query processing
Input: N sorted lists

Page: 547
Implementation: sort the M first list using N-way merge. Repeat until there is a single list
Section: 4.1
Chapter: 12
Variables: M the number of blocks in the main-memory buffer available for sorting
Name: External N-way merge
Returns: the union of the input, sorted
Context: query processing
Input: N sorted lists

Name: An equi-join
Definition: An inner-join of tables T and U on an equality T.a = U.b
Page: 549
Chapter: 12
Section: 5
Context: query processing

Page: 550
Implementation: for each tuple t_r in r:
  for each tuple t_s in s:
    if theta(t_r, t_s):
      add (t_r, t_s) to output
Section: 5.1
Chapter: 12
Variables: r, s tables
\(n_r\) and \(n_s\) the sizes of r and s
\(b_r\) and \(b_s\) the number of blocks used for r and s
\(\theta\) a predicate on r and s that is executed in time \(t_\theta\)
Name: nested-loop join
Time complexity: \(t_S +
b_r\times t_T +
n_r\times \left(
  t_S +
  b_s\times t_T +
  n_s\times t_\theta
\right)
\)
Returns: result of \(r\join_\theta s\)

Name: The outer relation
Page: 550
Chapter: 12
Section: 5.1
Variables: r, s tables
\(\theta\) a predicate on r and s
Context: \(r\join_\theta s\) nested-loop join
Etymology: outer loop in the implementation

Name: The inner relation
Page: 550
Chapter: 12
Section: 5.1
Variables: r, s tables
\(\theta\) a predicate on r and s
Context: \(r\join_\theta s\) nested-loop join
Etymology: inner loop in the implementation

Question: What heuristic to use to choose the inner and the outer relations
Answer: Use the relation that fit on the less number of block as inner relation
Page: 550
Chapter: 12
Section: 5.1
Variables: r, s tables
\(\theta\) a predicate on r and s
Context: \(r\join_\theta s\) nested-loop join

Page: 551
Implementation: for each block B_r of r:
  for each block B_s of s:
    for each tuple t_r in B_r:
      for each tuple t_s in B_s:
        if theta(t_r, t_s):
          return (t_r, t_s) to output
Section: 5.2
Chapter: 12
Variables: r, s tables
\(n_r\) and \(n_s\) the sizes of r and s
\(b_r\) and \(b_s\) the number of blocks used for r and s
\(\theta\) a predicate on r and s that is executed in time \(t_\theta\)
\(t_B\) the number of element in a block
Name: block nested-loop join
Time complexity: \(t_S +
b_r\times \left(t_S +
  b_s\times \left(
    t_T +
    t_B^2\times t_\theta
  \left)
\right)
\)
Returns: result of \(r\join_\theta s\)
Intuition: Put all pair of blocks in memory and iterate over all elements in memory

Page: 551
Implementation: for each tuple t_r in r:
  lookup the key in s determined by \(\theta\):
    if theta(t_r, t_s):
      add (t_r, t_s) to output
Section: 5.2
Chapter: 12
Variables: r, s tables
\(n_r\) and \(n_s\) the sizes of r and s
\(b_r\) and \(b_s\) the number of blocks used for r and s
\(\theta\) a predicate on r and s that is executed in time \(t_\theta\)
Name: indexed nested-loop join
Returns: result of \(r\join_\theta s\)
Assuming: \(\theta\) specify a key on \(s\) that may depends on \(r\)

Page: 551
Implementation: iterate over the values v used in the equality of \(\theta\), in increasing order:
  for each pair (t_r, t_s) satisfying \(\theta\):
    add the pair to the output
Section: 5.4
Chapter: 12
Variables: r, s tables
\(n_r\) and \(n_s\) the sizes of r and s
\(b_r\) and \(b_s\) the number of blocks used for r and s
\(\theta\) a predicate on r and s that is executed in time \(t_\theta\)
Name: merge-join
Returns: result of \(r\join_\theta s\)
Assuming: \(r\) and \(s\) are sorted on the keys used in \(\theta\) equality
Name2: sort-merge-join

Page: 551
Implementation: iterate over entry t_r of r in order:
  search elements t_s of s satisfying the equalities of \(\theta\):
     if \(\theta\)(t_r, t_r):
       add the pair to the output
Section: 5.4
Chapter: 12
Variables: r, s tables
\(n_r\) and \(n_s\) the sizes of r and s
\(b_r\) and \(b_s\) the number of blocks used for r and s
\(\theta\) a predicate on r and s that is executed in time \(t_\theta\)
Name: Hybrid merge-join
Returns: result of \(r\join_\theta s\)
Assuming: \(r\) is sorted according to some elements used in \(\theta\)'s equality, but not \(s\)
Intuition: If some element \(t_s\) is used for mulitple relation \(t_r\), they'll be needed at the same time and so only fetched once