Chapter 6: Database Development Process Performance

ion:Vendor (Vendor ID, Address, Contact Name)Item Quote (Vendor ID, Item ID, Description, Price)Results in significant duplication of data in Item QuoteData duplicationPartitioningzz“Denormalize” to create more tables (not fewer as before)Horizontal Partitioning: Distributing the rows of a tableinto several separate files– Useful for situations where different users need access to differentrows– Example: Partition customer data by sales region (can createsupertype/subtype relationship)zVertical Partitioning: Distributing the columns of a tableinto several separate files– Useful for situations where different users need access to differentcolumns– Example: Partition customer data into sales related columns andbilling related columns– The primary key must be repeated in each file (1:1 relationship)zCombinations of Horizontal and VerticalPartitioningz Advantages–––––of Partitioning:Records used together are grouped togetherEach partition can be optimized for performanceSecurity, recoveryPartitions stored on different disks: reduces contentionTake advantage of parallel processing capabilityz Disadvantagesof Partitioning:– Slow retrievals across partitions– Complexity– Data duplication across partitionsPartitions often correspond with User Schemas (user views)Data Replicationzzzzzzz“Denormalize” to create duplicate dataPurposely storing the same data in multiplelocations of the databaseImproves performance by allowing multiple usersto access the same data at the same time withminimum contentionSacrifices data integrity due to data duplicationBest for data that is not updated oftenSometimes used for clients that are disconnectedfrom the system at timesRequires data to be synchronized periodicallyThree-Level View of Databasez Externalview (multiple): logical view ofpart of the database made available to a usergroup (subschema)z Conceptual view: logical view of entiredatabase (schema)z Internal view: physical view of database asstored by the DBMSz3

Internal View: Physical RecordszzzPhysical Record: A group of fields stored inadjacent memory locations and retrieved togetheras a unit by the DBMS; may be one or more rows,or part of a rowPage (Block): The amount of data read or writtenin one I/O operation by the OS; may be one ormore physical recordsBlocking Factor: The number of physical recordsper page (block)I/O ProcessOS retrieves first pageOS passes first physical record in page to DBMSDBMS processes rows in first physical recordOS passes next physical record in page to DBMSDBMS processes rows in next physical recordEtc.When there are no more physical records inpage, OS retrieves next pageDesigning Physical Filesz– A named portion of secondary memory allocated for thepurpose of storing physical recordszSequential File OrganizationPhysical File:Constructs to link two pieces of data:– Sequential storage – one record physically followsanother on disk.zzz– Pointers – physical location (address) of record on disk.zFile Organization:– How the files are arranged on the disk.zAccess Method:– How the data can be retrieved based on the filezzzorganization.Figure 6-7 (a)Sequential fileorganizationIndexed File Organization12zzRecords of thefile are stored insequence by theprimary keyfield values.If sorted –zevery insert ordelete requiresresortzzIf not sortedAverage time to finddesired record n/2.nRecords physically stored in sequence usuallyaccording to primary keyRecords accessed in sequenceAccessing a specific record: all records thatphysically come before the desired record must beaccessed first. Average access time N/2Inserting a new record requires rewriting the fileDeleting a record may require rewriting the fileUpdating the key field of a record requiresrewriting the fileIndex – a separate table that contains location ofrecords based on a column or combination ofcolumnsPrimary keys are automatically indexedOracle has a CREATE INDEX operation, and MSACCESS allows indexes to be created for mostfield typesIndexing approaches:– Basic concept – SQL Indexes slides– Multi-level (tree) index, Fig. 6-7b– B treez4

Fig. 6-7b – Multi-level (tree) indexIn this example:Pointer pointsto values value to left ofpointerLast level is pagewith multiplephysicalrecordsLeaves of the treeare all at samelevel Æconsistent accesstimeB TreezzzB tree: A type of multiple level index (balancedtree)B tree: A type of B treeBenefits:– Each access requires the same amount of time– Modifications of database require only changes in index(data in database does not have to be rewritten)uses a tree search– Modifications of database do not change access timeAverage time to find desiredrecord depth of the treeB TreeEach index node consists of:Ptr1 Key1 Ptr2 Key2 KeyN PtrN 1Ptr1 pointer to index node for values Key1Prt2 pointer to index node forvalues Key1 and Key2PtrN 1 pointer to index node for values KeyNLast level contains pointers to physical recordsSee B tree transparency/handoutHashing AlgorithmDivision remainder algorithm: Divide primary keyby nearest prime number to size of file and useremainder to indicate disk addressEx: File size 5000 Nearest prime 4999PK 85274 85274/4999 17 remainder 291Store row with PK 85274 as record 291 insequence from the beginning of fileProblem: two PKs can give same disk addressEx: PK 90273 90273 18 remainder 291Called collision. Collision handling algorithmneededHashed (Direct, Random)File Organizationz Addressof each record determined by ahashing (randomizing) algorithm thatconverts the primary key into a disk addressFig 6-7cHashed file orindexorganizationHash algorithmUsually uses divisionremainder to determinerecord position. Recordswith same position aregrouped in lists.z5

Comparison of FileOrganizationsStorageutilizationSpeed ofsequentialaccessSpeed ofrandomaccessSequentialBestIndexedIn betweenHashedWorstBestOKCan’t bedoneCan’t bedoneOKBestRules for Using IndexesMost DBMSs use some sort of indexed file structure(B tree)When to use indexes?1. Use on larger tables2. Index the primary key of each table (automatic inOracle)3. Index frequently searched fields (fields frequentlyin WHERE clause)4. Fields in SQL ORDER BY and GROUP BYcommands5. When there are a variety of values for a column; 100 values but not when there are 30 valuesFig 6-9 Join Index – speeds up join operationsRules for Using Indexes6. DBMS may have limit on number of indexes pertable and number of bytes per indexed field(s)7. Null values will not be referenced from an index8. Use indexes heavily for non-volatile databases;limit the use of indexes for volatile databasesWhy? Because modifications (e.g. inserts, deletes)require updates to occur in index filesQuery Optimizationz ParallelQuery Processing – specify extentof parallelismz Override Automatic Query Optimization maybez Data Block Size -- Performance tradeoffs:–––––Block contention – smaller block betterRandom access speed – smaller block betterSequential access speed – larger block betterRow size – block size should be multiple of row sizeOverhead – larger block size betterQuery Optimizationz Wiseuse of indexesz Compatible data types in comparisonsz Simple queriesz Avoid query nesting (subqueries)z Temporary tables for query groupsz Select only needed columnsz No sort without indexz6

Database ImplementationImplement physical design of databaseResult is the conceptual view of databaseCode the conceptual view (schema) description(CREATE TABLE commands in SQL)Populate the database with test data (INSERT commandsin SQL)Test the conceptual view of the database (datamanipulation commands in SQL)Database ImplementationEnhance performanceCreate indexes to improve database performance, ifnecessary (CREATE INDEX commands in SQL)Provide access for system developersGrant privileges to analyst/programmers developing otherparts of information system (GRANT commands inSQL)Database ImplementationImplement external viewsCode each external view (subschema) description(CREATE VIEW commands in SQL)Test the external views (data manipulation commands inSQL)Database implementationPrepare for installation(After all parts of information system have beendeveloped)Populate database with actual ("live") data (INSERTcommands in SQL)Grant privileges to users and user groups (GRANTcommands in SQL)z7

Physical Database Design and Performance Modern Database Management 6th Edition Jeffrey A. Hoffer, Mary B. Prescott, Fred R. McFadden Robert C. Nickerson ISYS 464 – Spring 2003 Topic 23 Database Development Process Database planning Database requirements analysis Conceptual database design