Professor Kedem’s changes, if any, are marked in green, they are not copyrighted by the authors, and the authors are not responsible for them Dennis's changes in blue.Database DesignIssues Addressed in Physical DesignWhat is a Disk?What is a FileWhat is a File (cont.)Example: Storing a RelationExample: Storing a Relation (cont.)Vertical Partitioning ApproachProcessing a QueryCost ModelImplications of the Cost ModelExampleSlide 14File Organization and IndicesTradeoffReview of Data Structures to Store N NumbersHeap (assume contiguous storage)HashingHashing: Example of InsertionHashing: Example of Insertion (cont.)Slide 22Slide 23Hashing (cont.)Slide 252-3 Tree (an Example)2-3 TreesInsertion of a Node in the Right PlaceInsertion of a Node in the Right Place (cont.)Slide 30What to Use?B+-treesB+-trees (cont.)Slide 34Dense vs. sparse indicesDense Index FilesDense clustered index (for B trees these would be sorted)Dense unclustered indexExample of Sparse Index FilesSparse clustered index (fewer levels)Sparse unclustered index (never used – would not be able to find records)Index on Several ColumnsSymbolic vs. Physical PointersWhen to Use Indices to Find RecordsSQL Specification of indexesDeficiencies of Static HashingDynamic HashingGeneral Extendable Hash StructureUse of Extendable Hash StructureUpdates in Extendable Hash StructureUpdates in Extendable Hash Structure (Cont.)Example (Cont.)Slide 53Slide 54Slide 55Extendable Hashing vs. Other SchemesClustered Index (Remaining slides in this unit from Shasha and Bonnet Database Tuning book)Index “Face Lifts”Index MaintenanceCovering Index - definedCovering Index - impactScan Can Sometimes WinIndex on Small TablesProfessor Kedem’s changes, if any, are Professor Kedem’s changes, if any, are marked in green, they are not marked in green, they are not copyrighted by the authors, and the copyrighted by the authors, and the authors are not responsible for themauthors are not responsible for themDennis's changes in blue.Dennis's changes in blue.01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.2Database System ConceptsDatabase DesignDatabase DesignLogical DB Design:•Create a model of the enterprise (using ER diagrams perhaps)•Create a logical “implementation” (using a relational model perhaps)•Creates the top two layers: “User” and “Community”•Independent of any physical implementationPhysical DB Design•requires knowledge of hardware and operating systems characteristics•depends upon the implementation•possibly addresses questions of distribution, if necessary•creates the third layerQuery Optimization ties the two together©Zvi M. Kedem01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.3Database System ConceptsIssues Addressed in Physical DesignIssues Addressed in Physical DesignMain issues addressed generally in physical design•Storage Media•File structures•Indices•Query Optimization•DistributionWe concentrate on•Centralized (not distributed) databases•Database stored on a disk using a “standard” file system, not one “tailored” to the database•IndicesThe only issue for us: performanceperformance©Zvi M. Kedem01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.4Database System ConceptsWhat is a Disk?What is a Disk?Disk consists of a sequence of cylinderscylindersA cylinder consists of a sequence of trackstracksA track consist of a sequence of blocks (actually each block is blocks (actually each block is a sequence of sectors)a sequence of sectors)For us: A disk consists of a sequence of blocksAll blocks are of same size, say 16K bytesWe assume: physical block is essentially the same as a virtual memory pageA physical unit of access is always a block.If an application wants to read a single bit, the system reads a whole block and puts it as a whole page in a cache block•Unless an up-to-date copy of the page is in RAM already©Zvi M. Kedem01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.5Database System ConceptsWhat is a FileWhat is a FileFile can be thought of as “logical” of “physical” entityFile as a logical entity: a sequence of records.Records are either fixed size or variableA file as a physical entity: a sequence of blocks (on the disk)In fact, the blocks are organized into consecutive subsequences called “extents”.©Zvi M. Kedem01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.6Database System ConceptsWhat is a File (cont.)What is a File (cont.)Records are stored in blocks•This gives the relation between a “logical” file and a “physical” fileVery preliminary over-simplified assumptions:•Fixed size records•No record spans more than one block•There are several records in a block•There is some “left over” space in a block as needed later©Zvi M. Kedem01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.7Database System ConceptsExample: Storing a RelationExample: Storing a Relation1 12003 21004 18002 12006 23009 14008 1900E# Salary1 12003 21004 18002 12006 23009 14008 1900RecordsRelation01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.8Database System ConceptsExample: Storing a Relation (cont.)Example: Storing a Relation (cont.)Blocks1 12003 21004 18002 12006 23009 14008 1900Records6 23009 14001 1200 3 2100 8 19004 18002 1200Left-overSpaceFirst blockof the file©Silberschatz, Korth and Sudarshan12.9Database System ConceptsVertical Partitioning ApproachVertical Partitioning ApproachInstead of storing data one record at a time, one can store one column at a time.In our example that would mean storing the E# values contiguously and then the salaries contiguously with one another but separately from the E# values.This is a great idea for very wide tables (100s of columns) but where most queries want just a few columns. Particularly good for data warehouses. Example users of this idea: Sybase IQ, kdb, …01/11/06 07:56 AM©Silberschatz, Korth and Sudarshan12.10Database System ConceptsProcessing a QueryProcessing a QuerySimple querySELECT E#FROM RWHERE SALARY > 1500;What needs to be done “under the hood” by the file system:•Read into RAM at least all the blocks containing all records satisfying the condition (unless already there, which is often the case)•It may be necessary/useful to read other blocks too, as we see later•Get the relevant information from the blocks•Additional processing to produce the answer to the