Constructing Physical Query Plans for Database Systems
Learn the process of constructing physical query plans in database systems with efficient algorithms, relational algebra operations, logic laws, optimization techniques, and more. Dive into the optimization and security aspects involved in building physical query plans.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 24: Constructing physical query plans
CSCE-608 Report: Midterm Examination Max: Min: Avg: 97/100 66/100 82/100 100 90: 89 85: 84 80: 79 70: < 70: 1 4 5 3 1
Solutions to the questions in Midterm Midterm-Solutions.pdf
What Does DBMS Do? SELECT a1, b1, c1 FROM A, B, C WHERE a2=1 AND b2=2 AND c2=3 An input database program P Prepare a collection C of efficient algorithms for operations in relational algebra; parser A parse tree parse tree preprocessing parse tree a1, b1, c1 parse tree-lqp convertor a2=1, b2 =2, c2=3 logic query plan C apply logic laws A B logic query plan Optimization via logic and size a1, b1, c1 logic query plan Lqp-pqp convertor physical query plan a2=1 take care of issues in optimization and security. A b2 =2 c2=3 Optimization via algorithms and cost B C 2 Machine executable code
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M F G B A D E C
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M 1. Replacing each leaf R of T by scan(R) ; scan(F) scan(G) scan(B) scan(A) scan(D) scan(E) scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; scan(F) scan(G) scan(B) scan(A) index-scan index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) index-scan J1P index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; For each edge e in T, decide if e should be materialized ; J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) 4. index-scan J1P index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; For each edge e in T, decide if e should be materialized ; J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) 4. index-scan J1P index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; For each edge e in T, decide if e should be materialized ; Cut all materialized edges; J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) 4. index-scan J1P 5. index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M 3 CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; For each edge e in T, decide if e should be materialized ; Cut all materialized edges; Each subtree is a call to the subroutine at the root of the subtree. The order of the calls follows the bottom-up order in the structure. 2 J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) 4. 1 index-scan J1P 5. 6. index-scan scan(D) scan(E) index-scan scan(C)
Construction of Physical Query Plan Input: an optimized LQP T, and main memory constraint M 3 CJ 1. 2. Replacing each leaf R of T by scan(R) ; Combining the scan s with other operations; Replacing each internal node v of T by a proper algorithm; For each edge e in T, decide if e should be materialized ; Cut all materialized edges; Each subtree is a call to the subroutine at the root of the subtree. The order of the calls follows the bottom-up order in the structure. 2 J2P I1P scan(F) J2P 3. scan(G) scan(B) J1P scan(A) 4. 1 index-scan J1P 5. 6. index-scan scan(D) scan(E) index-scan scan(C) This produces an executable code for the input DB program
Physical Query Plan: Summary Replacing internal nodes of an LQP by proper algorithms; Deciding if a subroutine call should be pipelined or materialized; Many optimization techniques are involved here; In practice, heuristic optimization techniques are used to construct good physical query plans; The resulting physical query plan is an executable code.
What Does DBMS Do? SELECT a1, b1, c1 FROM A, B, C WHERE a2=1 AND b2=2 AND c2=3 An input database program P Prepare a collection C of efficient algorithms for operations in relational algebra; parser A parse tree parse tree preprocessing parse tree a1, b1, c1 parse tree-lqp convertor a2=1, b2 =2, c2=3 logic query plan C apply logic laws A B logic query plan Optimization via logic and size a1, b1, c1 logic query plan Lqp-pqp convertor physical query plan a2=1 take care of issues in optimization and security. A b2 =2 c2=3 Optimization via algorithms and cost B C 2 Machine executable code
What Does DBMS Do? SELECT a1, b1, c1 FROM A, B, C WHERE a2=1 AND b2=2 AND c2=3 An input database program P Prepare a collection C of efficient algorithms for operations in relational algebra; parser A parse tree parse tree preprocessing parse tree a1, b1, c1 parse tree-lqp convertor a2=1, b2 =2, c2=3 logic query plan C apply logic laws A B logic query plan Optimization via logic and size a1, b1, c1 logic query plan Lqp-pqp convertor physical query plan a2=1 take care of issues in optimization and security. A b2 =2 c2=3 Optimization via algorithms and cost B C 2 Machine executable code
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager What is still missing? index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager Efficient Algorithms for Relational algebriac operations index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager Efficient Algorithms for Relational algebriac operations index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS
