Database Systems

Query Processing in DBMS

Data storage in DBMS

File Organisations

Index

Hash-based Index

Tree-based index

Query evaluation

Operator evaluation techniques

Access paths

External Sorting

External Merge Sort

ExternalSort(file)
    # given a file on disk, sort it using three buffer pages
    # produce runs B pages long: Pass 0
    Read B pages into memory
    Sort them
    Write out a run
    # Merge (B-1) runs at a time to produce longer runs, until only
    # one run (containing all input records) remains
    while number of runs at end of previous pass > 1:
      # pass i = 1, 2, ...
      while there are runs to be merged from previous pass:
          choose next (B-1) runs from previous pass
          read each run into an input buffer (page by page)
          merge runs and write to output buffer
          write output buffer to disk page by page
end ExternalSort

Overview of relational operator algorithms

Selection

Projection

Evaluating Relational Operators


Edit this page.