Optimization

Statistics in Catalogs

  • Number of Tuples
  • Number of Pages
  • Number of Distinct Key Values
  • Low/High Key Values
  • Index Tree Height
  • Number of Index Pages

Reduction Factors

  • 1 / Number of Distinct Key Values
  • 1 / Max (Number of Distinct Key Values in A, Number of Distinct Key Values in B)
  • Size of Selected Range in A / Total Range in A
  • Input Size * All Reduction Factors = Output Size
  • Join Output Size: Number of Tuples in A * Number of Tuples in B / Number of Distinct Key Values for Join Attributes

Cost Estimation

  • Only consider left-deep plans which can be fully pipelined.
  • Pass 1: Find best 1-relation plans for each relations. Enumerating all access methods, selectivities, etc.
  • Pass 2: Find best join of each 1-relation plan as outer to another relation, considering all join methods.
  • Pass 3: Find best join for remaining relations

Transactions, Concurrency and Recovery

Another good slides: