Lezione 4-5
Indexing
Sources:
- Lecture
- Fundamentals of Database Systems - Chapter 17
Indexes are an auxiliary access structure used for speed-up the retrieval of records in response to certain research conditions. Indexes can be built on any field of the file, either a single field or multiple fields.
Say i have a library and i need to find a book. If books aren’t ordered, when i want to find a book a i need to do a full scan, aka the cost of reading the tile of every single book.
Indexes for Heap File (unordered)
Say i store books in an unordered file, FIFO. What i can do is to create another file where i store the physical address of the records that i have stored on the primary file.
Structure of the auxiliary file (or primary index)
We usually store a pair of values: a key, that is the index key and a pointer.
Ofcourse, the key here is not necessary the primary key from the table.
The auxiliary file will be much smaller than the data file
- First, there are fewer index entries than there are records in the data file.
- Second, each index entry is typically smaller in size than a data record because it has only two fields, both of which tend to be short in size;
With two layers, it costs me a linear scan of the auxiliary file. The values in the index are ordered so that we can do a binary search on the index.
From a BFR perspective (see BFR), i have the following properties:
(remember the bfr is a division) I also get that:
(where P is pages or blocks).
In the case of an heap file, we need an auxiliary structure where every item points to a record in the table. This is called dense index.
Another property of indexes is that they’re ordered. This also means that the query complexity time goes down from full scan to
BFR for indexes unsorted file
Where NT= Number of tuples. And NP is number of pages.
Multi-level indexing
We can creare an index of an index. On the second level, since the previous level is sorted, i need as many pointers as are pages on the first level of the index.
We can recursively creating more indexes until we get one single index, and a structure that looks like a tree. The three is sortered because every level is sorteted.
Given the first level, i recall that to find the height of the tree
Where
The BFR of the index is called fan-out. It is a value that gives the value of growth of the index
How much does it costs to find a record?
Given this tree structure, the costs is equal to
Sorted file
The starting costs of reading is
Sparse index In this case, the first level indexing is sparse because i have a sorted file and i don’t need an index for every record. A sparse index is when i have an index for every page. Thanks to this property, the first level will be much smaller than before, it’s like in our huge library, books are already alphabetically ordered.
BFR for indexes in sorted file
And the rest is calculated the same as in BFR for indexes unsorted file.
We also get here a complexity of
Indexes for unique, not unique, sorted and unsorted
We have four possibility.
Unique sorting field, sorted file
Considering the students table example. In this case, the primary file is sorted by matricola that it’s unique. the index will be sparse.
Not unique sorting field, sorted file
Having not unique sorting field is a valid option. I can sort using an arrangement like Clustered storage (or sorted storage).
Number of different values
In this case let’s introduce this new variable called NDV. In the previous student example, one field was of the countries from they come from. The total number of different value from this field is called NDV and will be used to calculate the Number of Pages (or Block) required for storing the index
If i have ten countries, then i just need ten pointers. It’s a sparse index. Also, on the first layer indexing i get an implicit sort by country.
Sparse index In this case for indexing, we need a pointer for each distinct value.
Unique sorting field, unsorted file
As we saw in the heap file, the index could be matricola, but the first level index is dense.
Not unique sorting field, Not sorted file
This is the worst case. I have an heap file and the index key is not unique. First, i need a dense index because i need a pointer for each value. But there is a problem, since that value is repeteated.
Three possibilities:
- I have a key with a list of pointers. The structure is fancier and each index’s record has variable length.
- I repeat the key, creating redundency and waste of memory, but the index is simple.
- I create another level. Where for example i put just the first IT and a pointer to another pages where there are the rest of records with “IT” value. It is very ineffcient because you have to do multiple searches and look in different places
Disadvantages with indexes
Writing
"What you save in reading you pay in writing"
The problem with index is that you get reading advantage in reading but you get disadvantage in writing. If you update data you also need to update the index. Not only, but index are sorted, so update means full scan of the index (
To mitigate this problem, as we saw in DST Lezione 2-3-4, free space is key here to avoid performance degradation.
Disadvantages with indexes: selectivity
Selectivity is measured as:
It’s very similar to probability, it could be seen as “how probably i would get an answer from a query”.
Examples
Let’s consider a table of students as in our previous examples If i have a query like (MAT=‘123’), how many tuples that matches this conditions exists? At mosts one (or 0). So assuming is one, and 1000 tuples, selectivity is 1/1000 = 0.001
Formal definition and equidistribution
FIrst we define the Number of Repeated Values as:
Where NDV = Number of different values. NT = Number of tuples. We defined selectivity as:
By putting NRV definition in the above formula we get that selectivy could also be calculated as
Equidistribution and histogram
Let’s say i have an histogram of each field that has repeating values in the table student example (where one field is region with values like IT, UK, FR and so on).
In our examples we will assume equidistribution for fields. The histogram represent the distribution of students from each region. Say i have 4 countries so NDV = 4 and 1000 tuples, so NT =1000. Assuming equi distribution it means that for each country we have the same number of student.
The selectivity would be:
What if there is no equidistribution?
In this case, we would have a different value for each possible fields. Ofcourse if most students are italian, we get an higher selectivity than selectivity of students from uk.
Composite query with AND logical operator
Suppose i have a query like this:
SEL(MAT='123' AND NAME='MARIO')
Selectivity is like probability. As seen in our previous example we saw that for matricola, which is a key with unique value, the selectivity would be
Recall from probability theory that:
If
In this case, we have a composite query with an AND, and Matricola is independent from Name, so the selectivity would be calculated as:
Notice that his value is much smaller than
I have three possibilities to manage this query:
- Index by matricola → costs h+1 and it’s the most convenient
- Index by name → costs
(number of repeated values) because i could have more students named Mario. - Composite index →
, but here the value is higher than the in the first case because the index is bigger. Also, in the case of a composite index, the selectivity is higher than indexing by matricola.
Number of Expecting Tuples
In the previous example with regions, where selectivity was 1/4. I get a NET of
Example with field ‘name’:
Consider that there are 100 people named mario. Then i would get a selectivy of
Multi-level indexing and Selectivity
What’s the conseguence of this? Think of a multi level indexing, what’s the cost of retrieving a value considering selectivity.
Example: selectivity 1 → 1/NT → h+1 — ok i have no problems here
But if selectivity is (250), what i need to consider that, if i index by ‘country’ field, once i get to the leaves of the trees in (h+1) steps, i need to look for the exactly record, the complexity grows to
Example: NET=250, h=3, Number of tuples = 1000 → Full scan costs 1000
Composite query with OR logical operator
Consider this query:
We have three possible options to manage this:
- Composite index: too high cost to update the index file in case of writing on the data file
- Index by name: selectivity is high (as saw in previous example) and it may cost same or more than a full scan
- Index by matricola: once i index by matricola, i still have to query every tuple looking for name ‘mario’, so basically another full scan and i get no advantage from the index.
Example: composite index
A composite index would be composed of three values:
OR conditions are the worst you can image in terms of query optimization, there is not solution. It’s not convenient to built an index based on name and not convenient to made an index on matricola or an index that is composite.
What to do then? UNIONS are better than OR at SQL level, or paritioning data, there are many possible way to avoid OR.
Composite query with non unique fields
Let’s consider this query:
: index by surname, costs me : index by name, costs same as above : costs me . In this specific case, option one and three are convenient because: - Indexing by surname is better than by name because there are less repeating surname (in average), so selectivity is higher
- Indexing by both with a composite index is also good because people that have the same name and surname are very rare.
By this example, we see that there is no universal answer and in general, it depends on data.
Common Pitfall with indexes
Usually when you have a query like this:
SELECT * FROM STUDENTS
WHERE (VERY COMPLICATED CONDITION)
What some programmers do is to build an index out of that “very complicated condition”. That’s a mistake because as we saw, what we may save in reading, we pay later that in writings.