Project 2: NanoQuery Columnar Mogrifier

Week 1-2: Parquet & SQL Parsing

2-5 hours

Parquet storage & analysis, hand-parsing (data generation already implemented)

Week 3: Joins & SQL

10-12 hours

Hash Join, Sort-Merge Join implementation

Week 4: Query Planning & Execution

10-12 hours

Query optimization, algorithm selection, memory management, query execution

Week 5: Benchmarking

6-8 hours

Performance testing, analysis, final polishing

✅ You CAN Use

• Pandas DataFrames - as data containers only
• NumPy arrays - for efficient array operations
• PyArrow - for Parquet file I/O only
• Python dictionaries - for hash tables
• Python sorting - sorted(), .sort()
• pd.merge() - for final merge step only (see FAQ)
• Basic Python - loops, list comprehensions

❌ You CANNOT Use

• pd.merge() as your entire join algorithm - implement the logic yourself
• Polars - has built-in columnar joins
• DuckDB - complete SQL engine
• SQLite/PostgreSQL - any SQL database
• Apache Arrow compute - has join operations
• Any library that replaces your algorithm design

⚠️ The Rule

You must implement:

• ✅ Hash partitioning logic
• ✅ Memory management
• ✅ Algorithm selection (HPJ vs SMJ)
• ✅ Overall join strategy

# Copy and run the complete data generation code from Ed Colab (no implementation needed)

            

# Read Parquet files into Pandas DataFrames
import pandas as pd
import pyarrow.parquet as pq

songs_df = pd.read_parquet('songs.parquet')
listens_df = pd.read_parquet('listens.parquet', columns=['song_id', 'user_id'])  # Only needed columns
users_df = pd.read_parquet('users.parquet')
            

def parse_sql(query):
    """YOUR TASK: Extract tables, joins, and aggregations"""
    # Parse SQL string to identify:
    # - Tables involved
    # - Join conditions
    # - GROUP BY columns
    # - Aggregation functions
    pass  # Your implementation here

def hash_partition_join(left_df, right_df, join_key):
    """YOUR IMPLEMENTATION - Build hash table and probe"""
    # 1. Hash partition both tables
    # 2. Build hash table from smaller partition
    # 3. Probe with larger partition
    # 4. Return joined results
    return joined_df
    
def sort_merge_join(left_df, right_df, join_key):
    """YOUR IMPLEMENTATION - Sort and merge"""
    # 1. Sort both tables by join key
    # 2. Merge sorted sequences
    # 3. Handle duplicates
    return joined_df

import pyarrow.parquet as pq

def analyze_metadata_before_loading():
    """YOUR TASK: Get table statistics WITHOUT loading data
    
    Hints:
    - Use pq.ParquetFile() to access metadata
    - Extract: num_rows, column names, file sizes
    - DON'T use pd.read_parquet() here - that loads data!
    """
    # TODO: For each table ('songs', 'users', 'listens'):
    #   - Open the Parquet file (but don't load data)
    #   - Extract metadata like row count, columns, sizes
    #   - Store in a dictionary
    pass  # Your implementation here

def plan_query_execution(metadata, parsed_query):
    """YOUR TASK: Use metadata to make smart decisions
    
    Questions to answer:
    - Which table is smallest? Largest?
    - Will a hash table fit in memory?
    - Which columns does the query actually need?
    - What's the optimal join order?
    """
    # TODO: Based on metadata, decide:
    #   1. Join order (smallest first? or different strategy?)
    #   2. Algorithm choice (HPJ if fits in memory, else SMJ)
    #   3. Which columns to load for each table
    pass  # Your implementation here

# After planning, load ONLY what you need:
# Example (you implement the actual logic):
# columns_needed = ['song_id', 'artist']  # From your planning
# df = pd.read_parquet('songs.parquet', columns=columns_needed)

# For 1GB+ datasets, save intermediate joins to avoid recomputation
result1.to_parquet('intermediate_join1.parquet', compression='snappy')

# Can read back if memory constrained
del result1  # Free memory
result1 = pd.read_parquet('intermediate_join1.parquet')

import time

# Benchmark at different scales
# you can use time.time() to measure the time taken for each query and the results.