Behind a query, something like the following occurs:

1. Query is parsed into an abstract syntax tree (AST)
2. From AST, decide the most efficient way to run the query + create immediate representation (IR)
3. Generate code (e.g. Java) that is equivalent to IR
4. Execution - compile the code and submit to cluster (e.g. Hadoop cluster)

Note that an RDBMS would just steps 1, 2, then execute directly.

Relational Algebra

Recall relational algebra operations:

• Selection ($\sigma$)

  

  • Simply involves performing a map-side filter (no reducer task)
    • Such operations can be pipelined
  • Can go as fast as HDFS can load/parse tuples
    • This is slower for text

• Projection ($\pi$)

  

  • Simply involves map-side tuple transformation (no reducer task)
  • Same performance as selection
  • Can be pipelined with selection
  • Need to remember column mappings
    • e.g. if column 4 → column 1 in projection

• Rename ($\rho$)

  • Renaming doesn’t matter at MapReduce level, as framework just sees tuples

• Union ($\cup$)

  

  • Hadoop MapReduce has a MultipleInputFile class - built-in union
  • Can have one mapper class per input file

• Difference ($-$)

  

  • Cannot be done on map side alone
  • Need MultipleInputFile
    • Each mapper has:
      • Key - entire tuple, also information about the mapper which sent it
      • Value - not used
      • Sort RHS tuples before equal LHS tuples
    • Reducers:
      • Remember last RHS tuple
      • Emit LHS tuples only if they do not equal the last RHS
    • Observe that this is simply a modification from merge sort

• Cartesian Product ($\times$)

  

  • e.g. SELECT table1...., table2.... FROM table1, table2
  • Generally avoid this, as you can end up with a huge amount of entries
    • e.g. 1 million record self-join ⇒ 1 trillion rows
  • if necessary:
    • Job setup looks at partitions and performs a cross
      • e.g. file1 has hdfs blocks 1, 2, 3, file2 has hdfs blocks a,b,c
      • Cross will be done with 1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c
    • Custom reader gets 2 files
      • e.g. reader given 3, a - read record 1 from 3, cross with all records of a, repeat
      • Mapper does nothing (can be pipelined)

• Aggregation

  • Reduce in MapReduce is often called “aggregation phase”
  • All SQL agregation functions are done on reduce side
    • e.g. count, sum, min, max

Relational Joins Performing efficient joins are one of the harder problems with query and schema design.

• Often main bottleneck in database operation - important to be good

Types of relationships in joins include one-to-one, one-to-many, and many-to-many - different strategies for each.