View
106
Download
0
Category
Preview:
Citation preview
OLAPOLAPÉquipe:
Johanne LavoieGiovanni Malizia
Présenté le 26 avril 2004
Prof. : Robert GodinCours : INF7115Session : Hiver 2004
2
Plan de présentationPlan de présentation Survol Problématiques Approches OLAP Amélioration de la performance Processus de sélection des vues à matérialiser Hiérarchies des attributs Contexte étudié
Cadre du treillis Algorithmes glouton Modèle de coût
Produits commerciaux Conclusion Références
3
SurvolSurvol
Introduit en 1993 par E.F. Codd
Performance inacceptable sur un environnement opérationnel
Utilisation pour l’aide à la décisionUtilisateurs OLAP autonomes
Différents types : MOLAP, ROLAP, HOLAP, DOLAPÉtroitement lié aux entrepôts de données
4
DéfisDéfis
Croissance constante des donnéesComplexité des requêtesTemps de réponseCoûts
Le dilemmeQuelles vues doit-on matérialiser pour
optimiser le temps de réponse, minimiser l’espace disque occupé et
diminuer les coûts ?
5
Approche MOLAPApproche MOLAP
Les données sont nettoyées, agrégées dans des dimensions
multiples Les données sont emmagasinées dans des rangées
multidimensionnelles Pré compilation des rangées d'organisation et de données qui
peuvent être consultées directement et plus rapidement Joints déjà fait Vue multidimensionnelle directe des données Facilité d'utilisation
Crystal decisions, « Compound OLAP. Crystal decisions, « Compound OLAP. An OLAP Architecture for the Real World », 2001, p.1-15An OLAP Architecture for the Real World », 2001, p.1-15
6
Approche ROLAPApproche ROLAP
Données volatiles Données agrégées et emmagasinées avec les bases de
données relationnelles Manipulation de requêtes complexes Interface multidimensionnelle aux données relationnelles Intégration possible à des BDs relationnelles existantes Jointures au moment de la requête Requête utilisant SQL
Crystal decisions, « Compound OLAP. Crystal decisions, « Compound OLAP. An OLAP Architecture for the Real World », 2001, p.1-15An OLAP Architecture for the Real World », 2001, p.1-15
7
Amélioration de la performanceAmélioration de la performance
Optimisateurs de requêtesTechniques d’évaluation de requête
Stratégies d’indexation Index « bit-map » Index de jointures
Alternatives pour la matérialisation des vues (cubes) Toutes les vues Aucune vue Quelques vues (une partie du cube)
8
Processus de sélection des vues à matérialiserProcessus de sélection des vues à matérialiser
Bellatreche, Ladjel, Techniques d’optimisation des requêtes dans les data warehouses, Laboratoire d’Informatique Scientifique et Industrielle, 2003, http://www.lisi.ensma.fr/
Ensemble des requêtes
Algorithme de sélection
Vues candidates
Contrainte de ressource Modèle de coût
Vues matérialiséessélectionnées
9
Hiérarchies des attributsHiérarchies des attributs
Deux types d’opérations couramment utilisées pendant les requêtes :
Le pliage (roll up) et le dépliage (drill down)
X
X
Jour
Semaine
Aucun
Mois
Année
Période
AnnéeAnnéeJan. Avr. Déc.Jan. Avr. Déc.
Jours du mois (1-31)Jours du mois (1-31)
Semaines du mois (1-5)Semaines du mois (1-5)Jours du mois (1-31)Jours du mois (1-31)
Harinarayan, Venky, Rajaraman, Anand, Ullman, Jeffrey, D., « Implementing Data Cubes Efficiently », Proceedings of the 1996 ACM SIGMOD international conference on Management of Data, p.205-216, ISSN:0163-5808
10
Modèle de coûtModèle de coût
11 22 33
Taille / Temps
Cadre de treillis Cadre de treillis pfc 6M
pc 6M
p 0,2M f 0,1M
fc 6M
c 0,1M
pf 0,8M
none 1
Vues possibles
Algorithme gloutonAlgorithme glouton
Espace / Temps
Contexte étudiéContexte étudié
11
Cadre de treillis Cadre de treillis pfc 6M
pc 6M
p 0,2M f 0,1M
fc 6M
c 0,1M
pf 0,8M
none 1
Vues possibles
Cadre de treillisCadre de treillis
12
3. Pièce, fournisseur (0,8M)
Huit (8) vues possibles
Treillis des 8 vues TPC-DTreillis des 8 vues TPC-D
pfc 6M
pc 6M
p 0,2M f 0,1M
fc 6M
c 0,1M
pf 0,8M
none 1
p = pièce, f = fournisseur, c = clientTotal: 19.1M
1. Pièce, fournisseur, client (6M)2. Pièce, client (6M)
5. Pièce (0,2M)6. Fournisseur (0,01M)7. Client (0,1M)8. None (1)
4. Fournisseur, client (6M)
Total: 7.1M
13
Treillis composé de dimensions hiérarchiquesTreillis composé de dimensions hiérarchiques
Combinaison de deux dimensions hiérarchiques
cp 6M ct 5,99 M
s 50 none 1
c = clientn = par paysp = pièces = taillet = type de pièce
ClientClient
PaysPays
AucunAucun
PiècePièce
TailleTaille
AucunAucun
TypeType++
Harinarayan, Venky, Rajaraman, Anand, Ullman, Jeffrey, D., « Implementing Data Cubes Efficiently », Proceedings of the 1996 ACM SIGMOD international conference on Management of Data, p.205-216, ISSN:0163-5808
14
Avantages du treillis composéAvantages du treillis composé
Fournit un cadre pour évaluer les dimensions hiérarchiques
Améliore la modélisation des requêtes communes entre les utilisateurs
Indique dans quel ordre matérialiser les vues
Réduction de l’accès aux données sources
15
Modèle de coûtModèle de coût
11 22 33
Taille / Temps
Cadre de treillis Cadre de treillis pfc 6M
pc 6M
p 0,2M f 0,1M
fc 6M
c 0,1M
pf 0,8M
none 1
Vues possibles
Algorithme gloutonAlgorithme glouton
Espace / Temps
Contexte étudiéContexte étudié
16
Algorithme gloutonAlgorithme glouton
Espace / Temps
Algorithme gloutonAlgorithme glouton
17
Déroulement de l’algorithme glouton (greedy)Déroulement de l’algorithme glouton (greedy)
La vue haut niveau est matérialisée
Sélection des vues additionnelles à matérialiser, une à une, jusqu’à l’atteinte du coût total choisie
À chaque étape, choisir la vue non matérialisée, avec les
bénéfices les plus avantageux
18
Résultats de l’algorithme gloutonRésultats de l’algorithme gloutonNuméro Sélection Bénéfice Temps total Espace total
1 c p infinit 72M 6M2 n s 24M 48M 6M3 n t 12M 36M 6M4 c 5,9M 30,1M 6,1M5 p 5,8M 24,3M 6,3M6 c s 1M 23,3M 11,3M7 n p 1M 22,3M 16,3M8 c t 0,01M 22,3M 22,3M9 t petit 22,3M 22,3M10 n petit 22,3M 22,3M11 s petit 22,3M 22,3M12 aucune petit 22,3M 22,3M
Nombre de vues
Espace
Temps
cp 6M ct 5,99 M
s 50 none 1
c = clientn = par paysp = pièces = taillet = type de pièce
19
Contexte étudiéContexte étudié
Modèle de coûtModèle de coût
11 22 33
Taille / Temps
Cadre de treillis Cadre de treillis pfc 6M
pc 6M
p 0,2M f 0,1M
fc 6M
c 0,1M
pf 0,8M
none 1
Vues possibles
Algorithme gloutonAlgorithme glouton
Espace / Temps
20
Modèle de CoûtModèle de Coût
Taille / Temps
11 22 33
Modèle de CoûtModèle de Coût
21
Huit (8) vues possibles1. Pièce, fournisseur, client (6M)2. Pièce, client (6M)
5. Pièce (0,2M)6. Fournisseur (0,01M)7. Client (0,1M)8. None (1)
4. Fournisseur, client (6M)3. Pièce, fournisseur (0,8M)
Rappel: Treillis des 8 vues TPC-DRappel: Treillis des 8 vues TPC-D
22
Modèle linéaire de coût Modèle linéaire de coût T = m * S + c
Source Taille (S) Temps (sec.) Ratio
Une cellule seulement 1 2,07 Non applicable
6. Vue – fournisseur 10 000 2,38 ,000031
3. Vue – pièce, fournisseur 800 000 20,77 ,000023
1. Vue – pièce, fournisseur, client 6 000 000 226,23 ,000037
Temps de réponse de la requête par rapport à la taille de la vue
(T) temps d’exécution (S) taille d’une vue (c) coût fixe (m) ratio du temps de requête/taille de la vue
Harinarayan, Venky, Rajaraman, Anand, Ullman, Jeffrey, D., « Implementing Data Cubes Efficiently », Proceedings of the 1996 ACM SIGMOD international conference on Management of Data, p.205-216, ISSN:0163-5808
2,38 – 2,07 = (0,31)/10000 = ,000031
23
Produits commerciauxProduits commerciaux
24
CatégorisationCatégorisation
http://www.olapreport.com/Architectures.htm#Matrixhttp://www.olapreport.com/Architectures.htm#Matrix
ROLAP MOLAP DOLAPMulti-pass SQL Cartesis Magnitude MicroStrategyMultidimensional server engine Crystal Holos (ROLAP mode) SAS CFO Vision
Hyperion Essbase Crystal HolosLongview Khalix Comshare DecisionSpeedware Media/MR Hyperion Essbase
Microsoft Analysis Services Oracle ExpressOracle Express (ROLAP mode) Oracle OLAP Option AWOracle OLAP Option (ROLAP mode)GentiaPilot Analysis Server Microsoft Analysis ServicesWhiteLight PowerPlay Enterprise Server
Pilot Analysis ServerApplix TM1
Client multidimensional engine Oracle Discoverer Comshare FDC Hyperion IntelligenceDimensional Insight BusinessObjectsHyperion Enterprise Cognos PowerPlayHyperion Pillar Personal Express
TM1 Perspectives
25
Tendance de part du marchéTendance de part du marché
http://www.olapreport.com/market.htmhttp://www.olapreport.com/market.htm
26
Résultats TPCRésultats TPC
Résultats des essais à 1,000 GB
Réf.: www.tpc.org
Produit Version QphH Prix / QphH
Oracle Enterprise Edition v9.2.0.2.0
34,492 141.00 $ US
IBM DB2 UDB 7.2 22,361 253.00 $ US
Microsoft SQL Server
2000
Server 2003 Enterprise Edition
64 bit
5,199 120.00 $ US
27
ConclusionConclusion
La distribution de l’espace disque entre les vues et les index
L’algorithme glouton considère seulement la contrainte de l’espace disque et exclut l’utilisation des index par les vues
Le découplage de la maintenance des vues dans l’entrepôt de données par rapport aux mises à jour constantes des données sources
28
RéférencesRéférencesUllman, Jeffrey D., « Efficient Implementation of Data Cubes Via Materialized Views », KDD Proceedings ,
1996, p.386-388
Harinarayan, Venky, Rajaraman, Anand, Ullman, Jeffrey, D., « Implementing Data Cubes Efficiently », Proceedings of the 1996 ACM SIGMOD international conference on Management of Data , p.205-216, ISSN:0163-5808
Gupta, Ashish, Mumick, Inderpal Singh, Ross, Kenneth A., « Adapting Materialized Views after Redefinition », ACM SIGMOD Conference, 1995, p.211-222
Goldstein, Jonathan, Larson, Per-Åke, « Optimizing Queries Using Materialized Views: A Practical, Scalable Solution », ACM SIGMOD Conference, 2001, Vol. 2 No. 3, 1999, p.331-342
Gupta, Himanshu, « Selection of Views to Materialized in a Data Warehouse », Proceedings of 23rd VLDB Conference, Athens, Greece 1997, p.1-15
Gupta, Himanshu, Mumick, Inderpal Singh, « Selection of Views to Materialize Under a Maintenance Cost Constraint », Proceeding of the 7th International Conference on Database Theory , 1999, p. 453-470
Bellatreche, Ladjel, Techniques d’optimisation des requêtes dans les data warehouses, Laboratoire d’Informatique Scientifique et Industrielle, 2003, http://www.lisi.ensma.fr/
29
30
Diapositives d'appuiDiapositives d'appui
31
Autres algorithmesAutres algorithmes
Algorithme Description
ECA (Eager CompensatingAlgorithm)
Adresse le découplage de vues avec les données sources
VRDS (View Relevance DrivenSelection)
Sélection d’un ensemble de vues à matérialiser dans uncontexte espace / coûts
ILGA (Inner Level GreedyAlgorithm)
Optimisation de GA initiale par une comparaison itérativedes combinaisons possibles des vues et des indexes
ITGA (Inverted Tree GreedyAlgorithm)
Utilise un arbre inversé pour le comparer au GA initiale etl’optimiser
GIA (Greedy InterchangeAlgorithm)
Utilise la solution généré par le GA et l’optimise enremplaçant une à une la vue déjà sélectionnée par une vuepas encore sélectionné
32
Tendances de rechercheTendances de recherche
OLAP Stream Data Cube Iceberg Cube-H Cube Étoile (Star cubing)
33
Techniques d’indexagesTechniques d’indexages
Produit Arbre B Bitmap Jointure
Oracle 9i Oui Oui Oui
IBM DB2 Universal Database 7.2 Oui Oui Oui
MySQL 4.0 Oui Non Oui
Sybase Adaptive Server Enterprise 12.5 Oui Non Non
Microsoft SQL Server 2000 SP2 Oui Non Oui
http://common.ziffdavisinternet.com/download/0/1387/ExtendedFeatures_SQL.xlshttp://common.ziffdavisinternet.com/download/0/1387/ExtendedFeatures_SQL.xls
Recommended