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

• CPU cache lines
• CPU and memory controller may reorder memory writes.
• cache line flush instruction (CLFLUSH for short) / memory fence instruction (MFENCE for short), to ensure the ordering of memory writes
• atomic memory write of NVM is 8 bytes, which is equal to the memory bus width for 64-bit CPUs

• Existing techniques, such as logging and copy-on-write (CoW), are used to guarantee consistency of the data whose sizes are larger than an atomic-write size.

  • The logging technique first stores the old data (undo logging) or new data (redo logging) into a log and then updates the old data in place.
  • The CoW first creates a new copy of data and then performs updates on the copy. The pointers that point to the old data are finally modified.
  • Nevertheless, logging and CoW have to write twice for each updated data.

• https://www.gnu.org/software/emacs/emacs-paper.html#SEC17

Like any Lisp, Emacs Lisp has always had a symbol data type: The expression ’emacs yields a symbol named emacs. One way to look at symbols is that they are immutable strings with a fast equality check and usually fast hashing. This makes them suitable for values representing enumerations or options. Another is that symbols can represent names in an Emacs Lisp program. Symbols are thus a key feature to make Emacs Lisp homoiconic, meaning that each Emacs Lisp form can be represented by a data structure called an S-expression that prints out the same as the form.

Richard Stallman chose dynamic scoping to meet extensibility requirements in Emacs [Stallman 1981]. The Emacs code base uses variables to hold configuration options. It would in principle be possible to structure the code base to pass configuration options explicitly, but this would make the code verbose, and require changing many function signatures once a new configuration option gets added to the system.

Quote is usually introduced via ' where the reader translates 'SEXP to (quote SEXP), and this expression evaluates to the value SEXP. For example:

1

'(a (b c d) c)

evalutes to a list whose first element is the symbol a, the second a list consisting of elements b, c, and d, and whose third element is c. It does so in constant time, by always returning the same value already present in the source code returned by the reader.

One important aspect of the extensibility Richard Stallman originally conceived for Emacs was the ability to make existing functions run additional code without having to change them, so as to extend their behavior. Emacs supports this at well-defined points called hooks.

Of course, authors do not always have the foresight to place hooks where users need them, so in 1992, the advice.el package was added to Emacs 19, providing a defadvice macro duplicating a design available in MacLisp and Lisp Machines.

1
2
3
4

(defadvice eval-region (around cl-read activate)
  "Use the reader::read instead of the original read if cl-read-active."
  (with-elisp-eval-region (not cl-read-active)
                          ad-do-it))

Furthermore, the way the defadvice macro gave access to function arguments did not work with lexical scoping. This was solved in late 2012: as a result of a discussion with a user asking how to put several functions into a single variable, Stefan Monnier developed a new package nadvice.el that can not only combine several functions into a single variable, but uses that to provide the same core features as defadvice but with a much simpler design.

For example, the old advice system had special features to control whether a piece of advice should be compiled whereas in the new system there is no need for that because a piece of advice is simply a normal function. Similarly, the old advice system has special primitives to get access to the function’s arguments, whereas in the new system, the function’s original arguments are passed as normal arguments to the piece of advice and can hence be accessed without any special construct. The nadvice.el package was released as part of Emacs 24.4, and has proved popular in the sense that it has largely replaced the old defadvice in new code, but rather few packages that used defadvice have been converted to the new system.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(defun forward-symbol (arg)
  "Move point to the next position that is the end of a symbol.
A symbol is any sequence of characters that are in either the word constituent or symbol constituent syntax class.
With prefix argument ARG, do it ARG times if positive, or move backwards ARG times if negative."
  (interactive "^p")
  (if (natnump arg)
      (re-search-forward "\\(\\sw\\|\\s_\\)+" nil 'move arg)
    (while (< arg 0)
      (if (re-search-backward "\\(\\sw\\|\\s_\\)+" nil 'move) (skip-syntax-backward "w_"))
      (setq arg (1+ arg)))))

In the above example, p means that the function accepts a prefix argument: The user can type C-u number prior to invoking the function, and the number will be passed to the function as an argument, in this case as arg. The ^ (a more recent addition) has to do with region selection with a pressed shift key–it may lead to the region being activated.

Variables can be both buffer-local and dynamically bound at the same time:

1
2
3

(let ((buffer-file-name "/home/rms/.emacs"))
  (with-current-buffer "some-other-buffer"
    buffer-file-name))

This example will not return /home/rms/.emacs but the buffer-local value of buffer-file-name in the buffer some-other-buffer instead, because with-current-buffer temporarily changes which buffer is current.

Emacs Lisp included support for string objects from the beginning of course. Originally, they were just byte arrays. In 1992, during the early development of Emacs 19, this basic type was extended by Joseph Arceneaux with support for text properties.

Each char of a string can be annotated with a set of properties, mapping property names to values, where property names can be any symbol. This can be used to carry information such as color and font to use when displaying the various parts of the string.

Along with buffer-local variables (Section 4.10), this is one of the cases where the core Emacs Lisp language has been extended with a feature that specifically caters to the needs of the Emacs text editor, to keep track of rendering information. It is more generally useful, of course, and turns strings into a much fancier datatype than in most other languages.

Rather than follow the usual design based on file or stream objects and primitives like open/read/write/close, Emacs Lisp offers only coarser access to files via two primitive functions insert-file-contents and write-region that transfer file contents between a file and a buffer. So all file manipulation takes place by reading the file into a buffer, performing the desired manipulation in this buffer, and then writing the result back into the file.

Since this approach does not extend naturally to interaction with external processes or remote hosts, these are handled in a completely different way. Primitive functions spawn a sub-process or open up a connection to a remote host and return a so-called process object. These objects behave a bit like streams, with process-send-string corresponding to the traditional write, but where the traditional read is replaced by execution of a callback whenever data is received from the sub-process or the remote host.

Emacs has two execution engines for Emacs Lisp,

• One is a very simple interpreter written in C operating directly on the S-expression representation of the source code.
• The other is a byte-code engine, implemented as a primitive byte-code function that interprets its string argument as a sequence of stack-based byte codes to execute. A compiler, written in Emacs Lisp, translates Emacs Lisp code to that byte-code language.

While Emacs Lisp is basically a "run of the mill" programming language, with some specific functions tailored to the particular use of a text editor, this byte-code language is much less standard since it includes many byte codes corresponding to Emacs Lisp primitives such as forward-char, insert, or current-column.

Emacs Lisp does not implement proper tail calls [Clinger 1998]: Each function call consumes stack space.

Dynamic scoping had two main drawbacks in practice:

• The lack of closures
• The global visibility of variable names

Finally in 2010 Igor Kuzmin worked on a summer project under the direction of Stefan Monnier, in which he tried to add lexical scoping to the byte-code compiler differently: instead of directly adding support for lexical scoping and closures to the single-pass byte-code compiler code (which required significant changes to the code and was made more complex by the need to fit into a single pass), he implemented a separate pass (itself split into two passes) to perform a traditional closure conversion as a pre-processing step. This freed the closure conversion from the constraints imposed by the design of the single-pass byte-code compiler, making it much easier to implement, and it also significantly reduced the amount of changes needed in the byte-code compiler, thus reducing the risk of introducing regressions.

Two years later, Emacs 24.1 was released with support for lexical scoping based on Miles Bader’s lexbind branch combined with Igor’s closure conversion.

While working on the lexical-binding feature, Stefan Monnier grew increasingly frustrated with the shape of the code used to traverse the abstract syntax tree, littered with car, cdr carrying too little information, compared to the kind of code he would write for that in statically-typed functional languages with algebraic datatypes.

So the pcase.el package was born, first released as part of Emacs 24.1, and used extensively in the part of the byte-code compiler providing support for lexical scoping.

• https://lists.gnu.org/archive/html/emacs-devel/2012-02/msg00283.html

During the development of Emacs 24.3 the issue of better integration of the cl.el package came up again. The main point of pressure was the desire to use cl.el functions within packages bundled with Emacs. Richard Stallman still opposed it, but this time, a compromise was found: replace the cl.el package with a new package cl-lib.el that provides the same facilities, but with names that all use the cl- prefix. This way, the cl-lib.el package does not turn Emacs Lisp into Common Lisp, but instead provides Common Lisp facilities under its own namespace, leaving Emacs Lisp free to evolve in its own way.

• MyRocks record format · facebook/mysql-5.6 Wiki

在MyRocks中，每个MySQL表的行存储为一个RocksDB键值对:

• 主键（Primary index）编码在 key 中，并且所有其他行数据编码在 value 中。

  • 主键的编码方式遵循 MySQL 的数据类型规则，例如整数按小端序编码，字符串按字节序编码。

• 辅助索引编码（Secondary Index），不一定唯一，被以独立的键值对存储；key 是 索引ID + 索引列值 + 主键值 value 留空；

  • 副索引查找转换为RocksDB范围查询
  • 索引 ID 用于区分不同的索引，确保不同索引的键不会冲突。

所有的RocksDB键都前缀了一个4字节的表ID或索引ID以便多个表或索引可以在一个RocksDB键空间共存。最后，一个随每次写入操作递增的世界序列号，被每个键值对存储以支持快照。快照用于实现多版本并发控制，反过来允许我们在RocksDB中实现ACID事务。