数据库系统架构

1. check that the query is correctly specified,
2. canonicalizes table names into a fully qualified name of the form server.database.schema.table
3. convert the query into the internal format used by the optimizer(catalog manager)
4. verify that the user is authorized to execute the query

The rewriter in many commercial systems is a logical component whose actual implementation is in either the later phases of query pars- ing or the early phases of query optimization. In DB2, for example, the rewriter is a stand-alone component, whereas in SQL Server the query rewriting is done as an early phase of the Query Optimizer. main responsibilities are:

1. View expansion
2. Constant arithmetic evaluation. R.x < 10+2+R.y as R.x < 12+R.y.
3. Logical rewriting of predicates NOT Emp.Salary > 1000000 as Emp.Salary < 1000000=
4. Semantic optimization

SELECT Emp.name, Emp.salary FROM Emp, Dept
WHERE Emp.deptno = Dept.dno

Such queries can be rewritten to remove the Dept table (assuming Emp.deptno is constrained to be non-null), and hence the join. Again, such seemingly implausible scenarios often arise naturally via views.

1. Subquery flattening and other heuristic rewrites

Predicate transi- tivity, for example, can allow predicates to be copied across subqueries [52].

Although Selinger’s paper is widely considered the “bible” of query optimization, it was preliminary research. All systems extend this work significantly in a number of dimensions. Among the main exten- sions are:

Most modern query executors employ the iterator model that was used in the earliest relational systems. Iterators are most simply described in an object-oriented fashion.

1

class iterator { iterator &inputs[]; void init(); tuple get_next(); void close(); }

Sequential bandwidth to and from disk is between 10 and 100 times faster than random access, and this ratio is increasing.

The best way for the DBMS to control spatial locality of its data is to store the data directly to the “raw” disk device and avoid the file system entirely. This works because raw device addresses typically correspond closely to physical proximity of storage locations.

An alternative to raw disk access is for the DBMS to create a very large file in the OS file system, and to manage positioning of data as offsets in that file. The file is essentially treated as a linear array of disk-resident pages. If the file system is being used rather than raw device access, special interfaces may be required to write pages of a different size than that of the file system; the POSIX mmap/msync calls, for example, provide such support.

DBMS contains critical logic that reasons about when to write blocks to disk. Most OS file systems also provide built-in I/O buffering mechanisms to decide when to do reads and writes of file blocks. If the DBMS uses standard file system interfaces for writing, the OS buffering can confound the intention of the DBMS logic by silently postponing or reordering writes. This can cause major problems for the DBMS.

The second set of problems with OS buffering concern performance, but have no implications on correctness. Modern OS file systems typically have some built-in support for read-ahead (speculative reads) and write-behind (delayed, batched writes). These are often poorly suited to DBMS access patterns.

The final performance issues are “double buffering” and the high CPU overhead of memory copies. Copying data in memory can be a serious bottleneck. Copies contribute latency, consume CPU cycles, and can flood the CPU data cache.

This fact is often a surprise to people who have not operated or implemented a database system, and assume that main-memory oper- ations are “free” compared to disk I/O. But in practice, throughput in a well-tuned transaction processing DBMS is typically not I/O-bound. This is achieved in high-end installations by purchasing sufficient disks and RAM so that repeated page requests are absorbed by the buffer pool, and disk I/Os are shared across the disk arms at a rate that can feed the data appetite of all the processors in the system. Once this kind of “system balance” is achieved, I/O latencies cease to be the primary system throughput bottleneck, and the remaining main-memory bottlenecks become the limiting factors in the system. Memory copies are becoming a dominant bottleneck in computer architectures: this is due to the gap in performance evolution between raw CPU cycles per second per dollar (which follows Moore’s law) and RAM access speed (which trails Moore’s law significantly) [67].

In order to provide efficient access to database pages, every DBMS implements a large shared buffer pool in its own memory space. The buffer pool is organized as an array of frames, where each frame is a region of memory the size of a database disk block. Blocks are copied into the buffer pool from disk without format change, manipu- lated in memory in this native format, and later written back. This translation-free approach avoids CPU bottlenecks in “marshalling” and “unmarshalling” data to/from disk; perhaps more importantly, fixed-sized frames sidestep the memory-management complexities of external fragmentation and compaction that generic techniques cause.

For full table scan access patterns, the recency of reference is a poor predictor of the probability of future reference, so OS page replacement schemes like LRU and CLOCK were well-known to perform poorly for many database access patterns [86]. A variety of alternative schemes were proposed, including some that attempted to tune the replacement strategy via query execution plan information [15]. Today, most systems use simple enhancements to LRU schemes to account for the case of full table scans.

• One that appears in the research literature and has been implemented in commercial systems is LRU-2 [64].
• Another scheme used in commercial systems is to have the replacement policy depend on the page type: e.g., the root of a B+-tree might be replaced with a different strategy than a page in a heap file. This is reminiscent of Reiter’s Domain Separation scheme [15, 75].

Roughly speaking, modern DBMSs implement isolation via a locking protocol.

• Durability is typically implemented via logging and recovery.
• Isolation and Atomicity are guaranteed by a combination of locking (to prevent visibility of transient database states), and logging (to ensure correctness of data that is visible).
• Consistency is managed by runtime checks in the query executor: if a transaction’s actions will violate a SQL integrity constraint, the transaction is aborted and an error code returned.

Serializability is enforced by the DBMS concurrency control model. There are three broad techniques of concurrency control enforcement. These are well-described in textbooks and early survey papers [7], but we very briefly review them here:

• Strict two-phase locking (2PL).Transactions acquire a shared lock on every data record before reading it, and an exclusive lock on every data item before writing it. All locks are held until the end of the transaction, at which time they are all released atomically. A transaction blocks on a wait-queue while waiting to acquire a lock.
• Multi-Version Concurrency Control (MVCC): Transactions do not hold locks, but instead are guaranteed a consistent view of the database state at some time in the past, even if rows have changed since that fixed point in time.
• Optimistic Concurrency Control (OCC): Multiple transactions are allowed to read and update an item without blocking. Instead, transactions maintain histories of their reads and writes, and before committing a transaction checks history for isolation conflicts they may have occurred; if any are found, one of the conflicting transactions is rolled back.

Most commercial relational DBMS implement full serializability via 2PL. The lock manager is the code module responsible for providing the facilities for 2PL. In order to reduce locking and lock conflicts some DBMSs support MVCC or OCC, typically as an add-on to 2PL. In an MVCC model, read locks are not needed, but this is often implemented at the expense of not providing full serializability, as we will discuss shortly in Section 4.2.1. To avoid blocking writes behind reads, the write is allowed to proceed after the previous version of the row is either saved, or guaranteed to be quickly obtainable otherwise. The in-flight read transactions continue to use the previous row value as though it were locked and prevented from being changed. In commercial MVCC implementations, this stable read value is defined to be either the value at the start of the read transaction or the value at the start of that trans- action’s most recent SQL statement. While OCC avoids waiting on locks, it can result in higher penalties during true conflicts between transactions. In dealing with conflicts across transactions, OCC is like 2PL except that it converts what would be lock-waits in 2PL into transaction rollbacks. In scenaries where conflicts are uncommon, OCC performs very well, avoiding overly conservative wait time. With frequent conflicts, however, excessive rollbacks and retries negatively impact performance and make it a poor choice