Nat Taylor — Blog, AI, Product Management & Tinkering

The paper is titled “Weaving Relations for Cache Performance”

The approach achieves high CPU cache performance by changing the in-page data placement from row to columnar without a penalty.

1. this is datapage in the database sense, so typically about 4kb of datarows are laid out on to a “page”
2. this works well, and snowflake (and the authors of that paper) want to keep that dataset on that page
3. but the research proposes a new way to organize(/layout) the data on the page, such that when the CPU says “Give me next value” that next value (and the next and the next) are usually in the cpu-cache already, which prevents a slow lookup from ram/disk

Snowflake docs suggest they typically compression 50-500mb down to around 16mb and “automatically determines the most efficient compression algorithm for the column“

Apache Parquet describes encodings including:

• Dictionary Encoding
• Run Length Encoding / Bit-Packing Hybrid
• Delta Encoding
• Delta-length byte array
• Delta Strings

The paper is “Efficiently Compiling Efficient Query Plans for Modern Hardware”

As main memory grows, query performance is more and more determined by the raw CPU costs of query processing itself. The classical iterator style query processing technique is very simple and flexible, but shows poor performance on modern CPUs due to lack of locality and frequent instruction mispredictions. Several techniques like batch oriented processing or vectorized tuple processing have been proposed in the past to improve this situation, but even these techniques are frequently out-performed by hand-written execution plans.
In this work we present a novel compilation strategy that translates a query into compact and efficient machine code using the LLVM compiler framework. By aiming at good code and data locality and predictable branch layout the resulting code frequently rivals the performance of handwritten C++ code. We integrated these techniques into the HyPer main memory database system and show that this results in excellent query performance while requiring only modest compilation time.

You can see the “scanned partitions” versus “total partitions” in the Query Profile.

“Snowflake keeps pruning-related metadata for every individual table file. The metadata not only covers plain relational columns, but also a selection of auto-detected columns inside of semi-structured data, see Section 4.3.2. During optimization, the metadata is checked against the query predicates to reduce (“prune”) the set of input files for query execution. The optimizer performs pruning not only for simple base-value predicates, but also for more complex expressions such as WEEKDAY(orderdate) IN (6, 7).
Besides this static pruning, Snowflake also performs dynamic pruning during execution. For example, as part of hash join processing, Snowflake collects statistics on the distribution of join keys in the build-side records. This information is then pushed to the probe side and used to filter and possibly skip entire files on the probe side. This is in addition to other well-known techniques such as bloom joins [40].”

This paper is “Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing” and tracks per-partition stats like

• min/max values
• #distinct values
• sum
• histogram
• #nulls
• dictionary
• bloom filters etc.

They decide how to partition with a strategy from the paper “Fine-grained Partitioning for Aggressive Data Skipping“

Using 10-20 filters(/features) and 50k-100k rows to determine the best partioning strategy, results in a 2-5x query time speedup over hash(/similar) partitioning.

The feature-vectors can be re-used for pruning if a query contains one or more of the feature-filters.

“We first extract representative filters in a workload as features using frequent itemset mining.”

NT: They look at query history

“Based on these features, each data tuple can be represented as a feature vector.”

NT: They also group-by here, to weight the vectors and reduce the # of vectors

“We then formulate the blocking problem as a optimization problem on the feature vectors, called Balanced MaxSkip Partitioning.”

NT: Balance is key so that the partitions come out to be the same size

“To find an approximate solution efficiently, we adopt the bottom-up clustering framework.”

Created virtual columns for paths with JSON is amazing to me.

You can get an idea of how they might calculate the stats for this here: Listing Distinct Key Names/Common Schema in JSON Data

So you could build a list of the most common paths in a JSON object and then project those, and keep metadata statistics useful for joining, etc

Snowflake announced that they use FoundationDB for this.

You can see some query profiles say “Metadata only”

To make it easy to add new metadata objects, we built an object-mapping layer on top of key-values. Schema definition, evolution and metadata versioning are done by this layer as well. User-visible objects, such as catalog definitions, users, sessions, access control, copy history and others all have metadata backing them. Every statement executed has a metadata entry, along with statistics of its execution. Transaction state and lock queues are also persisted in FoundationDB. In fact, lock queues are implemented using the watch feature mentioned earlier. A data manipulation statement is enqueued on a resource’s lock queue, and a FoundationDB watch notifies the statement when the statement reached the front of the resource’s queue. There is also user-invisible metadata such as data distribution information, servers and encryption keys.”