Big Data analytics has been approached exclusively from a data-parallel perspective, where data are partitioned to multiple workers ‐ threads or separate servers ‐ and model training is executed concurrently over different partitions, under various synchronization schemes that guarantee speedup and or convergence. The dual ‐ Big Model ‐ problem that, surprisingly, has received no attention in database analytics, is how to manage models with millions if not billions of parameters that do not fit in memory. This distinction in model representation changes fundamentally how in-database analytics tasks are carried out. In this paper, we introduce the first secondary storage array-relation dot-product join operator between a set of sparse arrays and a dense relation targeted. The paramount challenge in designing such an operator is how to optimally schedule access to the dense relation based on the sparse non-contiguous entries in the sparse arrays. We prove that this problem is NP-hard and propose a practical solution characterized by two important technical contributions— dynamic batch processing and array reordering. We execute extensive experiments over synthetic and real data that confirm the minimal overhead the operator incurs when sufficient memory is available and the graceful degradation it suffers as memory resources become scarce. Moreover, dot-product join achieves an order of magnitude reduction in execution time for Big Model analytics over alternative in-database solutions.
Dot-product join is a novel type of join operator between an ARRAY attribute and a relation. We are not aware of any other database operator with the same functionality. From a relational perspective, dot-product join is most similar to index join @cite_46 . However, for every vector @math , we have to probe the index on model @math many times. Thus, the number of probes can be several orders of magnitude the size of @math . The proposed techniques are specifically targeted at this scenario. The batched key access join https: dev.mysql.com doc refman 5.6 en bnl-bka-optimization.html in MySQL is identical to our batching optimization applied at vector level. However, it handles a single probe per tuple and its reordering is aimed at generating sequential storage access for @math . Array joins @cite_28 are a new class of join operators for array databases. While it is possible to view dot-product join as an array join operator, the main difference is that we consider a relational system and push the aggregation inside the join. This avoids the materialization of the intermediate join result.
@cite_28 @cite_46
2011129635 1569403765
Science applications are accumulating an ever-increasing amount of multidimensional data. Although some of it can be processed in a relational database, much of it is better suited to array-based engines. As such, it is important to optimize the query processing of these systems. This paper focuses on efficient query processing of join operations within an array database. These engines invariably chunk'' their data into multidimensional tiles that they use to efficiently process spatial queries. As such, traditional relational algorithms need to be substantially modified to take advantage of array tiles. Moreover, most n-dimensional science data is unevenly distributed in array space because its underlying observations rarely follow a uniform pattern. It is crucial that the optimization of array joins be skew-aware. In addition, owing to the scale of science applications, their query processing usually spans multiple nodes. This further complicates the planning of array joins. In this paper, we introduce a join optimization framework that is skew-aware for distributed joins. This optimization consists of two phases. In the first, a logical planner selects the query's algorithm (e.g., merge join), the granularity of the its tiles, and the reorganization operations needed to align the data. The second phase implements this logical plan by assigning tiles to cluster nodes using an analytical cost model. Our experimental results, on both synthetic and real-world data, demonstrate that this optimization framework speeds up array joins by up to 2.5X in comparison to the baseline. From the Publisher: This introduction to database systems offers a readable comprehensive approach with engaging, real-world examplesusers will learn how to successfully plan a database application before building it. The first half of the book provides in-depth coverage of databases from the point of view of the database designer, user, and application programmer, while the second half of the book provides in-depth coverage of databases from the point of view of the DBMS implementor. The first half of the book focuses on database design, database use, and implementation of database applications and database management systemsit covers the latest database standards SQL:1999, SQL PSM, SQL CLI, JDBC, ODL, and XML, with broader coverage of SQL than most other books. The second half of the book focuses on storage structures, query processing, and transaction managementit covers the main techniques in these areas with broader coverage of query optimization than most other books, along with advanced topics including multidimensional and bitmap indexes, distributed transactions, and information integration techniques. A professional reference for database designers, users, and application programmers.