# US 2024/0202257 A1 · Conditional filters with applications to join processing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0202257 A1
- Document ID: US20240202257A1
- Status: Published application
- Kind: A1
- Application number: 18/395,078
- Filed: 2023-12-22
- Published: 2024-06-20
- Earliest claimed: 2019-10-22
- Assignees: Tableau Software, Inc.
- Applicants: Tableau Software, LLC
- Inventors: Richard Lee COLE; Daniel Shaw TING
- Web page: https://patentgrep.com/patent/US20240202257A1

## CPC

- G06F 16/9532: Query formulation
- G06F 16/9538: Presentation of query results
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments are directed to data processing. A plurality of fact objects and a plurality of attribute objects may be provided such that each of the attribute objects may be associated with one or more fact objects. A fact key may be generated for each of the plurality of fact objects based on information associated with each fact object. Attribute objects associated with each of the plurality of fact objects may be determined based on attribute information associated with each fact object. An attribute key for each of the one or more attribute objects may be generated based on the attribute information. The attribute keys and a plurality of fact keys may be stored at a plurality of storage locations in a data catalog such that each storage location corresponds to one of the plurality of fact keys.

## Claims

### Claim 1

A method for data processing using one or more network computers performed at a computing device having one or more processors and memory storing one or more programs configured for execution by the one or more processors, the method comprising:
identifying a plurality of fact tables from a data source, each fact table having one or more respective attributes;
for each of the plurality of fact tables, generating a respective fact key, and for each attribute of each fact table, generating a respective attribute key based on attribute information associated with the respective attribute;
storing the fact keys and attribute keys at a plurality of storage locations in a data catalog, wherein each storage location corresponds to unique one of fact keys;
receiving a query that specifies a first fact table and one or more attributes of the first fact table; and
in response to receiving the query:
generating a query fact key based on the query;
generating one or more query attribute keys based on the one or more [query] attributes of the first fact table;
comparing the one or more query attribute keys with one or more attribute keys stored in the data catalog; and
providing a query result based on whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 2 (depends on 1)

The method of claim 1, wherein comparing the one or more query attribute keys comprises:
comparing the one or more query attribute keys to an attribute vector associated with a fact key in the data catalog, wherein the attribute vector includes a value representing a number of attributes that are associated with the first fact table.

### Claim 3 (depends on 1)

The method of claim 1, providing the query result comprises:
in accordance with a determination that attribute keys stored in the data catalog do not match the one or more query attribute keys, repeatedly shifting an attribute vector from a storage location associated with a fact key to accommodate inserting the one or more query attribute keys.

### Claim 4 (depends on 1)

The method of claim 1, The method of claim 1, further comprising:
generating a Bloom filter for one or more fact tables based on the one or more attribute keys;
storing the Bloom filter at each storage location in the data catalog associated with the one or more fact tables; and
using the Bloom filter to determine whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 5 (depends on 1)

The method of claim 1, further comprising, generating the data catalog based on a cuckoo filter, wherein each cuckoo filter key is a fact key or an alternate fact key associated with the first fact table.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
generating an alternate fact key for each of the plurality of fact tables based on information associated with each fact table; and
in accordance with a determination that a location in the data catalog corresponding to the query fact key being unavailable, storing the one or more attribute keys and the alternate fact key for each fact table at a storage location in the data catalog, wherein the storage location corresponds to the alternate fact key.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
generating an attribute vector for the first fact table stored at a storage location in the data catalog based on a number of one or more attributes associated with the first fact table and a capacity of the attribute vector;
storing one or more attribute keys for the one or more attributes in the attribute vector; and
storing the attribute vector at the storage location.

### Claim 8

A system for data processing:
one or more processors;
memory coupled to the one or more processors; and
one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs comprising instructions for:
identifying a plurality of fact tables from a data source, each fact table having one or more respective attributes;
for each of the plurality of fact tables, generating a respective fact key, and for each attribute of each fact table, generating a respective attribute key based on attribute information associated with the respective attribute;
storing the fact keys and attribute keys at a plurality of storage locations in a data catalog, wherein each storage location corresponds to unique one of fact keys;
receiving a query that specifies a first fact table and one or more attributes of the first fact table; and
in response to receiving the query:
generating a query fact key based on the query;
generating one or more query attribute keys based on the one or more attributes of the first fact table;
comparing the one or more query attribute keys with one or more attribute keys stored in the data catalog; and
providing a query result based on whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 9 (depends on 8)

The system of claim 8, wherein comparing the one or more query attribute keys comprises:
comparing the one or more query attribute keys to an attribute vector associated with a fact key in the data catalog, wherein the attribute vector includes a value representing a number of attributes that are associated with the first fact table.

### Claim 10 (depends on 8)

The system of claim 8, providing the query result comprises:
in accordance with a determination that attribute keys stored in the data catalog do not match the one or more query attribute keys, repeatedly shifting an attribute vector from a storage location associated with a fact key to accommodate inserting the one or more query attribute keys.

### Claim 11 (depends on 8)

The system of claim 8, wherein the one or more programs further comprise instructions for:
generating a Bloom filter for one or more fact tables based on the one or more attribute keys;
storing the Bloom filter at each storage location in the data catalog associated with the one or more fact tables; and
using the Bloom filter to determine whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 12 (depends on 8)

The system of claim 8, wherein the one or more programs further comprise instructions for generating the data catalog based on a cuckoo filter, wherein each cuckoo filter key is a fact key or an alternate fact key associated with the first fact table.

### Claim 13 (depends on 8)

The system of claim 8, wherein the one or more programs further comprise instructions for:
generating an alternate fact key for each of the plurality of fact tables based on information associated with each fact table; and
in accordance with a determination that a location in the data catalog corresponding to the query fact key being unavailable, storing the one or more attribute keys and the alternate fact key for each fact table at a storage location in the data catalog, wherein the storage location corresponds to the alternate fact key.

### Claim 14 (depends on 8)

The system of claim 8, wherein the one or more programs further comprise instructions for:
generating an attribute vector for the first fact table stored at a storage location in the data catalog based on a number of one or more attributes associated with the first fact table and a capacity of the attribute vector;
storing one or more attribute keys for the one or more attributes in the attribute vector; and
storing the attribute vector at the storage location.

### Claim 15

A non-transitory computer readable storage medium storing one or more programs, the one or more programs configured for execution by a computing device having one or more processors, and memory, the one or more programs comprising instructions for:
identifying a plurality of fact tables from a data source, each fact table having one or more respective attributes;
for each of the plurality of fact tables, generating a respective fact key, and for each attribute of each fact table, generating a respective attribute key based on attribute information associated with the respective attribute;
storing the fact keys and attribute keys at a plurality of storage locations in a data catalog, wherein each storage location corresponds to unique one of fact keys;
receiving a query that specifies a first fact table and one or more attributes of the first fact table; and
in response to receiving the query:
generating a query fact key based on the query;
generating one or more query attribute keys based on the one or more attributes of the first fact table;
comparing the one or more query attribute keys with one or more attribute keys stored in the data catalog; and
providing a query result based on whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 16 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein comparing the one or more query attribute keys comprises:
comparing the one or more query attribute keys to an attribute vector associated with a fact key in the data catalog, wherein the attribute vector includes a value representing a number of attributes that are associated with the first fact table.

### Claim 17 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein providing the query result comprises:
in accordance with a determination that attribute keys stored in the data catalog do not match the one or more query attribute keys, repeatedly shifting an attribute vector from a storage location associated with a fact key to accommodate inserting the one or more query attribute keys.

### Claim 18 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein the one or more programs further comprise instructions for:
generating a Bloom filter for one or more fact tables based on the one or more attribute keys;
storing the Bloom filter at each storage location in the data catalog associated with the one or more fact tables; and
using the Bloom filter to determine whether the one or more query attribute keys match the one or more attribute keys stored in the data catalog.

### Claim 19 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein the one or more programs further comprise instructions for generating the data catalog based on a cuckoo filter, wherein each cuckoo filter key is a fact key or an alternate fact key associated with the first fact table.

### Claim 20 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein the one or more programs further comprise instructions for:
generating an alternate fact key for each of the plurality of fact tables based on information associated with each fact table; and
in accordance with a determination that a location in the data catalog corresponding to the query fact key being unavailable, storing the one or more attribute keys and the alternate fact key for each fact table at a storage location in the data catalog, wherein the storage location corresponds to the alternate fact key.
