Processing of Theta-Join Queries on MapReduce
Creators: name: Κουμαρέλας, Ιωάννης Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: MapReduce
Σύνδεση-θ
Παράλληλη
Κατανεμημένη Επεξεργασία Δεδομένων
Theta-Join
Distributed Parallel Data Processing

description: In this dissertation we will examine at first the current theoretical background in processing large amounts of data. BigData technologies, that utilize parallel and distributed computing to be more efficient, are differentiating from the standard database technologies, that were used for many years. Large clusters are taking place of supercomputers, as we pass through to the age of Shared Nothing architectures, where commodity hardware is very easy to obtain. In such environments new processing models are taking the place from the old ones, where semi-structured or unstructured data needs to be processed in enormous sizes. MapReduce is such a model, that is currently having a great success in academic and business environments. Combining MapReduce with the popular operator of Theta-Join, which basically merges records (formally tuples) from two tables (formally relations) that satisfy a certain condition, is a great challenge. Based on the current work that has been done in this area, this dissertation tries to improve the efficiency in performing Theta-Joins, by utilizing clustering techniques in the conceptual model of the JoinMatrix, which helps us visualize the possible results of joining two relations. The core of this idea is to change the data partitioning, meaning what data are send from mapper to the reducer nodes, in a way that reduces the communication cost over the network, which usually is the dominating cost in parallel and distributed applications. The big advantage of our idea is that after performing the clustering, if the metrics that are extracted from the partitioning of the JoinMatrix, like how much tuples will be sent over the network or to a specific reducer, do not satisfy us we can either use another technique that improves the metrics we want or not use our idea at all. In the evaluation chapter of this dissertation, we test our approach under different clustering and partitioning techniques on the JoinMatrix, noting improvement in the metrics we are interested in, as well as in the execution time of the experiments in the MapReduce environment.
description: Σε αυτή την πτυχιακή θα εξετάσουμε στην αρχή την τρέχουσα θεωρητική βιβλιογραφία στην επεξεργασία μεγάλων ποσοτήτων δεδομένων. Τεχνολογίες BigData, οι οποίες χρησιμοποιούν παράλληλα και κατανεμημένα υπολογιστικά συστήματα προκειμένου να είναι πιο αποτελεσματικές, διαφοροποιούνται από τις καθιερωμένες τεχνολογίες βάσεων δεδομένων, που χρησιμοποιούνταν για πολλά χρόνια. Μεγάλα clusters υπολογιστών παίρνουν την θέση από τους υπερυπολογιστές, καθώς περνάμε στην εποχή των αρχιτεκτονικών Shared Nothing, όπου το υλικό υπολογιστών είναι εύκολο να αποκτηθεί. Σε τέτοια περιβάλλοντα, νέα υπολογιστικά μοντέλα παίρνουν την θέση από τα παλιά, όπου ημι-δομημένα ή αδόμητα δεδομένα χρειάζεται να επεξεργασθούν σε πολύ μεγάλα μεγέθη. Το MapReduce είναι ένα τέτοιο μοντέλο, που για την ώρα έχει μεγάλη επιτυχία αφού χρησιμοποιείται τόσο σε ακαδημαϊκά και επιχειρησιακά περιβάλλοντα. Ο συνδυασμός του MapReduce με τον δημοφιλή τελεστή του θ-join, ο οποίος ουσιαστικά συγχωνεύει εγγραφές (τυπικά πλειάδες) από δύο πίνακες (τυπικά σχέσεις) που εκπληρούν μια συγκεκριμένη συνθήκη, είναι μια μεγάλη πρόκληση. Βασισμένοι στην τρέχουσα δουλειά που έχει γίνει σε αυτό τον τομέα, αυτή η διπλωματική προσπαθεί να βελτιώσει την αποδοτικότητα στην υλοποίηση των θ-joins, χρησιμοποιώντας τεχνικές ομαδοποίησης στο ιδεατό μοντέλο του JoinMatrix, το οποίο μας βοηθάει να οπτικοποιήσουμε τα πιθανά αποτελέσματα της σύνδεσης δύο σχέσεων. Η βάση αυτής της ιδέας είναι να τροποποιηθεί η διαμέριση των δεδομένων, εννοώντας ποιά δεδομένα στέλνονται από τους κόμβους των mappers στους κόμβους των reducers, με τέτοιο τρόπο ώστε να μειωθεί το επικοινωνιακό κόστος μέσω του δικτύου, το οποίο συνήθως είναι το κυρίαρχο κόστος σε παράλλες και κατανεμημένες εφαρμογές. Το μεγάλο πλεονέκτημα τις ιδέας μας είναι ότι αφού έχει εφαρμοσθεί η ομαδοποίηση, αν οι μετρικές που εξάγονται από την διαμέριση του JoinMatrix πίνακα, όπως πόσες πλειάδες θα σταλθούν μέσω του δικτύου ή σε έναν συγκεκριμένο reducer κόμβο, δεν μας ικανοποιούν τότε μπορούμε είτε να χρησιμοποιήσουμε άλλη τεχνική ομαδοποίησης η οποία βελτιώνει τις μετρικές που θέλουμε ή να μην χρησιμοποιήσουμε καθόλου την ιδέα μας καθόλου. Στο κομμάτι της αξιολόγησης αυτής της διπλωματικής, δοκιμάζουμε την μέθοδό μας με διαφορετικές τεχνικές ομαδοποίησης και τμηματοποίησης του πίνακα JoinMatrix, διαπιστώνοντας βελτίωση στις μετρικές που μας ενδιαφέρουν καθώς και στον χρόνο εκτέλεσης των πειραμάτων στο περιβάλλον του MapReduce.