DST Lezione 8

Lezione 8

Range Partition

Say i have a student table and a field is region from they’re from, and the values are ofcourse not unique. The idea behind range partition is to have instead of the student table memorized in a single file, you have a student table splitted in three files:

1. File 1 with region equal to IT
2. File 2 with region equal to UK
3. File 3 with region equal to Other

The advantage from a physical and performance perspective depends on the kind of load that the database and that table has, and from the kind of query that are executed very often.

Let’s think of a query most advantageous, and one disadavantageous. Let’ say you do very frequently query with a ‘WHERE’ on ‘REGION’, a restriction on region. What changes if you have all the data in one table or if you have split data?

Advantageous case: Say that on this table we built a B+ index, that is dense, and the field has low cardinality (<10 values). The selectivity will be very low (because it’s a fraction, the denominator will be a big number). I expect a large number of students to be in IT or UK, so it’s not useful to use a B+ Index. B+indexes are good when you need to find an “ago nel pagliaio” i.e. to a query corresponds very few data (low NET). (AGGIUNGI PUNTATORE A LEZIONI PRECEDENTI).

In this case, if i split regions in each file, i just need a very small index that tells me in what partition there is the region i want. In this way i don’t have to pay a full scan of the table for finding students from IT. Also, the resulting file from range partition will be smaller than the entire table.

Say that the query now is:

WHERE REGION='x' AND DEGREE='CS'

I know region is from FILE 1 from the master index. Unless i have very small selectivity, building an index on this smaller file is convenient because i index only a fraction of data, i have a shorter tree in height and i basically i reduce the number of IO operations by 1/10 (i need to look only in a single file).

Say i want to do instead a division by University Department because most of my queries contains:

WHERE DEGREE='x'

So i would have File1: CS, File2: Biology, File3:Others - and so on. In this case make sense this division. Usually if i want to do evaluation on degree courses and do statistics i do them by the departmentent.

Advantages Recap

• Low cardinality fields with multiple different values
• Most of my queries includes the restriction WHERE FIELD=‘x’

Disadvantageous case: The obvious one first: if the previous query becomes:

WHERE SURNAME='ROSSI' AND DEGREE='CS'

I have built an index by region ‘IT’,‘UK’ and ‘Others’. So now i have the table split across 3 files. Rossi could be in one of the three file, so i need to scan three different files.

Another disadvantageous case, analogous to Bitmap Indexing (PUNTATORE A LEZIONE PRECEDENTE) is when cardinality of the field is too high. Data becomes too fragmented and performance are worst.

Another disadvantage is when partitions are umbalanced, for example if most of the row are placed in the first file, which is big, and the others are small.

Disadvantages Recap

• When data is unbalanced
• When cardinality is too high
• When i have very often queries from non range partitioned fields

Logical Partitions

Say i have a physical range partition on DEGREE, because most of my queries are alike:

WHERE DEGREE='x'

Where ‘x’ is a general variable could be IT (department), Biology, Telecomunications and so on.

If i have too many students from region = IT, and the table is too big what i can do is building something like a “view” with a subset of rows from that file we create. A sort of virtual column, where this field is derived.

CASE WHEN REGION='IT' THEN 1 ELSE 0

What we are doing is building a virtual field and can use this field for partition. So in this example we get two groups of data: all the data students and all the others. But ofcourse you can put how many regions you want.

Say i have a “Date of Enroll” Attribute in the table, why is it to frequently used? If you partition by this attribute, what you get? Let’s think about granularity: i have data of enroll. Should i partition at the day level? No, but i can attribute by trimester, semester, year and so on.

Granularity and thresholds between partitions

Say that my Students table contains the field “Date of Enroll”. The granularity depends on the volume of data. In this case, data becomes old, but most queries are from the most recent. So what makes sense to do is to Range Partition based on this field.

Imagine lika a roll transportation. Each trimester you get a new partition of data and you discard the oldest one. In real data warehouses the time window is usually 7 years.

In general, depending on the data volume, you can load new data each X time, like each month. Another possible way to organize data is to do a partition from Date X to Date Y, the next from Date Y to Z and so on. This helps to create uniformed partitions.

At logical level nothing changes because you still see one table. So this techniques if used in the right context is very powerful.

(PUNTATORE A LEZIONE FUTURA) This topic will be further explained in distributed systems, where data partitions are called data shards.

Extention of Range Partition: Multidimensional clustering

It means that you split data in multiple partitions, but using multiple attribute. For example, i can split a student table both by region and degree.

In this case, the memory area would be bi dimensional, so a matrix of size given by the cardinality of region multiplied by the cardinality of degree.

I can also do 3D clustering using the “Date Enrolled” dervied attribute at semester granularity if i want.

Advantage of multidimensional clustering

As in one dimension, it is useful when i often have queries with WHERE restrictions. In the case of multidimensional clustering i shoud have queries with one ore more AND logical restriction:

WHERE REGION='X' AND DEGREE ='Y'

From an I/O operations point of view, it only costs me to find the file that contains tables with this restriction.

Disadvantage of multidimensional clustering

It is not advantageous when you do a query by other fields, because i have to scan all the partitions. Clustering could be seen as a way of sorting data on the physicial layer, so i get an advantage only when i query using the sorting field.

Another problem is partition imbalance, which is even worst in this case because:

• If we want to balance partitions, it is harder because we have multiple attribute to consider: i.e i could get imbalance in one attribute but not on the other and so on.
• we could have empty partitions, that leads to memory waste and is a conseguence of imbalance.

In the end, multidimensional clustering is not much used. Range partition is more used. You can use the CASE WHEN to derive the partition from two attribute.

Materialized views

We all know that there can be VIEWS on data.

CREATE VIEW AS (....)

So a basic view does not exists is just a query that has a name and appears as a table. So i very often compute the average score of the students.

SELECT AVG(SCORE), MAT 
FROM STUDENTS 
JOIN EXAMS 
GROUP BY MATRICOLA;

Let’s say we wil call this view SCORES, so:

CREATE VIEW SCORE AS
(SELECT AVG(SCORE), MAT 
FROM STUDENTS 
JOIN EXAMS 
GROUP BY MATRICOLA);

Each time i open that view, the query is executed and the average score of students is shown. What changes if we create a materialized view?? As the name say we are saving the view on the disk. Why i should do that? We don’t execute each time the query, so we are saving computational time. In this case it’s very AVG, but if you have hundreds of thousands of students it may be not so fast. We seen a similar advantage also using Logical Indexes, the difference here is that we’re on the physical level.

What we can do is to simply save the view on the disk and retrieve it instead of doing computations every time, and i can also apply all the methods we are seen like indexing and range partitions.

Risks with materialized views

The risk is that data is not up-to-date. And in fact, when you create a materialized view you have a REFRESH on Commit. In this way data is up to date, but if you have heavy load in transaction and they come very often you have performance degradation.

So again it depends on the situation and it’s not an universal solution.

Refresh on commit is good for coherence but very risk for overload. You can use a less restricted policy of refresh, depends on the use of the data and that can relieve your system from a lot of computation. If you data is updated on 5 minutes ago, it depends. In the case of the students, the AVG can be done once per day. But if you do so, yes we are “wasting” a lit bit of memory (that is cheap) but we are saving computational time. So we don’t have to compute the average we just retrieve the values.

In general, you have to think to your use case and reason on how much would be tolerable.

Problem with views: outdated data

Materialized views like (logical) views can shows outdated data. Databases are multi-user systems. Consider a case when at time i have both Client A that query a table and Client B that writes it. Databases solves this problem using transactions. But Views don’t have a transaction mechanism, so in that case if A nd B are operating on a Views, A will see outdated data.

Phantoms, Incorrect summary problem and so on are problems derived from the use of view and are treated in detail elsewhere.

Sampling

Consider a student table. I don’t have all the students table from all the world, so it’s a sample of students. If i want to compute the average of the students i do:

SELECT AVG((SYSDATE-BirthDate)/365) FROM STUDENTS; 

This query gives you on number, but to compute it i need to full scan the entire table. In general, this operation could be too heavy if you have billions of tuples. What we could do is using statistics. We empirically know that age follows the gaussian distribution in the general population. Most of the students will have an age that i concentrated around the true mean of the distibution. The implication of this is that i can use a sample of students like 100 students to get a good enough precision. If i would use all the students, i would get ofcourse the best precision, but we’re talking about numbers after the comma.

If i want to know exactly the average of students i will get a number like 25.78353. But .78 is almost a month, at thirt number we are going at day and hour level, but we don’t care. The most significant is just one number.

In conclusion, what i could do is a random permutation of 100 students and compute the average age on that sample to get a good enough result wasting less computational time.