Block as a Value for SQL over NoSQL

Yang Cao, Wenfei Fan, Tengfei Yuan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper presents Zidian, a middleware for key-value (KV) stores to speed up SQL query evaluation over NoSQL. As opposed to common practice that takes a tuple id or primary key as key and the entire tuple as value, Zidian proposes a block-as-a-value model BaaV. BaaV represents a relation as keyed blocks (k, B), where k is a key of a block (a set) B of partial tuples. We extend relational algebra to BaaV. We show that under BaaV, Zidian substantially reduces data access and communication cost. We provide characterizations (sufficient and necessary conditions) for (a) result-preserving queries, i.e., queries covered by available BaaV stores, (b) scan-free queries, i.e., queries that can be evaluated without scanning any table, and (c) bounded queries, i.e., queries that can be answered by accessing a bounded amount of data. We show that in parallel processing, Zidian guarantees (a) no scans for scan-free queries, (b) bounded communication cost for bounded queries; and (c) parallel scalability, i.e., speedup when adding processors. Moreover, Zidian can be plugged into existing SQL-over-NoSQL systems and retains horizontal scalability. Using benchmark and real-life data, we empirically verify that Zidian improves existing SQL-overNoSQL systems by 2 orders of magnitude on average.
Original languageEnglish
Title of host publicationProceedings of the VLDB Endowment
Subtitle of host publicationProceedings of the 45th International Conference on Very Large Data Bases, Los Angeles, California
PublisherVery Large Data Base Endowment Inc.
Number of pages14
Publication statusPublished - 1 Jun 2019
Event45th International Conference on Very Large Data Bases - Los Angeles, United States
Duration: 26 Aug 201930 Aug 2019

Publication series

NameProceedings of the VLDB Endowment
PublisherVLDB Endowment
ISSN (Electronic)2150-8097


Conference45th International Conference on Very Large Data Bases
Abbreviated titleVLDB 2019
Country/TerritoryUnited States
CityLos Angeles
Internet address


Dive into the research topics of 'Block as a Value for SQL over NoSQL'. Together they form a unique fingerprint.

Cite this