Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (4 results)

  • Thesis
  • Peer Reviewed
UC Riverside Electronic Theses and Dissertations (2018)

The past decade has witnessed the proliferation of new ways to ingest, store, index, and query data. This explosion was driven by the needs of the modern applications, including social media, popular web services, and IoT sensors, characterized by high volumes and a rapid rate of incoming data. To cope with such high arrival rates, modern systems rely on the Log-Structured Merge Tree (LSM) storage model that uses sequential I/O instead of in-place updates. In addition to handling incoming data, LSM-based systems should provide useful analytics for their users, which in turn requires accurate statistics.

The first contribution of this thesis is developing a lightweight approach to collect and maintain concise statistical representations of the data in LSM-based systems so that it can be later used to drive cost-based optimizer decisions. In particular, we consider two problems, collecting statistics on indexed columns (which orders the stream of records based on the index key), as well as on non-indexed (unordered) columns. For each case, appropriate statistical summaries are considered so that the overall overhead on the system’s critical path remains low, thus not affecting the ingestion process.

Recent hardware trends such as growing main memory capacity, stagnating CPU speeds, and increasing usage of parallel architectures have also influenced the design of data processing systems. These advances in hardware allow analyzing large datasets entirely in memory, which requires

specialized algorithms to process memory-resident data. Apart from the algorithms implemented on traditional CPU architectures, implementations leveraging fine-grained hardware multithreading on FPGAs have been recently proposed. However, up to this moment, there has been a lack of studies directly comparing the performance of these two approaches.

The second part of the thesis is devoted to a comparative study of common analytical operations (joins, aggregations, selections) for in-memory workloads using both multicore CPU and hardware multithreading approaches. We present a thorough experimental evaluation and show that implementations that use hardware multithreading outperform state-of-the-art CPU-based algorithms in terms of raw throughput in many cases while achieving much better memory bandwidth utilization.

    Cover page: Query Processing and Cardinality Estimation in Modern Database SystemsCreative Commons 'BY-ND' version 4.0 license
    • Article
    • Peer Reviewed
    UC Riverside Previously Published Works (2019)
    Inexpensive DRAMs have created new opportunities for in-memory data analytics. However, the major bottleneck in such systems is high memory access latency. Traditionally, this problem is solved with large cache hierarchies that only benefit regular applications. Alternatively, many data-intensive applications exhibit irregular behavior. Hardware multithreading can better cope with high latency seen in such applications. This article implements a multithreaded prototype (MTP) on FPGAs for the relational selection operator that exhibits control flow irregularity. On a standard TPC-H query evaluation, MTP achieves a bandwidth utilization of 83%, while the CPU and the GPU implementations achieve 61% and 64%, respectively. Besides being bandwidth efficient, MTP is also 14.2× and 4.2× more power efficient than CPU and GPU, respectively.
      Cover page: Accelerating In-Memory Database Selections Using Latency Masking Hardware Threads
      • Article
      • Peer Reviewed
      UC Riverside Previously Published Works (2016)
      Recent trends in hardware have dramatically dropped the price of RAM and shifted focus from systems operating on disk-resident data to in-memory solutions. In this environment high memory access latency, also known as memory wall, becomes the biggest data processing bottleneck. Traditional CPU-based architectures solved this problem by introducing large cache hierarchies. However algorithms which experience poor locality can limit the benefits of caching. In turn, hardware multithreading provides a generic solution that does not rely on algorithm-specific locality properties. In this paper we present an FPGA-accelerated implementation of in-memory group-by hash aggregation. Our design relies on hardware multithreading to efficiently mask long memory access latency by implementing a custom operation datapath on FPGA. We propose using CAMs (Content Addressable Memories) as a mechanism of synchronization and local pre-aggregation. To the best of our knowledge this is the first work, which uses CAMs as a synchronizing cache. We evaluate aggregation throughput against the state-of-the-art multithreaded software implementations and demonstrate that the FPGA-accelerated approach significantly outperforms them on large grouping key cardinalities and yields speedup up to 10x.
        Cover page: FPGA-accelerated group-by aggregation using synchronizing caches
        • Article
        • Peer Reviewed
        UC Riverside Previously Published Works (2015)
        The wide and increasing availability of collected data in the form of trajectories has led to research advances in behavioral aspects of the monitored subjects (e.g., wild animals, people, and vehicles). Using trajectory data harvested by devices, such as GPS, RFID and mobile devices, complex pattern queries can be posed to select trajectories based on specific events of interest. In this paper, we present a study on FPGA- and GPU-based architectures processing complex patterns on streams of spatio-temporal data. Complex patterns are described as regular expressions over a spatial alphabet that can be implicitly or explicitly anchored to the time domain. More importantly, variables can be used to substantially enhance the flexibility and expressive power of pattern queries. Here we explore the challenges in handling several constructs of the assumed pattern query language, with a study on the trade-offs between expressiveness, scalability and matching accuracy. We show an extensive performance evaluation where FPGA and GPU setups outperform the current state-of-the-art (single-threaded) CPU-based approaches, by over three orders of magnitude for FPGAs (for expressive queries) and up to two orders of magnitude for certain datasets on GPUs (and in some cases slowdown). Unlike software-based approaches, the performance of the proposed FPGA and GPU solutions is only minimally affected by the increased pattern complexity.
          Top