I work with Prof. Neha Makhija at the DREAM Lab on package queries — a class of database problems where getting the exact answer means solving a hard optimization problem. My job is to find out, with experiments, exactly when the cheap shortcut gives the right answer and when it quietly fails.
A normal database query asks for rows one at a time: "show me every stock under $50." A package query asks for a set of rows that work together: "build me a portfolio under a $10,000 budget that maximizes expected return." That's no longer a lookup — it's a combinatorial optimization problem, and the number of possible sets explodes exponentially. Solving it exactly means integer linear programming (ILP), which can be brutally slow. Relaxing it to a plain linear program (LP) is fast — but sometimes wrong. My research measures the size and shape of that "sometimes."
Showed when the fast LP relaxation can be trusted. I ran 120 controlled experiments across 5 query templates (Gurobi as the solver, the TPC-H dataset, PaQL query syntax) measuring how often the LP relaxation lands on the same answer as the exact ILP. The result: 82% agreement overall — 100% on queries with only COUNT constraints, dropping to roughly 72% once SUM constraints enter. That gap is the finding: it identifies precisely which constraint structures make cheap approximation unsafe, which tells a database engine when it must pay for the exact solve.
Made the whole sweep reproducible from one command. I built the Python/Gurobi benchmarking harness the group now uses: it runs every template, logs objectives, optimality gaps, and solve times to CSV, and lets anyone in the lab regenerate the full 120-run result set without touching my notebook.
Found concrete worst cases for Progressive Shading (VLDB '24) — the lab's state-of-the-art package-query algorithm. By constructing low-constraint adversarial inputs at its partition boundaries, I produced instances that each force more partitioning steps than the paper's analysis predicts. Finding where a published algorithm breaks is the fastest way to understand why it works — and it's the same skeptical instinct behind the negative results in my inference engine.
Presented the LP-vs-ILP results and the adversarial analysis to the lab, backed by a seven-chart analysis workbook, which set the direction for the group's next round of experiments.
"When is the fast approximation good enough?" is one of the central questions of applied quantitative work — it shows up in portfolio construction, resource allocation, scheduling, and model selection. This research is where I learned to answer it the only trustworthy way: define the benchmark, run the experiment, and report where the method fails, not just where it shines. It's also the long-term engine behind HoopIQ's roster-optimization endgame — picking a team under a salary cap is a package query.
I'd love to compare notes — on this work, on where the field is going, or on what a strong researcher-in-training should be doing next. Advice welcome, always.