Cost-Based Query Optimization, Composite Indexing, and Physical Database Design
Cost-Based Query Optimization: Table Scan vs. Unclustered B+ Tree
Scenario Parameters:
Total database records: student records.
Attribute:
grade, uniformly distributed between and .Cost metric: Disk page I/O transfers.
Full table scan cost: Constant at disk pages.
Evaluation of Query:
grade > 70:Selectivity Calculation:
Qualifying Record Count:
I/O Cost Analysis:
Table Scan Cost: page I/Os.
Unclustered B+ Tree Cost: In the worst-case scenario, each qualifying record resides on a distinct disk page, resulting in page I/Os.
Optimizer Decision: The query optimizer selects the full table scan because .
Evaluation of Query:
grade > 98:Selectivity Calculation:
Qualifying Record Count:
I/O Cost Analysis:
Table Scan Cost: page I/Os.
Unclustered B+ Tree Cost: page I/Os.
Optimizer Decision: The optimizer chooses the unclustered B+ tree because .
Derivation of Optimizer Threshold for Generic Query:
grade > x:Cost of unclustered B+ tree:
Cost of full table scan:
Break-even equality:
Decision Boundaries:
If : The table scan is more efficient than the unclustered B+ tree.
If : The unclustered B+ tree is more efficient than the table scan.
If : Both access methods incur identical costs ( page I/Os).
Composite Search Keys
Definition & Lexicographical Ordering:
A composite search key contains multiple attributes within a single index (e.g.,
(age, salary)).Entries are ordered primarily by the first column (
age). The second column (salary) serves strictly as a tie-breaker for identical values of the primary column.An index structured as
(age, salary)differs fundamentally from an index structured as(salary, age). In(salary, age), entries are ordered primarily bysalaryand secondarily byage.
Query Match Evaluation for Equality Predicates:
Query:
WHERE age = 30 AND salary = 4000.Single-Attribute Index on
age: The search traverses the tree toage = 30. It must retrieve all data entries whereage = 30and fetch the underlying data pages to filter out tuples wheresalary eq 4000.Composite Index on
(age, salary)or(salary, age): Navigates directly to the specific data entry matching both values(30, 4000), retrieving the precise pointer without scanning unnecessary entries.For strict equality predicates on both fields, an index on
(age, salary)and an index on(salary, age)offer identical operational efficiency.Both Hash indexes and B+ trees support multi-attribute equality conditions.
Query Match Evaluation for Range Predicates:
Query:
WHERE age BETWEEN 20 AND 30 AND salary BETWEEN 3000 AND 5000.Index implementation must be a B+ tree; Hash indexes cannot process range queries.
Because range queries return substantial result sets, a clustered index is vital to prevent catastrophic random I/O overhead.
Query:
WHERE age = 30 AND salary BETWEEN 3000 AND 5000.Using
(age, salary): The search navigates directly toage = 30, locating a contiguous block of data entries ordered bysalaryfrom to .Using
(salary, age): The index must scan all entries across the salary range , checking each individual entry to see ifage = 30.Design Principle: When combining equality and range predicates, the index must lead with the equality attribute (the more selective predicate) to minimize search space.
Trade-offs of Composite Indexes:
Storage Overhead: Data entries are wider (e.g., storing
(age, salary, record_id)requires more bytes per leaf entry than(age, record_id)).Maintenance Cost: The index requires updates whenever any of the indexed composite attributes change.
Index-Only Evaluation Plans
Core Architectural Concept:
An index-only plan (covering index) allows a query to be answered entirely from the data entries stored inside the index leaf nodes without fetching actual data records from underlying relation pages.
Eliminates all data page I/O reads.
Clustering Irrelevance in Covering Indexes:
When an index-only plan executes, whether the index is clustered or unclustered is physically irrelevant because the execution engine never dereferences pointers to underlying data pages.
Database Design Rule: If an index enables an index-only plan, configure it as an unclustered index. Because a table can have at most one clustered index, this saves the single clustered index slot for an access path that genuinely requires physical clustering.
Demonstration Queries:
Query 1:
SELECT department_number FROM employee WHERE age > 40Clustered index on
age: Scans leaf nodes forage > 40, then follows record pointers to fetch data pages to readdepartment_number.Unclustered composite index on
(age, department_number): Leaf entries store bothageanddepartment_number. The system findsage > 40in the index and extractsdepartment_numberdirectly from the leaf nodes. Zero data pages are read.
Query 2:
SELECT department_number, COUNT(*) FROM employee WHERE age > 20 GROUP BY department_numberPredicate
age > 20has virtually zero selectivity (nearly all employees satisfy this condition).An unclustered composite B+ tree index on
(department_number, age)allows grouping and condition evaluation completely inside the index tree.
Query 3:
SELECT department_number, MIN(salary) FROM employee GROUP BY department_numberAn unclustered composite B+ tree on
(department_number, salary)provides an index-only evaluation plan.Because entries are ordered by
department_numberand thensalary, the minimum salary for each department is the very first entry within each department group.
Query 4:
SELECT AVG(salary) FROM employee WHERE age = 25 AND salary BETWEEN 3000 AND 5000An unclustered composite B+ tree on
(age, salary)isolatesage = 25, extracts the salary range , and calculates the aggregate directly from leaf node data entries.
Workload-Driven Physical Database Design
Architectural Invariants & Constraints:
Clustering Upper Bound: A database relation can maintain exactly one clustered index because physical records on disk can only be arranged in a single physical sort order.
Unique Key Lookups: When querying an attribute that is a primary or unique candidate key (e.g.,
WHERE ID = constant), the query matches at most one record. An unclustered index performs with the exact same data I/O cost ( page access) as a clustered index. Therefore, unique key lookups should never consume the relation's single clustered index.Covering Indexes: Queries requiring non-clustered range evaluations should be converted to index-only plans via unclustered composite indexes whenever feasible.
Comprehensive Workload Case Study:
Relation Schema:
Student(ID, name, GPA, credit, year)Workload Queries:
:
SELECT ID FROM Student WHERE GPA > x AND credit < y:
SELECT ID, name, GPA FROM Student WHERE year > w:
SELECT * FROM Student WHERE ID = a
Evaluation of Potential Indexing Configurations:
Proposal 1 (Invalid): Clustered B+ tree on
(GPA, credit)for , clustered B+ tree onyearfor , and clustered B+ tree onIDfor .Defect: Invalid. A table cannot support three clustered indexes.
Proposal 2 (Inefficient): Unclustered B+ tree on
(GPA, credit), unclustered B+ tree onyear, clustered Hash index onID.Defect: Wastes the single clustered index allocation on a unique key lookup () where clustering yields zero benefit.
Proposal 3 (Sub-optimal Covering Attempt): Index on
(year, ID)for .Defect: Does not cover because
nameandGPAare omitted; data pages would still require fetching.
Optimal Workload Index Design:
For (
SELECT * WHERE ID = a):Structure: Unclustered Hash Index on
ID.Justification: Equality match on a key attribute returns at most one record. Unclustered Hash gives access. It cannot be index-only due to
SELECT *.
For (
SELECT ID, name, GPA WHERE year > w):Structure: Clustered B+ Tree on
year.Justification: Range query returning many records. An index-only configuration would require an excessively wide composite key
(year, ID, name, GPA), producing unacceptable storage and update costs. Allocating the table's single clustered index here optimizes the retrieval of multi-record ranges.
For (
SELECT ID WHERE GPA > x AND credit < y):Structure: Unclustered Composite B+ Tree on
(GPA, credit, ID).Justification: Operates as an index-only plan. Attribute order must place search attributes
(GPA, credit)first, with projected attributeIDat the end. Since no data pages are accessed, it remains unclustered.
Storage, Buffer Management, and Indexing Review
Buffer Manager Fundamentals:
Buffer pool structure and page frame allocation.
Buffer replacement policies: Least Recently Used (LRU) versus Most Recently Used (MRU).
Record and Page Formats:
Fixed-length record layout versus variable-length record layout (using attribute offsets).
Slotted page architecture for managing variable-length records and record identification within pages via slot directories.
Tree-Structured Indexes (B+ Trees):
Occupancy Invariant: Every node must remain at least half full ( capacity) at all times, with the root node being the sole exception.
Search Operation: Root-to-leaf traversal using key comparisons.
Insertion Algorithm: Traversal to target leaf node. If over capacity, examine the immediate sibling node for redistribution; if redistribution cannot be accommodated, split the node and push the separator key to the parent node.
Deletion Algorithm: Traversal to target entry. If node falls below occupancy, attempt redistribution with adjacent sibling; if adjacent sibling is also at half-capacity, merge the nodes and remove the separator key from the parent.
Hash-Based Indexing:
Suitable exclusively for equality lookups.
Representation alternatives for data entries :
Alternative 1: Data record itself is stored inside the index leaf page.
Alternative 2: Data entry contains
(key, Record_ID).Alternative 3: Data entry contains
(key, list of Record_IDs).
Questions and Discussion
Question: What does the label say after the index diagram on the right?
Response: The diagram on the right represents an index on
agealone.
Question: Would an index on
(salary, age)yield a different outcome than(age, salary)for the queryWHERE age = 30 AND salary = 4000?Response: For this specific query, both yield identical performance. Because both conditions are equalities, either ordering resolves directly to the matching entry.
Question: In the composite index trick for
SELECT department_number FROM employee WHERE age > 40, where does the added storage overhead occur?Response: The extra storage occurs inside the index data entries. An index on
agestores pairs of(age, pointer). A composite index on(age, department_number)stores triples of(age, department_number, pointer)for every single record, increasing leaf page consumption.
Question: Should an index for
WHERE hobby = 'stamps'versusWHERE ID = 567be clustered or unclustered?Response:
IDreturns at most one record, making clustering completely irrelevant (both take 1 I/O); it should be unclustered.hobbycan match multiple employees (e.g., records). If unclustered, those records may require separate page reads; if clustered, they reside contiguously on a few pages. Hence,hobbyshould be clustered.
Question: In the final workload design for , why should
IDbe placed last in the index(GPA, credit, ID)instead of first?Response: Placing
IDfirst would sort the tree primarily byID, rendering it useless for range filtering onGPAandcredit.IDis purely a projected attribute, not a filtering predicate. It belongs at the end of the composite key to support the index-only plan without breaking index filtering onGPAandcredit.
Question: Does changing an index from clustered to unclustered alter its internal traversal cost?
Response: No. The cost variation between clustered and unclustered indexes depends entirely on how many records match the query. For a single record match, the data retrieval cost is identical. For multiple records, an unclustered index causes many random page reads, while a clustered index reads minimal, sequential pages.
Question: What chapters and topics are included on the upcoming midterm?
Response: The midterm covers Chapters 8 and 9 exclusively (storage, buffer management, record formats, page formats, file organizations, B+ trees, Hash indexing, clustered vs. unclustered properties, and composite indexing). Query processing is not covered; it begins after the midterm.
Question: Will the exam be excessively long, and is there a curve?
Response: Most students finished the previous exam on time. If a question is difficult, skip it and proceed. The course grades are curved overall, with historically at least one-third of the class earning grades between A and A-.
Question: Should students study from the textbook or the lecture slides/notes?
Response: For students who attended class, class notes and whiteboard derivations are the primary and sufficient study resource. Students who missed lectures should read the textbook to bridge conceptual gaps.
Question: Will a practice exam be provided?
Response: The in-class examples, whiteboard problems, and lecture workload scenarios serve as the practice material for the examination.