5. Indexes

5. Indexes
M = 3;
Insert: (“08 Qtr2”, “b”)
• Exercise 1. a
Time
Time
R
09 Qtr1
08 Qtr4
R
09 Qtr1
R3
R1
R3
08 Qtr4
R5
08 Qtr3
R5
R1
08 Qtr3
R4
08 Qtr2
R6
08 Qtr2
R2
08 Qtr1
R6
R2
08 Qtr1
a
b
c
d
e
f
g
Location
a
R41
b
c
d
e
f
g
R42
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
1
5. Indexes
M = 3;
Insert: (“08 Qtr2”, “c”)
• Exercise 1. a
Time
Time
R
09 Qtr1
R3
08 Qtr4
R
09 Qtr1
R5
R1
08 Qtr3
R3
08 Qtr4
R5
R1
08 Qtr3
08 Qtr2
08 Qtr2
R6
R2
08 Qtr1
a
R41
b
c
R42
d
e
f
g
R6
R2
08 Qtr1
a
R41
b
c
d
e
f
g
R42
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
2
5. Indexes
M = 3;
Insert: (“09 Qtr1”, “c”)
• Exercise 1. a
Time
Time
R
09 Qtr1
R
09 Qtr1
R3
08 Qtr4
R32
R31
R5
R1
08 Qtr3
08 Qtr4
R5
R1
08 Qtr3
08 Qtr2
08 Qtr2
R6
R2
08 Qtr1
a
R41
b
c
R42
d
e
f
R6
R2
08 Qtr1
g
a
R41
b
c
d
e
f
g
R42
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
3
5. Indexes
• Exercise 1. a
C
Time
R11
D
Time
08 Qtr4
R5
R1
08 Qtr4
08 Qtr3
08 Qtr3
08 Qtr2
08 Qtr2
R6
R2
08 Qtr1
A
a
b
c
d
e
f
g
R12
R
09 Qtr1
R
09 Qtr1
R32
R31
R5
R6
R2
08 Qtr1
R41
a
b
c
d
e
f
g
R42
B
On X, highest minimum rectangles are B and D = ‘b’, and lowest maximum are A and C = ‘a’
On Y, highest minimum rectangle is D = ’09Qtr1’, and lowest maximum is A = ’08Qtr2’
Dx = 1/3; Dy = 3/5; => D and A will create the new split nodes
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
4
5. Indexes
• Exercise 1. b
R11
R31
R31.1
R41
R31.2
R32
R41.1
R12
R42
R2
R5
R6
R41.2
R5.1
R32.1
R32.2
R42.1
R42.2
R5.2
R5.3
R6.1
R6.2
R6.3
R42.3
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
5
5. Indexes
Search: ([08 Qtr2, 08 Qtr3], [a,c])
• Exercise 1. c
R11
R32
R31
Time
R12
R
09 Qtr1
08 Qtr4
R5
08 Qtr3
08 Qtr2
R6
R2
08 Qtr1
R41
a
b
c
d
e
f
g
R42
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
6
5. Indexes
• Exercise 1. c
R11
R31
R31.1
R41
R31.2
R32
R41.1
R12
R42
R2
R5
R6
R41.2
R5.1
R32.1
R32.2
R42.1
R42.2
R5.2
R5.3
R6.1
R6.2
R6.3
R42.3
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
7
5. Indexes
ID
Qty
ID_Prod
ID_Date
1
…
5
1
2
2
3
ID
Product
Group
Category
1
1
Nokia N8
Cell Phones
Electronics
3
1
2
BlackBerry Bold
Cell Phones
Electronics
4
2
2
5
1
3
3
BlackBerry Storm
Cell Phones
Electronics
6
3
2
4
Apple Iphone
Cell Phones
Electronics
7
8
1
8
7
1
5
Samsung UE46
TV
Electronics
9
5
2
6
Panasonic TX50
TV
Electronics
10
6
1
11
5
3
7
Philips 46PFL
TV
Electronics
12
3
3
8
Panasonic TX46
TV
Electronics
13
2
3
14
8
4
15
6
2
16
7
2
17
5
4
18
3
4
19
4
1
20
2
4
21
1
4
ID
Qtr
Year
1
Q1
2010
2
Q2
2010
3
Q3
2010
4
Q4
2010
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
8
5. Indexes
• Exercise 2
– Start by building the Z-Curve with the indexes of the
dimensions through interleaving
• We have 2 dimensions, Products with 8 products ordered
by category and group, and Time, with 4 quarters
• Cell [0][0] represents product with id 1 sold in the first
quarter, and so on
• Since Nokia N8 was not sold in Q1
the field is empty, but that is the first
element on the Z curve
0
1
2
3
4
5
6
7
0
1
4
5
16
17
20
21
1
3
6
19
22
23
2
8
3
10
12
11
14
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
13
25
26
31
9
5. Indexes
• Exercise 2
– On selection of mobile phones over first 2 quarters, one
needs to read just [0;3] on Products and [0;1] on Time
– In our 2D space this is from [0][0] to [1][3]
– On Z-Curve this is from interleave(0,0) which is 0, to
interleave(1, 3) which is 7
– So we need to read from 0 to 7
since our region (block) is of
size 5, we need to read exactly
2 regions/blocks
– With no index we need to read everything
0
1
2
3
4
5
6
7
0
1
4
5
16
17
20
21
1
3
6
19
22
23
2
8
3
10
12
11
14
Data Warehousing & OLAP – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig
13
25
26
31
10