VLDB 2015 - Githubissues

Proceedings of the Third International Workshop on In-Memory Data Management and Analytics (IMDM 2015) http://portalparts.acm.org/2810000/2803140/fm/frontmatter.pdf?ip=58.251.152.225&CFID=603267437&CFTOKEN=21449131

Partitioned Bit-Packed Vectors for In-Memory-Column-Stores demo In this paper we propose a new data structure, the partitioned bit-packed vector. Therein the encoding length of the stored elements may increase dynamically, while still providing comparable single-value access performance. This paper outlines the access to this data structure and evaluates its performance characteristics.

其他的demo我都没有看呢还

In-Memory Performance for Big Data HP和GOOGLE的人一起写的，inspire一下你如果去monetdb的话可以考虑这个扩展到monetdb不实验用的TPCC，paper里还讨论了b-tree Contrary to those prior efforts, we enable buffer pool designs to match in-memory performance while supporting the “big data” workloads that continue to require secondary storage, thus providing the best of both worlds. We introduce here a novel buffer pool design that adapts pointer swizzling for references between system objects (as opposed to application objects), and uses it to practically eliminate buffer pool overheads for memoryresident data
In-Cache Query Co-Processing on Coupled CPU-GPU Architectures TPCH analytical queries, 文章好像用的是column store Recently, there have been some emerging processor designs that the CPU and the GPU (Graphics Processing Unit) are integrated in a single chip and share Last Level Cache (LLC). However, the main memory bandwidth of such coupled CPU-GPU architectures can be much lower than that of a discrete GPU. As a result, current GPU query coprocessing paradigms can severely suffer from memory stalls. In this paper, we propose a novel in-cache query co-processing paradigm for main memory On-Line Analytical Processing (OLAP) databases on coupled CPU-GPU architectures. Specifically, we adapt CPU-assisted prefetching to minimize cache misses in GPU query co-processing and CPU-assisted decompression to improve query execution performance. Furthermore, we develop a cost model guided adaptation mechanism for distributing the workload of prefetching, decompression, and query execution between CPU and GPU.
Memory-Efficient Hash Joins IBM 的人做的，感觉是设计了一个新的hash存储形式 We present new hash tables for joins, and a hash join based on them, that consumes far less memory and is usually faster than recently published in-memory joins. Our hash join is not restricted to outer tables that fit wholly in memory. Key to this hash join is a new concise hash table (CHT), a linear probing hash table that has 100% fill factor, and uses a sparse bitmap with embedded population counts to almost entirely avoid collisions. This bitmap also serves as a Bloom filter for use in multi-table joins.
Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement EPFL跟SAP合作的paper Main-memory column-stores are called to efficiently use modern non-uniform memory access (NUMA) architectures to service concurrent clients on big data. The efficient usage of NUMA architectures depends on the data placement and scheduling strategy of the column-store. Most column-stores choose a static strategy that involves partitioning all data across the NUMA architecture, and employing a stealingbased task scheduler. In this paper, we implement different strategies for data placement and task scheduling for the case of concurrent scans. We compare these strategies with an extensive sensitivity analysis.
Improving Main Memory Hash Joins on Intel Xeon Phi Processors: An Experimental Approach NTU的paper In this paper, we experimentally revisit the state-of-the-art hash join algorithms on Xeon Phi co-processors. In particular, we study two camps of hash join algorithms: hardware-conscious ones that advocate careful tailoring of the join algorithms to underlying hardware architectures and hardware-oblivious ones that omit such careful tailoring.
Distributed Architecture of Oracle Database In-memory ORACLE的人写的paper，既有说到single node的也有说到cluster的，是column store The Oracle RDBMS In-memory Option (DBIM) is an industryfirst distributed dual format architecture that allows a database object to be stored in columnar format in main memory highly optimized to break performance barriers in analytic query workloads, simultaneously maintaining transactional consistency with the corresponding OLTP optimized row-major format persisted in storage and accessed through database buffer cache. In this paper, we present the distributed, highly-available, and fault-tolerant architecture of the Oracle DBIM that enables the RDBMS to transparently scale out in a database cluster, both in terms of memory capacity and query processing throughput.
Query Optimization in Oracle 12c Database In-Memory Oracle的人写的，感觉跟上面那篇有相关性，一个偏存储一个偏优化我觉得 Oracle 12c Database In-memory, the industry’s first dual-format database, allows existing row major on-disk tables to have complementary in-memory columnar representations. The new storage format brings new data processing techniques and query execution algorithms and thus new challenges for the query optimizer. Execution plans that are optimal for one format may be sub-optimal for the other. In this paper, we describe the changes made in the query optimizer to generate execution plans optimized for the specific format – row major or columnar – that will be scanned during query execution.
SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 感觉只是考虑sort，数据集也不是TPC的，不知道是不是column store的 our new algorithm for sorting an array of structures by efficiently exploiting the SIMD instructions and cache memory of today’s processors. However, this approach has frequent cache misses in the final rearranging phase due to its random and scattered memory accesses so that this phase limits both single-thread performance and scalability with multiple cores. Our approach is also based on multiway mergesort, but it can avoid costly random accesses for rearranging the records while still efficiently exploiting the SIMD instructions.
Optimal Probabilistic Cache Stampede Prevention 不是column store，是做cache的 When a frequently-accessed cache item expires, multiple requests to that item can trigger a cache miss and start regenerating that same item at the same time. This phenomenon, known as cache stampede, severely limits the performance of databases and web servers. A natural countermeasure to this issue is to let the processes that perform such requests to randomly ask for a regeneration before the expiration time of the item. In this paper we give optimal algorithms for performing such probabilistic early expirations.
To Lock, Swap, or Elide: On the Interplay of Hardware Transactional Memory and Lock-Free Indexing This paper studies the interplay of HTM and lockfree indexing methods. First, we evaluate whether HTM will obviate the need for crafty lock-free index designs by integrating it in a traditional B-tree architecture. Second, we explore fundamental differences between HTM-based and lock-free B-tree designs.
Spatial Joins in Main Memory: Implementation Matters! christian jensen的文章 A recent PVLDB paper reports on experimental analyses of ten spatial join techniques in main memory. We build on this comprehensive study to raise awareness of the fact that empirical running time performance findings in main-memory settings are results of not only the algorithms and data structures employed, but also their implementation, which complicates the interpretation of the results
Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions. 不是column store不是OLAP，是set intersection Set intersection is one of the most important operations for many applications such as Web search engines or database management systems. This paper describes our new algorithm to efficiently find set intersections with sorted arrays on modern processors with SIMD instructions and high branch misprediction penalties. Our algorithm efficiently exploits SIMD instructions and can drastically reduce branch mispredictions.
Persistent B+-Trees in Non-Volatile Main Memory This paper studies persistent in-memory B+-Trees as B+-Trees are widely used in database and data-intensive systems. While traditional techniques, such as undo-redo logging and shadowing, support persistent B+-Trees, we find that they incur drastic performance overhead because of extensive NVM writes and CPU cache flush operations. PCM-friendly B+-Trees with unsorted leaf nodes help mediate this issue, but the remaining overhead is still large. In this paper, we propose write atomic B+-Trees (wB+-Trees), a new type of main-memory B+-Trees, that aim to reduce such overhead as much as possible
REWIND: Recovery Write-Ahead System for In-Memory Non-Volatile Data-Structures Existing mechanisms for transactional updates are not appropriate in such a setting as they are optimized for block-based storage. We present REWIND, a usermode library approach to managing transactional updates directly from user code written in an imperative generalpurpose language. REWIND relies on a custom persistent in-memory data structure for the log that supports recoverable operations on itself. The scheme also employs a combination of non-temporal updates, persistent memory fences, and lightweight logging.
Gorilla: A Fast, Scalable, In-Memory Time Series Database Large-scale internet services aim to remain highly available and responsive in the presence of unexpected failures. Providing this service often requires monitoring and analyzing tens of millions of measurements per second across a large number of systems, and one particularly effective solution is to store and query such measurements in a time series database (TSDB). A key challenge in the design of TSDBs is how to strike the right balance between efficiency, scalability, and reliability. In this paper we introduce Gorilla, Facebook's in-memory TSDB. Our insight is that users of monitoring systems do not place much emphasis on individual data points but rather on aggregate analysis, and recent data points are of much higher value than older points to quickly detect and diagnose the root cause of an ongoing problem.
GIS Navigation Boosted by Column Stores 这个是一个DEMO In this demo we show how to query a 640 billion point data set using a column store enriched with GIS functionality. Through a lightweight and cache conscious secondary index called Imprints, spatial queries performance on a flat table storage is comparable to traditional file-based solutions. All the results are visualised in real time using QGIS.
Towards Scalable Real-time Analytics: An Architecture for Scale-out of OLxP Workloads SAP的人写的，基于HANA的改进的数据库管理系统 We present an overview of our work on the SAP HANA Scale-out Extension, a novel distributed database architecture designed to support large scale analytics over realtime data. This platform permits high performance OLAP with massive scale-out capabilities, while concurrently allowing OLTP workloads.

/////////////

Lightning Fast and Space Efficient Inequality Joins 我觉得inequality join之前没有见过column store做过这篇是row stored，不过他将sort column抽出来的，也讨论到了Bitmap，不知道做到什么程度 While therehave been a wide range of optimization methods for joins indatabase systems, from algorithms such as sort-merge joinand band join, to various indices such as B+-tree, R-tree and Bitmap, inequality joins have received little attentionand queries containing such joins are usually very slow. Inthis paper, we introduce fast inequality join algorithms. We put columns to be joined in sorted arrays and we use per-mutation arrays to encode positions of tuples in one sortedarray w.r.t. the other sorted array. In contrast to sort-mergejoin, we use space eﬃcient bit-arrays that enable optimiza-tions, such as Bloom ﬁlter indices, for fast computation ofthe join results.
SEMA-JOIN: Joining Semantically-Related Tables Using Big Table Corpora not equal join, 微软的人做的，我觉得思路蛮新的 Given the growing demand for adhoc data analysis, we have seen an increasing number of scenarios where the desired join relationship is not equi-join For example, in a spreadsheet environment, a user may want to join one table with a subject column country-name, with another table with a subject column country-code. Traditional equi-join cannot handle such joins automatically, and the user typically has to manually find an intermediate mapping table in order to perform the desired join. We develop a SEMA-JOIN approach that is a first step toward allowing users to perform semantic join automatically, with a click of the button. Our main idea is to utilize a data-driven method that leverages a big table corpus with over 100 million tables to determine statistical correlation between cell values at both row-level and column-level
Rank aggregation with ties: Experiments and Analysis 这个aggregate multiple rankings，而且考虑了ranking ties, 感觉蛮新奇的大致扫了一下，不是column store，感觉都不是main memory的文章 The problem of aggregating multiple rankings into one consensus ranking is an active research topic especially in the database community. Additionally, in real applications, the rankings to be aggregated may not be permutations where elements are strictly ordered, but they may have ties where some elements are placed at the same position. However, most of the studies have not considered ties.
Efficient Processing of Window Functions in Analytical SQL Queries. 你之前是不是看过这篇文章，window function Window functions, also known as analytic OLAP functions, have been part of the SQL standard for more than a decade and are now a widely-used feature Despite being supported by all major database systems, there have been few publications that describe how to implement an efficient relational window operator. This work aims at filling this gap by presenting an efficient and general algorithm for the window operator
Trill: A High-Performance Incremental Query Processor for Diverse Analytics 微软的人写的，好像是row-based的，主要是看到了INCREMENTAL，感觉incremental是不是一个点可以考虑做 This paper introduces Trill – a new query processor for analytics. Trill fulfills a combination of three requirements for a query processor to serve the diverse big data analytics space: (1) Query Model: Trill is based on a tempo-relational model that enables it to handle streaming and relational queries with early results, across the latency spectrum from real-time to offline; (2) Fabric and Language Integration: Trill is architected as a high-level language library that supports rich data-types and user libraries, and integrates well with existing distribution fabrics and applications; and (3) Performance: Trill’s throughput is high across the latency spectrum. For streaming data, Trill’s throughput is 2-4 orders of magnitude higher than comparable streaming engines. For offline relational queries, Trill’s throughput is comparable to a major modern commercial columnar DBMS.
Possible and Certain SQL Key 感觉以前没见过讨论relational DB key的设置的，可以降低对key must be NOT NULL的限制不是column store，不是main memory的，只是觉得以前没见过 Driven by the dominance of the relational model, the requirements of modern applications, and the veracity of data,we revisit the fundamental notion of a key in relational databases with NULLs. In SQL database systems primary key columns are NOT NULL by default We investigate the notions of possible and certain keys, which are keys that hold in some or all possible worlds that can originate from an SQL table, respectively. Possible keys coincide with the unique constraint of SQL, and thus provide a semantics for their syntactic definition in the SQL standard. Certain keys extend primary keys to include NULL columns, and thus form a sufficient and necessary condition to identify tuples uniquely, while primary keys are only sufficient for that purpose.
Multi-Objective Parametric Query Optimization EPFL的paper，如果column store考虑多objective会不会有新的东西做？？ 2015的sigmod有一篇cite的它，也做得multiple objective的优化，是做incremental的优化 Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the MultiObjective Parametric Query Optimization (MPQ) problem where query plans are compared according to multiple cost metrics and the cost of a given plan according to a given metric is modeled as a function that depends on multiple parameters. The cost metrics may for instance include execution time or monetary fees; a parameter may represent the selectivity of a query predicate that is unspecified at optimization time
Deployment of Query Plans on Multicores 用的TPCW查询，考虑了多线程，多核，多查询sharing In this paper we explore the efficient deployment of query plans over a multicore machine. We focus on shared query systems, and implement the proposed ideas using SharedDB. The goal of the paper is to explore how to deliver maximum performance and predictability, while minimizing resource utilization when deploying query plans on multicore machines.
Interpretable and Informative Explanations of Outcomes GOOGLE, TWITTER, uni of washington的人写的，我是觉得解决的问题挺新奇，数据集有一个属性是boolean属性 In this paper, we solve the following data summarization problem:given a multi-dimensional data set augmented with a binary attribute, how can we construct an interpretable and informative summary of the factors affecting the binary attribute in terms of the combinations of values of the dimension attributes? We refer to such summaries as explanation tables. We show the hardness of constructing optimally-informative explanation tables from data, and we propose effective and efficient heuristics. The proposed heuristics are based on sampling and include optimizations related to computing the information content of a summary from a sample of the data
Real-Time Analytical Processing with SQL Server. Microsoft人做的，我觉得很新，讲MY SQL 2016的新特色，column store里面可以有个secondary index on disk Over the last two releases SQL Server has integrated two specialized engines into the core system: the Apollo column store engine for analytical workloads and the Hekaton in-memory engine for high-performance OLTP workloads. There is an increasing demand for real-time analytics, that is, for running analytical queries and reporting on the same system as transaction processing so as to have access to the freshest data. SQL Server 2016 will include enhancements to column store indexes and in-memory tables that significantly improve performance on such hybrid workloads. This paper describes four such enhancements: column store indexes on inmemory tables, making secondary column store indexes on diskbased tables updatable, allowing B-tree indexes on primary column store indexes, and further speeding up the column store scan operator.
Join Size Estimation Subject to Filter Conditions Oracle的人写的，估计join size的， equal join，适合于streamning 的数据 In this paper, we present a new algorithm for estimating the size of equality join of multiple database tables. The proposed algorithm, Correlated Sampling, constructs a small space synopsis for each table, which can then be used to provide a quick estimate of the join size of this table with other tables subject to dynamically specified predicate filter conditions, possibly specified over multiple columns (attributes) of each table. This algorithm makes a single pass over the data and is thus suitable for streaming scenarios.
SQLite Optimization with Phase Change Memory for Mobile Applications 是基于手机内存PCM，为mobile app的应用做优化的我觉得蛮新颖的，以前我好想没见过 This often has adverse effect on the flash memory storage in mobile devices because the small random updates cause high write amplification and high write latency. In order to address this problem, we propose a new optimization strategy, called per-page logging (PPL), for mobile data management, and have implemented the key functions in SQLite/PPL. The hardware component of SQLite/PPL includes phase change memory (PCM) with a byte-addressable, persistent memory abstraction.
Databases and Hardware: The Beginning and Sequel of a Beautiful Friendship 只有4页，感觉是demo EPFL的paper We discuss work done in the past four decades to tighten the interaction between the database software and underlying hardware and show that, as application and microarchitecture roadmaps evolve, the effort of maintaining smooth collaboration blossoms into a multitude of interesting research avenues with direct technological impact.
AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 一年中了两回
PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort 感觉不是很相关 effi-cient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its in-place nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) “speculative permutation” solves the first problem by assigning multiple non-continuous array stripes to each processor.
On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning. 是一个demo Partitioning a dataset into ranges is a task that is common in various applications such as sorting [1,6,7,8,9] and hashing [3] which are in turn building blocks for almost any type of query processing. Especially radix-based partitioning is very popular due to its simplicity and high performance over comparison-based versions [6].
Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service 微软的人做的. single cloud database servers上面支撑了多个tenants 这个跟你的新tipic可能无关，我只是觉得跟EDBT的extension有关联
Querying with Access Patterns and Integrity Constraints 这个可以作为EDBT扩展的时候要引用的参考文献、、、幸好当年没有看到他，不然EDBT又多了一重危险
Shared Execution of Recurring Workloads in MapReduce 可以用来指导EDBT In this work, we propose the first scalable multi-query sharing engine tailored for recurring workloads in the MapReduce infrastructure, called “Helix”. Helix deploys new sliced window-alignment techniques to create sharing opportunities among recurring queries without introducing additional I/O overheads or unnecessary data scans. And then, Helix introduces a cost/benefit model for creating a sharing plan among the recurring queries, and a scheduling strategy for executing them to maximize the SLA satisfaction.
Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms 跟EDBT的X->Y很相似，哈哈我当时literature review肯定做的很不完全

cswxu / loop_part

VLDB 2015 #5