University of Ioannina
In-memory indexing for parallel processing of single and multi-dimensional queries
Abstract
dc:descriptionDatabase Systems are essential for modern applications, providing structured, efficient, and reliable ways to manage data in fields like banking, healthcare, and scientific research. They are designed to handle large amounts of data and answer queries quickly. A key factor in making queries fast is the use of indices. Efficient indexing can significantly improve the speed, credibility, and overall performance of a database. A good index supports fast searches and updates, while having low space requirements. With the advancements in hardware, we can redesign index structures to be faster and more efficient. For example, larger memory capacities allow us to move computations from disk storage to faster in-memory processing. Additionally, the latest processors offer significantly more cores, enhancing parallel computing by distributing tasks across multiple cores to improve performance. These modern hardware components are affordable and found in commodity computers, making them accessible for a wide range of applications. This dissertation examines how in-memory indexing combined with parallel processing techniques can enhance the performance of relational, temporal, and spatial databases. It addresses challenges like managing large-scale data and running complex queries on modern systems. Interval joins are crucial for temporal databases and are also useful in many applications. However, a major challenge in parallel implementations of interval joins is dividing the workload effectively across processor cores. A simple approach is to split the data domain into disjoint partitions and assign the data in each partition to a different core. However, this creates a new problem: when an interval spans multiple stripes, it must be processed by multiple cores, possibly generating duplicate join results. One way to handle duplicates is by using a data structure like a set to store unique results. However, this increases memory usage and slows down query performance because of the extra checks for duplicates. Domain-based partitioning approach divides the data into partitions that can be processed independently and in parallel, maximizing multi-core hardware capabilities. This study introduces three distinct strategies for parallel partitioning applicable to both hash-based and domain-based methods, significantly accelerating partitioning operations by reducing computational overhead and improving scalability. Indexing spatial data is challenging due to their shape and dimensionality. This complexity affects query performance, particularly for spatial intersection joins, which are the most resource-intensive. Like temporal databases, spatial databases also face duplication issues. For example, in a 2D grid, duplicates can occur when spatial objects overlap multiple grid tiles. The most common technique to avoid duplicates is the reference point approach, which reports a result in only one tile of the grid but requires additional computations. This dissertation primarily focuses on non-point data, where duplication issues arise. Our first study focuses on improving the Partition-Based Spatial Join (PBSM) algorithm for in-memory and parallel evaluation of spatial joins. We show how to choose the best partitioning settings based on data statistics to fine-tune the algorithm for specific join inputs. In our second study, we introduce a new secondary partitioning technique for space-oriented partitioning (SOP) indices, such as grids. This technique removes duplicate results during spatial queries by organizing objects within each partition and only accessing classes that do not produce duplicates. This innovation greatly improves the efficiency of grid-based spatial indices for range (disk and rectangle) and intersection joins. Finally, we propose a parallel method that boosts the performance of range queries. Relational databases also face challenges in creating efficient indices. This dissertation focuses only on tree-like indices. One of the most well-known and efficient indexing structures in this domain is the B+-tree, particularly suited for skewed workloads with dynamic data and for supporting range queries. With the rise of machine learning, many learned indices have been introduced. A learned index uses ML models to “learn” the data distribution and predict the location of the search key within a dataset aiming to reduce the space requirements and the memory accesses. The main difference between a traditional B+-tree and a learned index is that learned indices replace inner nodes with machine learning models. We believe that B+-tree are more efficient than learned indices because their query performance is stable and not affected by the data distribution. We also believe that advancements in hardware technology create new opportunities to further improve B-tree performance. Building on the foundational B+-tree structure, this research introduces BS-tree, a new indexing structure designed for main memory and modern hardware. The BS-tree leverages data parallelism and integrates innovative optimizations, offering significant advancements over both traditional B+-tree and emerging learned indices. Key features include a data-parallel branching mechanism implemented using SIMD instructions, a gap management strategy employing duplicate keys to delay splits and reduce data-shifting overhead, and a node compression scheme that minimizes memory usage while maintaining high throughput. In summary, this dissertation provides a comprehensive framework for enhancing the performance of relational, temporal, and spatial databases. Through the integration of in-memory indexing, parallel processing techniques and duplicate avoidance techniques, this dissertation delivers robust, scalable, and efficient solutions for the evolving needs of modern data-intensive applications.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tsitsigkos, Dimitrios
- Τσιτσίγκος, Δημήτριος
Subjects
dc:subject × 18- Δεδομένα εύρους
- Γεωχωρικά δεδομένα
- Σχεσιακά δεδομένα
- Ευρετηρίαση
- Παραλληλοποίηση
- Κύρια μνήμη
- Interval
- Geospatial data
- Relational data
- Indexing
- Parallelization
- Main memory
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Computer science, Hardware and Architecture
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/58214