Dear learning community,
as many of you asked for some more details on the correct answers for the closed assignments or access to the past questions if you missed them, we decided to put the solutions online in the respective week.
If there are any questions left, please do not hesitate to ask in the forum.
Best regards,
Ralf for the IMDB Teaching Team
Question Name: Scan in Row Store
Text: How long does it take to do a full table scan covering all attributes in a row store table if the table is ~10TB large? The assumed scan speed is 4 MB/ms per core.
Correct answer:
- ~62.5 s with 40 cores
Incorrect answers:
- ~62.5 s with 1 core
- ~50 s with 1 core
- ~125 s with 40 cores
General explanation: With an assumed scan speed of 4 MB/ms (or 4 GB/s), we need 10 TB / 4 GB / s = 2,500 s on one core, and 62.5s on 40 cores.
Question Name: Execution Plans
Text: For any SELECT statement...
Correct answer:
- several execution plans with the same result set, but differing performance may exist
Incorrect answers:
- exactly one execution plan exists
- several executions plans may exist that deliver differing result sets
- there always exist exactly two execution plans, which perform identically in each aspect
General explanation: For any SELECT statement, several execution plans with the same result set, but different runtimes may exist. As an example, we want to query all men living in Italy from world population table; the database offers three different execution plans. We could query for the gender 'male' first and then for the country 'Italy' in the result set or we start with the selection for 'Italy' and then we narrow the result to only males, or we might perform the two selections on 'male' and 'Italy' in parallel queries, both running on the full dataset and then create the intersection. All three execution plans create the same result set, but require different runtimes. For example its faster to query first for 'Italy'and then for 'male', because in this case first 8 billion entries (all entries) and then further select on the resulting 60 million entries (all Italiens), if you start with 'male' and then query for 'Italy' you have to scan through 8 billion (all Italiens) and then through 4 billion entries (all males).
Question Name: Tuple Reconstruction Performance Factors
Text: The number of attributes of the reconstructed tuple is an important factor that can influence the performance of the operation on the column layout. Which of the following is the right explanation for this behavior?
Correct answer:
- A new cache line must be read for every attribute of the tuple and thus the number of the processed bytes will increase
Incorrect answers:
- The size of the reconstructed tuple increases
- There is a risk that the size of a whole tuple exceeds the size of a cache line and therefore it cannot be read in one cache access
- The number of attributes is not an important factor for the tuple reconstruction in a column layout, but the size of the tuple is the key factor, because the data is stored tuple-wise
General explanation: In a columnar layout, each attribute of a tuple has to be retrieved via an own cache access, because the attributes of one tuple are located faw away from each other in memory. So the number of bytes to be read increases with every attribute of the reconstructed tuple and this answer is correct. The size of the reconstructed tuple is not increased, this size is fixed for a given tuple. Of course, with every additional attribute, the whole tuple gets bigger, but the important factor that we want to describe within this question is that we need an additional cache access for every attribute, regardless how small it is. The risk, that a whole tuple could not fit into one cache line is also not of interest, since this, as described above, clearly does not reflect the retrieval behavior. Last but not least, the option that the number of attributes is not an important factor but the size of the tuple is the key factor is wrong, because it has the false addition "because the data is stored tuple-wise", which is not the case in a columnar layout.
Question Name: Scan performance on column and row layout: table scan
Text: Given is a table with the following characteristics containing information about all customers in Germany:
- columns: CustomerId, Customer Name, City, Street, Status, Sector, Category;
- size per field (uncompressed): 28 byte;
- number of rows: 500,000;
- cardinality of the city column: 12,200.
The size of a cache line is 64 byte.
A user wants to know "How many customers do we have in Berlin?"
How long will this query take on one CPU core with a scan speed of 4 MB per millisecond?
Correct answer:
- row store: 24.5 milliseconds
Incorrect answers:
- row store: 12.25 milliseconds
- row store with stride access: 4 milliseconds
- column store with dictionary compression: 2.75 milliseconds
- column store with dictionary compression: 1.75 milliseconds
General explanation: The needed time in a row store without stride access is (7 attributes * 28 byte per attribute per row * 500,000 rows / ( 4 MB / ms / core ) = 7 * 28 * 500,000 / 4,000,000ms = 24.5ms
The needed time in a row store with stride access is (size of a cache line * number of accesses / scan speed) = 64 * 500,000 / 4,000,000ms = 8ms;
The needed time in a dictionary encoded column store is (number of needed bits to encode attribute * number of values / scan speed / cores) = (14 bit / 8 bit/byte) * 500,000 / 4,000,000 byte/ms = 0.21875ms
So, only the answer for the row store without stride access is a valid answer here.
Question Name: Late Materialization
Text: What is late materialization?
Correct answer:
- A processing strategy, which restores the requested tuple at the latest possible point during processing
Incorrect answers:
- An advanced aggregation strategy compared to basic ones like SUM
- A strategy that works on uncompressed data as long as possible
- Long batch operations that are run over night in big enterprises
General explanation: Late materialization, in contrast to early materialization, is a processing strategy, which aims at reconstructing the actual attribute values from the valueIDs at the latest possible point during processing. Working with the compressed integer values leads to speed advantages in most cases. Depending on the circumstances, there are also constellations where early materialization is favorable, however these situations are seldom. In general, late materialization is tried to keep up as long as possible. The other answers are wrong. There is no way to determine or even a special name for complex or advanced aggregation strategies. To work on uncompressed data as long as possible is like the correct answer, just twisted. Because data is saved in a compressed format, it is not the case that we work on uncompressed data first and than compress it afterwards. The last wrong answer, that late materialization describes long batch operations run over night is just messing with the word "late". These scheduled batch jobs that are run over night have no distinguished term we know of, sometimes they are just called "over-night batch jobs".
Question Name: Early Materialization
Text: What is early materialization?
Correct answer:
- A processing strategy, where valueIDs are decoded into actual values at the earliest time during processing
Incorrect answers:
- An advanced aggregation strategy compared to basic ones like SUM
- A strategy, which works on compressed data as long as possible
- Long batch operations that are run in the early morning hours in big enterprises
General explanation: Early materialization, in contrast to late materialization, decodes valueIDs into the actual values at the earliest time during processing. The other answers are wrong, for an analog description please have a look on the explanation of the question "Late Materialization".
Question Name: Faster Materialization Strategy
Text: Assuming the execution of the question which queries and returns the complete data of all people in the world whose first name is NOT Jean-Pierre. Which of the following statements is true?
Correct answer:
- Both strategies, early and late early and late materialization, will equally take a decent amount of time, as the predicate selects a lot of values, i.e., the costs are bound by the dictionary lookups to materialize the result
Incorrect answers:
- Late materialization should be faster, since the predicate can be evaluated solely by using the dictionary of the column fname.
- Early materialization should be faster, since the result will contain less returned rows.
- The query will not return at all, because databases are not suitable to perform such queries and simply drop those.
General explanation: It is correct that a lot of data has to be transferred to the client in the end and that there will be plenty of dictionary lookups. Therefore, it is likely that no relevant speed difference between late and early materialization is noticeable.
Question Name: Querying the Differential Buffer
Text: Correctly complete the following sentence: Whereas write accesses are going solely against the differential buffer, ...
Correct answer:
- read accesses are going against the main store and the differential buffer
Incorrect answers:
- read accesses are solely going against the main store
- read accesses against the differential buffer are denied
- read accesses are cached in a row-oriented format
General explanation: Read accesses have to go against the main store and the differential buffer, in order retrieve the most recent, valid entries. Just querying the main store would return potentially outdated information or lack completely new entries, just querying the differential buffer would not suffice since it holds only a fraction of the total data. Read accesses are not cached for any reason, regardless of the format.
Question Name: Statements Concerning the Differential Buffer
Text: Which statement related to the differential buffer is true?
Correct answer:
- Since the dictionary of the differential buffer is unsorted, range selects on the differential buffer are less efficient than on the main store
Incorrect answers:
- Tuples in the differential buffer require less memory, because the advanced compression techniques used there result in better compression than in the main store
- The differential buffer is read-optimized
- The differential buffer should not exceed the size of a cache line (64 byte) for performance reasons
General explanation: The differential buffer has an unsorted dictionary to improve the write performance. Therefore it is not read-optimized. Tuples in the differential buffer require at least as much memory as the associated tuples in the main store, since no additional compression is employed. The size of a cache line is certainly not enough for the differential buffer. The correct answer is therefore, that range selects are less efficient in the differential buffer, because the dictionary is not sorted. Even with a CSB+ tree, which allows fast access on the unsorted values, we can not determine whether a value is in the desired range by just checking for example whether it is >=10 and <20, but we have to check against a set of 10 individual values.
Question Name: Merge Properties
Text: What is NOT an objective of the merge process?
Correct answer:
- It stops all other queries
Incorrect answers:
- It can be executed asynchronously
- It has as little impact as possible on all other operations
- It does not prohibit any OLTP or OLAP queries
General explanation: The merge process should integrate all occured changes held in the differential buffer into the main store while affecting all other processes as little as possible. Therefore, it should be executed asynchronously and does not prohibit or stop any other query.
Question Name: Asynchronous Merge
Text: The merge process is asynchronous. This means:
Correct answer:
- It allows reading and writing of tuples during the merge phase
Incorrect answers:
- During the merge process, no data modifications or queries can be performed until the merge is completed. All queries are saved and delayed to be executed immediately after the merge finished.
- Immediately after one record is merged, a new query is executed and thus the overall execution is interleaved
- After each INSERT operation the merge process is triggered
General explanation: An asynchronous merge is essential for real time settings, since it allows reading and writing of tuples during the merge phase. This functionality is necessary to decouple the inner optimizations of the database from the availability of the database in general with regards to accepting incoming data and queries. Saving or buffering write queries until the merge finished would not yield any benefit to the direct appliance of the modifications into the new differential buffer. In contrast, it would either prohibit also read operations, or it would lead to inconsistent reads because all modifications that were applied in the meantime, would not be reflected before the merge finished. Interleaving as described in the wrong answer, would also lead to unpredictable behavior, since one does not know exactly when a read or write operation will take place. Triggering the merge after each INSERT would simply render the whole concept of a differential buffer useless.
Question Name: Hash Join
Text: Regarding the hash join, which statement is correct?
Correct answer:
- Hashing introduces additional complexity since we cannot guarantee the absence of collisions
Incorrect answers:
- The hash-join has a higher run-time complexity than the nested-loop join
- A sorted dictionary structure slows down the performance of the hash-join
- Hashing of values is only possible when these are stored within a columnar layout
General explanation: Hashing maps an arbitrary value to a so called hash key of fixed length. This key has to be computed via a hashing function, that may produce collisions, if two or more different values are mapped to the same key. Therefore, hashing introduces additional complexity. However, the hash-join ( O (n*log(n) ) has a better run-time complexity than the nested loop join ( O(n^2) ). The presence of a sorted dictionary generally never slows down any other algorithm. Also, the idea of hashing is independent of the data storage format.
Question Name: Many-to-Many Relationship
Text: What is a many-to-many relationship?
Correct answer:
- A many-to-many relationship between two tables means that each object on the left side is joined to zero or more objects on the right side of the table and vice versa each object on the right side has zero or more join partners on the left side of the table
Incorrect answers:
- A many-to-many relationship between two tables means that for each object on the left side, there are one or more objects on the right side of the joined table
- A many-to-many relationship between two tables means that for exactly one object on the left side of the join exists exactly one object on the right side
- A many-to-many relationship between two tables randomly combines each object of the left table with many objects from the right table and vice versa
General explanation: The first wrong answers makes no statement concerning the cardinalities from the right side to the left side of the joined table. Additionally, the statement "one or more objects" is not correct, since it has to be "zero or more" objects. The second wrong answer would enforce a one-to-one relationship and additionally would not allow any entries without partners. This requirement does not have a common name. To clarify, the relationship "one-to-one" allows also entries without partners and is written "0..1 - 0..1". The third incorrect answer states that the entries are connected randomly, which is never the case in relational databases.