M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, Jul 1981.  @ NUS  Home/Search   Document Not in Database   Summary   Related Articles   Check

.... network access costs and protocol overhead [2, 8, 20, 29] A related source of inefficiency stems from poor integration of applications and file system services; lack of control over kernel policies leads to problems such as double caching, false prefetching and poor concur rency management [34]. As a result, databases and other performance critical applications often bypass file systems in favor of raw block storage access. This sacrifices the benefits of the file system model, including ease of administration and safe sharing of resources and data. These problems have also motivated ....

....with inadequate kernel support for asynchronous I O, and it offers full ap plication control over caching, data movement and prefetching. It has long been recognized that the kernel policies for file system caching and prefetching are poorly matched to the needs of some important ap plications [34]. Migrating these OS functions into libraries to allow improved application control and specialization is similar in spirit to the library oper ating systems of Exokernel [21] protocol service decomposition for high speed networking [24] and re lated approaches. User level file systems were ....

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412-418, July 1981.

....All of the above approaches rely on a single, system global allocation policy. We consider this overly restrictive because this policy is always a compromise between performance and generality; related work has shown that applications are often ill served by the default operating system policy [1, 50] and can benefit significantly from managing their own memory resources [15, 19, 20, 27, 29, 39] Also, while the allocation policy can be configured in some of the approaches, other policies, e.g. for placement or replacement, cannot be influenced at all. Furthermore, the effectivity of this ....

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, Jul 1981.

....represents the summary of a spatial join, then the pages of R are clustered using their spatial relationship with the pages of S, and the proposed method is called Asymmetric Spatial Clustering. The OPAS FB problem is a special case of buffer pool management problems for databases. Prior work [36, 8, 39] has examined access patterns for index traversal, scan, and nested loop join. They have not explored buffer management for join computation given a join index, which is the focus of various solutions to OPAS FB problem. 2.1 Basic Idea Behind Asymmetric Clustering(AC) The example in Figure 4 ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

....constraints that are very di#erent from regular desktop computers or dedicated equipment in data centers, and query processing has to be aware of these constraints. One way of thinking about such constraints is the analogous interaction with the file systems in traditional database systems [37]. Database systems bypass the file system bu#er to have direct This is only a rule of thumb, since transmission range, bit error rates, and instruction width influence this parameter significantly. control over the disk. For a sensor network database system, the analogous counterpart is the ....

M. Stonebraker. Operating system support for database management. CACM, 24(7):412--418, 1981.

.... System with the Berkeley DB Nick Murphy nmurphy fas.harvard.edu Mark Tonkelowitz mtonkel fas.harvard.edu Mike Vernal vernal fas.harvard.edu October 16, 2001 1 Introduction In 1981, Michael Stonebraker argued that many operating system services were suboptimal for database applications [6]. Despite these deficiencies, most users continue to run their Database Management Systems (DBMSs) on top of a regular operating system. In fact, though Stonebraker suggested that the gap between the OS and Database community was widening in 1981, we find that much novel research in operating ....

Michael Stonebraker. Operating system support for database management. In Communications of the ACM, v.24, no. 7, pages 412-- 418. Association for Computing Machinery, 1981. 5

....a file server running the Sun Network File System (NFS) protocol that uses DBFS as its backing store, and we compare it with a traditional user level NFS server implementation. 1 Introduction In 1981, Michael Stonebraker lamented that operating system support for databases was suboptimal [7]. Stonebraker argued that kernel scheduling and allocation policies were often pessimal for common database workloads, and that the file system abstraction was often superfluous. Despite these deficiencies, users continue to run database systems on top of normal operating systems. Though it was ....

....4, we discuss the actual implementation of DBFS on top of BDB. We describe our measurement methodology and results in section 5. We suggest some future work in section 6 and we conclude in section 7. 2 Related Work Stonebraker noted a number of problems that DBMSs had with typical file systems [7], including: 1. Block allocation is not always physically contiguous, which defeats attempts by databases to localize data. 2. The overlapping of the tree structure of most block oriented file systems and the tree structure of a database index adds unnecessary overhead. 3. Bu#er allocation ....

Michael Stonebraker. Operating system support for database management. In Communications of the ACM, v.24, no. 7, pages 412-- 418. Association for Computing Machinery, 1981.

....50 80 worse than that of the Berkeley Fast File System (FFS) For metadata operations, we significantly outperformed normal FFS, though we were outperformed by FFS with Soft Updates. 1 Introduction In 1981, Michael Stonebraker lamented that operating system support for databases was sub optimal [11]. Stonebraker argued that kernel scheduling and allocation policies were often pessimal for common database workloads. The file system abstraction was superfluous. Twenty years later, though, users continue to run database systems on top of general operating systems. The gap between the operating ....

....the actual implementation of DBFS with relation to BDB. We discuss our experimental results in section 5, and we suggest some areas for future work in section 6. 2 Related Work It was more than twenty years ago that Stonebraker noted a number of problems that DBMSs had with typical file systems [11], including: Block allocation is not always physically contiguous, which defeats attempts by databases to localize data. The overlapping of the tree structure of most block oriented file systems and the tree structure of a database index adds unnecessary overhead. Bu#er allocation ....

Michael Stonebraker. Operating system support for database management. In Communications of the ACM, v.24, no. 7, pages 412--418. Association for Computing Machinery, 1981.

....phase locking, etc. are available for ensuring serializability in such systems [10] 2.2.2 Buffer Manager In most computer setups, the operating system is responsible for the management of physical resources. However, the policies used by the OS are often unsuitable to meet database objectives [94]. Therefore, some OS functionalities are re implemented by database system builders to suit their requirements. In particular, database systems reserve a region of main memory to serve as a database cache of the persistent data on disk. This memory space is usually referred to as the buffer pool ....

M. Stonebraker, "Operating System support for Database Management", Comm. of ACM, Vol. 24, No. 7, 1981.

....be retrieved faster with HTTP servers, or be played back in real time [Anderson92, Ramakrishnan93, Fall94, Mercer94, Pasquale94] 2. Databases: researchers are looking for methods to improve the performance of Unix le systems, and or for le systems that provide built in support for concurrency [Stonebraker81, Stonebraker86]. 3. Mobility: replicated and distributed le systems with disconnected and caching operations gure heavily in an environment where network latency and reliability is highly variable [Satyanarayanan90, Kistler91, Tait91, Tait92, Kistler93, Zadok93a, Kuenning94, Marsh94, Mummert95] 4. ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412-18, July 1981.

....exposed to applications. This can have a serious impact on application performance if the resource usage and access patterns used by the application do not map well onto the operating systems policies. This is one of the major issues with operating system design often cited by database designers [121]. Internet services do not have the luxury of paying an arbitrary penalty for processing such requests under heavy resource contention. In many cases it is necessary for a service to prioritize request processing based on resource availability. For instance, a service may be able to process ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

....requirements is usually minimal or total; that is, they may give the application the choice of taking either no responsibility or full responsibility for device access and management. Consequently, demanding applications such as database management systems prefer to take total responsibility [67]. In the analogous case of the network interface, there is also much interest in allowing applications to access devices directly and bear responsibility for management [6, 46, 72] An important recent approach to application customization in operating systems can also be applied to storage ....

STONEBRAKER, M. Operating system support for database management. Communications of the ACM 7, 24 (July 1981).

.... copying, network access costs and protocol overhead [2, 8, 20, 29] A related source of ine#ciency stems from poor integration of applications and file system services; lack of control over kernel policies leads to problems such as double caching, false prefetching and poor concurrency management [34]. As a result, databases and other performance critical applications often bypass file systems in favor of raw block storage access. This sacrifices the benefits of the file system model, including ease of administration and safe sharing of resources and data. These problems have also motivated ....

....with inadequate kernel support for asynchronous I O, and it o#ers full application control over caching, data movement and prefetching. It has long been recognized that the kernel policies for file system caching and prefetching are poorly matched to the needs of some important applications [34]. Migrating these OS functions into libraries to allow improved application control and specialization is similar in spirit to the library operating systems of Exokernel [21] protocol service decomposition for high speed networking [24] and related approaches. User level file systems were ....

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412--418, July 1981.

....data. Persistence is integrated into the programming language with high level of transparency. Representative projects include PS Algol [5, 4] Napier88 [28] and PJama [6] In the early 80 s, Stonebraker pointed out the poor operating systems support for database management systems requirements [58]. Representative projects having taken into account such requirements include the work on Mach s external mapers [64] single address space operating systems such as Angel [46] Opal [21] and Mungi [62] persistent virtual shared memories such as ARIAS [29] and RVM [54] re ective operating ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412-418, July 1981.

....2.1 Needs of a Fail Safe Mechanism Extending operating systems is motivated by the needs of many applications. For example, developers for database applications want to change disk I O bu#ering because a traditional general algorithm for bu#ering does not suit for disk access patterns of database [46]. In the field of multimedia, the issues of CPU scheduling, memory management, and network implementation in the current operating systems are pointed out [42] A part of these issues would be solved by extending the operating systems on demand. The extension of operating systems has two ....

Stonebraker, M., "Operating System Support for Database Management," Communications of the ACM, vol. 24, pp. 412--418, July 1981.

....of CHAPTER 1. INTRODUCTION 9 each page, not requiring any external hint. A representative approach of this class is the LRU K algorithm proposed by O Neil et.al. 39] The LRU K algorithm is motivated by knowing that the popular LRU algorithm is not always appropriate for the database environment [43, 45, 18, 50]. By keeping only the time of last reference to a page, the LRU algorithm cannot well distinguish between frequently referenced pages and infrequently referenced pages. The basic idea of LRU K is to consider the time of the last K references to a page and uses such information to make page ....

M. Stonebraker. Operating system support for database management. In Communications of the ACM, volume 24, pages 412--418, July 1981.

.... the history of computer science there has been a fairly constant opinion that current operating systems are inadequate [4, 7, 9, 11, 15, 18] The literature is rife with specific examples that describe the cost of the inappropriate, inefficient abstractions peddled by operating systems [2, 4, 12, 13, 18, 23, 24]. This situation has persisted for the last three decades, and has survived numerous assaults (object oriented operating systems and micro kernels are two of the more popular movements) As a general rule, a concept that cannot be realized after such a long period of time should be reexamined. ....

....abstractions; unfortunately, such emulation is typically clumsy, complicated, and prohibitively expensive. For example, once the application has no access to the raw disk interface, database records must be emulated on top of files. The list of such examples is painfully long and continues to grow [2, 4, 13, 18, 23, 24]. In short, operating systems are complex, fragile, inflexible, and slow, because they have dabbled in the practice of providing a general purpose virtual machine. The operating system is basically hardware masquerading as software: it cannot be changed, all applications must use it, and the ....

M. Stonebraker. Operating system support for database management. CACM, 24(7):412--418, July 1981.

....an arbitrary penalty for processing such requests under heavy resource contention. Most operating systems hide the performance aspects of their interfaces; for instance, the existence of (or control over) the underlying file system buffer cache is typically not exposed to applications. Stonebraker [26] cites this aspect of OS design as a problem for database implementations as well. Coarse grained scheduling: The thread based concurrency model yields a coarse degree of control over resource management and scheduling decisions. While it is possible to control the prioritization or runnable ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

.... System Support for Database Management Systems Revisited Daniel Fellig, Olga Tikhonova December 18, 2000 Abstract In the early 1980s Michael Stonebraker [9] wrote a paper titled Operating System Support for Database Management , outlining where and how operating systems at the time failed to meet the needs of database management systems in terms of some typical services that operating systems provide to applications. Stonebraker points out these ....

....the interfaces that NT provides to applications for imposing their own bu er policies on top of NT s. This is precisely what Stonebraker described twenty years ago in terms of database management systems having to manage their own bu er pool on top of UNIX, citing Ingres as a speci c example [9]. In essence, this paper simply asks whether Microsoft Windows NT 4.0, a commodity operating system, is any closer to satisfy bu er requirements of RDBMS than UNIX was twenty years ago; and if the answer is in the negative, we investigate what appropriate interfaces NT exposes for the DBMS bu er ....

M. Stonebraker. "Operating System Support for Database Management", Communications of the ACM, vol.24, no. 7, pp. 412-418, 1981. 13

....described in section 3. The advantage of W conductor is based on closelycoupled predefined W cluster structure. In this sense the W conductor implementation is topology dependent while the W router implementation is topology independent. 2. 2 Software Architecture of Omega As it was shown in [12], an operating system support provided by an universal operating system is not appropriate for specific DBMS needs in many ways. For example, a message passing initiation in UNIXsimilar distributed operating system Helios for MVS 100 includes about 3000 instructions. It forces DBMS designers to ....

Stonebraker M. "Operating System Support for Database Management" CACM. July 1981; 24 (7): pp 412-418.

....for the longest period of time is replaced. This algorithm is chosen as the page replacement policy by almost all commercial systems. The LRU K algorithm is motivated by knowing that the popular LRU algorithm is not always appropriate for the database environment (for more details, see [Rei76] [Sto81] [SS86] and [CD85] The key observation is that LRU keeps only the time of last reference to each page when making page replacement decision. Thus, the LRU algorithm cannot well distinguish between frequently referenced pages and infrequently referenced pages due to the limited information it is ....

M. Stonebraker. Operating system support for database management. In Communications of the ACM, volume 24, pages 412--418, July 1981. 7

....as a buffer management system that makes intelligent replacement decisions will increase the frequency that the requested page will be found in the buffer pool. It is interesting to note that although an LRU replacement strategy provides poor 2 performance for many relational operators [STON81, SACC82], it appears that an LRU policy is best for managing the replacement 4 of shared data pages. Thus to achieve optimal performance a database system may have to use different algorithms depending on whether or not a data page is being shared. We are currently investigating this issue. To explore ....

Stonebraker, M., "Operating System Support for Database Management," Communications of the ACM, Vo. 24, No. 7, July 1981, pp. 412-418.

....f uzz makes room for the hash table overhead. In reality, even this threshold memory results in thrashing, because the working set for the algorithm is greater than the theoretical threshold memory and the LRU paging scheme then makes the wrong decision, removing useful pages prematurely. See [31, 34] for more discussion on this problem. In the next section, we derive an approximation for the amount of extra I O that takes place when memory is insufficient. 7.3 Analysis The disk band sizes during pass 0 and pass 1 are BandSize pass0 = P R P S i P R S i P RP i and BandSize pass1 = P R S ....

Stonebraker, M. Operating system support for database management. CACM, 24(7):412--418, July 1981.

....hardware to provide high level abstractions such as processes and file systems that enable application developers to build systems both efficiently and portably. Although high level abstractions like this are suitable for many systems, there are also systems for which they are not appropriate [4, 6, 25, 43, 46]. This would be acceptable if the developers of these systems could simply ignore the abstractions that are unsuitable and create their own from scratch. However, since the operating system defines a high level virtual machine, applications are effectively forced to use the abstractions provided. ....

M. Stonebraker, "Operating System Support for Database Management", Communications of the ACM, 24(7), pp. 412-418, 1981.

....those needed to enforce security) directly accessible from user level. This is discussed further in [3] 1] and [7] The duplication of information between user level and the kernel is a source of inefficiency in many persistent, database and middleware systems and has been reported elsewhere [8] [2] The most notable example of this involves the virtual address translation tables that are often wholly or partially replicated in user level memory managers and the kernel. We seek to eliminate the replication of such data structures and wherever possible give the user level control of them ....

M. Stonebraker, "Operating System Support for Database Management", Communications of the ACM, 24(7), pp. 412-418, 1981.

....common techniques for meeting those requirements. By examining these techniques it attempts to identify deficiencies in traditional operating system support for the implementation of persistent systems. These deficiencies have much in common with those reported by implementers of database systems [61] [13] Section 3 surveys some operating systems that have attempted to provide direct operating system support for orthogonal persistence. In each case, only those operating system features related to persistence are discussed. Section 4 analyses the lessons learned from these attempts. In ....

....observe that inappropriate operating system abstractions have hindered their development since their inception. That conventional operating system abstractions are inappropriate for the construction of persistent systems and database systems has been known to many for a considerable period of time [61] [13] The major hurdles encountered are: 1. That no widely used operating system provides sufficiently flexible mechanisms to enable the hardware facilities to be exploited to their full potential in order to manage persistent objects and their inter relationships. 2. The abstractions provided ....

M. Stonebraker, "Operating System Support for Database Management", Communications of the ACM, 24(7), pp. 412-418, 1981.

....policy minimizes paging activity due to most applications locality of reference. 2.5.3 Degrees of flexibility for virtual memory Even though many applications work well with locality based page replacement policies, quite a few applications are detrimentally affected by them. Stonebraker [Stonebraker 81] noted that LRU can behave poorly for managing database buffer pages (a topic revisited in Section 4) and other researchers have examined particular reference patterns, noting their adverse behavior when being serviced by the LRU policy [Hagmann 92] To improve performance in these situations, ....

....are committed to backing storage. Atomicity and consistency, on the other hand, do not directly involve specialized memory management. Atomicity is enforced using synchronization and one of a variety of logging techniques. Consistency is dependent upon program correctness. 19 Stonebraker [Stonebraker 81] noted that the two memory management interfaces provided by operating systems (i.e. virtual memory and files) can not be easily or efficiently used to directly implement transactions. Thus database systems traditionally implement their own memory management systems upon which they build ....

Michael Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412--418, 1981.

....guarantees that joins will use more memory than is physically available in order to trigger the adaptive mechanism. It has been shown that database algorithms perform significantly better when they manage their own memory, rather than relying on the virtual memory manager of the operating system [Ver86, Sto81]. In contrast, since BAS knows exactly how much memory is in use by all queries in the system, it can arrange memory usage such that the sum total of memory used by all queries never exceeds the physical memory available. This means that BAS will never cause page faults during the execution of a ....

Michael Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7), 1981.

....to customized applications. Prominent prototypes are Mach, Chorus, and Amoeba, but also conventional systems like Silicon Graphics IRIX and Sun s Solaris 6 provide hooks for better memory and process management. Stonebraker discarded the possibility of using memory mapped files in databases [16], on the grounds that operating systems did not give sufficient control over the buffer management strategy, and the fact that virtual management schemes waste memory. Now a decade later we think the picture has changed. Operating systems like Solaris and IRIX do provide hooks to give memory ....

M. Stonebraker. Operating system support for database management. Communications of the ACM, 14(7), July 1981.

....1 Introduction Disk I O is recognized as a major performance bottleneck in many database applications. To reduce the number of I O accesses, it is necessary to carefully select which disk pages to bu er in memory. Consequently, the topic of bu er management has received considerable attention [6, 7, 9, 13, 14, 15, 17]. Conventional bu er management schemes exploit interpage access skew to e ectively bu er only the most popular pages. However, with the increasing size of disk pages, more and more data today ts on a single disk page. As a result, even within a page, there may be substantial inter tuple access ....

....Work The goal of bu er management is to minimize disk I O by keeping in a software bu er in memory the pages that are likely to be accessed in the near future. In this bu er, the page management algorithms that work well for the operating system do not necessarily work best for database workloads [17]. In response, there has been much work on bu er management algorithms for databases. Broadly speaking, the algorithms can be classi ed into workload aware and statistical. Workload aware algorithms use workload information from the query optimizer. For example, Sacco [15] observed that if the ....

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412-418, July 1981.

No context found.

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, Jul 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Commun. ACM, 24(7):412-- 418, 1981.

No context found.

Stonebraker, M. Operating System Support for Database Management. In Communications of the ACM, 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, Jul 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Commun. ACM, 24(7):412-- 418, 1981.

No context found.

Stonebraker M (1981) Operating system support for database management. Commun ACM 24(7):412--418

No context found.

Stonebraker, M. Operating system support for database management. CACM. 24(7). pp. 412-418. 1981

No context found.

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412--418, July 1981.

No context found.

STONEBRAKER, M. Operating system support for database management. Communications of the ACM 24, 7 (July

No context found.

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7), July 1981.

No context found.

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412-418, Jul 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981. 211.

No context found.

Stonebraker M. Operating System Support for Database Management // Communications of the ACM. 1981. Vol. 24. No. 7. P. 412-418.

No context found.

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

No context found.

Michael Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, Jul 1981.

No context found.

M. Stonebraker. Operating system support for database management. Communications of the ACM, 24(7):412--418, July 1981.

No context found.

M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412--418, July 1981.

No context found.

Stonebraker, M. Operating System Support for Database Management. Communications of the ACM, Vol.24(7), July 1981.

No context found.

M. Stonebraker, "Operating System Support for Database Management," Communications of the ACM, Vol. 24, No. 7, July 1981, pp. 412-418.

No context found.

Stonebraker, M. Operating Systems Support for Database Management Systems. CACM 24, 7 (July 1981), 412-418. 16

First 50 documents  Next 50

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.