Exam

Question 1

Name advantages of colum-wise storage (DMS)

Answer 1

Store only one column per page
=> All data is relevant for query

• Fetch less data from memory
• Data compression might work better
• if lucky, full data fits into cache

Question 2

Explain Binary Association Tables (MonetDB)

Answer 2

All tables have two columns (head and tail)

Each column yields one binary association table (BAT)

Identify matching entries by using object identifiers (oid)

Using virtual oids they do not need to be materialized in memory (using only an index)

Question 3

Describe Hardware Trends and memory wall, and their implications

Answer 3

Processors get performance boosts faster than memory, yielding a performance gap between CPU and meory speed which is called “memory wall”.
This means that CPUs spend much of their time waiting for memory

Question 4

Do modern processors implement write back or write through?

Answer 4

Write back

Question 5

Explain Direct-Mapped Cache

Answer 5

A block can appear at only one place in the cache

• simpler to implement
• faster
• increased chances of conflict

Question 6

Explain Fully Asociative Cache

Answer 6

A block can be loaded into any cache line

• does not scale
• used for small Translation Lookaside Buffers (TLB)

Question 7

Explain Principle of Locality

Answer 7

Pareto Principle (80-20)

Spatial Locality:

• Code contains loops
• Data is spatially close

Temporal Locality:

• Reuse functions
• Reuse data

Question 8

Explain Set-Associative Cache

Answer 8

• Group cache lines into sets
• map blocks to sets
• place block anywhere within a set

Question 9

Explain the consequences of operator-at-a-time processing

Answer 9

Consume and produce full columns
Materialize every (sub)result in memory
Run each operator exactly once

Extremely tight loops

• fit into instruction caches
• -can be optimized by compilers:
• – Loop unrolling
• – Vectorization (SIMD)
• – Hardware prefetching

Question 10

Explain the consequences of tuple-at-a-time processing

Answer 10

Tightly interleaved
=> Combined instruction footprint large
=> Instruction Cache Misses

Large function call overhead
=> Millions of calls

Very Low instructions-per-cycle (IPC) ratio

Combined states too large for cache
=> Data Cache Misses

Hard to optimize by compiler

Question 11

Explain Volcano Iterator Model (tuple-at-a-time)

Answer 11

• operator request tuples from their input using next()
• “Pipelining”
• operators keep their states

Question 12

Explain Word Size

Answer 12

Word Size refers to the size of the natural unit of data “word”

A wordsize typically today is 32bit or 64bit

1 Word or multiple words are used to save integers/floats/adresses

Question 13

Explain Write Back

Answer 13

Data is only written into cache

• Status field acts as modified marker

Write on eviction of dirty cache lines

Question 14

Explain Write Through

Answer 14

Data is directly written to lower-level memory (and cache)

• Writes stall the CPU
• Simplifies Data Coherency

Question 15

How do systems compensate for slow memory? (name 6)

Answer 15

Systems use caches:

• DRAM with high capacity, but long latency
• SRAM with better latency, but low capacity
• Memory Hierarchy
• Cache Lines
• Set associativity
• Locality of data and code

Question 16

How to identify a block?

Answer 16

Derive a tag from the memory address

Question 17

Implications of Cache Parameters (Size, n-way associative)

Answer 17

Cache misses decrease

Question 18

Name a disadvantage of row-based storage (NSM)

Answer 18

Tuples are stored sequentially on a database page

• Load irrelevant information into the cache

Question 19

Name advantages of colum-wise storage (DMS)

Answer 19

Store only one column per page
=> All data is relevant for query

• Fetch less data from memory
• Data compression might work better
• if lucky, full data fits into cache

Question 20

Name three different strategies of block replacement

Answer 20

Least Recently Used LRU
First In First Out FIFO
Random