How do databases like MySQL store data efficiently for querying? It seems like something like protobuf would do well here, though you'd need to generate code for each dataset.
Typically they use row-oriented binary storage, optionally with individual columns or subsets of columns duplicated into indices for fast querying. Have you tried protobufs? How many hundreds of megs per second do you get? I think it is remarkably slow on the scales we're talking about here.
Traditional DBMS's get performance by optimizing storage down to the physical layout of the data on the hardware. So MySQL makes a lot of assumptions based on the mechanics if spinning disks and buffers tailored to their physics. Database Systems: The Complete Book is a good text on the subject and the second half is all about the hardware and software used in implementing traditional systems.
http://www.andresmh.com/nyctaxitrips/
Some background on this data:
http://chriswhong.com/data-visualization/taxitechblog1/
And data for 2014 directly from the city:
https://data.cityofnewyork.us/view/gn7m-em8n