# US 2020/0004736 A1 · Techniques for enabling and integrating in-memory semi-structered data and text document searches with in-memory columnar query processing

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

- Number: US 2020/0004736 A1
- Document ID: US20200004736A1
- Status: Published application
- Kind: A1
- Application number: 16/022,465
- Filed: 2018-06-28
- Published: 2020-01-02
- Earliest claimed: 2018-06-28
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: ZHEN HUA LIU; AUROSISH MISHRA; SHASANK K. CHAVAN; DOUGLAS J. MCMAHON; VIKAS ARORA; HUI JOE CHANG; SHUBHRO JYOTI ROY
- Web page: https://patentgrep.com/patent/US20200004736A1

## CPC

- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/81: Indexing, e.g. XML tags; Data structures therefor; Storage structures
- G06F 16/2255: {Hash tables}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/2455: Query execution
- G06F 16/84: Mapping; Conversion
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A “hybrid derived cache” stores semi-structured data or unstructured text data in an in-memory mirrored form and columns in another form, such as column-major format. The hybrid derived cache may cache scalar type columns in column-major format. The structure of the in-memory mirrored form of semi-structured data or unstructured text data enables and/or enhances access to perform path-based and/or text based query operations. A hybrid derived cache improves cache containment for executing query operations. The in-memory mirrored form is used to compute queries in a transactionally consistent manner through the use of an invalid vector that used to determine when to retrieve the transactionally consistent persistent form of semi-structured data or unstructured text data in lieu of the in-memory form.

## Claims

### Claim 1

A method comprising:
storing one or more tables in a persistent form, said one or more tables comprising a plurality of columns, said plurality of columns comprising a scalar column and a certain column that contains semi-structured data or unstructured-text data;
within an IMCU stored in RAM, storing a subset of rows that include said scalar column and said certain column, said subset of rows containing a plurality of hierarchical data objects in said certain column of said subset of rows;
wherein within said IMCU, said scalar column is stored in a column-major format and said certain column is stored in a representation that includes a posting index, said posting index mapping a plurality tokens in said plurality of hierarchical data objects to token locations within said plurality of hierarchical data objects;
maintaining transactional consistency between said IMCU and said scalar column and certain column stored in said persistent form in said one or more tables:
receiving a request to execute a database statement that requires predicate evaluation of a predicate against said certain column; and
in response to receiving the request, evaluating said predicate using said IMCU, wherein evaluating said predicate includes evaluating a first predicate condition of said predicate against said posting index.

### Claim 2 (depends on 1)

The method of claim 1,
wherein said scalar column is stored in a column vector within said IMCU;
wherein said posting index is index aligned with said column vector;
wherein evaluating said predicate includes generating a first result vector representing the evaluation of said first predicate condition against said posting index, wherein generating a result vector includes setting a particular bit corresponding to an index of said column vector that said posting index maps to a hierarchical data object of said plurality of hierarchical data objects.

### Claim 3 (depends on 2)

The method of claim 2, wherein evaluating said predicate includes:
before generating said first result vector, generating another result vector representing the evaluation of a second predicate condition against said scalar column, wherein said another result vector sets another bit corresponding to a different index than an index corresponding to said particular bit;
wherein evaluating said first predicate condition includes foregoing fully evaluating said first predicate condition against a row indexed to the different index.

### Claim 4 (depends on 2)

The method of claim 2, the method further including:
generating another result vector representing evaluation of a second predicate condition against said scalar column;
combining said first result vector and said another result vector by performing an AND operation between said first result vector and said another result vector to generate a third result vector.

### Claim 5 (depends on 1)

The method of claim 1,
wherein said scalar column is stored in a column vector within said IMCU; and
wherein said posting index includes a plurality of index entries, each index entry mapping a token to one or more indexes of said column vector, each of said one or more indexes being an object reference to a respective hierarchical data object of said plurality of hierarchical data objects.

### Claim 6 (depends on 1)

The method of claim 1, wherein:
wherein said scalar column is stored in a column vector within said IMCU; and
wherein said posting index includes a plurality of posting index entries that each map a token to one or more token locations within said plurality of hierarchical data objects;
wherein each posting index entry of said plurality of posting index entries includes a respective set of one or more lists, each respective set of one or more lists includes:
an index of said column vector as an object reference to a respective hierarchical data object of said plurality of hierarchical data objects, and
one or more token locations within said respective hierarchical data object.

### Claim 7 (depends on 1)

The method of claim 1, the method further including:
wherein evaluating a first predicate condition of said predicate against said posting index includes evaluating said first predicate condition against a persistent form of a particular hierarchical data object of said plurality of hierarchical data objects stored in certain column.

### Claim 8 (depends on 7)

The method of claim 7, wherein said first predicate condition is based on a containment relationship, wherein evaluating said first predicate condition against a persistent form of a particular hierarchical data object includes generating a posting index for said particular hierarchical data object in response to determining that said first predicate condition is based on said containment relationship.

### Claim 9 (depends on 1)

The method of claim 1, wherein said posting index is stored as a serialized hash table.

### Claim 10 (depends on 6)

The method of claim 6, wherein the method includes:
generating a delta posting index that indexes a changed hierarchical data object that has changes in the persistent form that are not reflected in said posting index;
wherein said delta posting index includes a plurality of delta posting index entries that each map a token to one or more token locations within said changed hierarchical data object in the persistent form;
wherein a particular delta posting index entry of said delta posting index entries includes a plurality of delta lists, each delta list of said plurality of delta lists including an index of said column vector as an object reference to a hierarchical data object of said plurality of hierarchical data objects;
wherein a particular delta list of said plurality of delta lists includes a particular index as an object reference to said changed hierarchical data object;
wherein an existing posting index entry of said plurality of posting index entries includes an existing plurality of lists;
wherein an existing list of said existing plurality of lists includes said particular index as an object reference to said changed hierarchical data object;
wherein said posting index is stored as a serialized hash table;
generating another posting index as a serialized hash table, wherein generating another posting index includes:
generating a new posting index entry by at least performing a sort merge operation between said plurality of delta lists and said existing plurality of lists, said sort merge operation excluding said existing list that includes said particular index as an object reference to said changed hierarchical data object.

### Claim 11

A non-transitory storage media storing sequences of instructions, said sequences of instructions, wherein execution of said sequences of instructions, by one or more computing devices causes:
storing one or more tables in a persistent form, said one or more tables comprising a plurality of columns, said plurality of columns comprising a scalar column and a certain column that contains semi-structured data or unstructured-text data;
within an IMCU stored in RAM, storing a subset of rows that include said scalar column and said certain column, said subset of rows containing a plurality of hierarchical data objects in said certain column of said subset of rows;
wherein within said IMCU, said scalar column is stored in a column-major format and said certain column is stored in a representation that includes a posting index, said posting index mapping a plurality tokens in said plurality of hierarchical data objects to token locations within said plurality of hierarchical data objects;
maintaining transactional consistency between said IMCU and said scalar column and certain column stored in said persistent form in said one or more tables:
receiving a request to execute a database statement that requires predicate evaluation of a predicate against said certain column; and
in response to receiving the request, evaluating said predicate using said IMCU, wherein evaluating said predicate includes evaluating a first predicate condition of said predicate against said posting index.

### Claim 12 (depends on 11)

The non-transitory storage media of claim 11,
wherein said scalar column is stored in a column vector within said IMCU;
wherein said posting index is index aligned with said column vector;
wherein evaluating said predicate includes generating a first result vector representing the evaluation of said first predicate condition against said posting index, wherein generating a result vector includes setting a particular bit corresponding to an index of said column vector that said posting index maps to a hierarchical data object of said plurality of hierarchical data objects.

### Claim 13 (depends on 12)

The non-transitory storage media of claim 12, wherein evaluating said predicate includes:
before generating said first result vector, generating another result vector representing the evaluation of a second predicate condition against said scalar column, wherein said another result vector sets another bit corresponding to a different index than an index corresponding to said particular bit;
wherein evaluating said first predicate condition includes foregoing fully evaluating said first predicate condition against a row indexed to the different index.

### Claim 14 (depends on 12)

The non-transitory storage media of claim 12, the sequences of instructions including instructions that, when executed by said one or more computing devices, causes:
generating another result vector representing evaluation of a second predicate condition against said scalar column;
combining said first result vector and said another result vector by performing an AND operation between said first result vector and said another result vector to generate a third result vector.

### Claim 15 (depends on 11)

The non-transitory storage media of claim 11,
wherein said scalar column is stored in a column vector within said IMCU; and
wherein said posting index includes a plurality of index entries, each index entry mapping a token to one or more indexes of said column vector, each of said one or more indexes being an object reference to a respective hierarchical data object of said plurality of hierarchical data objects.

### Claim 16 (depends on 11)

The non-transitory storage media of claim 11, wherein:
wherein said scalar column is stored in a column vector within said IMCU; and
wherein said posting index includes a plurality of posting index entries that each map a token to one or more token locations within said plurality of hierarchical data objects;
wherein each posting index entry of said plurality of posting index entries includes a respective set of one or more lists, each respective set of one or more lists includes:
an index of said column vector as an object reference to a respective hierarchical data object of said plurality of hierarchical data objects, and
one or more token locations within said respective hierarchical data object.

### Claim 17 (depends on 11)

The non-transitory storage media of claim 11, the sequences of instructions including instructions that, when executed by said one or more computing devices, causes:
wherein evaluating a first predicate condition of said predicate against said posting index includes evaluating said first predicate condition against a persistent form of a particular hierarchical data object of said plurality of hierarchical data objects stored in certain column.

### Claim 18 (depends on 17)

The non-transitory storage media of claim 17, wherein said first predicate condition is based on a containment relationship, wherein evaluating said first predicate condition against a persistent form of a particular hierarchical data object includes generating a posting index for said particular hierarchical data object in response to determining that said first predicate condition is based on said containment relationship.

### Claim 19 (depends on 11)

The non-transitory storage media of claim 11, wherein said posting index is stored as a serialized hash table.

### Claim 20 (depends on 6)

The non-transitory storage media of claim 6, the sequences of instructions including instructions that, when executed by said one or more computing devices, causes:
generating a delta posting index that indexes a changed hierarchical data object that has changes in the persistent form that are not reflected in said posting index;
wherein said delta posting index includes a plurality of delta posting index entries that each map a token to one or more token locations within said changed hierarchical data object in the persistent form;
wherein a particular delta posting index entry of said delta posting index entries includes a plurality of delta lists, each delta list of said plurality of delta lists including an index of said column vector as an object reference to a hierarchical data object of said plurality of hierarchical data objects;
wherein a particular delta list of said plurality of delta lists includes a particular index as an object reference to said changed hierarchical data object;
wherein an existing posting index entry of said plurality of posting index entries includes an existing plurality of lists;
wherein an existing list of said existing plurality of lists includes said particular index as an object reference to said changed hierarchical data object;
wherein said posting index is stored as a serialized hash table;
generating another posting index as a serialized hash table, wherein generating another posting index includes:
generating a new posting index entry by at least performing a sort merge operation between said plurality of delta lists and said existing plurality of lists, said sort merge operation excluding said existing list that includes said particular index as an object reference to said changed hierarchical data object.
