Index on Demand
Publication Date: 2017-Jun-07
The IP.com Prior Art Database
TITLE: Index on Demand
Dynamic decisions are made which index structures are dropped and replaced with new ones providing
better support for the running workload. This is addressing the need that data scientist look at data
from different angles within a short amount of time, more and more queries are generated and issued
and less and less workload is known at design time allowing a data modeler and / or database
administrator (DBA) to create appropriate index structures ahead of time.
Database technologies use index structures to improve query performance. State of the art today is that
database administrators (DBAs) / data modelers need to identify where indexes are needed and at
creation time they also need to decide the type of index, e.g. B-Tree vs. Hash Index. The different types
of indexes have different advantages / disadvantages and are optimized for different usage, examples
• B-Tree: good for query predicates with range selections
• Hash Tree: good for random access patterns
• Functional indexes: e.g. UPPER on index column
• Index for text searches: e.g. supporting predicates as “LIKE”, “CONTAINS”, …
• Synopsis tables / zone maps known from commercial databases.
• Data consistency index structures: they are used to enforce uniqueness
• Index with includes option: in these index structures content of columns is stored as
The benefits of using index structures are:
• Avoiding sorts
• Indexes with include columns can avoid table lookups
• Performance gains for operations like
o single or ranges of values
o supporting joins between tables (reducing n*n to n*log n which is a dramatic
reduction on runtime (e.g. n=1000 is 1.000.000 vs. 3.000 pairs)
All index structures are created and written on storage from which they get loaded into memory. In the
current state of the art this task is cumbersome and so some utilities have been developed to assist
DBAs and data modelers to make better decisions where an index would be beneficial, which are:
• Monitoring of queries at execution time to determine the index quality score which is
the ratio of records selected vs. record read. For example a ratio of 1:1000 would mean
that for 1000 records read, only 1 record qualified for the query selector which is a poor
ratio for an index. On the other hand, a ratio of 1:2 means for every 2 records read 1
record qualifies for the query selector which is a pretty good ratio.
• Index advisor: This capability basically assesses the query access plan to determine if the
usage of an index would significantly improve query performance and if that’s the case,
suggests the use of an index.
There is a drastic demand in increased flexibility needed because:
• Application change over time. A few changes in the UI can cause significant different
workload on the database.
• Month/Quarter/Year end reporting is typical very special workload. It does not make
sense to keep and maintain physical indexes for this few occasions.
• Data Analyst / Data...