O. Kennedy, und L. Ziarek. Proceedings of the 7th Biennial Conference on Innovative Data Systems Research, (Januar 2015)
Zusammenfassung
Adaptive indexing is a promising alternative to classical of-
fline index optimization. Under adaptive indexing, index
creation and re-organization take place automatically and
incrementally as a side-effect of query execution. Adaptive
indexing implementations optimize the index’s structure by
progressively rewriting it until it converges to a single idealized
form such as a sorted array or B-Tree. However, the
ideal representation changes over time: An adaptive index
that is initially optimal for one workload becomes suboptimal
as the workload’s characteristics change.
In this paper we generalize adaptive indexing, adding the
ability to adjust the layout and behavior of the index to
workload changes even after convergence. This radical justin-time
data structure approach to index construction and
maintenance allows for indexes that dynamically adapt to
changing workloads. Even with this generality, specialization
is still possible. A just-in-time data structure emulates
classical adaptive indexing schemes when appropriate, while
also being able to adopt a hybrid stance tailored to a specific
workload. We show that our approach is feasible and enables
indexes that quickly pivot between different behaviors.
%0 Conference Paper
%1 Kennedy:2015:JITD
%A Kennedy, Oliver
%A Ziarek, Lukasz
%B Proceedings of the 7th Biennial Conference on Innovative Data Systems Research
%D 2015
%K DataStructure Database Indexing JIT Optimization Performance
%T Just in Time Datastructures
%U http://odin.cse.buffalo.edu/wp-content/uploads/2014/11/main.pdf
%X Adaptive indexing is a promising alternative to classical of-
fline index optimization. Under adaptive indexing, index
creation and re-organization take place automatically and
incrementally as a side-effect of query execution. Adaptive
indexing implementations optimize the index’s structure by
progressively rewriting it until it converges to a single idealized
form such as a sorted array or B-Tree. However, the
ideal representation changes over time: An adaptive index
that is initially optimal for one workload becomes suboptimal
as the workload’s characteristics change.
In this paper we generalize adaptive indexing, adding the
ability to adjust the layout and behavior of the index to
workload changes even after convergence. This radical justin-time
data structure approach to index construction and
maintenance allows for indexes that dynamically adapt to
changing workloads. Even with this generality, specialization
is still possible. A just-in-time data structure emulates
classical adaptive indexing schemes when appropriate, while
also being able to adopt a hybrid stance tailored to a specific
workload. We show that our approach is feasible and enables
indexes that quickly pivot between different behaviors.
@inproceedings{Kennedy:2015:JITD,
abstract = {Adaptive indexing is a promising alternative to classical of-
fline index optimization. Under adaptive indexing, index
creation and re-organization take place automatically and
incrementally as a side-effect of query execution. Adaptive
indexing implementations optimize the index’s structure by
progressively rewriting it until it converges to a single idealized
form such as a sorted array or B-Tree. However, the
ideal representation changes over time: An adaptive index
that is initially optimal for one workload becomes suboptimal
as the workload’s characteristics change.
In this paper we generalize adaptive indexing, adding the
ability to adjust the layout and behavior of the index to
workload changes even after convergence. This radical justin-time
data structure approach to index construction and
maintenance allows for indexes that dynamically adapt to
changing workloads. Even with this generality, specialization
is still possible. A just-in-time data structure emulates
classical adaptive indexing schemes when appropriate, while
also being able to adopt a hybrid stance tailored to a specific
workload. We show that our approach is feasible and enables
indexes that quickly pivot between different behaviors.},
added-at = {2015-08-07T13:32:36.000+0200},
author = {Kennedy, Oliver and Ziarek, Lukasz},
biburl = {https://www.bibsonomy.org/bibtex/2d1be4d3c97fe04b0f2b6dd3ee89a7bcc/gron},
booktitle = {Proceedings of the 7th Biennial Conference on Innovative Data Systems Research},
interhash = {e6a36393436c493a1d78404a594c853e},
intrahash = {d1be4d3c97fe04b0f2b6dd3ee89a7bcc},
keywords = {DataStructure Database Indexing JIT Optimization Performance},
month = {January},
series = {CIDR'15},
timestamp = {2015-08-07T13:32:36.000+0200},
title = {Just in Time Datastructures},
url = {http://odin.cse.buffalo.edu/wp-content/uploads/2014/11/main.pdf},
year = 2015
}