Abstract | ||
---|---|---|
this paper, we study relationship queries on graph databases with binary relationship. A relationship query is a graph reachability query bounded on primary-keys and foreign-keys with aggregation on single output attribute. Both row stores and column stores miss key opportunities towards the efficient execution of relationship queries, making them unacceptably slow in real-world OLAP scenarios. present the FastR in-memory analytics engine that utilizes a new form of bottom-up fully pipelined query processing execution strategy. The plans run on a novel data organization that combines salient features of column-based organization, indexing and compression. Furthermore, FastR compiles its query plans into query-aware executable C++ source codes. Besides achieving runtime efficiency, FastR also reduces main memory requirements because, unlike column databases, FastR selectively allows more dense forms of compression including heavy-weighted compressions, which do not support random access. In our experiments, we used FastR to accelerate queries for two OLAP dashboards in the biomedical field. The first dashboard runs queries on the PubMed dataset and the second one on the SemMedDB dataset. FastR outperforms Postgres by 2-4 orders of magnitude and MonetDB by 1-3 orders of magnitude, when all of them are running on RAM. Our experiments dissect the FastR advantage between (i) the novel FastR execution strategy and associated data structures and (ii) the use of compiled code. We also provide an analysis and experiments illustrating space savings due to appropriate use of compression methods. Finally, we investigate the beneficial effect of the increasing CPU cycles / RAM transfer rate ratio on the space-time tradeoff for various compression methods used in FastR. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Databases | SQL,Data mining,Data structure,Graph database,Source code,Computer science,Search engine indexing,Online analytical processing,Database,Random access,Executable |
DocType | Volume | Citations |
Journal | abs/1602.00033 | 1 |
PageRank | References | Authors |
0.35 | 27 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chunbin Lin | 1 | 95 | 12.22 |
Benjamin Mandel | 2 | 8 | 1.15 |
Yannis Papakonstantinou | 3 | 5657 | 837.56 |
Matthias Springer | 4 | 2 | 2.11 |