Neutrale TU Graz-Standardpräsentation 4:3

Neutrale TU Graz-Standardpräsentation 4:3

1 SCIENCE PASSION TECHNOLOGY Database Systems 07 Physical Design & Tuning Matthias Boehm Graz University of Technology, Austria Computer Science and Biomedical Engineering Institute of Interactive Systems and Data Science BMVIT endowed chair for Data Management Last update: Apr 29, 2019 2 Announcements/Org #1 Video Recording Since lecture 03, video/audio recording Link in TeachCenter & TUbe (video recorder fixed?) #2 Statistics Exercise 1 All submissions accepted (submitted/draft) In progress of grading, but understaffed #3 New Exercise Rules Still mandatory exercises (final exam admission) Relaxed 50% successful completion rule: 1 exercise 2%-50% allowed 65.3% 77.4% Ex.1 Sample / Feedback #4 Exercise 2 Various issues (data cleaning, schema, etc), latest update Apr 22 Modified deadline: Apr 30 May 07 11.59pm INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 3

Physical Design, and why should I care? Performance Tuning via Physical Design Select physical data structures for relational schema and query workload #1: User-level, manual physical design by DBA (database administrator) #2: User/system-level automatic physical design via advisor tools Example SELECT * FROM R, S, T WHERE R.c = S.d AND S.e = T.f AND R.b BETWEEN 12 AND 73 Base Tables R Mat Views S T MV1 MV2 e=f T c=d 10 1000000

12R.b73R.bR.b7373 S Partitioning B+BitMap Hash Physical Access Paths Tree Compression RINF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 4 Agenda Compression Techniques Index Structures Table Partitioning Materialized Views INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 5 Compression Techniques INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Compression Techniques 6 Overview Database Compression Background: Storage System Buffer and storage management

(incl. I/O) at granularity of pages PostgreSQL default: 8KB Different table/page layouts (e.g., NSM, DSM, PAX, column) 136 115 81 136 Header tuple 115 175 Header tuple tuple offsets Compression Overview Fit larger datasets in memory, less I/O, better cache utilization Some allow query processing directly on the compressed data #1 Page-level compression (general-purpose GZIP, Snappy, LZ4) #2 Row-level heavyweight/lightweight compression #3 Column-level lightweight compression [Patrick Damme et al: Lightweight #4 Specialized log and index compression Data Compression Algorithms: An Experimental Survey. EDBT 2017] INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Compression Techniques 7 Lightweight Database Compression Schemes Null Suppression Compress integers by omitting leading zero bytes/bits (e.g., NS, gamma)

Run-Length Encoding Compress sequences of equal values by runs of (value, start, run length) Dictionary Encoding Compress column w/ few distinct values as pos in dictionary ( code size) Delta Encoding Compress sequence w/ small changes by storing deltas to previous value 106 00000000 00000000 00000000 01101010 11 01101010 1 1 1 1 7 7 7 7 7 3 3 3 3 3 3 ... 3,10, 1,1,4 7,5,5 6 1 7 7 3 1 7 1 3 3 7 1 3 3 7 3 ... 1,3,7 dictionary (code size 2 bit) 1 3 3 2 1 3 1 2 2 3 1 2 2 3 2 ... 20 21 22 20 19 18 19 20 21 20 ... 0 1 1 -2 -1 -1 1 1 1 -1... 20 21 22 20 71 70 71 69 70 21 ... 22 21 70 -1 0 1 -1 1 0 1 -1 0 Frame-of-Reference Encoding INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning 1 ... Matthias Boehm, Graz University of Technology, SS 2019

8 Index Structures INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Index Structures 9 Overview Index Structures Table Scan vs Index Scan Index Scan Table Scan For highly selective predicates, index scan asymptotically much better than table scan Index scan higher per tuple overhead (break even ~5% output ratio) Multi-column predicates: fetch/RID-list intersection ix sorted Uses of Indexes Lookups / Range Scans ix table data Unique Constraints Index Nested Loop Joins

contains key 107? ix Aggregates (count, min/max) R ix S INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 size= 7100 ix Index Structures 10 Classification of Index Structures Traditional Classification 1D Access Methods Key Comparison Sequential Tree-Based [Theo Hrder, Erhard Rahm: Datenbanksysteme Konzepte und Techniken der Implementierung, Springer, 2001] Key Transformation Sort-Based Hash-Based

Binary Search Trees Sequential Lists Multiway Trees (B-Tree) Linked Lists Prefix Trees (Tries) Prefix Trees for in-memory DBs [Matthias Boehm et al: Efficient In-Memory Indexing with Generalized Prefix Trees. BTW 2011] [Viktor Leis, Alfons Kemper, Thomas Neumann: The adaptive radix tree: ARTful Indexing for Main-Memory Databases. ICDE 2013] INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Static Dynamic Index Structures 11 Recap: Index Creation/Deletion via SQL Create Index CREATE INDEX ixStudLname ON Students USING btree Create a secondary (nonclustered) index on a set of attributes Clustered (primary): tuples sorted by index (Lname ASC NULLS FIRST); Non-clustered (secondary): sorted attribute with RIDs ix Can specify uniqueness, order, and indexing method table data PostgreSQL: [btree], hash, gist, and gin Delete Index Drop indexes by name

DROP INDEX ixStudLname; Tradeoffs Indexes often automatically created for primary keys / unique attributes Lookup/scan/join performance vs insert performance Analyze usage statistics: pg_stat_user_indexes, pg_stat_all_indexes INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Index Structures 12 B-Tree Overview History B-Tree Bayer and McCreight 1972 (multiple papers), Block-based, Balanced, Boeing Multiway tree (node size = page size); designed for DBMS Extensions: B+-Tree/B*-Tree (data only in leafs, double-linked leaf nodes) Definition B-Tree (k, h) n 1 1 2 log 2 k 1 (n 1) h log k 1 All paths from root to leafs have equal length h All nodes (except root=leaf) have [k, 2k] key entries All nodes (except root, leafs) have [k+1, 2k+1] successors Data is a record or a reference to the record (RID) k=2

P0 Key K1 Data D1 P1 Key K2 Data D2 P2 Key K3 Data D3 P3 Key K4 Data D4 P4 Subtree w/ keys K1 Subtree w/ K2 < keys K3 INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Index Structures 13 B-Tree Search 25 Example B-Tree k=2 Get 38 D38 Get 20 D20 Get 6 NULL 10 20 2 5 7 30 40 41 42 45 46 8 13 14 15 18 22 24 32 35 38 26 27 28 Lookup QK within a node Scan / binary search keys for QK, if Ki=QK, return Di If node does not contain key If leaf node, abort search w/ NULL (not found), otherwise

Decent into subtree Pi with Ki < QK Ki+1 Range Scan QL

41 42 first k 2k+1 41 42 45 46 47 overflow 30 40 45 1 46 47 last k INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Index Structures 15 B-Tree Insert, cont. (Example w/ k=1) Insert 1 Insert 4 1 2 6 1 4 5 7 1 5 Insert 5 Insert 8 2 6

2 Insert 2 (split) 1 1 7 8 5 Insert 3 (2x split) 2 Insert 6 4 5 5 6 1 4 2 1 6 3 5 2 6 Insert 7 (split) 1 5

7 Note: Exercise 03, Task 3.2 (B-tree insertion and deletion) INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 7 8 Index Structures 16 B-Tree Delete Basic Deletion Approach Lookup deletion key, abort if non-existing Case inner node: move entry from fullest successor node into position Case leaf node: if underflows (

underflow 4 2 1 4 1 5 3 7 8 1 2 8 5 4 7 3 7 5 4 7 8 underflow INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 1 2 5

8 Index Structures 17 Prefix Trees (Radix Trees, Tries) Generalized Prefix Tree Arbitrary data types (byte sequences) Configurable prefix length k Node size: s = 2k references Fixed maximum height h = k/k Secondary index structure insert (107,value4) 0000 0000 0110 1011 k = 16 k = 4 Characteristics Partitioned data structure Order-preserving (for range scans) Update-friendly Properties Deterministic paths Worst-case complexity O(h) INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Bypass array Adaptive trie expansion Memory

preallocation + reduced pointers Index Structures 18 Excursus: Learned Index Structures A Case For Learned Index Structures [Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis: The Case for Learned Index Structures. SIGMOD 2018] Sorted data array, predict position of key Hierarchy of simple models (stages models) Tries to approximate the CDF similar to interpolation search (uniform data) Systems for ML, ML for Systems [Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, Vikram Nathan: SageDB: A Learned Database System. CIDR 2019] Follow-up INF.01014UF Work Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 19 Table Partitioning INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 20 Overview Partitioning Strategies Horizontal Partitioning Relation partitioning into disjoint subsets

Vertical Partitioning Partitioning of attributes with similar access pattern Hybrid Partitioning Combination of horizontal and vertical fragmentation (hierarchical partitioning) Derived Horizontal Partitioning INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 21 Correctness Properties #1 Completeness R R1, R2, , Rn (Relation R is partitioned into n fragments) Each item from R must be included in at least one fragment #2 Reconstruction R R1, R2, , Rn (Relation R is partitioned into n fragments) Exact reconstruction of fragments must be possible #3 Disjointness R R1, R2, , Rn (Relation R is partitioned into n fragments) INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 22 Horizontal Partitioning Row Partitioning into n Fragments Ri Complete, disjoint, reconstructable Schema of fragments is equivalent to schema of base relation

Partitioning = ( ) Split table by n selection predicates Pi (partitioning predicate) on attributes of R Beware of attribute domain and skew Reconstruction Union of all fragments Bag semantics, but no duplicates across partitions R3 R1 = R2 INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 23 Vertical Fragmentation Column Partitioning into n Fragments Ri PK Complete, reconstructable, but not disjoint (primary key for reconstruction via join) Completeness: each attribute must be included in at least one fragment Partitioning Partitioning via projection

Redundancy of primary key = , ( ) Reconstruction A1 A2 PK A1 PK A2 Natural join over primary key Hybrid horizontal/vertical partitioning w/ w/ INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 24 Derived Horizontal Fragmentation Row Partitioning R into n fragements Ri, with partitioning predicate on S Austria Potentially complete (not guaranteed),

restructable, disjoint Foreign key / primary key relationship determines correctness Partitioning Selection on independent relation S Semi-join with dependent relation R to select partition Ri Reconstruction Equivalent to horizontal partitioning Union of all fragments = INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Table Partitioning 25 Exploiting Table Partitioning Partitioning and query rewriting #1 Manual partitioning and rewriting #2 Automatic rewriting (spec. partitioning) #3 Automatic partitioning and rewriting Example PostgreSQL (#2) CREATE TABLE Squad( JNum INT PRIMARY KEY, Pos CHAR(2) NOT NULL, Name VARCHAR(256) ) PARTITION BY RANGE(JNum); CREATE Squad FOR CREATE Squad FOR CREATE Squad FOR

TABLE Squad10 PARTITION OF VALUES FROM (1) TO (10); TABLE Squad20 PARTITION OF VALUES FROM (10) TO (20); TABLE Squad24 PARTITION OF J# Pos 1 12 22 2 4 5 15 16 17 20 3 6 7 8 9 13 14 18 19 21 23 10 11 GK GK GK DF DF DF DF DF DF DF MF

MF MF MF MF MF MF MF MF MF MF FW FW INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning VALUES FROM TO University (24);of Technology, SS 2019 Matthias(20) Boehm, Graz Name Manuel Neuer Ron-Robert Zieler Roman Weidenfeller Kevin Grokreutz Benedikt Hwedes Mats Hummels Erik Durm Philipp Lahm Per Mertesacker Jrme Boateng Matthias Ginter Sami Khedira Bastian Schweinsteiger Mesut zil Andr Schrrle Thomas Mller Julian Draxler Toni Kroos Mario Gtze Marco Reus Christoph Kramer

Lukas Podolski Miroslav Klose Table Partitioning 26 Exploiting Table Partitioning, cont. Example, cont. JNum>11 SELECT * FROM Squad WHERE JNum > 11 AND JNum < 20 JNum<20 S10 JNum>11 S24 S20 JNum>11 JNum>11 JNum<20 JNum<20 S1 0 in JNum [1,10) S20

JNum in [10,20) JNum<20 S24 JNum in [20,24) INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 JNum>11 S20 Table Partitioning 27 Excursus: Database Cracking Core Idea: Queries trigger physical reorganization (partitioning and indexing) A ACRK 17 3 3 4 8 Q1 : A5 A10 6 2 copy 12

13 4 15 #1 Automatic Partitioning the more we crack, the more we learn 5 2 8 6 [Stratos Idreos, Martin L. Kersten, Stefan Manegold: Database Cracking. CIDR 2007] 5 Q2 : A2 A15 ACRK 2 4 3 8 in-place 6 12 12 15 13 17

13 10 #2 AVL/B-tree over Partitions INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 17 15 2 2 5 10 15 28 Materialized Views INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Materialized Views 29 Overview Materialized Views Core Idea of Materialized Views Identification of frequently re-occuring queries (views) Precompute subquery results once, store and reuse many times The MatView Lifecycle #1 View Selection (automatic selection via advisor tools, approximate algorithms) Materialized Views

#3 View Maintenance (maintenance time and strategy, when and how) #2 View Usage (transparent query rewrite for full/partial matches) INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Materialized Views 30 View Selection and Usage Motivation Shared subexpressions very common in analytical workloads Ex. Microsofts Analytics Clusters #1 View Selection Exact view selection (query containment) is NP-hard Heuristics, greedy and approximate algorithms [Alekh Jindal, Konstantinos Karanasos, Sriram Rao, Hiren Patel: Selecting Subexpressions to Materialize at Datacenter Scale. PVLDB 2018] [Leonardo Weiss Ferreira Chaves, Erik Buchmann, Fabian Hueske, Klemens Boehm: Towards materialized view selection for distributed databases. EDBT 2009] #2 View Usage Given query and set of materialized view, decide which views to use and rewrite the query for produce correct results Generation INF.01014UF Databases / 706.004plans Databases 1 07 Physical Design and Tuning of compensation Matthias Boehm, Graz University of Technology, SS 2019

Materialized Views 31 View Maintenance When? Materialized view creates redundancy Need for #3 View Maintenance Eager Maintenance (writer pays) Immediate refresh: updates are directly handled (consistent view) On Commit refresh: updates are forwarded at end of successful TXs Deferred Maintenance (reader pays) Maintenance on explicit user request Potentially inconsistent base tables and views Lazy Maintenance (async/reader pays) Same guarantees as eager maintenance Defer maintenance until free cycles or view [Jingren Zhou, Per-kefor Larson, Hichamand queries) required (invisible updates G. Elmongui: Lazy Maintenance of Materialized Views. VLDB 2007] INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 Materialized Views 32 View Maintenance How? Incremental Maintenance Propagate: Compute required updates Apply: apply collected updates to the view Global Net Delta R Local View Delta VL

77 Apply Delta VA SUM2 A SUM + NULL 12 NULL 12 107 119 +X 3 X 3 30 Update NULL Update 9 Z 9

NULL 33 A +X 3 + NULL 3 +Z 9 +X 3 Incremental Propagate 30 SUM SUM 9 Super Delta VS 107 A A +Z

Y SUM SUM B 9 VG A SELECT A, SUM(B) NULL FROM Sales GROUP BY CUBE(A) X [Global View Delta] A + NULL Example View: +Z X Insert Z Incremental Apply INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 9 Materialized Views 33

Materialized Views in PostgreSQL View Selection Manual definition of materialized view only With or without data View Usage CREATE MATERIALIZED VIEW TopScorer AS SELECT P.Name, Count(*) FROM Players P, Goals G WHERE P.Pid=G.Pid AND G.GOwn=FALSE GROUP BY P.Name ORDER BY Count(*) DESC WITH DATA; REFRESH MATERIALIZED VIEW TopScorer; Manual use of view No automatic query rewriting View Maintenance Manual (deferred) refresh Complete, no incremental maintenance [Yugo Note: Community work on IVM View Nagata: Implementing Incremental Name Count James Rodrguez Thomas Mller Robin van Persie Neymar Lionel Messi Arjen Robben

6 5 4 4 4 3 Maintenance on PostgreSQL, PGConf 2018] INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019 34 Conclusions and Q&A Summary Physical Access Paths: Compression and Index Structures Logical Access Paths: Table Partitioning and Materialized Views Exercise 2 Reminder Submission deadline: Apr 30 May 07 11.59pm Start early (most time consuming of all four exercises) Next Lectures May 6: 08 Query Processing May 13: 09 Transaction Processing and Concurrency INF.01014UF Databases / 706.004 Databases 1 07 Physical Design and Tuning Matthias Boehm, Graz University of Technology, SS 2019

Recently Viewed Presentations

  • Chapter 4 MICROBIAL DISEASES OF THE SKIN

    Chapter 4 MICROBIAL DISEASES OF THE SKIN

    Folliculitis. Staphy. Colonize skin and upper resp. tract of infants within 24 hrs after birth. Invade thru hair follicle- producing folliculitis (form of pimples and pustules)
  • Napoleon Bonaparte - Quia

    Napoleon Bonaparte - Quia

    1769 - 1821 (lived) 1799 - 1815 (ruled France) The Partitioning of Poland Prussia is concerned over Russian expansion into Ottoman lands Prussia suggests partitioning Poland instead Frederick II Catherine the Great Prussia finally joins Brandenburg and Prussian lands Duchy...
  • Medical Surgical Prime Vendor (MSPV) Prime 1 VHA

    Medical Surgical Prime Vendor (MSPV) Prime 1 VHA

    Volume III. Volume II. Volume I . NG-MSPV Requirement. Offerors shall be a VA FSS holder for Schedule 65 and/or 66 by the date and time for receipt of offers/quotations. Late quotes may be accepted at the discretion of the...
  • Effective Care Transitions to and from Acute Care Hospitals ...

    Effective Care Transitions to and from Acute Care Hospitals ...

    The U.S. Department of Health and Human Services, Health Resources and Services Administration developed this module under a contract. Some of the views expressed in this presentation module are solely the opinions of the author(s) and do not necessarily reflect...
  • Chapter 7

    Chapter 7

    • Hall-Petch Equation: Adapted from Fig. 8.14, Callister & Rethwisch 3e. (Fig. 8.14 is from A Textbook of Materials Technology, by Van Vlack, Pearson Education, Inc., Upper Saddle River, NJ.) * • Impurity atoms distort the lattice & generate stress....
  • Academic Stress

    Academic Stress

    possible to predict a child's high school math performance much earlier . than Asian mothers said was possible. American . parents are . satisfied with their . children's mediocre performance, whereas Asian parents express much less satisfaction with their children's...
  • Approved Evaluator Training Provider Application Process Informational Power

    Approved Evaluator Training Provider Application Process Informational Power

    The purpose of approving evaluator training providers on the State Model System or a unique system is to help districts distribute leadership, manage workload and ensure high quality feedback to all educators. State statute and rule allow designees to conduct...
  • www.go3project.com GO3 Project: Enabling Student Scientists to Measure

    www.go3project.com GO3 Project: Enabling Student Scientists to Measure

    What is the GO3 Project? A STEM project for middle and high schools where students measure air pollutants at their schools andshare and discuss their data with other students around the world.. Global Ozone Project