source: liacs/ACA2010/presentation1/presentation-rvdzwet.lyx@ 198

Last change on this file since 198 was 83, checked in by Rick van der Zwet, 15 years ago

Fixed typo's

File size: 15.5 KB
Line 
1#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
2\lyxformat 345
3\begin_document
4\begin_header
5\textclass beamer
6\begin_preamble
7\usetheme{Warsaw}
8% or ...
9
10\setbeamercovered{transparent}
11% or whatever (possibly just delete it)
12\end_preamble
13\use_default_options false
14\language english
15\inputencoding auto
16\font_roman times
17\font_sans default
18\font_typewriter default
19\font_default_family default
20\font_sc false
21\font_osf false
22\font_sf_scale 100
23\font_tt_scale 100
24
25\graphics default
26\paperfontsize default
27\spacing single
28\use_hyperref false
29\papersize default
30\use_geometry false
31\use_amsmath 2
32\use_esint 0
33\cite_engine basic
34\use_bibtopic false
35\paperorientation portrait
36\secnumdepth 2
37\tocdepth 2
38\paragraph_separation indent
39\defskip medskip
40\quotes_language english
41\papercolumns 1
42\papersides 1
43\paperpagestyle default
44\tracking_changes false
45\output_changes false
46\author ""
47\author ""
48\end_header
49
50\begin_body
51
52\begin_layout Standard
53\begin_inset Note Note
54status open
55
56\begin_layout Plain Layout
57This file is a solution template for:
58\end_layout
59
60\begin_layout Itemize
61Talk at a conference/colloquium.
62
63\end_layout
64
65\begin_layout Itemize
66Talk length is about 20min.
67
68\end_layout
69
70\begin_layout Itemize
71Style is ornate.
72\end_layout
73
74\end_inset
75
76
77\end_layout
78
79\begin_layout Standard
80\begin_inset Note Note
81status collapsed
82
83\begin_layout Plain Layout
84Copyright 2004 by Till Tan tau <tantau@users.sourceforge.net>.
85
86\end_layout
87
88\begin_layout Plain Layout
89In principle, this file can be redistributed and/or modified under the terms
90 of the GNU Public License, version 2.
91 However, this file is supposed to be a template to be modified for your
92 own needs.
93 For this reason, if you use this file as a template and not specifically
94 distribute it as part of a another package/program, the author grants the
95 extra permission to freely copy and modify this file as you see fit and
96 even to delete this copyright notice.
97
98\end_layout
99
100\end_inset
101
102
103\end_layout
104
105\begin_layout Title
106Architectural optimizations in databases
107\begin_inset OptArg
108status open
109
110\begin_layout Plain Layout
111Architectural optimizations in databases
112\begin_inset Note Note
113status collapsed
114
115\begin_layout Plain Layout
116optional, use only with long paper titles
117\end_layout
118
119\end_inset
120
121
122\end_layout
123
124\end_inset
125
126
127\end_layout
128
129\begin_layout Subtitle
130Data Morphing: An Adaptive, Cache-Conscious Storage Technique
131\end_layout
132
133\begin_layout Author
134Rick van der Zwet
135\begin_inset Note Note
136status collapsed
137
138\begin_layout Itemize
139Give the names in the same order as the appear in the paper.
140
141\end_layout
142
143\begin_layout Itemize
144Use the
145\begin_inset Quotes eld
146\end_inset
147
148Institute mark
149\begin_inset Quotes erd
150\end_inset
151
152 inset (
153\family sans
154Insert\SpecialChar \menuseparator
155Custom Insets\SpecialChar \menuseparator
156InstituteMark
157\family default
158) only if the authors have different affiliations.
159\end_layout
160
161\end_inset
162
163
164\begin_inset OptArg
165status open
166
167\begin_layout Plain Layout
168Rick van der Zwet <hvdzwet@liacs.nl>
169\begin_inset Note Note
170status collapsed
171
172\begin_layout Plain Layout
173- optional, use only with lots of authors
174\end_layout
175
176\begin_layout Plain Layout
177- if there are really lots of authors, use
178\begin_inset Quotes eld
179\end_inset
180
181Author ET al.
182\begin_inset Quotes erd
183\end_inset
184
185
186\end_layout
187
188\end_inset
189
190
191\end_layout
192
193\end_inset
194
195
196\end_layout
197
198\begin_layout Institute
199LIACS - Leiden University
200\end_layout
201
202\begin_layout Date
203Advanced Compilers and Architectures, 2010
204\begin_inset Note Note
205status collapsed
206
207\begin_layout Itemize
208Either use conference name or its abbreviation.
209
210\end_layout
211
212\begin_layout Itemize
213Not really informative to the audience, more for people (including yourself)
214 who are reading the slides online
215\end_layout
216
217\end_inset
218
219
220\begin_inset OptArg
221status open
222
223\begin_layout Plain Layout
224ACA2010
225\begin_inset Note Note
226status collapsed
227
228\begin_layout Plain Layout
229optional, should be abbreviation of conference name
230\end_layout
231
232\end_inset
233
234
235\end_layout
236
237\end_inset
238
239
240\end_layout
241
242\begin_layout Standard
243\begin_inset Note Note
244status open
245
246\begin_layout Plain Layout
247If you have a file called "institution-logo-filename.xxx", where xxx is a
248 graphic format that can be processed by latex or pdflatex, resp., then you
249 can add a logo by uncommenting the following:
250\end_layout
251
252\end_inset
253
254
255\end_layout
256
257\begin_layout Standard
258\begin_inset ERT
259status open
260
261\begin_layout Plain Layout
262
263
264\backslash
265pgfdeclareimage[height=0.5cm]{institution-logo}{institution-logo-filename}
266\end_layout
267
268\begin_layout Plain Layout
269
270\end_layout
271
272\begin_layout Plain Layout
273
274
275\backslash
276logo{
277\backslash
278pgfuseimage{institution-logo}}
279\end_layout
280
281\end_inset
282
283
284\end_layout
285
286\begin_layout Standard
287\begin_inset Note Note
288status open
289
290\begin_layout Plain Layout
291The following causes the table of contents to be shown at the beginning
292 of every subsection.
293 Delete this, if you do not want it.
294\end_layout
295
296\end_inset
297
298
299\end_layout
300
301\begin_layout Standard
302\begin_inset Note Note
303status open
304
305\begin_layout Plain Layout
306If you wish to uncover everything in a step-wise fashion, uncomment the
307 following command:
308\end_layout
309
310\end_inset
311
312
313\end_layout
314
315\begin_layout Standard
316\begin_inset ERT
317status open
318
319\begin_layout Plain Layout
320
321%
322\backslash
323beamerdefaultoverlayspecification{<+->}
324\end_layout
325
326\end_inset
327
328
329\end_layout
330
331\begin_layout BeginFrame
332Outline
333\end_layout
334
335\begin_layout Standard
336\begin_inset CommandInset toc
337LatexCommand tableofcontents
338
339\end_inset
340
341
342\end_layout
343
344\begin_layout Standard
345\begin_inset Note Note
346status open
347
348\begin_layout Plain Layout
349Structuring a talk is a difficult task and the following structure may not
350 be suitable.
351 Here are some rules that apply for this solution:
352\end_layout
353
354\begin_layout Itemize
355Exactly two or three sections (other than the summary).
356
357\end_layout
358
359\begin_layout Itemize
360At *most* three subsections per section.
361
362\end_layout
363
364\begin_layout Itemize
365Talk about 30s to 2min per frame.
366 So there should be between about 15 and 30 frames, all told.
367\end_layout
368
369\begin_layout Itemize
370A conference audience is likely to know very little of what you are going
371 to talk about.
372 So *simplify*!
373\end_layout
374
375\begin_layout Itemize
376In a 20min talk, getting the main ideas across is hard enough.
377 Leave out details, even if it means being less precise than you think necessary.
378
379\end_layout
380
381\begin_layout Itemize
382If you omit details that are vital to the proof/implementation, just say
383 so once.
384 Everybody will be happy with that.
385
386\end_layout
387
388\end_inset
389
390
391\end_layout
392
393\begin_layout Section
394Data Morphing
395\end_layout
396
397\begin_layout Subsection
398The Basic Problem That We Studied
399\begin_inset OptArg
400status open
401
402\begin_layout Plain Layout
403Basic Problem
404\end_layout
405
406\end_inset
407
408
409\end_layout
410
411\begin_layout BeginFrame
412Database Storage Methods.
413\end_layout
414
415\begin_layout FrameSubtitle
416The Order Matters
417\begin_inset Note Note
418status open
419
420\begin_layout Plain Layout
421A title should summarize the slide in an understandable fashion for anyone
422 how does not follow everything on the slide itself.
423
424\end_layout
425
426\end_inset
427
428
429\end_layout
430
431\begin_layout Itemize
432Traditional Row Based, Space Oriented Storage
433\end_layout
434
435\begin_layout Itemize
436Column based, New Trend.
437 Search Oriented Storage.
438\end_layout
439
440\begin_layout Itemize
441Both has advantages and disadvantages
442\end_layout
443
444\begin_layout BeginFrame
445Row Based Storage.
446\end_layout
447
448\begin_layout Itemize
449Focused on keeping data of a related entry close to each other
450\end_layout
451
452\begin_layout Itemize
453Common implementation N-ary storage model
454\end_layout
455
456\begin_layout Itemize
457\begin_inset Tabular
458<lyxtabular version="3" rows="2" columns="3">
459<features>
460<column alignment="center" valignment="top" width="0">
461<column alignment="center" valignment="top" width="0">
462<column alignment="center" valignment="top" width="0">
463<row>
464<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
465\begin_inset Text
466
467\begin_layout Plain Layout
4681
469\end_layout
470
471\end_inset
472</cell>
473<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
474\begin_inset Text
475
476\begin_layout Plain Layout
4772
478\end_layout
479
480\end_inset
481</cell>
482<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
483\begin_inset Text
484
485\begin_layout Plain Layout
4863
487\end_layout
488
489\end_inset
490</cell>
491</row>
492<row>
493<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
494\begin_inset Text
495
496\begin_layout Plain Layout
4974
498\end_layout
499
500\end_inset
501</cell>
502<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
503\begin_inset Text
504
505\begin_layout Plain Layout
5065
507\end_layout
508
509\end_inset
510</cell>
511<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
512\begin_inset Text
513
514\begin_layout Plain Layout
5156
516\end_layout
517
518\end_inset
519</cell>
520</row>
521</lyxtabular>
522
523\end_inset
524
525
526\end_layout
527
528\begin_layout BeginFrame
529Row Based Storage Engine.
530\end_layout
531
532\begin_layout Standard
533\begin_inset Graphics
534 filename system_arch.jpg
535 width 11cm
536
537\end_inset
538
539
540\end_layout
541
542\begin_layout BeginFrame
543Column Based Storage
544\end_layout
545
546\begin_layout Itemize
547Focused on allowing fast search on attributes
548\end_layout
549
550\begin_layout Itemize
551PAX storage model used.
552\end_layout
553
554\begin_layout Itemize
555\begin_inset Tabular
556<lyxtabular version="3" rows="2" columns="3">
557<features>
558<column alignment="center" valignment="top" width="0">
559<column alignment="center" valignment="top" width="0">
560<column alignment="center" valignment="top" width="0">
561<row>
562<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
563\begin_inset Text
564
565\begin_layout Plain Layout
5661
567\end_layout
568
569\end_inset
570</cell>
571<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
572\begin_inset Text
573
574\begin_layout Plain Layout
5753
576\end_layout
577
578\end_inset
579</cell>
580<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
581\begin_inset Text
582
583\begin_layout Plain Layout
5845
585\end_layout
586
587\end_inset
588</cell>
589</row>
590<row>
591<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
592\begin_inset Text
593
594\begin_layout Plain Layout
5952
596\end_layout
597
598\end_inset
599</cell>
600<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
601\begin_inset Text
602
603\begin_layout Plain Layout
6044
605\end_layout
606
607\end_inset
608</cell>
609<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
610\begin_inset Text
611
612\begin_layout Plain Layout
6136
614\end_layout
615
616\end_inset
617</cell>
618</row>
619</lyxtabular>
620
621\end_inset
622
623
624\end_layout
625
626\begin_layout Subsection
627The Approach
628\end_layout
629
630\begin_layout BeginFrame
631Definitions
632\end_layout
633
634\begin_layout Itemize
635
636\emph on
637group:
638\emph default
639Set of attributes that are writing to consecutive memory addresses
640\end_layout
641
642\begin_layout Itemize
643
644\emph on
645partition:
646\emph default
647Set of groups that uniquely defines the position of every attribute in a
648 relation
649\end_layout
650
651\begin_layout Itemize
652
653\emph on
654zone:
655\emph default
656Area of a page where all instances of a particular group are written
657\end_layout
658
659\begin_layout Itemize
660
661\emph on
662zone-record:
663\emph default
664defines a instance of the attributed in a particular group
665\end_layout
666
667\begin_layout BeginFrame
668The Algorithm
669\end_layout
670
671\begin_layout Enumerate
672Calculating cache-efficient storage template.
673\end_layout
674
675\begin_layout Enumerate
676Re-organizing the data into a cache-efficient organization.
677\end_layout
678
679\begin_deeper
680\begin_layout Enumerate
681Static evaluation, based on heuristics
682\end_layout
683
684\begin_layout Enumerate
685Dynamic restructuring based a request recognition.
686\end_layout
687
688\end_deeper
689\begin_layout Section
690Results
691\end_layout
692
693\begin_layout Subsection
694Main Results
695\end_layout
696
697\begin_layout BeginFrame
698Conclusions and Future Work
699\end_layout
700
701\begin_layout Itemize
702Speed-up made, but only on specific well-defined data-sets.
703\end_layout
704
705\begin_layout Itemize
706Finding a general optimization algorithm is hard.
707\end_layout
708
709\begin_layout Itemize
710Experiments did only cover memory based databases.
711\end_layout
712
713\begin_layout Section*
714Summary
715\end_layout
716
717\begin_layout BeginFrame
718Summary
719\end_layout
720
721\begin_layout Itemize
722Data Morphing is a Promising Method.
723\end_layout
724
725\begin_layout Itemize
726Combining both Row Based Storage and Column Based Storage could lead to
727 nice speeds-up.
728\end_layout
729
730\begin_layout Itemize
731Depending which method to choose how-ever is really hard.
732\end_layout
733
734\begin_layout Standard
735\begin_inset Note Note
736status open
737
738\begin_layout Plain Layout
739An outlook is always optional.
740\end_layout
741
742\end_inset
743
744
745\end_layout
746
747\begin_layout Standard
748\begin_inset ERT
749status collapsed
750
751\begin_layout Plain Layout
752
753
754\backslash
755vskip0pt plus.5fill
756\end_layout
757
758\end_inset
759
760
761\end_layout
762
763\begin_layout Itemize
764Outlook
765\end_layout
766
767\begin_deeper
768\begin_layout Itemize
769Make it scale so it also take the variable 'disk access' into count.
770\end_layout
771
772\begin_layout Itemize
773Build a framework to allow easy and proper testing for various combinations.
774\end_layout
775
776\end_deeper
777\begin_layout EndFrame
778
779\end_layout
780
781\begin_layout Section*
782\start_of_appendix
783\begin_inset Note Note
784status open
785
786\begin_layout Plain Layout
787All of the following is optional and typically not needed.
788\end_layout
789
790\end_inset
791
792Appendix
793\end_layout
794
795\begin_layout Subsection*
796For Further Reading
797\end_layout
798
799\begin_layout BeginFrame
800\begin_inset ERT
801status collapsed
802
803\begin_layout Plain Layout
804
805[allowframebreaks]
806\end_layout
807
808\end_inset
809
810For Further Reading
811\end_layout
812
813\begin_layout Standard
814\begin_inset ERT
815status collapsed
816
817\begin_layout Plain Layout
818
819
820\backslash
821beamertemplatebookbibitems
822\end_layout
823
824\end_inset
825
826
827\begin_inset Note Note
828status open
829
830\begin_layout Plain Layout
831Start with overview books.
832\end_layout
833
834\end_inset
835
836
837\end_layout
838
839\begin_layout Bibliography
840\begin_inset CommandInset bibitem
841LatexCommand bibitem
842key "DM2003"
843
844\end_inset
845
846Richard A.
847 Hankins
848\begin_inset ERT
849status collapsed
850
851\begin_layout Plain Layout
852
853
854\backslash
855newblock
856\end_layout
857
858\end_inset
859
860
861\emph on
862Data Morphing: An Adaptive, Cache-Conscious Storage Technique
863\emph default
864
865\begin_inset ERT
866status collapsed
867
868\begin_layout Plain Layout
869
870
871\backslash
872newblock
873\end_layout
874
875\end_inset
876
877 Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
878\begin_inset ERT
879status collapsed
880
881\begin_layout Plain Layout
882
883
884\backslash
885beamertemplatearticlebibitems
886\end_layout
887
888\end_inset
889
890
891\begin_inset Note Note
892status open
893
894\begin_layout Plain Layout
895Followed by interesting articles.
896 Keep the list short.
897
898\end_layout
899
900\end_inset
901
902
903\end_layout
904
905\begin_layout EndFrame
906
907\end_layout
908
909\end_body
910\end_document
Note: See TracBrowser for help on using the repository browser.