Filter Before You Parse
Many big data applications often run on raw, unstructured or semi-structured data formats, such as JSON. Querying these files is often very time-consuming, especially for exploratory applications, where data scientists run queries to explore and better understand their data. Surprisingly, 80-90% of the execution time in these applications is actually spent on parsing the data, not on evaluating the actual query itself. Parsing is, in fact, the bottleneck.
In this post, we introduce Sparser ((code)), a recent research project from the Stanford DAWN group that addresses this performance gap. Sparser’s key insight is to filter data before it’s parsed using SIMD-accelerated filtering functions. On JSON, Avro, and Parquet data, Sparser is up to 22x faster than state-of-the-art parsers, and improves end-to-end query runtimes in Apache Spark by up to 9x.
Slow parsing of raw data streams is not a new problem in the database community; at VLDB 2017, researchers at Microsoft presented Mison, a new JSON parser that uses SIMD instructions to build a structural index over each JSON record, which enables efficient field projection without deserializing the record completely. While Mison is significantly faster than previous state-of-the-art parsers, such as RapidJSON, it can still leave a lot of performance on the table. When we measured Mison’s parsing throughput on sample JSON data, we found that it still executed multiple CPU cycles per byte on average. Compared to a simple byte-by-byte SIMD scan of the data (the theoretical upper bound for parsing), Mison was multiple orders of magnitude slower.
Mison’s improvement on previous parsers comes from a simple idea: apply projections before parsing. That is, take the projections found in most user-specified queries over the JSON data, and apply the projections before the parsing stage, so that only the necessary fields that users want are parsed.
Inspired by Mison, Sparser uses an analogous idea: what if we push filters down to the parser as well? This is especially helpful for exploratory queries in data analytics, because these queries are often highly selective. For example, when we looked at profiling metadata about Spark SQL queries on Databricks’ cloud service that read JSON or CSV data, we found that 40% of the queries selected less than 20% of the records. We ran a similar analysis on researchers’ queries on JSON data from Censys, a search engine for Internet port scans, and found even higher selectivity for those queries.
