Dissertation: Efficient Design and Implementation Techniques for Pattern-Based Graph Query Engines
Teaching Assistant: CMU 18-746 Storage Systems (F22), CMKL 18-613 Foundation of Computer Systems (S24)

Selected Coursework: CMU 15-799 Query Optimization (S25), CMU 15-721 Advanced Database Systems (S23), CMU 18-746 Storage Systems (F21), CMU 15-745 Optimizing Compilers (S23), CMU 18-740 Modern Computer Architecture (F22)

Co-Founder of CS-INFINITE, a group of students who initiates passion-based activities for undergraduate students including Code Arcade and Programming Bootcamp.
Selected Coursework: Database Systems, Data Warehousing, Operating Systems, Automata Theory

Abstract

Triangle counting and enumeration are commonly used in real-world applications on directed graphs. However, the performance of triangle counting algorithms is usually benchmarked on undirected graphs. As such, many of these algorithms and formulations are not suitable for identifying the types of directed triangles in directed graphs. In this work, we show how algorithms for counting each type of directed triad (directed triangle) can be formulated using linear algebra. Leveraging the FLAME methodology, we show that provably correct counting and enumeration algorithms for directed triads can be derived from the linear algebraic formulation. These algorithms can be used to either count individual triads or together to count all possible triads. We show that despite being designed for individual use, the combined use of these algorithms yields a speedup of 16.77x to 1122.2x over the implementation in NetworkX, and 0.37x to 33.49x over GraphBLAS implementations using SuiteSparse 7.2 on various workloads from real-world directed graphs.

Abstract

Queries in a graph database are often converted into a sequence of graph operations by a graph query engine. In recent years, it has been recognized that the query engine benefits from using high-performance graph libraries via the GraphBLAS interface to implement time-consuming operations such as graph traversal. However, using GraphBLAS requires explicitly casting data into linear algebra objects and decomposing the query into multiple operations, some of which are expressible by the GraphBLAS. The combination of these two requirements translates into increased memory footprints and additional execution times. In this paper, we show that fusing different stages of the query engines into GraphBLAS calls can reduce the size of the intermediate data generated during the query. Furthermore, by relaxing the semi-ring constraints imposed by GraphBLAS, more aggressive fusions of the stages can be performed. We show a speedup of up to 1235.89x (8.82x on geometric average) relative to an open-source graph query engine using GraphBLAS (i.e. RedisGraph) for processing undirected subgraph enumeration queries.

Semester Offered: Spring 2024, Spring 2025, Spring 2026
Topics include data persistence, database management systems, data models (focused on the Codd's Relational model), query languages (focused on SQL), data organization, storage model (NSM, DSM, PAX), database indexes, query engine, and concurrency control. DuckDB is used to demonstrate the concepts.

This course aims to discuss challenges from 3Vs (Volume, Variety, Velocity) and techniques to address them. Those techniques include data partitioning/replication, distributed processing, schemaless data models, object storage, data warehouse, data lake, lakehouse, and stream processing. This course uses modern data platforms to demonstrate the concepts (e.g., Spark, MongoDB, Neo4j, DuckLake, Kafka).

Semester Offered: Fall 2024, Spring 2026
Topics include performance, parallelism basics, modern computer architecture (pipelining, superscalar, out-of-order processing, multicore, GPU), instruction-level parallelism (unrolling, separate accumulator, vectorization), and shared-memory parallelism (memory consistency, cache coherency). SIMD, POSIX thread (pthread), and OpenMP are used to demonstrate the concepts.

Semester Offered: Summer 2024, Fall 2025
Topics include problem solving, algorithmic thinking, abstractions, generalization, basic programming, control flow, programming practices (e.g., code reuse, external libraries, code testing). Python is used to demonstrate the concepts.

Topics include multi-disk systems (RAID), internal consistency mechanism, caching, distributed system basics, and distributed file systems (multi-client, multi-server).

Topics include device management, persistent storage (HDD, NAND Flash SSD), file system design and implementation techniques.

Topics include SQL (single-table, multiple-table, DDL, constraints) and logical database design. MySQL and DuckDB are used to demonstrate the concepts.

Topics include data abstraction, machine language, memory hierarchy, code optimization, virtual memory, dynamic memory allocation, network programming, concurrent programming, and thread-level parallelism.

Data transformation tools (like dbt) allow users to provide multiple queries as a dependency graph to perform their tasks. These queries often contain redundant computations, resulting in unnecessary execution time. This project implements an optimizer that rewrites the dependency graph to enhance performance. This optimizer currently employs three optimization heuristics: predicate pushdown, common CTE elimination, and projection pushdown. Additionally, we experimentally incorporate statistics from databases to determine whether to apply these heuristics. To evaluate our optimizer, we synthesize dependency graphs from TPC-H databases. The preliminary results show that the optimizer can significantly improve performance.

A two-phase query optimizer (rule-based then cost-based) based on Apache Calcite (Volcano-style). The optimizer includes applying built-in projection/filter pushdown, query decorrelation. Some additional rules (e.g., FilterDistributiveRule) and the NestedLoopJoin's custom cost computation are (re-)written by myself to improve query plans.

The "just-workable" database management system for visually impaired persons. This is a troll project featured in SHiT8.

A PostgreSQL extension for libfixeypointy, an open-source fast fixed-point decimal library by CMU-DB.

A PostgreSQL foreign data wrapper for accessing columnar file formats (similar to Apache Parquet). The foreign data wrapper includes query optimizations such as projection and predicate pushdown.

An approach to improve elasticity of FlexGen for supporting multi-tenancy environments.

A hybrid cloud/local file system implemented via FUSE aiming to minimize cloud expenses. Key features are deduplication, snapshot, and write-back caching.

An open-source autograding system for programming assignments.

An interpretative, turing-incomplete, and esoteric programming language for seals written in C. Due to its overwhelming stupidity, it won an award at SHT5.

A (possibly legacy) learning management system for CS-KMITL students.