Result Cache Hits

Medium

Caching · Snowflake

A warehouse caches query results per tenant. You are given a list of events in chronological order (timestamps never decrease) and an integer ttl.

["query", tenant, sql, ts]: tenant tenant runs the query text sql at time ts.
["write", tenant, ts]: tenant tenant modifies its data at time ts.

Each tenant's data starts at version 0, and every write by that tenant increases its version by 1. Writes by one tenant never affect another tenant.

The cache holds at most one entry per (tenant, sql) pair, recording the data version and the time it was last stored. A query is a hit if an entry for its (tenant, sql) exists, the entry's version equals the tenant's current version, and ts - stored_time <= ttl. Otherwise it is a miss.

After every query, hit or miss, the entry for (tenant, sql) is set to the tenant's current version and time ts (so a hit also refreshes the entry's age).

Return a list with one boolean per query event, in order: True for a hit, False for a miss. Write events produce no output.

Example 1

Input:: events = [["query", "acme", "q1", 0], ["query", "acme", "q1", 4], ["write", "acme", 6], ["query", "acme", "q1", 7], ["query", "acme", "q1", 9]], ttl = 10
Output:: [False, True, False, True]
Explanation: The first query is a miss that fills the cache. The second is a hit (age 4). The write moves acme to version 1, so the third query misses and re-caches at version 1, and the fourth hits.

Example 2

Input:: events = [["query", "t", "q", 0], ["query", "t", "q", 5], ["query", "t", "q", 10], ["query", "t", "q", 16]], ttl = 5
Output:: [False, True, True, False]
Explanation: At time 5 the entry is exactly 5 old, which is allowed, and it is refreshed to 5. At time 10 it is 5 old again and hits. At time 16 it is 6 old, more than ttl.

Example 3

Input:: events = [["query", "a", "q", 1], ["write", "b", 2], ["query", "a", "q", 3], ["query", "b", "q", 4]], ttl = 100
Output:: [False, True, False]
Explanation: The write by b does not change a's version, so a hits at time 3. Tenant b has never run q, so its query is a miss.

Constraints

0 ≤ events.length ≤ 10⁵
0 ≤ ts ≤ 10⁹, and timestamps are non-decreasing
0 ≤ ttl ≤ 10⁹
Tenant ids and SQL strings are non-empty and compared exactly