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: 80,00080{,}000 student records.

    • Attribute: grade, uniformly distributed between 11 and 100100.

    • Cost metric: Disk page I/O transfers.

    • Full table scan cost: Constant at 4,0004{,}000 disk pages.

  • Evaluation of Query: grade > 70:

    • Selectivity Calculation:         Fraction of qualifying records=100−70100=30%=0.30\text{Fraction of qualifying records} = \frac{100 - 70}{100} = 30\% = 0.30

    • Qualifying Record Count:         Qualifying students=80,000×0.30=24,000\text{Qualifying students} = 80{,}000 \times 0.30 = 24{,}000

    • I/O Cost Analysis:

      • Table Scan Cost: 4,0004{,}000 page I/Os.

      • Unclustered B+ Tree Cost: In the worst-case scenario, each qualifying record resides on a distinct disk page, resulting in 24,00024{,}000 page I/Os.

    • Optimizer Decision: The query optimizer selects the full table scan because 4,000<24,0004{,}000 < 24{,}000.

  • Evaluation of Query: grade > 98:

    • Selectivity Calculation:         Fraction of qualifying records=100−98100=2%=0.02\text{Fraction of qualifying records} = \frac{100 - 98}{100} = 2\% = 0.02

    • Qualifying Record Count:         Qualifying students=80,000×0.02=1,600\text{Qualifying students} = 80{,}000 \times 0.02 = 1{,}600

    • I/O Cost Analysis:

      • Table Scan Cost: 4,0004{,}000 page I/Os.

      • Unclustered B+ Tree Cost: 1,6001{,}600 page I/Os.

    • Optimizer Decision: The optimizer chooses the unclustered B+ tree because 1,600<4,0001{,}600 < 4{,}000.

  • Derivation of Optimizer Threshold for Generic Query: grade > x:

    • Cost of unclustered B+ tree:         Costtree=100−x100×80,000=(100−x)×800\text{Cost}_{\text{tree}} = \frac{100 - x}{100} \times 80{,}000 = (100 - x) \times 800

    • Cost of full table scan:         Costscan=4,000\text{Cost}_{\text{scan}} = 4{,}000

    • Break-even equality:         4,000=(100−x)×8004{,}000 = (100 - x) \times 800         5=100−x5 = 100 - x         x=95x = 95

    • Decision Boundaries:

      • If x<95x < 95: The table scan is more efficient than the unclustered B+ tree.

      • If x>95x > 95: The unclustered B+ tree is more efficient than the table scan.

      • If x=95x = 95: Both access methods incur identical costs (4,0004{,}000 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 by salary and secondarily by age.

  • Query Match Evaluation for Equality Predicates:

    • Query: WHERE age = 30 AND salary = 4000.

    • Single-Attribute Index on age: The search traverses the tree to age = 30. It must retrieve all data entries where age = 30 and fetch the underlying data pages to filter out tuples where salary 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 to age = 30, locating a contiguous block of data entries ordered by salary from 3,0003{,}000 to 5,0005{,}000.

      • Using (salary, age): The index must scan all entries across the salary range [3000,5000][3000, 5000], checking each individual entry to see if age = 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 > 40

      • Clustered index on age: Scans leaf nodes for age > 40, then follows record pointers to fetch data pages to read department_number.

      • Unclustered composite index on (age, department_number): Leaf entries store both age and department_number. The system finds age > 40 in the index and extracts department_number directly from the leaf nodes. Zero data pages are read.

    • Query 2: SELECT department_number, COUNT(*) FROM employee WHERE age > 20 GROUP BY department_number

      • Predicate age > 20 has 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_number

      • An unclustered composite B+ tree on (department_number, salary) provides an index-only evaluation plan.

      • Because entries are ordered by department_number and then salary, 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 5000

      • An unclustered composite B+ tree on (age, salary) isolates age = 25, extracts the salary range [3000,5000][3000, 5000], and calculates the aggregate directly from leaf node data entries.

Workload-Driven Physical Database Design

  • Architectural Invariants & Constraints:

    1. 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.

    2. 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 (11 page access) as a clustered index. Therefore, unique key lookups should never consume the relation's single clustered index.

    3. 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:

      • Q1Q_1: SELECT ID FROM Student WHERE GPA > x AND credit < y

      • Q2Q_2: SELECT ID, name, GPA FROM Student WHERE year > w

      • Q3Q_3: SELECT * FROM Student WHERE ID = a

    • Evaluation of Potential Indexing Configurations:

      • Proposal 1 (Invalid): Clustered B+ tree on (GPA, credit) for Q1Q_1, clustered B+ tree on year for Q2Q_2, and clustered B+ tree on ID for Q3Q_3.

        • Defect: Invalid. A table cannot support three clustered indexes.

      • Proposal 2 (Inefficient): Unclustered B+ tree on (GPA, credit), unclustered B+ tree on year, clustered Hash index on ID.

        • Defect: Wastes the single clustered index allocation on a unique key lookup (Q3Q_3) where clustering yields zero benefit.

      • Proposal 3 (Sub-optimal Covering Attempt): Index on (year, ID) for Q2Q_2.

        • Defect: Does not cover Q2Q_2 because name and GPA are omitted; data pages would still require fetching.

    • Optimal Workload Index Design:

      1. For Q3Q_3 (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 O(1)O(1) access. It cannot be index-only due to SELECT *.

      2. For Q2Q_2 (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.

      3. For Q1Q_1 (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 attribute ID at 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 (≥50%\ge 50\% 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 50%50\% 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 k∗k^*:

      • 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 age alone.

  • Question: Would an index on (salary, age) yield a different outcome than (age, salary) for the query WHERE 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 age stores 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' versus WHERE ID = 567 be clustered or unclustered?

    • Response: ID returns at most one record, making clustering completely irrelevant (both take 1 I/O); it should be unclustered. hobby can match multiple employees (e.g., 100100 records). If unclustered, those 100100 records may require 100100 separate page reads; if clustered, they reside contiguously on a few pages. Hence, hobby should be clustered.

  • Question: In the final workload design for Q1Q_1, why should ID be placed last in the index (GPA, credit, ID) instead of first?

    • Response: Placing ID first would sort the tree primarily by ID, rendering it useless for range filtering on GPA and credit. ID is 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 on GPA and credit.

  • 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.