数据库原理与技术

Size: px

Start display at page:

Download "数据库原理与技术"

赦蛮毕
6 years ago
Views:

1 信息学院 2015 级,2017-2~6, 教 2221 数据库系统概论孟小峰中国人民大学

2 课程大作业实验进度安排实验阶段报告提交截止时间需求分析 5 月 18 日 24:00 概念数据库设计 5 月 25 日 24:00 逻辑数据库设计 6 月 1 日 24:00 物理数据库设计 6 月 8 日 24:00 系统实现 6 月 15 日 24:00 作业报告 6 月?? 日

3 第三篇系统篇

4 DBMS 的系统成分和工作流程

5 DBMS 的系统成分和工作流程

6 DBMS 的系统成分和工作流程

7 DBMS 的系统成分和工作流程

8 第三篇系统篇第? 章存储管理及索引第九章查询处理及查询优化第十章数据库恢复技术第十一章并发控制

9 数据库系统概论 An Introduction to Database Systems 第 X 章数据库存储管理 2017, 5, 11

10 File Organization(1) 数据库中的数据存储在操作系统管理的文件中 : 一个关系对应到一个文件一个关系对应到多个文件一个文件对应到多个关系操作系统分配给数据库系统一个大的操作系统文件所有关系都存储在这个文件中, 这个文件的管理由数据库系统进行

11 样例数据库 : File Organization(2) Branch-schema = (branch-name,branch-city,assets) Customer-schema = (customer-name,customer-street, customer-city) Account-schema = ( account-number, branch-name, balance) Loan-schema = ( loan-number, branch-name,amount) Depositor-schema = (customer-name,account-number) Borrower-schema = (customer-name,loan-number)

12 File Organization(3) 记录的物理存储文件中记录的组织

13 Record Storage(1) Fixed-Length Records( 定长记录文件 ) 文件中所有的记录都具有相同的长度, 从而一个块中所有的记录都是等长的 Variable-Length Records( 变长记录文件 ) 文件中的记录可以有不同的长度, 从而一个块中的各个记录可以具有不同的长度

14 Record Storage(2) 定长记录文件顺序存储法严重缺点删除一条记录十分困难待删除记录所占据的空间必须由文件中的其它记录来填充, 或者必须用一种方法标记被删除的记录使得它可以被忽略记录 0 Perryridge A 记录 1 Rouond Hill A 记录 2 Mianus A 记录 3 Downtown A 记录 4 Redwood A 记录 5 Perryridge A 记录 6 Brighton A 记录 7 Downtown A 记录 8 Perryridge A account 关系

15 Record Storage(3) 定长记录文件空闲指针链法 account 关系文件头记录 0 Perryridge A 记录 1 记录 2 Mianus A 记录 3 Downtown A 记录 4 记录 5 Perryridge A 记录 6 记录 7 Downtown A 记录 8 Perryridge A

16 Record Storage(4) 变长记录文件以下情况下需要变长记录文件 : 多种记录类型在一个文件中存储 Account-list ( branch-name, account-info: (account-number, balance)* ) 记录类型允许一个或多个字段是变长的 VARCHAR

17 Record Storage(5) 变长记录文件 ( 定长表示法 ) 使用一个或多个定长记录来代表一个变长记录预留空间 : 使用长度为最大记录长度的定长记录对较短记录未使用的空间用特殊的空值或记录终结符号来填充使用指针 : 变长记录用一系列通过指针链接起来的定长记录来表示

18 Record Storage(6) 预留空间的方法记录 0 Perryridge A A A 记录 1 Round Hill A 记录 2 Mianus A 记录 3 Downtown A A 记录 4 Redwood A 记录 5 Brighton A account-info 关系

19 Record Storage(7) 使用指针的方法记录 0 Perryridge A 记录 1 Rouond Hill A 记录 2 Mianus A 记录 3 Downtown A 记录 4 Redwood A 记录 5 A 记录 6 Brighton A 记录 7 A 记录 8 A account-info 关系

20 Record Storage(8) 使用指针的方法 (anchor block and overflow block) anchor block Perryridge A Round Hill A Mianus A Downtown A Redwood A Brighton A overflow block A A A

21 Record Storage(9) 变长记录文件 ( 变长表示法 ) Byte-String( 字节流 ) 表示 : 把每个记录作为一个连续的字节流存储, 每个记录的末尾附加一个特殊的记录终止符号 0 Perryridge A A A Round Hill A Mianus A Downtown A A Redwood A Brighton A 不易重新使用被删除记录的空间分配给记录的空间不能随记录的改变而改变

22 Record Storage(10) 变长记录文件 ( 变长表示法 ) 页 / 块结构 : 每个块的开始处有一个块头块头记录条目个数大小空闲空间尾指针位置空闲空间

23 Organization of Records in Files(1) How to organize the records in a file: Heap file( 堆文件组织 ): 记录没有顺序, 一条记录可以放在文件中的任何地方通常一文件一关系. Sequential file( 顺序文件组织 ): 记录根据检索码的值顺序存储 Hashing file( 散列文件组织 ): 散列函数的计算结果确定记录应存储到文件的哪个块中 Clustering file( 聚集文件组织 ): 几个不同关系的记录可以存储在同一个文件中不同关系中的相关记录存储在相同的块中

24 Organization of Records in Files(2) Many relational-database systems store each relation in a separate file to use OS file system However, many large-scale database systems do not relay directly on the underlying OS file. Instead, one large OS file is allocated to database system. All relations are stored in this one file. Database systems manage the file.

25 Organization of Records in Files(3) To see the advantage of method, consider the following SQL for bank database: Select account-number, customer-name, customer-street, customer-city from depositor, customer where depositor.customer-name = customer.customer-name

26 Organization of Records in Files(4) 聚集文件组织 Customer-name Account-number Hayes A-102 Hayes A-220 Hayes A-503 Turner A-305 depositor 关系聚集文件 Hayes Main Brooklyn Hayes A-102 Hayes A-220 Hayes A-503 Turner Putnam Stanford Turner A-305 Customer-name Customer-street Customer-city Hayes Main Brooklyn Turner Putnam Stanford Customer 关系

27 Organization of Records in Files(5) Clustering enhances the processing of join (depositor, customer), but slowing processing of other types of query. For example: Select * from customer; The query requires more block accesses than it did in one-relation-in-one-file It can be improved by chaining together all the records of the relation using pointers

28 Organization of Records in Files(6) 聚集文件组织 ( 带指针链 ) Hayes Main Brooklyn Hayes A-102 Hayes A-220 Hayes A-503 Turner Putnam Stanford Turner A-305

29 Organization of Records in Files(7) The determination of when clustering is to be used depends on the types of query that database designer believes to be most frequent Careful use of clustering can produce significant performance gains in query processing

30 Large Objects Storage(1) Large objects are called binary large objects (blobs) In relational systems, use long field to store large objects Most relational databases restrict the size of a record to be no larger than the size of a page, to simplify the buffer manager and free-space manager Large objects or long fields are often stored in a special file (or collection of files)

31 Large Objects Storage(2) Allocation of buffer pages for large objects is a big problem We often modify large objects by updating part of the object. For practical reasons, large objects are manipulated in application programs, rather than in database: Text data Graphical data Audio/video data

32 Access Methods: Sequential Access/Table Scan Consider query: select * from Employees where name = Bill Sequential access/scan: (tuples are scanned one at a time) to evaluate the condition on name. This is reasonable if Relation Employees is small, or High percentage of the tuples in the relation satisfy the condition. Too slow for most other cases.

33 Access Methods: Hash Index (1) Using a hash table: Create a hash table based on the values of A in advance. Suppose h( ) is the hash function used. To process a query with condition A = v, first use h(v) to find the bucket in the hash table and then compare v with the A-values in the bucket to identify qualified tuples.

34 Access Methods: Hash Index (2) Example: Suppose Employees has 9 tuples. Build a hash table based on Name. Suppose we have 3 buckets and each can hold 3 entries and an overflow pointer. Hash function: h(x) = seq(x) mod 3 seq(x) returns the serial number of the first letter in x in the English alphabet.

35 0 1 2 Access Methods: Hash Index (3) Hash Table Liz Roy Amy Mike Ann Bill Bob Bill Beth Stored Employees Table SSN Name Salary Bill 35k Amy 28k Bob 30k Mike 27k Liz 43k Bill 30k Ann 31k Beth 25k Roy 36k

36 Access Methods: Hash Index (4) Evaluate query using the hash table: select * from Employees where Name = Bill 1. Apply hash function to obtain a bucket#: hash( Bill ) = seq( Bill ) mod 3 = 2 mod 3 = 2 2. Search the found bucket (and related overflow bucket(s)) for Bill and follow proper pointer(s) to obtain the tuple(s).

37 Access Methods: Hash Index (5) Using hash table can reduce search time substantially. Example: Suppose Employees table has 1000 pages. The hash table on SSN has 50 pages and can be kept in memory. Finding a tuple using sequential scan needs about 500 page I/Os. Finding a tuple using the hash table needs 1 or 2 page I/Os.

38 Access Methods: Hash Index (6) Hash tables are effective only when op is = but not effective for other comparators. Best for primary keys where order is meaningless (e.g., SSN). Complications of implementing hash tables: hash function selection, collision resolution, bucket overflow, hash table overflow.

39 Access Methods: B + Tree (1) A B + tree is a balanced search tree. Each node (internal or external) is stored as a page. Format of an internal node: p1 a1 ai-1 pi ai ak-1 pk ak a <= a1... ai-1 < a <= ai... ak-1 < a < ak

40 Access Methods: B + Tree (2) Format of a leaf node: a1 p1 ai pi ak pk p All leaf nodes form a linked list in nondecreasing A-values. Every non-root node must be at least half full.

41 Access Methods: B + Tree (3)

42 Access Methods: B + Tree (4) Definition: If the tuples of a relation R are stored in ascending (or descending) A- values, then the B+tree index on A is a primary index (clustered index). Primary index is not directly related with the primary key. Definition: A secondary index (nonclustered index) is an index on an attribute whose values are not sorted.

43 Clustered / Non clustered index Clustered index (primary index) A clustered index on attribute X co-locates records whose X values are near to one another. Non-clustered index (secondary index) A non clustered index does not constrain table organization. There might be several non-clustered indexes per table. Records Records

44 Access Methods: B + Tree (5) Several pointer implementations possible: 1. Each p i in the leaf node points to a tuple. This is suitable for attributes that are candidate keys or have low-degree of repeating values.

45 Access Methods: B + Tree (6) Build an index based on R.A: (1) Sort R based on A and store the sorted R. (2) Create a pair (a, p) for each tuple t, where a is t[a] and p is the address of t. Sort all pairs based on a.

46 Access Methods: B + Tree (7) (3) Build the leaf nodes, starting with pairs with the smallest a s. Each leaf node has a pointer to the next leaf node. (4) Build the upper level nodes, one level at a time. (5) If insertion and update are expected, leave some free space in each page.

47 Access Methods: B + Tree (8) Stored Employees Table SSN Name Salary e1: Amy 28k e2: Ann 31k e3: Beth 25k e4: Bill 35k e5: Bob 30k e6: Fay 30k e7: Liz 43k e8: Mike 27k e9: Roy 36k Page k Page k+1 Page k+2 Page k+3 Page k+4

48 Access Methods: B + Tree (9) Fay Roy Ann Bill Fay Mike Roy Amy Ann Beth Bill Bob Fay Liz Mike Roy e1 e2 e3 e4 e5 e6 e7 e8 e9

49 Access Methods: B + Tree (10) Another pointer implementation: 2. Each p i in the leaf node points to a page that contains pointers to tuple(s) whose index value is a i. This is suitable for attributes that have highdegree of repeating values. For each distinct index value, exactly one pointer exists in the leaf node. An extra indirection is needed to access a tuple.

50 Access Methods: B + Tree (11)

51 Dense / Sparse Index Sparse index Pointers are associated to pages Dense index Pointers are associated to records Non clustered indexes are dense P1 P2 Pi record record record

52 Access Methods: B + Tree (12) Normal height of a B + tree is only 2 or 3. Example: Suppose Employees has 100,000 tuples of length 100 bytes. Each key value is 10 bytes and each pointer is 4 bytes. Each page is 2 KB. Each cell (a, p) has 14 bytes. Each page (2048 bytes) can contain 146 cells. # of cells (a, p): , needs 685 pages at the bottom level. # of cells at next level: 685, needs 5 pages. # of cells at next level: 5, needs 1 page.

53 Access Methods: B + Tree (14) Some questions: Can we create multiple primary indexes for the same relation? Can we create multiple secondary indexes for the same relation? Which is faster: primary index or secondary index?

54 Guidelines on Index Creation (1) Information that guides the creation of indexes is the transactional analysis of the requirements document. The following are the main factors on whether or not to create an index on an attribute A: Search frequency: How frequently A is searched, including for evaluating conditions and joins? Update frequency: How frequently A is updated, including insertion and deletion? Candidate key: Must the values of A be unique? Size: How large is the relation containing A?

55 Guidelines on Index Creation (2) No index on attribute A is needed if: There is low search frequency on A. The size of the relation containing A is very small. An index on attribute A should be created if: The search frequency on A is high. The values of A must be kept unique and there are not many insertions and updates involving A. Maintenance cost: Maintaining an index can be costly if frequent changes are needed. Be cautious if A is not a candidate key and has high update frequency.

56 Guidelines on Index Creation (3) Among all the attributes of a relation that should have an index, only one attribute can have a primary index, and all others will have secondary indexes. Attribute A should be favored to have a primary index if: Searches on A are more likely to returned multiple tuples (due to repeating values and range queries). A is the primary key of the relation (more joins are likely involve primary key).

57 An example (1) Consider table R(A, B, C, D) with the following information: A is the primary key and no other candidate key exists. Approximately, the number of distinct values under B is two times of that under C and this ratio does not change. Out of every 100 operations against R, 10 will be insertions; 10 will be deletions with 5 based on conditions on A and 5 based on conditions on B; 70 will be selection queries with 30 based on conditions on A, and 20 based on conditions on B and 20 based on conditions on C; and 10 will be updates with 5 based on conditions on B and 5 based on conditions on C. All conditions are equality conditions. Discuss which attribute should be used to build the primary index and which attribute(s) should be used to build secondary index(es).

58 An example (2) From the given information, the following can be derived: Out of every 100 operations: 45 need to search based on A (10 insertions, 5 deletions, 30 selections) 30 need to search based on B (5 deletions, 20 selections, 5 updates) 25 need to search based on C (20 selections, 5 updates) 0 need to search based on D

59 An example (3) A should have a secondary index (having a primary index on A does not improve efficiency because at most one tuple will satisfy each condition). D should not have any index because it is not used to search in any operation. B should have a secondary index and C should have a primary index. Even though a lightly larger percentage of all conditions involves B than C, the number of tuples satisfying each condition involving C is two times of that involving B because B has two times the number of distinct values than C. This implies that if both B and C had secondary indexes, each search based on C would cost twice as much as each search based on B. Therefore, having a primary index on C would reduce more cost than having a primary index on B.

60 Types of Queries 1. Point Query SELECT balance FROM accounts WHERE number = 1023; 2. Multipoint Query SELECT balance FROM accounts WHERE branchnum = 100; 3. Range Query SELECT number FROM accounts WHERE balance > 10000; 4. Prefix Match Query SELECT * FROM employees WHERE name = Jensen and firstname = Carl and age < 30;

61 Types of Queries 5. Extremal Query SELECT * FROM accounts WHERE balance = max(select balance from accounts) 6. Ordering Query 7. Grouping Query SELECT branchnum, avg(balance) FROM accounts GROUP BY branchnum; 8. Join Query SELECT * FROM accounts ORDER BY balance; SELECT distinct branch.adresse FROM accounts, branch WHERE accounts.branchnum = branch.number and accounts.balance > 10000;

62 Index and Query 1. Use a hash index for point queries only. Use a B-tree if multipoint queries or range queries are used 2. Use clustering if your queries need all or most of the fields of each records returned if multipoint or range queries are asked 3. Use a dense index to cover critical queries 4. Don t use an index if the time lost when inserting and updating overwhelms the time saved when querying

63 Covering Index Select name from employee where department = marketing Good covering index would be on (department, name) Index on (name, department) less useful. Index on department alone moderately useful. 3 - Index Tuning 63

64 Constraints and Indexes Primary Key, Unique A non-clustered index is constructed on the attribute(s) that compose the primary key with the constraint that values are unique. Foreign Key By default, no index is created to enforce a foreign key constraint.

65 Throughput (queries/sec) Scan Can Sometimes Win scan non clustering % of selected records IBM DB2 v7.1 on Windows 2000 Range Query If a query retrieves 10% of the records or more, scanning is often better than using a nonclustering non-covering index. Crossover > 10% when records are large or table is fragmented on disk scan cost increases. 3 - Index Tuning Dennis Shasha, Philippe Bonnet 2002,

66 Index Implementations in some major DBMS SQL Server B+-Tree data structure Clustered indexes are sparse Indexes maintained as updates/insertions/deletes are performed DB2 B+-Tree data structure, spatial extender for R-tree Clustered indexes are dense Explicit command for index reorganization Oracle B+-tree, hash, bitmap, spatial extender for R-Tree No clustered index Index organized table (unique/clustered) Clusters used when creating tables. MySQL B+-Tree, R-Tree (geometry and pairs of integers) Indexes maintained as updates/insertions/deletes are performed

67 SELECT questions FROM you SELECT thanks FROM me Tape is Dead Disk is Tape Flash is Disk -- Jim Gray, December 2006 未来每 18 个月产生的数据量等于有史以来的数据量之和 -- Jim Gray1998 图灵奖获奖演说 Copyright Do not duplicate without permission. 数据库系统概论讲义, 数据库存储管理 67,2017,5

数据库原理与技术

数据库原理与技术第三篇系统篇 DBMS 的系统成分和工作流程 DBMS 的系统成分和工作流程 DBMS 的系统成分和工作流程 DBMS 的系统成分和工作流程第三篇系统篇第? 章存储管理及索引第九章查询处理及查询优化第十章数据库恢复技术第十一章并发控制 Storage, File Organization and Indexing 11/30 File Organization(1) 数据库中的数据存储在操作系统管理的文件中