[SOLVED] CS Sorting

Sorting

>>
Sorting

The Sort Operation

Two-way Merge Sort

Comparison for Sorting

Cost of Two-way Merge Sort

n-Way Merge Sort

Cost of n-Way Merge Sort

Sorting in PostgreSQL

COMP9315 21T1 Sorting [0/14]

>>
The Sort Operation

Sorting is explicit in queries only in the order by clause

select * from Students order by name;

Sorting is used internally in other operations:

eliminating duplicate tuples for projection

ordering files to enhance select efficiency

implementing various styles of join

forming tuple groups in group by

Sort methods such as quicksort are designed for in-memory data.

For large data on disks, need external sorts such as merge sort.

COMP9315 21T1 Sorting [1/14]

<< >>
Two-way Merge Sort

Example:

COMP9315 21T1 Sorting [2/14]

<< >>
Two-way Merge Sort (cont)

Requires at least three in-memory buffers:

Assumption: cost of Merge operation on two in-memory buffers 0.

COMP9315 21T1 Sorting [3/14]

<< >>
Comparison for Sorting

Above assumes that we have a function to compare tuples.

Needs to understand ordering on different data types.

Need a function tupCompare(r1,r2,f) (cf. Cs strcmp)

int tupCompare(r1,r2,f)
{
if (r1.f < r2.f) return -1; if (r1.f > r2.f) return 1;
return 0;
}

Assume =, <, > are available for all attribute types.

COMP9315 21T1 Sorting [4/14]

<< >>
Comparison for Sorting (cont)

In reality, need to sort on multiple attributes and ASC/DESC, e.g.

example multi-attribute sort
select * from Students
order by age desc, year_enrolled

Sketch of multi-attribute sorting function

int tupCompare(r1,r2,criteria)
{
foreach (f,ord) in criteria {
if (ord == ASC) {
if (r1.f < r2.f) return -1; if (r1.f > r2.f) return 1;
}
else {
if (r1.f > r2.f) return -1;
if (r1.f < r2.f) return 1;} } return 0;}COMP9315 21T1 Sorting [5/14]<< >>
Cost of Two-way Merge Sort

For a file containing b data pages:

require ceil(log2b) passes to sort,

each pass requires b page reads, b page writes

Gives total cost: 2.b.ceil(log2b)

Example: Relation with r=105 and c=50
b=2000 pages.

Number of passes for sort: ceil(log22000) = 11

Reads/writes entire file 11 times! Can we do better?

COMP9315 21T1 Sorting [6/14]

<< >>
n-Way Merge Sort

Initial pass uses: B total buffers

Reads B pages at a time, sorts in memory, writes out in order

COMP9315 21T1 Sorting [7/14]

<< >>
n-Way Merge Sort (cont)

Merge passes use:
n = B-1 input buffers,
1 output buffer

COMP9315 21T1 Sorting [8/14]

<< >>
n-Way Merge Sort (cont)

Method:

// Produce B-page-long runs
for each group of B pages in Rel {
read B pages into memory buffers
sort group in memory
write B pages out to Temp
}
// Merge runs until everything sorted
numberOfRuns = ceil(b/B)
while (numberOfRuns > 1) {
// n-way merge, where n=B-1
for each group of n runs in Temp {
merge into a single run via input buffers
write run to newTemp via output buffer
}
numberOfRuns = ceil(numberOfRuns/n)
Temp = newTemp // swap input/output files
}

COMP9315 21T1 Sorting [9/14]

<< >>
Cost of n-Way Merge Sort

Consider file where b = 4096, B = 16 total buffers:

pass 0 produces 256 16-page sorted runs

pass 1
performs 15-way merge of groups of 16-page sorted runs

produces 18 240-page sorted runs (17 full runs, 1 short run)

pass 2
performs 15-way merge of groups of 240-page sorted runs

produces 2 3600-page sorted runs (1 full run, 1 short run)

pass 3
performs 15-way merge of groups of 3600-page sorted runs

produces 1 4096-page sorted runs

(cf. two-way merge sort which needs 11 passes)

COMP9315 21T1 Sorting [10/14]

<< >>
Cost of n-Way Merge Sort (cont)

Generalising from previous example

For b data pages and B buffers

first pass: read/writes b pages, gives b0 = ceil(b/B) runs

then need ceil(lognb0) passes until sorted, where n = B-1

each pass reads and writes b pages (i.e. 2.b page accesses)

Cost = 2.b.(1 + ceil(lognb0)), where b0 and n are defined above

COMP9315 21T1 Sorting [11/14]

<< >>
Sorting in PostgreSQL

Sort uses a merge-sort (from Knuth) similar to above:

backend/utils/sort/tuplesort.c

include/utils/sortsupport.h

Tuples are mapped to SortTuple structs for sorting:
containing pointer to tuple and sort key

no need to reference actual Tuples during sort

unless multiple attributes used in sort

If all data fits into memory, sort using qsort().

If memory fills while reading, form runs and do disk-based sort.

COMP9315 21T1 Sorting [12/14]

<< >>
Sorting in PostgreSQL (cont)

Disk-based sort has phases:

divide input into sorted runs using HeapSort

merge using N buffers, one output buffer

N = as many buffers as workMem allows

Described in terms of tapes (tape sorted run)

Implementation of tapes: backend/utils/sort/logtape.c

COMP9315 21T1 Sorting [13/14]

<< Sorting in PostgreSQL (cont)Sorting comparison operators are obtained via catalog (in Type.o):// gets pointer to function via pg_operatorstruct Tuplesortstate { … SortTupleComparator … };// returns negative, zero, positiveApplySortComparator(Datum datum1, bool isnull1,Datum datum2, bool isnull2,SortSupport sort_helper);Flags in SortSupport indicate: ascending/descending, nulls-first/last.ApplySortComparator() is PostgreSQL’s version of tupCompare()COMP9315 21T1 Sorting [14/14]Produced: 1 Mar 2021