MonetDB/XQuery (2/2): High-Performance, Purely Relational ... · 13 Stefan.Manegold@CWI.nl...

ADT 2010ADT 2010

MonetDB/XQuery (2/2):MonetDB/XQuery (2/2):

High-Performance, Purely Relational High-Performance, Purely Relational

XQuery ProcessingXQuery Processing

http://pathfinder-xquery.org/http://pathfinder-xquery.org/

http://monetdb-xquery.org/http://monetdb-xquery.org/

Stefan ManegoldStefan.Manegold@cwi.nl

http://www.cwi.nl/~manegold/

Stefan.Manegold@CWI.nl MonetDB/XQuery ADT 2010

XPath evaluation (SQL)XPath evaluation (SQL)

Example query: /descendant::open_auction[./bidder]/annotation

SELECT DISTINCT a.pre FROM doc r, doc oa, doc b, doc a WHERE r.pre=0 AND oa.pre > r.pre AND oa.post < r.post AND oa.name = “open_auction” AND oa.kind = “elem” AND b.pre > oa.pre AND b.post < oa.post AND b.level = oa.level + 1 AND b.name = “bidder” AND b.kind < “elem” AND a.pre > oa.pre AND a.post < oa.post AND a.level = oa.level + 1 AND a.name = “annotation” AND a.kind = “elem” ORDER BY a.pre

• (potentially?) expensive joins due to range predicates• (potentially?) expensive duplicate elimination

<- descendant

} child

Staircase Join Staircase Join [VLDB03][VLDB03]

document

List of context nodes

pre|post are not random numbers: =>exploit the tree properties encoded in them

document

seek scan skip seek scan skip ...

• skipping: avoid touching node ranges that cannot contain results

Generate a duplicate-free result in document order • pruning: reduce the context set a-priori• partitioning: single sequential pass over the document

document

seek scan skip seek scan skip ...

Example:

(c1,c2)/descendant:*

SELECT DISTINCT doc.pre FROM c, doc WHERE doc.pre > c.pre AND doc.post < c.post

Avoid comparing large chunks of the document table.

Staircase Join: SkippingStaircase Join: Skipping

Example:

(c1,c2,c3,c4)/ancestor:*

SELECT DISTINCT doc.pre FROM c, doc WHERE doc.pre < c.pre AND doc.post > c.post

Eliminate: c1, c3

Keep: c2, c4

Staircase Join: PruningStaircase Join: Pruning

Example:

(c1,c2,c3)/ancestor:*

SELECT DISTINCT doc.preFROM c, doc WHERE doc.pre < c.pre AND doc.post > c.post

Single-pass algorithm that avoids generating duplicates

Staircase Join: PartitioningStaircase Join: Partitioning

Example:

(c1,c2,c3)/ancestor:*

SELECT DISTINCT doc.preFROM c, doc WHERE doc.pre < c.pre AND doc.post > c.post

Single-pass algorithm that avoids generating duplicates

Staircase Join: PartitioningStaircase Join: Partitioning

ScheduleSchedule•So far:

•RDBMS back-end support for XML/XQuery (1/2):

•Document Representation (XPath Accelerator, Pre/Post

plane)

•XPath navigation (Staircase Join)

ScheduleSchedule•So far

•Document Representation (XPath Accelerator, Pre/Post

plane)

•XPath navigation (Staircase Join)

•Now:

•XQuery to Relational Algebra Compiler:

•Item- & Sequence- Representation

•Efficient FLWoR Evaluation (Loop-Lifting)

•Optimization

•Updateable Document Representation

Source Language: XQuery CoreSource Language: XQuery Core

Target Language: Relational AlgebraTarget Language: Relational Algebra

• sequence = table of items• add pos column for maintaining order• ignore polymorphism for the moment

Sequence RepresentationSequence Representation

■ Item sequences, sequence order

(10, “x”, <a/>, 10) →

Node Atom Item1 NULL 10 1 10

2 NULL “x” → 2 “X”3 NULL 34 NULL 10 4 10

Pos Pos

pre(a) pre(a)

■ Problems:

● Polymorphic columns

● Redundant storage

● Copy overhead (especially with strings)

Sequence RepresentationSequence Representation

■ Item sequences, sequence order

(10, “x”, <a/>, 10) →

Node Atom Item1 NULL 10 1 10

2 NULL “x” → 2 “X”3 NULL 34 NULL 10 4 10

Pos Pos

pre(a) pre(a)

Pos Item Pos Item Kind str_values1 10 1 Int “x”2 “X” → 2 Str3 pre(a) 3 Node int_values4 10 4 Int 10

1@0 1@01@00@01@0 1@0

Item RepresentationItem Representation

IterationsIterations

Loop-LiftingLoop-Lifting

Deriving Deriving looploop

Nested ScopesNested Scopes

Loop-liftingLoop-lifting

Full ExampleFull Example

join calc project

XQuery On SQL HostsXQuery On SQL Hosts [VLDB04][VLDB04]

XQuery Construct

sequence construction

if-then-else

for-loops

calculations

list functions, e.g. fn:first()

element construction

XPath steps

Relational Mapping

A union B

select(A=true,B) union select(A=false,C)

cartesian product

project(A,x=expr(Y1,..Yn))

select(A,pos=1)

updates in temporary tables

staircase-join

XMark Query 8XMark Query 8let $auction := doc("auctions.xml")return for $p in $auction/site/people/person let $a := for $t in $auction/site/ closed_auctions/closed_auction where $t/buyer/@person = $p/@id return $treturn <item person="{$p/name/text()}"> {count($a)} </item>

Peephole OptimizationPeephole Optimization[Grust, XIME-P 2005][Grust, XIME-P 2005]

Peephole OptimizationPeephole OptimizationPeephole OptimizationPeephole Optimization[Grust, XIME-P 2005][Grust, XIME-P 2005]

• Plan simplification

• Sort Avoidance

generated by DENSE RANK pos ORDER BY pos PARTITION BY iter

by tracking secondary ordering properties [pos|iter], [Wang&Cherniack, VLDB’03]

C43B23A13Z102Y51X41

itempositer

[iter,pos]

Peephole OptimizationPeephole Optimization[Boncz et al., SIGMOD 2006][Boncz et al., SIGMOD 2006]

• Sort Avoidance

C43B23A13Z102Y51X41

itempositer

C33B23A13Z12Y21X11

itempositer

[iter,pos]

Peephole OptimizationPeephole OptimizationPeephole OptimizationPeephole Optimization[Boncz et al., SIGMOD 2006][Boncz et al., SIGMOD 2006]

• Sort Avoidance

hash-based (streaming) DENSE_RANK

C43B23Y51A13Z102X41

itempositer

C33B23Y21A13Z12X11

itempositer

[pos|iter]

• Sort Avoidance

• Sort Reduction

if [iter,item] order is required, and [iter] only is present

use a refine-sort rather than a full sort.

pipelinable sort

• Sort Avoidance

by tracking secondary ordering properties [item|iter], [Wang&Cherniack, VLDB’03]

• Sort Reduction

if [iter,item] order is required, and [iter] only is present

use a refine-sort rather than a full sort.

pipelinable sort

• Join Detection

detect cartesian products as multi-valued dependencies

in the precense of a theta-selection theta-join

Loop-lifted XPath StepsLoop-lifted XPath Steps

Many algorithms have been proposed & studied for XPath evaluation:• Dataguide based, • Structural Join,• Staircase Join, • Holistic Twig Join

IN: sequence of context nodes in (doc order)OUT: sequence of document nodes (unique, in doc order)

Loop-lifted XPath StepsLoop-lifted XPath Steps

In XQuery, expressions generally occur inside FLWR blocks, i.e. inside a for-loop

for $x in doc()//employee $x/ancestor::department

Choice:• call XPath algorithm N times, accessing document and index structures N times.• use a loop-lifted algorithm:

IN: for each iteration, a sequence of context nodesOUT: for each iteration, a sequence of document nodes (per iteration unique, in doc order)

Staircase joinStaircase join

document

Loop-lifted staircase joinLoop-lifted staircase join

document document

List of context nodes Active stack

Multiple lists of context nodes

Adapt:

pruning, partitioning and skipping rules

to correctly deal with multiple context sets

Loop-lifted staircase joinLoop-lifted staircase join

Results on the 20 XMark queries:

Performance EvaluationPerformance Evaluation

Extensive performance Evaluation on XMark• data sizes 110KB, 1MB, 11MB, 110MB, 1.1GB, 11GB• MonetDB/XQuery, Galax0.6, X-Hive 6.0, Berkeley DB XML 2.0, eXisT• 8GB RAM

Extensive XMark performance Literature Overview• IPSI-XQ v1.1.1b , Dynamic Interval Encoding , Kweelt , QuiP, FluX , TurboXPath, Timber, Qizx/Open (Version 0.4/p1), Saxon (Version 8.0), BEA/XQRL, VX• Crude comparison (normalized by CPU SPECint)

XMark BenchmarkXMark Benchmark1MB XML 1GB XML

X-Hive

BerkeleyDB XML

• http://monetdb.cwi.nl/XQuery/Benchmark/

• S. Manegold: “An Empirical Evaluation of XQuery Processors”, Information Systems, 33:203-220, April 2008. http://repository.cwi.nl/search/fullrecord.php?publnr=13811

More Benchmarks & Performance Results?More Benchmarks & Performance Results?

• S. Manegold: “An Empirical Evaluation of XQuery Processors”, Information Systems, 33:203-220, April 2008. http://www.cwi.nl/htbin/ins1/publications?request=abstract&key=Ma:IS:08

MonetDB/XQuery (2/2): High-Performance, Purely Relational ... · 13 Stefan.Manegold@CWI.nl...

Documents

Cone - INSILVISÓ INSILVIS, 2007 - INSILVIS Communication - ITALFORMS Systems The images are purely illustrative: forms and colors can differ sensitively form the originals on account

XML - Semaine 5 · XML-Semaine5 XQuery Présentation XQueryestunlangagepermettantdetraiterundocumentXML. CommeXSLT,ilproduitundocumentensortie. Lesinstructions XQueryseplacentaumilieud

Débats économiques et financiers - Banque de France · 2017-11-03 · systemic risk, then measuring it, purely statistical indicators may also be useful: in the absence of a canonical

FlashCam: A camera concept and design for the Cherenkov ... · FlashCam is a simple and straightforward concept of an electronics system for use in CTA cameras. It is based purely

Architecture Hadoop - Chewbii.comchewbii.com/wp-content/uploads/2016/10/handout_Hadoop.pdf · ESILV : Hadoop Vertigo N. Travers RDBMS vs Hadoop RDBMS • Giga octets de données •

1 XSLT - XQuerybilasco/labd/labd-11/ex22015.pdf · 1 XSLT - XQuery OnconsidèreleﬁchierXML denomreseau.xml décrivantunréseauferré.Cettedonnéecontient

XQuery - Sébastien Laborieslaborie.perso.univ-pau.fr/images/Cours-XML/cours5-xquery.pdf · XQuery:)présentation 11 • Les BD XML –modèle : o BD relationnelle Collection de relations

NoSQL - RMLL2011.rmll.info/IMG/pdf/nosql.pdf · 2011-07-12 · En résumé RDBMS Enregistrements de petite taille, dôtés de relations bien définies et normalisées Requêtes pouvant

XML Technologies - ksi.mff.cuni.czXML Technologies XML DB XML data XML Schema native relational XML DB parsing validation SAX DOM DTD RELAX NG Schematron StAX LINQ querying XPath XQuery

ETUIX UN CONCEPT ABSOLUMENT FABULEUX! IL FALLAIT …€¦ · ETUIX was a solution for companies to re-propose their advertising campaign through unique objects, with a purely B2B

Corrosion-cavitation-erosion: surface morphology study of ...The erosion is considered as a purely mechanical phenomenon, in which the metal is removed or mechanically destroyed, so

SemWeb : Interrogation sémantique du web avec XQuery fileCEDRIC / CNAM, équipe VERTIGO, Paris LINA, équipe Bases de données et Recherche d’information, Nantes LIP6, équipe Bases

РЕЛЯЦИОННАЯ СУБД - Linter SQL RDBMS · компания РЕЛЭКС не гарантирует, что документ не содержит ошибок и пропусков,

1 RDBMS 2 徹・底・研・究...DB Magazine 2010 January の文字コード 1 RDBMS徹・底・研・究文字コードの基礎 SQL Serverで使用できる文字コードを説明

r · 2021. 1. 27. · Notification for walk-in-interview for engagement Of Guest Faculty (On purely temporary basis) No. 102/2/2019-Estt/ Dated: 27-01-2021 An online walk-in-interview

Louis Roederer Brut Premier NV - Purely Maldives