检索结果-内蒙古大学图书馆

28th ACM Symposium on Operating Systems Principles (SOSP)

作者： Qin, Dai Brown, Angela Demke Goel, Ashvin Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450387095

Deterministic databases offer several benefits: they ensure serializable execution while avoiding concurrency-control related aborts, and they scale well in distributed environments. Today, most deterministic database designs use partitioning to scale up and avoid contention. However, partitioning requires significant programmer effort, leads to poor performance under skewed workloads, and incurs unnecessary overheads in certain uncontended workloads. We present the design of Caracal, a novel shared-memory, deterministic database that performs well under both skew and contention. Our deterministic scheme batches transactions in epochs and executes the transactions in an epoch in a predetermined order. Our scheme enables reducing contention by batching concurrency control operations. It also allows analyzing the transactions in the epoch to determine contended keys accurately. Certain transactions can then be split into independent contended and uncontended pieces and run deterministically and in parallel, further reducing contention. Based on these ideas, we present two novel optimizations, batch append and split-on-demand, for managing contention. With these optimizations, Caracal scaleswell and outperforms existing deterministic schemes in most workloads by 1.9x to 9.7x.

关键词： deterministic concurrency control contention main-memory databases

来源：评论

学校读者我要写书评

暂无评论

Combining Two Worlds: MonetDB with Multi-Dimensional Index Structure Support to Efficiently Query Scientific Data 2020

Combining Two Worlds: MonetDB with Multi-Dimensional Index S...

引用

32nd International Conference on Scientific and Statistical Database Management (SSDBM)

作者： Blockhaus, Paul Broneske, David Schaeler, Martin Koeppen, Veit Saake, Gunter Univ Magdeburg Magdeburg Germany Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9781450388146

Reproducibility and generalizability are important criteria for today's data management society. Hence, stand-alone solutions that work well in isolation, but cannot convince at system level lead to a frustrating user experience. As a consequence, in our demo, we take the step of accelerating queries on scientific data by integrating the multi-dimensional index structure Elf into the main-memory-optimized database management system MonetDB. The overall intention is to show that the stand-alone speed ups of using Elf can also be observed when integrated into a holistic system storing scientific data sets. In our prototypical implementation, we demonstrate the performance of an Elf-backed MonetDB on the standard OLAP-benchmark, TPC-H, and the genomic multi-dimensional range query benchmark from the scientific data community. Queries can be run live on both benchmarks by the audience, while they are able to create different indexes to accelerate selection performance.

关键词： multi-dimensional index structures main-memory databases integration concepts GMRQB TPC-H

来源：评论

学校读者我要写书评

暂无评论

Efficient Evaluation of Multi-Column Selection Predicates in main-memory

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2019年第7期31卷 1296-1311页

作者： Broneske, David Koeppen, Veit Saake, Gunter Schaeler, Martin Univ Magdeburg Comp Sci Fac D-39106 Magdeburg Sachsen Anhalt Germany Karlsruher Inst Technol Comp Sci Dept D-76131 Karlsruhe Germany

Efficient evaluation of selection predicates is a performance-critical task, for instance to reduce intermediate result sizes being the input for further operations. With analytical queries getting more and more complex, the number of evaluated selection predicates per query and table rises, too. This leads to numerous multi-column selection predicates. Recent approaches to increase the performance of main-memory databases for selection-predicate evaluation aim at optimally exploiting the speed of the CPU by using accelerated scans. However, scanning each column one by one leaves tuning opportunities open that arise if all predicates are considered together. To this end, we introduce Elf, an index structure that is able to exploit the relation between several selection predicates. Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In a large-scale evaluation, we compare its query performance to state-of-the-art approaches and a sequential scan using SIMD capabilities. Our results indicate a clear superiority of our approach for queries returning less than 10 percent of all tuples - a selectivity almost one order of magnitude larger than observed for related indexing approaches. For TPC-H queries with multi-column selection predicates, we achieve a speedup between factor five and two orders of magnitude, mainly depending on the selectivity of the predicates. Further scaling experiments reveal that for large data sets, these speedup factors are expected to increase, due to more densely populated data spaces. Finally, our results indicate that using a delta-store like concept to support periodic insertions results in virtually no performance penalty for reasonable sizes of a write-optimized Elf as delta store.

关键词： Multi-column selection predicate main-memory databases hardware-sensitive indexing

来源：评论

学校读者我要写书评

暂无评论

Accelerating Analytical Processing in MVCC using Fine-Granular High-Frequency Virtual Snapshotting 18

Accelerating Analytical Processing in MVCC using Fine-Granul...

引用

44th ACM SIGMOD International Conference on Management of Data

作者： Sharma, Ankur Schuhknecht, Felix Martin Dittrich, Jens Saarland Univ Big Data Analyt Grp Homburg Germany

ISBN: (纸本)9781450317436

Efficient transaction management is a delicate task. As systems face transactions of inherently different types, ranging from point updates to long-running analytical queries, it is hard to satisfy their requirements with a single execution engine. Unfortunately, most systems rely on such a design that implements its parallelism using multi-version concurrency control. While MVCC parallelizes short-running OLTP transactions well, it struggles in the presence of mixed workloads containing long-running OLAP queries, as scans have to work their way through vast amounts of versioned data. To overcome this problem, we reintroduce the concept of hybrid processing and combine it with state-of-the-art MVCC: OLAP queries are outsourced to run on separate virtual snapshots while OLTP transactions run on the most recent version of the database. Inside both execution engines, we still apply MVCC. The most significant challenge of a hybrid approach is to generate the snapshots at a high frequency. Previous approaches heavily suffered from the high cost of snapshot creation. In our approach termed AnKer, we follow the current trend of co-designing underlying system components and the DBMS, to overcome the restrictions of the OS by introducing a custom system call vm_snapshot. It allows fine-granular snapshot creation that is orders of magnitudes faster than state-of-the-art approaches. Our experimental evaluation on an HTAP workload based on TPC-C transactions and OLAP queries show that our snapshotting mechanism is more than a factor of 100x faster than fork-based snapshotting and that the latency of OLAP queries is up to a factor of 4x lower than MVCC in a single execution engine. Besides, our approach enables a higher OLTP throughput than all state-of-the-art methods.

关键词： htap main-memory databases transaction processing mvcc virtual snapshotting

来源：评论

学校读者我要写书评

暂无评论

GRFusion: Graphs as First-Class Citizens in main-memory Relational Database Systems 18

GRFusion: Graphs as First-Class Citizens in Main-Memory Rela...

引用

44th ACM SIGMOD International Conference on Management of Data

作者： Hassan, Mohamed S. Kuznetsova, Tatiana Jeong, Hyun Chai Aref, Walid G. Sadoghi, Mohammad Purdue Univ W Lafayette IN 47907 USA Univ Calif Davis Davis CA 95616 USA

ISBN: (纸本)9781450317436

The maturity of RDBMSs has motivated academia and industry to invest efforts in leveraging RDBMSs for graph processing, where efficiency is proven for vital graph queries. However, none of these efforts process graphs natively inside the RDBMS, which is particularly challenging due to the impedance mismatch between the relational and the graph models. In this demonstration, we present GRFusion, an in-memory relational database system, where graphs are managed as first-class citizens. GRFusion is realized inside VoltDB. The SQL and query engines of VoltDB are empowered to declaratively define graphs and execute cross-data-model query plans that consist of relational operators and newly-introduced graph operators. Using a social network and a real continental-sized road network covering the entire U.S., we demonstrate the functionality and the performance of GRFusion in evaluating queries that reference both relational tables and graphs seamlessly in the same query execution pipeline. GRFusion shows up to four orders-of-magnitude speedup in query-time w.r.t. state-of-the-art approaches.(1)

关键词： graph queries path traversals main-memory databases cross-data-model query plans

来源：评论

学校读者我要写书评

暂无评论

Runtime Fragility in main memory 1

引用

7th International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS) / International Workshop on In-memory Data Management (IMDM)

作者： Palatinus, Endre Dittrich, Jens Saarland Univ Informat Syst Grp Saarbrucken Germany

ISBN: (数字)9783319561110

ISBN: (纸本)9783319561110;9783319561103

In this paper we investigate the following problem: Given a database workload (tables and queries), which data layout (row, column or a suitable PAX-layout) should we choose in order to get the best possible performance? We show that this is not an easy problem. We explore careful combinations of various parameters that have an impact on the performance including: (1) the schema, (2) the CPU architecture, (3) the compiler, and (4) the optimization level. We include a CPU from each of the past 4 generations of Intel CPUs. In addition, we demonstrate the importance of taking variance into account when deciding on the optimal storage layout. We observe considerable variance throughout our measurements which makes it difficult to argue along means over different runs of an experiment. Therefore, we compute confidence intervals for all measurements and exploit this to detect outliers and define classes of methods that we are not allowed to distinguish statistically. The variance of different performance measurements can be so significant that the optimal solution may not be the best one in practice. Our results also indicate that a carefully or ill-chosen compilation setup can trigger a performance gain or loss of factor 1.1 to factor 25 in even the simplest workloads: a table with four attributes and a simple query reading those attributes. This latter observation is not caused by variance in the measured runtimes, but due to using a different compiler setup. Besides the compilation setup, the data layout is another source of query time fragility. Various size metrics of the memory subsystem are round numbers in binary, or put more simply: powers of 2 in decimal. System engineers have followed this tradition over time. Surprisingly, there exists a use-case in query processing where using powers of 2 is always a suboptimal choice, leading to one more cause of fragile query times. Using this finding, we will show how to improve tuple-reconstruction costs by using a novel

关键词： main-memory databases Data layouts Robust query processing Tuple reconstruction

来源：评论

学校读者我要写书评

暂无评论

Cache-Sensitive Skip List: Efficient Range Queries on Modern CPUs 1

引用

7th International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS) / International Workshop on In-memory Data Management (IMDM)

作者： Sprenger, Stefan Zeuch, Steffen Leser, Ulf Humboldt Univ Inst Comp Sci Unter Linden 6 D-10099 Berlin Germany

ISBN: (数字)9783319561110

ISBN: (纸本)9783319561110;9783319561103

Due to ever falling prices and advancements in chip technologies, many of today's databases can be entirely kept in main memory. However, reusing existing disk-based index structures for managing data in memory leads to suboptimal performance due to inefficient cache usage and negligence of the capabilities of modern CPUs. Accordingly, a number of main-memory optimized index structures have been proposed, yet most of them focus entirely on single-key lookups, neglecting the equally important range queries. We present Cache-Sensitive Skip Lists (CSSL) as a novel index structure that is optimized for range queries and exploits modern CPUs. CSSL is based on a cache-friendly data layout and traversal algorithm that minimizes cache misses, branch mispredictions, and allows to exploit SIMD instructions for search. In our experiments, CSSL's range query performance surpasses all competitors significantly. Even for lookups, it is only surpassed by the recently presented ART index structure. We therefore see CSSL as a serious alternative for mixed key/range workloads on main-memory databases.

关键词： Index structures main-memory databases Scientific databases

来源：评论

学校读者我要写书评

暂无评论

ERMIA: Fast memory-Optimized Database System for Heterogeneous Workloads 16

ERMIA: Fast Memory-Optimized Database System for Heterogeneo...

引用

ACM SIGMOD International Conference on Management of Data

作者： Kim, Kangnyeon Wang, Tianzheng Johnson, Ryan Pandis, Ippokratis Univ Toronto Toronto ON Canada LogicBlox Atlanta GA USA Amazon Web Serv Seattle WA USA

ISBN: (纸本)9781450335317

Large main memories and massively parallel processors have triggered not only a resurgence of high-performance transaction processing systems optimized for large main-memory and massively parallel processors, but also an increasing demand for processing heterogeneous workloads that include read-mostly transactions. Many modern transaction processing systems adopt a lightweight optimistic concurrency control (OCC) scheme to leverage its low overhead in low contention workloads. However, we observe that the lightweight OCC is not suitable for heterogeneous workloads, causing significant starvation of read-mostly transactions and overall performance degradation. In this paper, we present ERMIA, a memory-optimized database system built from scratch to cater the need of handling heterogeneous workloads. ERMIA adopts snapshot isolation concurrency control to coordinate heterogeneous transactions and provides serializability when desired. Its physical layer supports the concurrency control schemes in a scalable way. Experimental results show that ERMIA delivers comparable or superior performance and near linear scalability in a variety of workloads, compared to a recent lightweight OCC-based system. At the same time, ERMIA maintains high throughput on read-mostly transactions when the performance of the OCC-based system drops by orders of magnitude.

关键词： serial safety net epoch-based resource management indirection arrays main-memory databases multiversion concurrency control log manager heterogeneous workloads multicore scalability append-only storage

来源：评论

学校读者我要写书评

暂无评论

Accelerating XPath evaluation in any RDBMS

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2004年第1期29卷 91-131页

作者： Grust, T Van Keulen, M Teubner, J Univ Konstanz Dept Comp & Informat Sci D-78457 Constance Germany Univ Twente Fac Comp Sci NL-7500 AE Enschede Netherlands

This article is a proposal for a database index structure, the XPath accelerator, that has been specifically designed to support the evaluation of XPath path expressions. As such, the index is capable to support all XPath axes ( including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on the child and descendant axes only. The index has been designed with a close eye on the XPath semantics as well as the desire to engineer its internals so that it can be supported well by existing relational database query processing technology: the index (a) permits set-oriented ( or, rather, sequence-oriented) path evaluation, and (b) can be implemented and queried using well-established relational index structures, notably B-trees and R-trees. We discuss the implementation of the XPath accelerator on top of different database backends and show that the index performs well on all levels of the memory hierarchy, including disk-based and main-memory based database systems.

关键词： performance theory main-memory databases XML XML indexing XPath

来源：评论

学校读者我要写书评

暂无评论

Accelerating XPath evaluation in any RDBMS

Accelerating XPath evaluation in any RDBMS

引用

21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)

作者： Grust, T Van Keulen, M Teubner, J Univ Konstanz Dept Comp & Informat Sci D-78457 Constance Germany Univ Twente Fac Comp Sci NL-7500 AE Enschede Netherlands

关键词： performance theory main-memory databases XML XML indexing XPath

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：