Query Processingمعالجة الاستعلامات
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- The basic steps of query processing and how query cost is measured.
- Translating SQL queries into relational algebra (query blocks).
- External sorting with merge sort and its cost.
- Catalog information, selectivity and the algorithms for selection operations.
- Materialization versus pipelining.
- Join algorithms: nested-loop, block nested-loop, indexed nested-loop and sort-merge join, with their costs.
أقسام الفصل
- 1Query processing steps and query costخطوات معالجة الاستعلام وتكلفته
- 2Translating SQL queries into relational algebraترجمة SQL إلى الجبر العلائقي
- 3External sorting: merge sortالفرز الخارجي: الفرز بالدمج
- 4Catalog information, scans and selectivityمعلومات الفهرس والمسح والانتقائية
- 5Algorithms for simple selection (S1–S5)خوارزميات الاختيار البسيط (S1–S5)
- 6Complex selections (S7–S10) and negationالاختيار المركب (S7–S10) والنفي
- 7Materialization and pipeliningالتجسيد وخط الأنابيب
- 8Nested-loop joinsالربط بالحلقات المتداخلة
- 9Sort-merge joinالربط بالفرز والدمج
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Basic steps in query processingخطوات معالجة الاستعلام
Query processing steps and query cost
- 1
Parsing and translation: the parser checks syntax and semantic, verifies relations, and translates the query into its relational algebra form.
- 2
Query optimization: choosing a suitable execution strategy — amongst all equivalent evaluation plans choose the one with lowest cost.
- 3
Evaluation: the query evaluation engine takes a query execution plan, executes it, and returns the answers.
Measures of query costقياس التكلفة
Query processing steps and query cost
- Query cost = total elapsed time to answer a query (disk access, CPU, network communication).
- Disk access is typically the predominant cost and relatively easy to estimate.
- For simplicity the cost measure is the number of block transfers from disk.
- Costs depend on the size of the buffer in main memory: more memory reduces the need for disk access.
Translating SQL into relational algebraالترجمة إلى الجبر العلائقي
Translating SQL queries into relational algebra
The basic unit that can be translated into the algebraic operators and optimized: a single SELECT-FROM-WHERE expression, with GROUP BY and HAVING if part of the block. Nested queries are separate query blocks.
Inner block
- SELECT MAX (SALARY) FROM EMPLOYEE WHERE DNO = 5
- ℱ MAX SALARY (σ DNO=5 (EMPLOYEE)) → C
Outer block
- SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > C
- π LNAME, FNAME (σ SALARY>C (EMPLOYEE))
External sorting: the sorting phaseالفرز الخارجي
External sorting: merge sort
- Sorting is needed in order by, join, union, intersection, distinct, …; quicksort for relations that fit in memory.
- External sorting: for large files on disk that do not fit in main memory — merge sort is a good choice.
- Two steps: a partial sort step (runs) and a merge step.
المسألة
Example (slide 12): nB = 5 blocks and file size b = 1024 blocks.
المعطيات
- nB (buffer pages)
- 5
- b (file blocks)
- 1024
الصيغة
nR = ⌈b / nB⌉; sorting cost = 2b
خطوات الحل
- nR = ⌈1024 / 5⌉ = 205
- Each initial run is 5 blocks
- Sorting phase reads b blocks and writes b blocks
النتيجة
205 initial sorted runs; the sorting phase costs 2b = 2048 block transfers. (Slide 12; the 2048 is 2b computed from slide 11.)
External sorting: merging and total costالدمج والتكلفة
External sorting: merge sort
min(nB − 1, nR) — one buffer block per run being merged, and one block for the merged result.
⌈log_dM(nR)⌉ — repeated passes until all runs are merged into one.
2b + 2b × nP = 2b (⌈log_dM(nR)⌉ + 1) — every pass reads and writes every block once.
- Example (slide 14): dM = min(5−1, 205) = 4; nP = ⌈log_4(205)⌉ = 4: 205 → 52 → 13 → 4 → 1 runs.
المسألة
Exercise (slide 17): a file of 10,000 pages and 3 buffer pages.
خطوات الحل
- Q1: nR = ⌈10000 / 3⌉ = 3334 runs in the first pass
- dM = min(3 − 1, 3334) = 2
- Q2: nP = ⌈log_2(3334)⌉ = 12 merge passes
- Q3: 2b (nP + 1) = 2 × 10000 × (12 + 1)
النتيجة
3334 runs; 12 passes; 260,000 I/O.
Catalog information and selectivityمعلومات الفهرس والانتقائية
Catalog information, scans and selectivity
| Symbol | Meaning (slides 18, 20) |
|---|---|
| r | # of records in the file |
| R | record size |
| b | # of blocks in the file |
| bfr | blocking factor |
| x | # of levels of a multilevel index |
| bI1 | # of first-level index blocks |
| d | # of distinct values of an attribute |
| sl | selectivity: records satisfying the condition ÷ total records |
| s | selection cardinality = sl × r |
Key attribute
- d = r
- sl = 1/r
- s = 1
Nonkey attribute (uniform distribution)
- sl = 1/d
- s = r/d
- File scan: search algorithms that locate and retrieve records fulfilling a selection condition. Index scan: search algorithms that use an index (condition on the index search-key).
- Cost estimate C = # of disk blocks scanned.
Simple selection: S1–S5خوارزميات الاختيار
| Algorithm | When | Cost C |
|---|---|---|
| S1 linear search |
| b |
| S1 linear search | Equality on a key attribute | b/2 if found, else b |
| S2 binary search | Equality on the attribute the file is ordered on | ⌈log2 b⌉ |
| S3 primary index | Equality on a key | x + 1 |
| S3 hash index | Equality on a key |
|
| S4 primary index | Range on a key (>, ≥, <, ≤) | x + b/2 |
| S5 clustered index | Equality on a nonkey | x + ⌈s/bfr⌉ |
- S2 needs an equality comparison on the attribute on which the file is ordered (blocks stored contiguously).
- S3 primary index: 1 more block than the # of index levels.
- S4: find the first matching record with the index, then retrieve all subsequent (or preceding) records of the ordered file.
- S5: records are on consecutive blocks.
Complex selections and negationالاختيار المركب والنفي
Complex selections (S7–S10) and negation
- S7Conjunctive, one indexPick the condition and algorithm with the least cost; test the other conditions after fetching the tuple into memory.
- S8Conjunctive, composite indexEquality conditions on two or more attributes with a composite index (or hash structure) on the combined field: use it directly.
- S9Conjunctive, intersection of record pointersOne index per condition; intersect the sets of record pointers, then fetch the records; test unindexed conditions in memory.
- S10Disjunctive, union of identifiersOnly if **all** conditions have indices (otherwise linear scan); take the union of the record pointers.
Use a linear scan on the file; if very few records satisfy ¬θ and an index applies, find them with the index and fetch them.
Materialization vs pipeliningالتجسيد وخط الأنابيب
Materialization and pipelining
| Materialization | Pipelining | |
|---|---|---|
| How | One operation at a time, from the lowest level | Several operations simultaneously |
| Intermediate results | Stored as temporary relations | Passed directly to the next operation |
| Cost | Writing temporary files to disk is time consuming | Much cheaper: no temporary relation on disk |
| Limits | لا تذكر الشرائح شيئًا هنا. | Not always possible (e.g., sort, hash-join) |
Nested-loop joinالربط بالحلقات المتداخلة
Join algorithms (slide 34)
- Nested-loop join
- Block nested-loop join
- Indexed nested-loop join
- Merge-join
- For each tuple tr of the outer relation r, test every tuple ts of the inner relation s; add matching pairs to the result.
- Requires no indices and can be used with any kind of join condition, but is expensive: it examines every pair of tuples.
- Worst case: C = bR + (rR × bS) + bRS. If the smaller relation fits entirely in memory, use it as the inner relation: bR + bS + bRS.
المسألة
Slide 40: customer (10,000 records, 400 blocks) ⋈ depositor (5,000 records, 100 blocks), worst case.
خطوات الحل
- depositor as outer: 5000 × 400 + 100
- customer as outer: 10,000 × 100 + 400 (printed "1000 × 100")
- smaller relation (depositor) in memory: 100 + 400
النتيجة
2,000,100; 1,000,400; 500 block transfers (each + bRS).
Block nested-loop and indexed nested-loop joinالحلقات على الكتل والمفهرسة
Nested-loop joins
Block nested-loop join
- Every block of the inner relation is paired with every block of the outer relation
- Worst case: C = bR + (bR × bS) + bRS
- Smaller relation in memory as inner: bR + bS + bRS
- If neither fits in memory, choose the smaller relation for the outer loop
Indexed nested-loop join (J2)
- Index lookups replace file scans when an index exists on the inner relation's join attribute
- For each outer tuple, use the index to retrieve matching inner tuples
- Indices on both: use the relation with fewer tuples as the outer
- Primary index: bR + (rR × (x + 1)) + bRS
المسألة
Slides 46–47: depositor (outer, 5,000 records, 100 blocks) ⋈ customer (400 blocks) with a primary B+-tree index on customer-name: height 4 + 1 data access = 5.
خطوات الحل
- Block nested loops (worst case): 100 + 100 × 400
- Indexed nested loops: 100 + 5000 × 5
النتيجة
40,100 vs 25,100 block accesses (each + bRS).
Sort-merge joinالربط بالفرز والدمج
- 1
Sort both relations on their join attribute (if not already sorted).
- 2
Merge the sorted relations (like the merge stage of external sort-merge), matching every pair with the same join value (duplicates).
- Can be used only for equi-joins and natural joins.
- Each block needs to be read only once: bR + bS + sorting cost (if not sorted) + bRS.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Query processing steps and query costخطوات معالجة الاستعلام وتكلفته
- Translating SQL queries into relational algebraترجمة SQL إلى الجبر العلائقي
- External sorting: merge sortالفرز الخارجي: الفرز بالدمج
- Catalog information, scans and selectivityمعلومات الفهرس والمسح والانتقائية
- Algorithms for simple selection (S1–S5)خوارزميات الاختيار البسيط (S1–S5)
- Complex selections (S7–S10) and negationالاختيار المركب (S7–S10) والنفي
- Materialization and pipeliningالتجسيد وخط الأنابيب
- Nested-loop joinsالربط بالحلقات المتداخلة
- Sort-merge joinالربط بالفرز والدمج