Database Systems: Physical Database Design, Indexing, Relational Algebra, and Query Optimization

Physical Database Design and Storage Architecture

Data stored within a Relational Database Management System (RDBMS) is maintained on non-volatile secondary storage devices, primarily hard disk drives (HDDs) or solid-state drives (SSDs). Main memory (RAM) is limited in capacity and volatile, preventing permanent storage of whole databases. Disk Input/Output (I/O) operations represent a major performance bottleneck due to mechanical latency and physical transfer times. Consequently, overall database query performance depends heavily on the physical arrangement of data on disk blocks.

A disk is physically and logically formatted into fixed-size contiguous storage blocks or pages. A page or block serves as the fundamental unit of data transfer between secondary storage and main memory. When an RDBMS requires a specific data record, it reads the entire page containing that record into RAM. A structured collection of these pages stored on disk forms a database file.

Hard Disk Physical Architecture

The physical disk geometry consists of stacked circular platters rotating around a central spindle. Read-write heads attached to a synchronized arm assembly move radially across the surface of the platters. Concentric ring paths on each platter surface are designated as tracks (tt). Vertically aligned tracks across all platters form a cylinder (cc). Each track is subdivided into arcs called sectors (ss).

Primary File Organization Methods

File organization determines the physical layout of records within disk blocks and establishes the retrieval mechanisms supported by the storage subsystem. The three primary types of file organization are heap files, sequential files, and hash files.

An unordered file, also known as a heap file, places incoming records in any available space on the disk where free storage exists, typically appending new records to the end of the last page. Record insertion is exceptionally fast with time complexity O(1)\mathcal{O}(1). Conversely, search and update operations are slow with time complexity O(n)\mathcal{O}(n) because a linear scan across all blocks is required to locate a record. Deletion is similarly inefficient, as it requires searching for the target record; deleting a record leaves unused space or a hole in the page, leading to internal fragmentation.

An ordered file, or sequential file, arranges records physically sorted according to the values of one or more specified attributes known as the ordering key or search key. Search operations are fast with time complexity O(log⁡2n)\mathcal{O}(\log_2 n) because binary search can be performed over the sorted disk blocks. Record deletion is also fast due to rapid location of the target record. However, insertion operations are slow and inefficient because inserting a record into its correct ordered position requires shifting, on average, half of the subsequent records in the file. To mitigate insertion overhead, an auxiliary unordered overflow file (or heap file) is established to buffer newly inserted records. Periodically, the overflow file is merged with the main sorted sequential file.

Access patterns differ between sequential and random file organizations. Sequential access retrieves data in a predetermined, continuous order, yielding optimal read throughput. Random access splits files across non-contiguous memory blocks, permitting arbitrary offset reads at the expense of higher seek times and rotational latency.

Hashing Techniques and Collision Resolution

A hash file structure organizes records into an array of buckets located in storage memory. A bucket represents a disk block or memory location storing actual data records. A hash function h(k)h(k) computes the address index of the target bucket for a record with hash key kk. The primary key of a relation is typically selected as the hash key. A common modular hash function is defined as:

h(K)=K(modM)h(K) = K \pmod M

where KK is the integer value of the hash field key and MM represents the total number of allocated memory buckets.

Data Buckets in Memory with Hash Table Pointer Address

Mapping a key value to an array index involves evaluating the hash function. For instance, mapping keys 77, 1818, 4141, and 3434 into a table of size M=10M = 10 yields:

h(7)=7(mod10)=7h(7) = 7 \pmod{10} = 7

h(18)=18(mod10)=8h(18) = 18 \pmod{10} = 8

h(41)=41(mod10)=1h(41) = 41 \pmod{10} = 1

h(34)=34(mod10)=4h(34) = 34 \pmod{10} = 4

A collision occurs when a newly inserted record hashes to a bucket address that is already fully occupied by a previously stored record. For example, inserting keys 8080, 4040, 6565, 2424, 5858, 3535, and 9898 into a table of size M=11M = 11 using h(k)=k(mod11)h(k) = k \pmod{11} produces:

h(80)=80(mod11)=3h(80) = 80 \pmod{11} = 3

h(40)=40(mod11)=7h(40) = 40 \pmod{11} = 7

h(65)=65(mod11)=10h(65) = 65 \pmod{11} = 10

h(24)=24(mod11)=2h(24) = 24 \pmod{11} = 2

h(58)=58(mod11)=3(Collision at index 3 with 80)h(58) = 58 \pmod{11} = 3 \quad (\text{Collision at index } 3 \text{ with } 80)

h(35)=35(mod11)=2(Collision at index 2 with 24)h(35) = 35 \pmod{11} = 2 \quad (\text{Collision at index } 2 \text{ with } 24)

h(98)=98(mod11)=10(Collision at index 10 with 65)h(98) = 98 \pmod{11} = 10 \quad (\text{Collision at index } 10 \text{ with } 65)

Collision resolution techniques fall into static hashing (separate chaining, linear probing, quadratic probing, double hashing) and dynamic hashing (extendible hashing).

In static hashing, the number of allocated memory buckets remains fixed. Static hashing cannot dynamically expand or shrink when database volume fluctuates, leading to frequent bucket overflows or wasted memory space.

Separate chaining, or open hashing, handles collisions by appending colliding keys to a linked list attached to the corresponding hash bucket index.

Open Hashing / Separate Chaining Diagram

Advantages of separate chaining include simple collision management, prevention of primary clustering, and fast record insertion. Disadvantages include memory overhead required for storing linked list pointers, performance degradation to O(n)\mathcal{O}(n) search time in worst-case long chains, and reduced CPU cache locality due to non-contiguous list pointers.

Linear probing is an open addressing strategy that searches sequentially for the next available empty slot using the probe formula:

h(x,i)=(h′(x)+i)(modm)h(x, i) = (h'(x) + i) \pmod m

where i=0,1,2,…i = 0, 1, 2, \dots represents the probe attempt number and mm is the table size.

Linear Probing Collision Resolution Steps

Consider inserting keys 2323, 4343, 1313, 3333, and 5353 into a hash table of size m=10m = 10 with base function h(k)=k(mod10)h(k) = k \pmod{10}:

Inserting 2323: h(23)=23(mod10)=3h(23) = 23 \pmod{10} = 3. Index 33 is empty. Place 2323 at index 33.

Inserting 4343: h(43)=43(mod10)=3h(43) = 43 \pmod{10} = 3. Index 33 is occupied. Probe i=1i=1: (3+1)(mod10)=4(3+1) \pmod{10} = 4 (empty). Place 4343 at index 44.

Inserting 1313: h(13)=13(mod10)=3h(13) = 13 \pmod{10} = 3. Indices 33 and 44 are occupied. Probe i=2i=2: (3+2)(mod10)=5(3+2) \pmod{10} = 5 (empty). Place 1313 at index 55.

Inserting 3333: h(33)=33(mod10)=3h(33) = 33 \pmod{10} = 3. Indices 33, 44, and 55 are occupied. Probe i=3i=3: (3+3)(mod10)=6(3+3) \pmod{10} = 6 (empty). Place 3333 at index 66.

Inserting 5353: h(53)=53(mod10)=3h(53) = 53 \pmod{10} = 3. Indices 33, 44, 55, and 66 are occupied. Probe i=4i=4: (3+4)(mod10)=7(3+4) \pmod{10} = 7 (empty). Place 5353 at index 7$.\n\nLinear probing eliminates pointer overhead and offers good cache locality, but suffers from primary clustering, where long contiguous blocks of occupied slots form, causing search times to degrade as the load factor increases.\n\nQuadratic probing resolves collisions by adding a quadratic polynomial offset to the initial hash address, mitigating primary clustering:\n\nh_i(k) = (h(k) + i^2) \pmod m\n\nwhere i = 0, 1, 2, \dotsandandm is table size.\n\n![Quadratic Probing Step 1 and 2](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/7.jpg)\n\n![Quadratic Probing Steps 3 to 5 and Final Table](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/8.jpg)\n\nConsider inserting keys 23,,43,,13,,33,and, and53intoatableofsizeinto a table of sizem = 10withwithh(k) = k \pmod{10}:\n\nInserting 23::h(23) = 3,,i=0 \rightarrowindexindex3(empty).Place(empty). Place23atindexat index3$.

Inserting 4343: h(43)=3h(43) = 3, i=0→3i=0 \rightarrow 3 (occupied). Probe i=1→(3+12)(mod10)=4i=1 \rightarrow (3 + 1^2) \pmod{10} = 4 (empty). Place 4343 at index 4$.\n\nInserting 13::h(13) = 3,,i=0 \rightarrow 3(occupied),(occupied),i=1 \rightarrow 4(occupied).Probe(occupied). Probei=2 \rightarrow (3 + 2^2) \pmod{10} = 7(empty).Place(empty). Place13atindexat index7$.

Inserting 3333: h(33)=3h(33) = 3, i=0,1,2i=0, 1, 2 indices (3,4,73, 4, 7) checked. Probe i=3→(3+32)(mod10)=12(mod10)=2i=3 \rightarrow (3 + 3^2) \pmod{10} = 12 \pmod{10} = 2 (empty). Place 3333 at index 2$.\n\nInserting 53::h(53) = 3,,i=0, 1, 2, 3indices(indices (3, 4, 7, 2)checked.Probe) checked. Probei=4 \rightarrow (3 + 4^2) \pmod{10} = 19 \pmod{10} = 9(empty).Place(empty). Place53atindexat index9$.

The final table layout for quadratic probing contains: index 2→332 \rightarrow 33, index 3→233 \rightarrow 23, index 4→434 \rightarrow 43, index 7→137 \rightarrow 13, index 9 \rightarrow 53$.\n\nQuadratic probing reduces primary clustering but induces secondary clustering, where keys hashing to the same initial slot follow identical probe sequences.\n\nDouble hashing applies a secondary hash function h_2(k) to calculate probe offsets when collisions occur:\n\nh(k, i) = (h_1(k) + i \times h_2(k)) \pmod m\n\nwhere h_1(k) = k \pmod mandandh_2(k) = \text{PRIME} - (k \pmod{\text{PRIME}}),with, with\text{PRIME} < m.Thesecondaryfunction. The secondary functionh_2(k) must never evaluate to zero.\n\nFor a table size m = 7withwithh_1(k) = k \pmod 7andandh_2(k) = 5 - (k \pmod 5),insertingkeys, inserting keys10,,17,and, and24 proceeds as follows:\n\nInserting 10::h_1(10) = 10 \pmod 7 = 3(empty).Place(empty). Place10atindexat index3$.

Inserting 1717: h1(17)=17(mod7)=3h_1(17) = 17 \pmod 7 = 3 (occupied). Evaluate h2(17)=5−(17(mod5))=5−2=3h_2(17) = 5 - (17 \pmod 5) = 5 - 2 = 3. Probe i=1→(3+1×3)(mod7)=6i=1 \rightarrow (3 + 1 \times 3) \pmod 7 = 6 (empty). Place 1717 at index 6$.\n\nInserting 24::h_1(24) = 24 \pmod 7 = 3(occupied).Evaluate(occupied). Evaluateh_2(24) = 5 - (24 \pmod 5) = 5 - 4 = 1.Probe. Probei=1 \rightarrow (3 + 1 \times 1) \pmod 7 = 4(empty).Place(empty). Place24atindexat index4$.

Extendible hashing is a dynamic hashing technique that adjusts storage buckets using a directory structure. Directories contain pointers to buckets, and the number of directories is 2Dg2^{D_g}, where DgD_g is the Global Depth. The Global Depth represents the number of hash key bits used to index the directory array. Each bucket maintains a Local Depth (DlD_l), representing the bit precision of the keys stored within that bucket. The local depth DlD_l is always less than or equal to DgD_g.

Extendible Hashing Overflow Decision Tree

When a bucket exceeds its maximum record capacity, an overflow occurs:

If Dl<DgD_l < D_g, only a Bucket Split is performed. The overflowing bucket splits into two, its local depth increases (Dl=Dl+1D_l = D_l + 1), and keys are rehashed between the two buckets based on their DlD_l-th bit. The directory array size remains unchanged.

If Dl=DgD_l = D_g, both a Bucket Split and Directory Expansion occur. The global depth increases (Dg=Dg+1D_g = D_g + 1), doubling the directory entries from 2Dg2^{D_g} to 2Dg+12^{D_g+1}. The local depth of the split bucket increases (Dl=Dl+1D_l = D_l + 1), and directory pointers are updated.

Tracing extendible hashing for keys 16,4,6,22,24,10,31,7,9,20,2616, 4, 6, 22, 24, 10, 31, 7, 9, 20, 26 with bucket capacity 33 using Least Significant Bits (LSBs):

Binary LSB values: 16=10000216 = 10000_2, 4=0010024 = 00100_2, 6=0011026 = 00110_2, 22=10110222 = 10110_2, 24=11000224 = 11000_2, 10=01010210 = 01010_2, 31=11111231 = 11111_2, 7=0011127 = 00111_2, 9=0100129 = 01001_2, 20=10100220 = 10100_2, 26=11010226 = 11010_2.

Initial State: Dg=1D_g = 1. Directories 0 and 1. Bucket 0 holds 16,4,616, 4, 6 (Dl=1D_l=1).

Inserting 2222 (101102→10110_2 \rightarrow LSB 0): Bucket 0 overflows (16,4,6,2216, 4, 6, 22). Since Dl=Dg=1D_l = D_g = 1, directory expands to Dg=2D_g = 2 (00, 01, 10, 11). Bucket splits to Dl=2D_l = 2: LSB 00 gets 16,416, 4; LSB 10 gets 6,226, 22.

Inserting 2424 (110002→11000_2 \rightarrow 00) & 1010 (010102→01010_2 \rightarrow 10): Placed into existing buckets without overflow (00 holds 16,4,2416, 4, 24; 10 holds 6,22,106, 22, 10).

Inserting 3131 (11), 77 (11), 99 (01): Mapped to directory pointers 01 and 11 which point to an empty bucket (Dl=1D_l=1). Bucket now holds 31,7,931, 7, 9.

Inserting 2020 (101002→10100_2 \rightarrow 00): Bucket 00 (16,4,2416, 4, 24) overflows. Since Dl=Dg=2D_l = D_g = 2, perform Directory Expansion (Dg=3D_g = 3) and Bucket Split (Dl=3D_l = 3). Directory expands to 8 entries (000 through 111). LSB 000 gets 16,2416, 24 (Dl=3D_l=3); LSB 100 gets 4,204, 20 (Dl=3D_l=3).

Inserting 2626 (110102→11010_2 \rightarrow 010): Bucket pointing to 010 (6,22,106, 22, 10) overflows (6,22,10,266, 22, 10, 26). Here Dl=2<Dg=3D_l = 2 < D_g = 3. Perform Bucket Split only. Local depth increases to Dl=3D_l = 3. LSB 010 gets 10,2610, 26; LSB 110 gets 6, 22$.\n\nExtendible hashing guarantees dynamic expansion without full rehash operations or data loss. However, non-uniform hash distributions can cause directory sizes to grow exponentially, wasting memory space in directory pointers.\n\n\n# Database Indexing Architectures\n\nDatabase indexing provides auxiliary access structures designed to speed up the retrieval of records by minimizing the number of disk block I/Os during query processing. An index file consists of index entries of the form `

Set Difference (r−sr - s) retrieves tuples present in relation rr but absent from union-compatible relation ss.\n\nAssignment Operator (\leftarrow$) evaluates an algebra expression and assigns the result to a temporary variable:\n\n\text{Physics} \leftarrow \sigma_{\text{dept_name}='Physics'}(\text{instructor})\n\nRename Operator (\rho_x(E))renamesanexpression) renames an expressionEtotox,orrenamesattributesusing, or renames attributes using\rho_{x(A_1, A_2, \dots, A_n)}(E).\n\n\rho_{(A, B)}(\text{Department})\n\n\rho_{\text{Pro}(P, Q, R)}(\text{Project})\n\n\n# Translating SQL Queries to Relational Algebra\n\nSQL statements translate directly into relational algebra primitives according to established operator mappings.\n\n![SQL to Relational Algebra Mapping Table](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/64.png)\n\nSQL Translation Examples:\n\nExample 1: SQL Query:\n```sql\nSELECT Name FROM STUDENT WHERE Dept = 'CSE';\n```\nRelational Algebra:\n\pi_{\text{Name}}(\sigma_{\text{Dept}='CSE'}(\text{STUDENT}))\n\nExample 2: SQL Query:\n```sql\nSELECT Name FROM STUDENT WHERE Dept = 'CSE' AND CGPA > 8;\n```\nRelational Algebra:\n\pi_{\text{Name}}(\sigma_{\text{Dept}='CSE' \land \text{CGPA}>8}(\text{STUDENT}))\n\nExample 3: SQL Query:\n```sql\nSELECT Name, Dept_Name FROM STUDENT S JOIN DEPARTMENT D ON S.Dept_ID = D.Dept_ID;\n```\nRelational Algebra:\n\pi_{\text{Name, Dept_Name}}(\text{STUDENT} \bowtie_{\text{STUDENT.Dept_ID} = \text{DEPARTMENT.Dept_ID}} \text{DEPARTMENT})\n\nExample 4: SQL Query:\n```sql\nSELECT Name FROM CSE_STUDENT UNION SELECT Name FROM ECE_STUDENT;\n```\nRelational Algebra:\n\pi_{\text{Name}}(\text{CSE_STUDENT}) \cup \pi_{\text{Name}}(\text{ECE_STUDENT})\n\nExample 5: SQL Query:\n```sql\nSELECT Dept, COUNT(*) FROM STUDENT GROUP BY Dept;\n```\nRelational Algebra:\n\gamma_{\text{Dept}, \text{COUNT}(*)}(\text{STUDENT})\n\nPractice Transformations:\n\n1. `SELECT Name, CGPA FROM STUDENT WHERE Dept = 'CSE' AND CGPA > 8.0;`\n\pi_{\text{Name, CGPA}}(\sigma_{\text{Dept}='CSE' \land \text{CGPA}>8.0}(\text{STUDENT}))\n\n2. `SELECT S.Name, E.Course_ID FROM STUDENT S JOIN ENROLLMENT E ON S.Student_ID = E.Student_ID;`\n\pi_{\text{S.Name, E.Course_ID}}(\text{STUDENT} \bowtie_{\text{S.Student_ID}=\text{E.Student_ID}} \text{ENROLLMENT})\n\n3. `SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS101' UNION SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS102';`\n\pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS101'}(\text{ENROLLMENT})) \cup \pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS102'}(\text{ENROLLMENT}))\n\n4. `SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS101' INTERSECT SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS102';`\n\pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS101'}(\text{ENROLLMENT})) \cap \pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS102'}(\text{ENROLLMENT}))\n\n5. `SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS101' EXCEPT SELECT Student_ID FROM ENROLLMENT WHERE Course_ID = 'CS102';`\n\pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS101'}(\text{ENROLLMENT})) - \pi_{\text{Student_ID}}(\sigma_{\text{Course_ID}='CS102'}(\text{ENROLLMENT}))\n\n\n# Query Processing and Optimization\n\nQuery processing refers to the multi-step pipeline required to convert a high-level query into physical database execution operations.\n\n![Steps in High Level Query Processing](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/47.jpg)\n\nThe high-level query passes through the scanner to isolate language tokens, the parser to verify SQL syntax, and the validator to check attribute and relation schemas against the system data dictionary. The database system then builds an internal relational algebra query tree, converts it into an optimized execution plan via the query optimizer, compiles or interprets the query execution code, and runs the result through the runtime database processor.\n\nQuery optimization paradigms include Cost-Based Optimization and Heuristic Optimization.\n\nCost-based optimization estimates the physical cost of alternative evaluation plans using catalog statistics (record counts, block counts, primary key uniqueness, index choices, and CPU/IO cost models) to select the cheapest plan.\n\nHeuristic optimization applies rule-based relational algebra transformations to rewrite query trees into equivalent forms that minimize intermediate relation sizes.\n\nRelational Algebra Equivalence Rules:\n\n1. Conjunctive selections cascade into individual selections:\n\sigma_{\theta_1 \land \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))\n\n2. Selection operations are commutative:\n\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))\n\n3. Cascaded projections reduce to the final projection:\n\pi_{L_1}(\pi_{L_2}(\dots \pi_{L_n}(E))) = \pi_{L_1}(E)\n\n4. Selections combine with Cartesian products to form theta joins:\n\sigma_\theta(E_1 \times E_2) = E_1 \bowtie_\theta E_2\n\n5. Theta joins and natural joins are commutative:\nE_1 \bowtie_\theta E_2 = E_2 \bowtie_\theta E_1\n\n6. Natural joins and theta joins are associative:\n(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)\n\n7. Selection distributes over theta join if attributes in \theta_0involveonlyexpressioninvolve only expressionE_1:\n\sigma_{\theta_0}(E_1 \bowtie_\theta E_2) = (\sigma_{\theta_0}(E_1)) \bowtie_\theta E_2\n\n![Equivalence Rules Diagram for Join Commutativity, Associativity, Selection Pushdown](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/55.jpg)\n\nCore Heuristic Rules:\n\nRule 1: Perform Selection Early (Push Selections Down). Move selection operations down the query tree below joins to reduce intermediate table cardinality.\n\nRule 2: Perform Projection Early (Push Projections Down). Eliminate unnecessary columns early to reduce intermediate tuple width.\n\nRule 3: Perform Most Restrictive Selections First. Execute filters that eliminate the largest percentage of rows before applying other operations.\n\nRule 4: Order Joins Carefully. Join smaller intermediate relations first to minimize execution memory overhead.\n\nDetailed Heuristic Optimization Example:\n\nGiven the SQL Query:\n```sql\nSELECT S.Name \nFROM STUDENT S, MARKS M \nWHERE S.Student_ID = M.Student_ID \n AND S.Dept = 'CSE' \n AND M.Mark > 80;\n```\n\nUnoptimized Execution Plan: Calculates the full Cartesian product `STUDENT` \times‘MARKS‘,thenappliescombinedselection`MARKS`, then applies combined selection\sigma_{\text{S.Student_ID}=\text{M.Student_ID} \land \text{S.Dept}='CSE' \land \text{M.Mark}>80}, and projects `Name`.\n\nOptimized Transformation:\n\nStep 1: Push Selections Down. Apply \sigma_{\text{Dept}='CSE'}(\text{STUDENT})andand\sigma_{\text{Mark}>80}(\text{MARKS}) independently before performing the join.\n\nStep 2: Push Projections Down. Project `Student_ID, Name` from `STUDENT` and `Student_ID, Mark` from `MARKS` before performing the join.\n\n![Heuristic Query Optimization Execution Steps](https://assets.knowt.com/pdf-flow-prod/de73f7ab-36d0-4988-b10d-54b307c69568-figures/59.jpg)\n\nExecution Walkthrough on Sample Dataset:\n\n`STUDENT` contains 100,000rows;filtering‘Dept=′CSE′‘yieldsrows; filtering `Dept = 'CSE'` yields2 matching rows (`101 Arun`, `103 Ravi`).\n\n`MARKS` contains 500,000rows;filtering‘Mark>80‘yieldsrows; filtering `Mark > 80` yields2 matching rows (`101 DBMS 85`, `103 DBMS 90`).\n\nJoining the reduced intermediate tables on `Student_ID` evaluates 2 \times 2 = 4comparisonsinsteadofcomparisons instead of100,000 \times 500,000 = 50,000,000,000comparisons,producingcomparisons, producing2 joined rows.\n\nFinal projection outputs `Arun` and `Ravi` (2 rows).\n\nHeuristic Example 2:\n```sql\nSELECT LNAME\nFROM EMPLOYEE, WORKS_ON, PROJECT\nWHERE PNAME = 'Aquarius'\n AND PNUMBER = PNO\n AND ESSN = SSN\n AND BDATE > '1957-12-31';\n```\nPushing \sigma_{\text{PNAME}='Aquarius'}onto‘PROJECT‘andonto `PROJECT` and\sigma_{\text{BDATE}>'1957-12-31'}$$ onto EMPLOYEE drastically minimizes intermediate join sizes, demonstrating the computational performance benefits of query optimization.