DOC PREVIEW
MIT 6 830 - Lecture Notes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.830 Lecture 59/17/2014Project partners due next Wednesday. Lab 1 due next Monday — start now!!!Recap Anatomy of a database systemMajor Components:Admission ControlConnection Management ---------------------------------------(Query System)--------------------------- (sql) | Parser Memory Management (parse tree) | Rewriter Disk Space Management | (parse tree) Planner Replication Services |(query plan) Optimizer Admin Utilities |(query plan) Executor--------------------------------(Storage System)----------------------------Access Methods Buffer Manager Lock Manager Log Manager(Show query rewrite example)Rewrites are complicated — see “Query rewrite rules in IBM DB2 Universal Database”step 2 : plan formation (SQL -> relational algebra)notationπf1.. fn A σp AA ⨝p Bαf1..fn, g1.. gn, pemp (eno, ename, sal, dno)dept (dno, dname, bldg)kids (kno, eno, kname, bday)select ename, count(*)from emp, dept, kidsand emp.dno=dept.dnoand kids.eno=emp.enoand emp.sal > 50000and dept.name = 'eecs'group by enamehaving count(*) > 7What is the equivalent relational algebra?π (αcount(*), ename, count(*)>7 ( kids ⨝eno=eno ( σsal > 50k emp ⨝dno=dno (σname=eecs dept)))What is the equivalent query plan?Generating the best plan is the job of the optimizer -- 2 steps;1) logical -- ordering of operators2) physical -- operator selection / implementation (joins and access methods)Several different approaches to building an optimizer:1) heuristic -- a set of rules that are designed to leadto a good plan (e.g., push selections to leaves, perform cross products last, etc.)2) cost-based -- enumerate all possible plans, pick one of lowest cost -- we will discuss how this works in a couple weeksPhysical storage:In order to understand how these queries are actually executed, we need to develop a model of how data is stored on disk.All records are stored in a region on disk ("extent" in system R); probably easiest to just think of each table being in a file in the file system.Tuples are arranged in pages in some order --> "heap file"Access path is a way to access these tuples on disk.Several alternatives:heap scanheap file is a unordered collection of records split into fixed size pagesheader on each page to indicate where tuples beginpages chained together (e.g., in a linked list)index scan provide an efficient way to find particular tuples.what is an index? what does it do?insert (key, recordid) --> points from a key to a record on disk{records} = lookup (key) {records} = lookup ([lowkey ... highkey])Hierarchical indices are the most commonly used-- e.g., B-TreesIn most databases, indexes point from key values to records in the heap file.diagram:Tree stores salaries in order; leaves point to records with those salariesTypically, in a database, indexes are keyed on a particular attribute (e.g., employee salary), which allows efficient lookup on that attribute. What does it mean to "cluster" an index? (arrange keys on disk so that they are in order of index)Why is that good?Typically, an access path also supports a "scan" operation, that allows access to all tuples in the table. Because a given lookup or scan can return lots of tuples, most database indices use an "iterator" abstraction:it = am.open(predicate)loop:tup = it.get_next()We can place different access methods at the leaves of query plans:- Heap scan looks at all tuples, but in sequential order- Index scan traverses leaves of index, so may access tuples in random order if index is not clustered*** study break -- postgres queries ***Step 3 : query executionDatabase query plans -- iterator modelvoid open ();Tuple next ();void close ();every operator implements this interfacesmakes it possible to compose operators arbitrarilyexample 1:example 2:Iterator code:(show slides)Note the “pull from top” processingWhy tuple at a time? What is good about this?What’s bad about this?Alternatives:Batch at a time (iterators pass arrays of tuples)Relation at a time (each operator runs to completion)Batches / iterators allow pipelining — earlier result outputs, and each step in the plan can be running in parallel.Plan types:Left deep vs. bushy(discuss pipelining)pipelining -- means that results of one operator can be fed into another operator ⨝outer ⨝  ⨝ inner A B C Dfor t1 in outerfor t2 in innerif p(t1,t2)emit join(t1,t2)problem -- have to either store the result of C ⨝ D, or continually recompute it"left deep" plan ⨝⨝  D ⨝C A BNo materialization necessary. Many database systems restrict themselves to left or right deep plans for this reason.(Lecture will end here)Buffer management and storage system:What's the "cost" of a particular plan?CPU cost (# of instructions) - 1 ghz == 1 billions instrs / sec, 1 nsec / instrI/O cost (# of pages read, # of seeks) - 100 MB / sec = 10 nsec / byteRandom I/O = page read + seek - 10 msec / seek = 100 seeks / secRandom I/O can be a real killer (10 million instrs/seek) . When does a disk need to seek?Which do you think dominates in most database systems?(Depends. Not always disk I/O. Typically vendors try to configure machines so they are 'balanced'. Can vary from query to query. ) For example, fastest TPC-H benchmark result (data warehousing benchmark), on 10 TB of data, uses 1296 74 GB disks, which is 100 TB of storage. Add'l storage is partly for indices, but partly just because they needed add'l disk arms. 72 processors, 144 cores -- ~10 disks / processor!But, if we do a bad job, random I/O can kill us!100 tuples/page select * from 10 pages RAM emp, dept., kids10 KB/page where e.sal > 10kemp.dno = dept.dno10 ms seek time e.eid = kids.eid100 MB/sec 1/O|dept| = 100 = 1 page|emp| = 10K = 100 pages|kids| = 30K = 300 pages ⨝(NLJoin)1000 / k ⨝ (NLJoin) 100 | \ 1000d σsal>10k | e1st Nested loops join -- 100,000 predicate ops; 2nd nested loops join -- 3,000,000 predicate opsLet's look at # disk I/Os/costas assuming LRU and no indicesif d is outer:1 scan of d 100 sequential scans of e (100 x 100 pg. reads) -- cache doesn't benefit since e doesn't fit1 scan of e: 1 seek + read in 1MB10 ms + 1 MB / 100 MB/sec = 20 msec20 ms x 100 depts = 2 sec10 msec seek to start of d and read into memory2.01 secsif d is innerread page of e -- 10 msecread all of d into RAM -- 10 msecseek back


View Full Document
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?