Ovation Ventures Ovation Developer Docs

Tools

Apache Parquet: What's the Big Deal?

By Ben C. Forsberg

I’ve been pushing very hard to convert our Mixpanel exports from GZipped JSON files to Apache Parquet. I keep promising that it’ll make our Athena queries so much faster. What is Apache Parquet, in a nutshell, and why do I think it’s so great?

Apache Parquet is a “column-store” storage format. That means that, instead of recording, say:

last name first name birthday phone number
last name first name birthday phone number
last name first name birthday phone number

Instead, in Parquet, it’s stored as:

last name last name last name
first name first name first name
birthday birthday birthday
phone number phone number phone number

Why on Earth would you want to do that? That seems crazy!

Well, let’s say first that your file has more than those four columns. Let’s say that you also have multiple addresses, and that they are flattened, like address.0.name address.0.street_line_1 address.0.street_line_2 address.0.city address.0.state address.0.postal_code , etc. And maybe you have a lot of other fields, besides. Let’s also say you’ve been traveling around the world and have collected MILLIONS of contacts, and have a GIANT list of contact information you need to sort through. Now, if you want to ask a question, like “When is Ben Forsberg’s Birthday?” you have to look through these contacts.

With a GZipped JSON file, everything is compressed all in one blob. With compression, you can’t just skip to the middle of a file without reading everything that came first. So even if you suspect that “Ben Forsberg’s” record is in the middle or near the end, you have to start at the beginning and work your way through, decompressing each byte as you go. Each record has a certain structure with all the fields. So in order to ask “Is this record’s last name ‘Forsberg’ and is its first name ‘Ben’?”, you need to scan the entire record into memory and parse it into fields. Because it’s all a text format, the only way to find the entry for “Last Name” is to scan each byte leading up to it, and the only way to know if the value is “Forsberg” is to first compare F=F, then o=o, then r=r, and so on. If you find a byte that doesn’t match, you’re not off the hook, because you have to keep scanning byte-by-byte to find the byte that marks the end of the field, the quote or comma character. In the end, you have to scan every single byte of your entire file in order to answer your question.

With a column-store format, each field is compressed separately. This means you get a much better compression ratio, because each compressed stream is only dealing with a single type of data. For example, the phone number field. You have a lot of patterns in phone numbers: area codes, region prefixes, etc. Adaptive compression algorithms will be able to reduce these patterns to a few bits.

Scanning the column-store database, you would first find the “last name” column. This is a binary format with a manifest, which you can read first to find the exact byte offset of the beginning of the “last name” column data. You can begin decompressing and scanning the “last name” data to find “Forsberg”. But you don’t have to compare every byte. Strings are encoded with a prefix byte, so you only have to look at the first byte to see whether the string is 8 bytes long (as is “Forsberg”) or not. If it’s not, you know exactly how far to skip ahead. Even if it’s the right length, if the first letter is “G”, you can stop scanning and just jump to the next entry.

When you’ve finished scanning the “last name” field, you have a list of indices for the matches. You can start scanning the “first name” field next. But you don’t have to check each entry for “Ben”, only the indices that returned from the “last name” scan. So you only have to look at those prefix bytes and jump through the data.

When you have a reduced set of indices for people named “Ben Forsberg”, you still don’t have to load the entire record, because the “birthday” column is also a separate data block. Just scan it for the right index, and you have your answer. There’s no need to even load the other fields from disk into memory, or request those bytes over the wire from S3.

BUT WE’RE NOT DONE YET!

There are only two “Bens Forsberg” in the world that I know of, but there are a lot of “Bens” and a lot of “Forsbergs”. For the “first name” and “last name” fields, you can use a hybrid dictionary/plain encoding. This means that the Parquet writer will encode the full text “Forsberg” if it wouldn’t save any space by putting it in the dictionary (you’re collecting contact information in Peru, for example). But if the value is common enough (you’re traveling through Sweden), it will create a dictionary entry in the file’s header section. Now, comparing each field value against “Forsberg” is a constant-time operation, comparing the two or three byte dictionary code.

BUT WAIT! THERE’S MORE!

Parquet files aren’t just big buckets of data, but have some internal structure. While each column is stored separately, groups of rows are stored in a block called a “Row Group”. You decide how big to make a row group when you write the Parquet file, but it pays to make them as large as you possibly can, given the limits of the writer’s memory buffer. The reason is that each Row Group has its own metadata section. In the metadata section, you can put useful things, like “Bloom Filters”. (A Bloom Filter is named after the guy who invented it: Bloom. It’s not some kind of fancy math concept that resembles “blooming” in some abstract way.) Bloom filters are pretty cool, but the short version is that, if given a relatively tiny amount of file space, and a constant-time lookup, a bloom filter can tell you if a value is either “definitely not in” or “probably in” a set. So scanning through all your contacts that you collected through your world travels, the bloom filter will tell you that you can definitely skip all the row groups you made in your journeys through Peru and Argentina: you met no Forsbergs in South America. That can reduce the amount of data you have to load into memory (or transfer over a network from S3) by gigabytes!

There are other optimizations we can put in the row group metadata as well. Let’s say that, instead of contacts, our data files contain log entries. Perhaps records of page views from a web site. This data has been spooled in order until it’s large enough to make a row group, then converted to Parquet, and added to our file system. This in turn means that the data are sorted by a timestamp. We can write in our row group metadata that the “timestamp” field is a sorted field. It doesn’t change anything else about how that field is stored, but if you’re searching for records from a particular range of time, the reader might choose to decompress the entire field into memory, and use a binary search to find the start and end indices of that range in O(log(n)) time, which is very fast.

You can break your Parquet data into multiple files: one file will have your manifest, and then multiple files will have multiple row groups, making access over a network even more efficient.

Why would you choose any other data format?

Well… about that.

Some things you cannot do with a Parquet file: you can’t append data without rewriting at least the row group and the manifest. Breaking your Parquet data into multiple files helps, because then you can append a row group at a time to the latest file, and only re-write your manifest file. But you still can’t add one record at a time. And you still can’t go back and edit any record without re-writing everything that came after it.

There’s a lot of metadata in a Parquet file, so if you only have a small number of records, the metadata will dwarf the data, and all those lovely compression ratios won’t help you. You’d be better off with a traditional row-store format like JSON or CSV in that case.

But if you have lots of data that that you add to only in big batches, that lives on a disk somewhere, that needs to be queried fast, but never needs to be updated, Parquet is for you!

Are there other formats like Parquet?

There are two main ones. ORC is similar to Parquet, and I hear it can even support appending records better than Parquet. Amazon Athena understands Parquet, though, so that’s the choice here.

Parquet is part of the Apache Arrow project, and Arrow also has another data format: arrow format. The Apache Arrow format is primarily concerned with efficient, column-oriented layout of memory for live processes, and the arrow format is just a dump of memory. So it is primarily for “IPC” between programs, or for dumping diagnostic data. The arrow format will be much less efficient at disk usage than Parquet.