Hippo: A Fast, yet Scalable, Database Indexing Approach
Even though existing database indexes (e.g., B+-Tree) speed up the query execution, they suffer from two main drawbacks: (1) A database index usually yields 5% to 15% additional storage overhead which results in non-ignorable dollar cost in big data scenarios especially when deployed on modern stora...
Main Authors: | , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2016
|
Subjects: | |
Online Access: | http://arxiv.org/abs/1604.03234 |
id |
ftarxivpreprints:oai:arXiv.org:1604.03234 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:1604.03234 2023-09-05T13:23:43+02:00 Hippo: A Fast, yet Scalable, Database Indexing Approach Yu, Jia Sarwat, Mohamed 2016-04-11 http://arxiv.org/abs/1604.03234 unknown http://arxiv.org/abs/1604.03234 Computer Science - Databases H.2.2 text 2016 ftarxivpreprints 2023-08-16T13:58:06Z Even though existing database indexes (e.g., B+-Tree) speed up the query execution, they suffer from two main drawbacks: (1) A database index usually yields 5% to 15% additional storage overhead which results in non-ignorable dollar cost in big data scenarios especially when deployed on modern storage devices like Solid State Disk (SSD) or Non-Volatile Memory (NVM). (2) Maintaining a database index incurs high latency because the DBMS has to find and update those index pages affected by the underlying table changes. This paper proposes Hippo a fast, yet scalable, database indexing approach. Hippo only stores the pointers of disk pages along with light weight histogram-based summaries. The proposed structure significantly shrinks index storage and maintenance overhead without compromising much on query execution performance. Experiments, based on real Hippo implementation inside PostgreSQL 9.5, using the TPC-H benchmark show that Hippo achieves up to two orders of magnitude less storage space and up to three orders of magnitude less maintenance overhead than traditional database indexes, i.e., B+-Tree. Furthermore, the experiments also show that Hippo achieves comparable query execution performance to that of the B+-Tree for various selectivity factors. Comment: 12 pages, 10 figures, conference Text The Pointers ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Databases H.2.2 |
spellingShingle |
Computer Science - Databases H.2.2 Yu, Jia Sarwat, Mohamed Hippo: A Fast, yet Scalable, Database Indexing Approach |
topic_facet |
Computer Science - Databases H.2.2 |
description |
Even though existing database indexes (e.g., B+-Tree) speed up the query execution, they suffer from two main drawbacks: (1) A database index usually yields 5% to 15% additional storage overhead which results in non-ignorable dollar cost in big data scenarios especially when deployed on modern storage devices like Solid State Disk (SSD) or Non-Volatile Memory (NVM). (2) Maintaining a database index incurs high latency because the DBMS has to find and update those index pages affected by the underlying table changes. This paper proposes Hippo a fast, yet scalable, database indexing approach. Hippo only stores the pointers of disk pages along with light weight histogram-based summaries. The proposed structure significantly shrinks index storage and maintenance overhead without compromising much on query execution performance. Experiments, based on real Hippo implementation inside PostgreSQL 9.5, using the TPC-H benchmark show that Hippo achieves up to two orders of magnitude less storage space and up to three orders of magnitude less maintenance overhead than traditional database indexes, i.e., B+-Tree. Furthermore, the experiments also show that Hippo achieves comparable query execution performance to that of the B+-Tree for various selectivity factors. Comment: 12 pages, 10 figures, conference |
format |
Text |
author |
Yu, Jia Sarwat, Mohamed |
author_facet |
Yu, Jia Sarwat, Mohamed |
author_sort |
Yu, Jia |
title |
Hippo: A Fast, yet Scalable, Database Indexing Approach |
title_short |
Hippo: A Fast, yet Scalable, Database Indexing Approach |
title_full |
Hippo: A Fast, yet Scalable, Database Indexing Approach |
title_fullStr |
Hippo: A Fast, yet Scalable, Database Indexing Approach |
title_full_unstemmed |
Hippo: A Fast, yet Scalable, Database Indexing Approach |
title_sort |
hippo: a fast, yet scalable, database indexing approach |
publishDate |
2016 |
url |
http://arxiv.org/abs/1604.03234 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
http://arxiv.org/abs/1604.03234 |
_version_ |
1776204308261371904 |