47 lines
2.7 KiB
Plaintext
47 lines
2.7 KiB
Plaintext
Adaptive indexing is a promising alternative to classical offline index
|
|
optimization. Under adaptive indexing, index creation and re-organization take
|
|
place automatically and incrementally as a side-effect of query execution. Over
|
|
time, the index's structure converges to an idealized form suitable for the
|
|
workload it is being used for. 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.
|
|
|
|
Recent work has hinted at the possibility of a radical new class of adaptive
|
|
indexes called just-in-time data structures that adapt their layout to rapidly
|
|
changing workloads. A just-in-time data structure (JITD) can emulate the
|
|
structure and performance characteristics of a variety of static and adaptive
|
|
indexing schemes, while being able to gracefully transition between them in
|
|
response to changing workloads.
|
|
|
|
If successful, the proposed research will realize this radical new class of
|
|
index structures by
|
|
(1) generalizing preliminary work in this area to emulate a broader class of index structures and performance tradeoffs,
|
|
(2) identifying opportunities for automation in the design of a JITD,
|
|
(3) addressing practical challenges such as concurrency in JITDs, and
|
|
(4) further generalizing JITDs to a new class of workload: incremental view maintenance.
|
|
|
|
-- Intellectual Merit --
|
|
JITDs represent a new direction in research on indexing and physical layout
|
|
design for data management systems that combines elements of programming
|
|
language design with more classical database techniques. The proposed work
|
|
will demonstrate the generality of the JITD model, and establish groundwork
|
|
for future research in the area through specification languages, a compiler,
|
|
and a generalization of functional datastructures and lazy evaluation that
|
|
promises to have significant consequences for work on distributed computation.
|
|
|
|
-- Broader Impact --
|
|
Index and physical layout design are a critical part of making data management
|
|
systems perform well. If successful, the proposed work promises to enable a
|
|
new class of index structures that dynamically adapt to changing workloads.
|
|
This in turn promises to help next generation data management systems cope
|
|
with the variability, volume, and velocity of big data. This proposal will
|
|
also result in the education and training of two PhD students, and help to
|
|
support the core curriculum development and outreach goals of the PIs. The
|
|
PIs have a long history of outreach at the K-12 level, and routinely work with
|
|
and provide professional development opportunities for local high-school
|
|
teachers.
|
|
|
|
-- Keywords --
|
|
Data Structures; Indexing; View Maintenance; Compilers; Physical Design;
|
|
Programming Languages
|