Year: 1989

Authors: DJ DeWitt, S Ghandeharizaheh, DA Schneider et al

Summary

First, all relations are horizontally partitioned across multiple disk drives enabling relations to be scanned in parallel. Second, novel parallel algorithms based on hashing are used to implement the complex relational operators such as join and aggre- gate functions. Third, dataflow scheduling techniques are used to co- ordinate multioperator queries. By using these techniques it is possible to control the execution of very complex queries with minimal coordination-a necessity for configurations involving a very large number of processors.

Hardware Architecture

Shared-nothing!

  • nothing to prevent the architecture from scaling to thousands of processors
  • use off-the-shelf mass storage technology
  • no need for custom hardware

Omit more hardware details that I don’t understand.

Software Architecture

  • Storage Organizations: horizontal partition: round robin, hashed, and range partitioned.
  • Process Structure:

example dataguide * Query Execution: an ad-hoc query language and an embedded query language interface in which queries can be embedded in a C program (templates). * Operator and Process Structure: iterators so the process acts like it’s for non-distributed system. * Operating and Storage System: built on NOSE (not going to go to details)

Query processing algorithms

  • Selection Operator: trivial
  • Join Operator: applying a hash function to the join attribute of each tuple.
    • they found that the Hybrid hash join almost always provides the best performance. It works like the follows
      1. Uses a hash function to partition the inner (smaller) relation R into N buckets.
      2. first bucket are used to build an in-memory hash table while the remaining N - 1buckets are stored in temporary files
      3. During the second phase, relation S is partitioned using the hash function from step 1. Again, the last N - 1buckets are stored in temporary files while the tuples in the first bucket are used to immediately probe the in-memory hash table built during the first pass.
      4. and the rest
  • Aggregate Operations: each processor compute its piece of the result in parallel.
  • Update Operators: standard

Transaction and failure management

  • Concurrency Control: 2PL
    • Deadlock? Gamma uses a centralized deadlock detection algorithm.
  • Recovery Architecture and Log Manager: log records are sent by the query processors to one or more log managers (each running on a separate processor) which merges the log records it receives to form a single log stream.
  • Failure Management: chained declustering: both a primary and backup copy of each relation. The basic idea is that the backup copies are scattered around machines. It’s nice because:
    • it off loads the work to different machines as opposed all on one.
    • the reassignment of active fragments incurs neither disk I/O nor data movement.

Key Features

  • “All relations are horizontally partitioned across multiple disk drives enabling relations to be scanned in parallel.”
  • “novel parallel algorithms based on hashing are used to implement the complex relational operators such as join and aggregate functions.”
  • “dataflow scheduling techniques are used to coordinate multioperator queries.”
  • Pioneering shared-nothing architecture with commodity hardware.