2.0 Example Compression Process

FIG. 2 is a flow diagram that depicts computer 100 applying anisotropic compression to a dependent column based on compression of an independent column, in an embodiment. FIG. 2 is discussed with reference to FIG. 1.

Step 202 generates compressed independent column 140 by compressing uncompressed independent column 110. For example, Snappy compression may be used. As explained in related U.S. patent application Ser. No. 15/907,565, dictionary encoding may entail tokenization. For example, a text document (not shown) may be decomposed into a sequence of tokens (i.e. more or less atomic substrings) that represent individual values as discussed later herein.

For example, whitespace and/or punctuation may be interpreted as delimiters between tokens and, in some embodiments, may be discarded or preserved as discussed later herein. The sequence of tokens may be stored, pipelined, or otherwise processed (e.g. parsed into datatypes as explained later herein) as uncompressed independent column 110. Each token or subsequence of adjacent tokens may be copied or replaced with a reference or dictionary code and then written into compressed independent column 140.

Step 204 generates compressed dependent column 150 by applying, based on compression results of step 202, anisotropic compression to uncompressed dependent column 120. For example, uncompressed dependent column 120 may contain redactions of values that are stored in uncompressed independent column 120. As explained earlier herein, uncompressed columns 110 and 120 may share entropy such that much of the content of uncompressed dependent column 120 may already be symbolically (i.e. not literally) represented in compressed independent column 140. That is, a same portion of compressed independent column 140 may represent corresponding portions of both uncompressed columns 110 and 120. Thus, portions of uncompressed dependent column 120 may be entirely omitted from compressed dependent column 150.

Step 206 writes both compressed columns 140 and 150 into file 130 in a particular way. For example, file 130 may be a Parquet file that has different internal partitions for different columns and/or metadata. Included in the steps of FIG. 3, as discussed later herein, are particular operations for applying step 206 to a Parquet file.

Some or all of steps 202, 204, and 206 may overlap for pipeline parallelism. For example, a first execution thread or processing core may perform step 202, the compression results of which are incrementally available to a second thread or core to perform step 204. The compression results of both steps 202 and 204 may be incrementally available to a third thread or core that performs step 206. For example, writing compressed independent column 140 into file 130 may occur before, during, or after compressed dependent column 150 is generated.

Horizontal (e.g. elastic) scaling may be achieved on a computer cluster. For example, a huge uncompressed independent column may be subdivided into shards (subsequences of values). Each shard may be distributed to a different computer of a cluster.

Each computer of the cluster may treat its shard as an instance of uncompressed independent column 110. Each computer may generate (e.g. redact values from independent column 110) or otherwise obtain a corresponding instance of uncompressed dependent column 120. Each computer may use anisotropic compression as described earlier herein to generate an instance of each of compressed columns 140 and 150, and then persist those two compressed instances into an instance of file 130. Multiple (e.g. distributed) instances of file 130 may each be an individual low level file that operates as a partition or shard of a single huge dataset such as for Parquet and/or HDFS.

3.0 Example Additional Activities

FIG. 3 is a flow diagram that depicts computer 100 performing additional activities for working with dependent and independent columns, in some embodiments. FIG. 3 is discussed with reference to FIGS. 1-2.

Steps 302A-C generate an interdependent pair of uncompressed columns. Step 302A parses text values into typed values. For example, raw text values may be generated by tokenizing a text document as described earlier and later herein. In one embodiment, datatypes of parsed values are indicated in a schema-on-write schema as discussed later herein. In another embodiment, a typed (i.e. parsed) value may be a composite of: a binary identifier of a type, and a binary value for that type. For example, a first byte or first few bits of the composite may be reserved for the type identifier, and the remaining bits or bytes may be reserved for the value.

Original parsing in step 302A is an activity for schema-on-write. Thus, step 302A uses a schema, which is metadata. During various steps in FIG. 3, computer 100 accumulates (i.e. generates without flushing to file 130) primary metadata that describes independent column(s) and secondary metadata that describes dependent columns. The schema becomes part of the primary metadata. Metadata storage is discussed later herein.

Step 302B stores the parsed (i.e. typed) values into uncompressed independent column 110. Parsed values may be homogenous (e.g. all integers) or heterogenous (e.g. integers, floats, dates, times, etc). For example and according to a schema, there may be many compressed and uncompressed columns for values segregated (i.e. homogenous) by datatype or by field. For example, weight and cost fields may have a same numeric datatype, but there may be one column for weight and a different column for cost.

In the case of a heterogenous parsed column, value widths (i.e. amount of bytes) may vary. For example: a) all integers may have a first fixed width, b) all floats may have a second fixed width, but c) first and second widths may differ. Parsing may leave some values unchanged. For example, a string literal has a same value before and after parsing. Each string literal may have its own width. An embodiment may impose a maximum string literal width.

Step 302C stores the raw text values, as discussed for step 302A, into uncompressed dependent column 120. Such strings may: a) be null terminated, b) have expressly indicated respective lengths, or c) be padded (i.e. aligned) to a fixed length.

Steps 304A-B and 306 entail compression and, depending on the embodiment, some metadata generation. Step 304A performs independent column compression, such as previously shown step 202. Step 304B performs dependent column anisotropic compression, such as previously shown step 204.

When uncompressed independent column 110 has multiple dependent columns, such as progressively severe redactions as explained earlier herein, then step 206 applies anisotropic compression to any additional uncompressed dependent columns. For example, a second compressed dependent column is generated from a second uncompressed dependent column.

At each of steps 304A-B and 306, metadata for a respective column may be generated, such as statistical metadata. For example, analyzing parsed values may yield statistics such as minimum, maximum, and mean values. Analyzing unparsed (i.e. raw text) values may yield statistics such as a count of distinct values or a most frequent value. Such statistical metadata is added to either the primary metadata or secondary metadata depending on whether the statistics regard an independent or dependent column.

Writing file 130 occurs during steps 308A-D that may need to occur in the shown ordering, depending on the embodiment, especially such as a Parquet embodiment. The ordering of steps 308A-D may reflect constraints on the internal structure of file 130, such as imposed by Parquet. For example, Parquet requires that the primary metadata (i.e. for independent columns) be placed in a standard footer at the end of file 130.

When the ordering of steps 308A-D is respected, a well formed Parquet file may be written, even if a write once or append only filesystem is used. Some non-Parquet embodiments may necessarily or optionally reorder steps 308A-D. Details of the Parquet file format are presented in related paper “APACHE PARQUET”.

Step 308A stores content of independent column(s), which may be any (compressed or uncompressed) column(s) not generated by anisotropic compression. Thus, step 308A does not store dependent columns. Columns stored during step 308A are recognized as columns by Parquet. For example, any standard Parquet reader may read any columns written during step 308A. In that sense, columns written during step 308A are backward compatible.

During steps 308A-B more of the primary and secondary metadata, as introduced for steps 304A-B and 306, may be accumulated (i.e. generated but not flushed to file 130), such as metadata that describes how column content and secondary metadata is written into file 130. For demonstrative purposes, mapping of data and metadata into file(s) is discussed with an example mapping of relational tables to Parquet files as follows.

A relational table (not shown) may have unredacted (i.e. independent) columns and redacted (i.e. dependent columns). A Parquet file may more or less have any size. Thus, all of the independent and dependent columns may be stored into one file 130.

With shredding (i.e. vertical partitioning) each independent column or disjoint (i.e. non-overlapping) subset of independent columns may be written to a separate file 130. Shredding accelerates subsequent analytics because unused columns can be left idle on disk. A dependent column is always written to a same file 130 as the corresponding independent column, and each independent column may have multiple dependent columns. For example, compressed dependent column 150 should reside in a same file 130 as compressed independent column 140.

With sharding (i.e. horizontal partitioning) each disjoint (i.e. non-overlapping) subset of (e.g. adjacent) rows is written into a separate file 130. Sharding facilitates horizontal scaling such as with a cluster of computers. Sharding also accelerates subsequent analytics such as with predicate pushdown. With sharding, records (e.g. documents or table rows) are segregated such as by creation date or by field value.

Data within each file 130 is divided into pages that are tracked in the metadata that computer 100 generates for each file 130. Thus, during steps 308A-B, the primary and/or secondary metadata respectively records which pages of file 130 contain which independent or dependent columns. Step 308B appends content of compressed dependent column(s) into file 130, which may entail a similar layout as step 308A, except on later pages in file 130.

By the end of step 308B, all columns have been stored in file 130, and writing metadata into file 130 may begin. Step 308C appends the secondary metadata, including a manifest of pages used by step 308B, into file 130.

Step 308D appends the primary metadata, including the schema and a manifest of pages used by step 308A, into file 130, which may be formatted as a standard Parquet file footer that can be fully understood by any Parquet reader (i.e. backward compatibility). However, the primary metadata does not include: a) the manifest of pages used by step 308B, which was already written as secondary metadata by step 308C, nor b) a manifest of pages used by step 308C, which means that pages used by step 308C are unaccounted for. Thus, the secondary metadata appears to legacy Parquet readers as wasted (i.e. unused) space in file 130.

Thus, the secondary metadata is hidden from legacy readers. Likewise, because the secondary metadata contains the manifest of pages used for dependent columns by step 308B, the pages for the dependent columns are also hidden from legacy readers. Thus, the dependent columns and secondary metadata are contiguous and in between the independent columns and the footer that are at opposite ends of file 130. Thus to legacy readers, the dependent columns and secondary metadata appear together as a hole in the middle of file 130. Because metadata and anisotropic compressed dependent column(s) are small, the hole is small (i.e. a few pages).

After step 308D, writing of file 130 is finished. A legacy reader may use the footer to normally access the independent column(s). A reader that is enhanced according to techniques herein may access the hidden pages. For example, the enhanced reader may use the secondary metadata to access the dependent column(s). In other words, the enhanced reader may use all of the data and metadata in file 130.

4.0 Document Regeneration from Piecemeal Storage

FIG. 4 is a block diagram that depicts an example computer 400, in an embodiment. Computer 400 uses piecemeal storage of document 410's values for eventual retrieval in flexible ways such as schema-on-read and document regeneration. Computer 400 may be an implementation of computer 100.

Document 410 may be a sequence of text characters such as a text file, a log file, a web page, a JSON or XML file, or a binary representation of text, such as a word processor file. Computer 400 tokenizes the monolithic content of text document 410 into a sequence of meaningful text values 421-423 and a sequence of more or less meaningless separator values. Text document 410 itself may contain those values as an alternating sequence of text values and separator values as shown. For example, a comma separated values (CSV) file may store text values separated by otherwise meaningless commas.

A typical separator value may include one or more particular characters such as punctuation and/or whitespace. Interpretation of character(s) at a location in text document 410 may be changed from separator to meaningful text by an adjacent override indicator (not shown) such as quoting or character escaping.

Text values 421-423 are processed differently than separator values 431-432. Separator values 431-432 are directly stored as raw text substrings in uncompressed dependent column 440. For example in text document 410, a first separator is separator value 431 that is stored as a first value in uncompressed dependent column 440 as shown.

Text values 421-423 are parsed into various (e.g. primitive) respective datatypes such as integer value 461, floating point value 462, and timestamp (i.e. date and time) value 463, which are then stored in uncompressed independent column 450. For example text value 421 is parsed and stored as integer value 461 as shown.

Anisotropic compression of uncompressed columns 440 and 450 generates respective compressed columns 460 and 480 that are stored in file 470. Segregation of values in text document 410 into parsed values and separator values may facilitate analytics. For example, semantics of the content of text document 410 may be efficiently analyzed in various ways and at various times by reading only compressed independent column 460.

In any case, boundaries and classification of substrings in text document 410 entails some aspects similar to those of schema-on-write, which is fragile as explained earlier herein. For example, whether or not an XML tag such as </end> is split into three separate tokens </, end, > may depend on the implementation. For example, </ and > may or may not be classified as separators. In another example, $5 may or may not be split into a separator and a number. In another example, a zip-plus-four such as 12345-6789 may or may not be split into a base zipcode and a five character trailing separator such as −6789, which at the time of schema-on-write may be considered a useless suffix.

Classification decisions for which values are or are not separators may be fragile and not meet the needs of a future reader. For example with zip-plus-four, a future reader may decide that the plus-four suffix should not have been a suffix and, further, that the −6789 suffix is not a negative number. In that case, schema-on-read is more or less essential to support future semantics of legacy data.

Example schema-on-read activities are as follows. In a less inconvenient case, a zip-plus-four is tokenized as: a) a base zipcode as text value 421, which is then parsed into integer value 461 and, b) a plus-four suffix as separator value 431. The original zip-plus-four is not stored as a whole value in file 470, but the whole value can be regenerated by decoding values 421 and 431 from respective compressed columns 460 and 480. Thus, potentially only one or two or three values need decoding to regenerate an original value.

In a more inconvenient case, many or all values in compressed columns 460 and/or 480 may need decoding. In a worst case, text document 410 needs complete regeneration, which anisotropic decompression facilitates for schema-on-read and other purposes. For example, an audit or other presentation may expect whole text document 410 at any time in the future, even though text document 410 may have been deleted after anisotropic compression.

Thus, file 470 is a functional equivalent of original text document 410 and is enhanced for semantic (e.g. strongly typed) analytics. For example, text document 410 might not have had a schema. Whereas, file 470 may contain a (i.e. schema-on-write) schema. Thus, file 470 may be self describing even if text document 410 is not.

In that sense, persisting only file 470 (and not text document 410) may be more useful than persisting only text document 410. For example, text document 410 may be more aggressively evicted from a cache and/or more aggressively purged from a backing store. For example, regeneration facilitates not persisting text document 410 at all. Furthermore, file 470 is usually smaller than text document 410, in addition to being more useful.

5.0 Example Regeneration Process

FIG. 5 is a flow diagram that depicts computer 400 using piecemeal storage of document 410's values for eventual retrieval in flexible ways such as schema-on-read and document regeneration, in an embodiment. FIG. 5 is discussed with reference to FIG. 4.

Step 501 tokenizes text document 410 into separator values 431-432 and text values 421-423 as discussed above. Step 502 parses text values 421-423 into parsed values 461-463 that are strongly typed as discussed above. Steps 501-502 may be more or less combined such as with a scanner/parser library such as Lex with yet another compiler compiler (YACC).

Step 503 stores parsed values 461-463 into uncompressed independent column 460. In an unshown embodiment such as with Google Dremel, parsed values are segregated by field and/or type. For example, the three parsed values 461-463 may be segregated into three different homogenous uncompressed independent columns (not shown). Field processing for Parquet with Dremel is discussed further in related paper “DREMEL MADE SIMPLE WITH PARQUET”.

Step 504 stores separator values 431-432 into uncompressed dependent column 440 as discussed above. Additional activities (not shown) occur between steps 504-505. These additional activities include writing file 470, possibly deleting document 410, and receiving a request to retrieve document 410. That request may cause step 505.

Step 505 regenerates document 410 by decompressing both of compressed independent column 460 and compressed dependent column 480. Decompression regenerates parsed values 461-463 and separator values 431-432. Parsed values 461-463 are then rendered as text values 421-423. Text values 421-423 and separator values 431-432 may then be interleaved (i.e. alternated) as shown for document 410. In that way, document 410 is regenerated.

6.0 Security

FIG. 6 is a block diagram that depicts an example computer 600, in an embodiment. Computer 600 increases security by hiding an encryption key needed to read an encrypted column. Computer 600 may or may not be an implementation of computer 100.

As explained earlier herein, anisotropic compression is suited for redaction, which increases privacy and security. Compressed column(s), such as 640, are stored in file 630. Any compressed column, whether dependent or independent, may be encrypted for increased security. In an important use case: a) compressed column 640 is an encrypted independent (i.e. unredacted) column, b) a compressed dependent (i.e. redacted) column (not shown) may or may not be encrypted, and c) if both compressed column are encrypted, then each is encrypted with a separate key.

Depending on the embodiment, an encryption key (e.g. 620 or 670) may be a symmetric key such as advanced encryption standard (AES), an asymmetric key such as Rivest Shamir Adleman (RSA), and/or an elliptic curve (ECC) key. When key 620 and/or 670 is asymmetric, then that key may be a public or private key, depending on the embodiment. In some asymmetric embodiments such as shown, a particular public key (not shown) is used for encryption of compressed column 640, and private key 670 is used for decryption of compressed column 640.

In the shown embodiment, at least two keys (i.e. 620 and 670) are needed to decrypt compressed column 640. In the shown embodiment, a DBMS (not shown) mediates decryption as follows. To the DBMS, a client (not shown) may send read request 610 that contains a credential of a user or a role, such as public key 620. The DBMS may use public key 620 to decrypt encrypted private key 660 that is stored in metadata 660 in file 630. By that decryption, the DBMS obtains decrypted private key 670 that the DBMS uses to decrypt compressed column 640.

In an embodiment not shown, public key 620 is not contained in read request 610, but is instead hidden in the DBMS itself. For example, the DBMS may contain public keys that the DBMS associates with respective users or roles.

Regardless of whether a user or the DBMS keeps public key 620, file 630 contains encrypted private key 660 in metadata 650. Metadata 650 may have an embedded keystore that contains multiple encrypted (e.g. private) keys. In an embodiment, file 630 may contain multiple (e.g. independent and/or dependent) encrypted columns, and the keystore may contain a different key for each encrypted column. For example, a different public key may be needed to decrypt each private key.

In another embodiment, subsets of private keys (e.g. for different encrypted columns) are encrypted together, such that public key 620 may decrypt the subset of private keys to gain access to multiple encrypted columns. For example, public key 620 may be associated with a role that has access to the subset of encrypted columns. For example, different roles may have different public keys that decrypt different (e.g. overlapping) subsets of private keys for different (e.g. overlapping) subsets of encrypted columns.

Depending on the embodiment, such mapping of roles or users to encrypted columns may or may not be fragile (i.e. broken by evolving security needs). For example, access to a particular encrypted column may eventually be granted or revoked for a particular user or role. In a robust (i.e. not fragile) embodiment, which encrypted columns are grouped into which subsets may be redefined by replacing (i.e. overwriting in metadata 650 in file 630) an old version of a keystore with a new version.

For example, the new version of the keystore may add or remove a role or a user and/or add or remove an encrypted column from a particular subset. Generating the new version of the keystore does not require: changing which compressed columns are encrypted, nor generating or discarding a key.

Thus, keystore evolution may adjust metadata 650 without disturbing any compressed columns in file 630. Thus, the new version of the keystore may be quickly imposed without overhead (e.g. latency) of reprocessing compressed column(s). In other words, content as originally recorded (i.e. compressed and encrypted) remains valid despite evolving security.

7.0 Example Security Process

FIG. 7 is a flow diagram that depicts computer 600 increasing security by hiding an encryption key needed to read an encrypted column, in an embodiment. FIG. 7 is discussed with reference to FIG. 6.

In metadata 650, step 701 stores encrypted private key 660 for decrypting encrypted column 640. For example, metadata 650 may contain an embedded keystore that associates encrypted private key(s) with encrypted column(s).

In file 630, step 702 stores encrypted column 640 and metadata 650. Because a standard Parquet file footer (not shown) does not accommodate a keystore, metadata 650 is not stored in the standard footer, but is instead stored in the hidden (i.e. secondary) metadata as discussed earlier herein. After step 702, writing file 630 finishes, and file 630 is ready to use.

Step 703 receives request 610 to read encrypted column 640. Based on file 630 and public key 620, step 704 generates decrypted private key 670 by decrypting encrypted private key 660. Depending on the embodiment, public key 620 resides either in read request 610 or in a DBMS (not shown) that is hosted on computer 600 for managing whatever dataset (not shown) that file 630 is part of. For example, the DBMS may use an identity of a user that sent read request 610 or an identity of a role of that user to look up public key 620 such as in a lookup table or database dictionary that is part of the DBMS.

Step 705 executes read request 610 by using file 630 and decrypted private key 670 to decrypt encrypted column 640. Thus, read request 610 has access to the content of encrypted column 640.

8.0 Example Parquet Implementation

The following is an exemplary implementation of techniques herein. This particular implementation is based on Parquet and Thrift as introduced earlier herein. Some possibly optional features of this implementation are based on Oracle and Dremel as introduced earlier herein.

8.1 Column Store and Apache Parquet Relationship

Regardless of whether or not a standard Oracle DBMS includes a column store, this implementation has a DBMS that operates a column store for persistence of data columns in Parquet files that are enhanced as discussed above and below herein. The column store file format is based on the Parquet file format, and is fully compliant and therefore backward compatible with Parquet. The features of the column store are delivered using the column store extra data stored in spare pages within Parquet containers.

Parquet is a Columnar (i.e. column major, column vector) data format that is popular in the Hadoop community. It is strictly a Schema-on-Write format, and relies in ahead-of-time ETL. Therefore, Parquet is not capable of supporting Schema-on-Read. The Parquet format has optional partitioning based on data values, such that a column is grouped by value(s), and each value group may reside in its own Parquet file, in a Parquet file with other groups of a same column, or in a Parquet file having multiple columns of a same (e.g. relational) table. In an embodiment, a relational database management system (RDBMS) stores a partial, entire, or multiple column(s) of a relational table into a column vector in memory or in a columnar file.

In the innovative format disclosed herein, all of the above new features are delivered without any compromise to backward compatibility of the file. In particular, the features continue with full backward compatibility where old generation Parquet readers in the Open Source can access original features and behavior without any problems, but not new features disclosed herein.

Enhanced reader is able to engage the additional features, including such important features as: a) the faithful (i.e. high fidelity, lossless) unzip of row-major data is delivered while still retaining the column-major layout of the file for accelerating Schema-On-Write (SoW) queries with Columnar IO avoidance, b) the resulting single the column store file, which is capable of supporting both SoW and Schema on Read (SoR) use cases at the same time, can replace two files in storage, namely a Parquet file and a text file, and yet is only as big as either one of the two, and c) support self-auditing and provenance validation of the files by a combination of faithful unzip and digital signature validation.

Implementations herein are much more full-featured and have additional advantages compared to the Open Source solutions due to various benefits of integrating the Oracle developed Anisotropic Compression algorithms. This patent disclosure explains the particular ways in which (1) the Parquet file format has been modified and the user-requirements have been interpreted in a innovative manner so as to support the new user-visible features and (2) the particular new algorithms introduced into the Parquet implementation to successfully integrate Anisotropic Compression into a deliverable solution.

Column stores herein should not be seen as a simple enhancement of Parquet or other columnar formats. Instead it is a packaging of output from the Nymbl algorithm into the (e.g.) Parquet container format. This is done in such a way that one partition of the resulting file is virtually indistinguishable from Parquet to unmodified standard Parquet readers, thus giving rise to backward compatibility with Parquet readers. However, this similarity is merely superficial.

The output compression stream format is standard, but the compression algorithm is innovative. The compression algorithm is not standard Google Snappy (a.k.a. Zippy), but instead is Nymbl compression which implements the Anisotropic Compression algorithm and facilitates Secured data representations. However, the compressed stream output by Nymbl appears indistinguishable from a Snappy produced stream to an unmodified Parquet reader, which gives rise to the backward compatibility.

There is a second partition of the file which is typically hidden from standard Parquet readers. When the second partition is used in combination with the first partition, innovative technologies herein may engage.

Due to the compression innovations from Nymbl, the hidden extra Enterprise Partition is very space efficient. The total of the the column store file comprised of the two partitions (i.e. the Parquet partition for Columnar Schema-on-Write plus the enhanced Extra partition containing Unzip, Schema-on-Read, and Secured data capabilities) does not typically exceed the size of the original source file that the two are derived from.

The sections that follow describe the wire-format and layout of the column store file, its compliance with Parquet layout for perfect backward-compatibility, and the additional data and meta-data that is required to unlock the new features.

8.2 Column Store Modes of Access

A column store file can be accessed in one of three different modes:

- Mode A: or Standard, Parquet backward-compatible Schema-on-Write mode. In this mode, the functionality provided is indistinguishable from standard Parquet readers. It uses standard Parquet wire encodings and standard decompression libraries (even though the data streams might have been compressed using the Nymbl compression algorithm, the resulting compressed stream is fully backward compatible).
- Mode B: or Enhanced Schema-On-Write mode. In this mode, the additional representations are unlocked by using the enhanced Nymbl decompressor, instead of the standard de-compressor library. This mode also supports unlocking Secured representations (ie. “un-redacted” or “un-masked” data) if the query has the correct security credentials and is able to provide the requisite keys as discussed later herein.
- Mode C unzip: unzip mode, is a special case of Mode C access, where the entire file is decompressed to faithfully reconstruct the original source file.

Mode B and Mode C are typically engaged only by column store readers, while Mode A (i.e. backward compatibility) can be accessed equally both by column store readers as well as all existing Parquet readers.

8.3 NYMBL Anisotropic Compression Overview

Anisotropic Compression is an innovative enhancement of the standard compression algorithms, developed at Oracle. In anisotropic compression, multiple (i.e. plurality of) data streams are compressed simultaneously; compare to standard compression algorithms which only compress one data stream at a time. In the cases where these multiple streams to be compressed are related to each other, or even are in fact derived from each other, then anisotropic compression is able to compress these multiple streams into a resulting disk footprint which is not much bigger than the disk footprint occupied by the compressed image of any one of the plurality of input streams to be compressed. Thus, for Nx different representations or encodings of the same logical data, the footprint after anisotropic compression is of the order of 1×, i.e. of the compressed size of any of the representations or encodings, and not N of them. That is a linear improvement of effective compression ratios and consequent reduction of disk footprint and storage recurring and life-cycle maintenance costs.

For the purpose of this disclosure, it suffices to consider the above summary of anisotropic compression and observe one specific requirement of anisotropic compression algorithm which is not present in regular compression algorithms. This is the requirement that in anisotropic compression, each data stream, or buffer, is also required to provide a method or mechanism for atomization of the buffer or stream so that shared entropy can be correctly and efficiently extracted during compression. The specific manner in which this atomizer function is implemented in the context of Parquet data types and encodings is one subject matter of this disclosure.

Anisotropic Compression itself and related algorithms are disclosed in related US patent application “Entropy Sharing Across Multiple Concurrent Compression Streams” that is cited above. In this particular disclosure, the innovation is the manner in which Anisotropic Compression has been adapted so that the above discussed goals of column store files may be fulfilled.

Nymbl is a new and improved compression algorithm that is used in the column store. Nymbl is a new algorithm, but not a new compression format. Nymbl produces an output stream that is exactly compatible with industry standard compression algorithms including snappy, zlib/gzip, or zstd. Nymbl compression may be a foundation over which different features of the column store are implemented, such as: multiple representations (for CPU speedup for SoW queries), and fine-grained file based access control (for role-based access control, redaction, and masking). Nymbl differs from traditional compression algorithms in one very important way. Traditional compression algorithms take in one source stream and produce one output stream that is compressed to a fraction of the size of the source stream. Nymbl instead takes a set of N related source streams, and produces an output stream which has one primary and (N−1) secondary or dependent streams. The primary compressed stream is perfectly wire-compatible with standard compressed formats, and can be read and decompressed by any standard decompression library.

The secondary streams are typically very small in size and add very little to the total size of the compressed stream compared to the compressed size of just the one primary stream. Essentially, N streams may be compressed into a space that is not much bigger than that required for compressing just one stream. This is true for all streams that are related and for all data that has typical compression ratios that are encountered in database workloads. This property of Nymbl is where significant space savings and compression benefits of the column store arise from.

8.4 Enhanced Features Delivered with No Compromise of Backward Compatibility

Metadata is encoded in an innovative way. The Parquet metadata and file layout has been modified such that complete backward compatibility is unconditionally maintained. Older generation readers will notice no difference from older format files and will deliver no more than older functionality. New enhanced reader software can engage the new features and deliver new functionality. At the same time, only one copy of the data is in the file even though the file has two distinct facets, behaving almost as though it were two files one of each format, and yet, the size of the one resulting combined file is no bigger than the larger of the two original files.

The column store metadata is placed in a new footer that immediately precedes the standard Parquet footer that is at the end of the file. The way this placement results in this enhanced footer being invisible to the standard Parquet reader. This footer in turn opens up access to other data pages in the file which are therefore not accessible from the standard primary footer. Thus, a hidden partition in the file is created, which is hidden in the sense that it is not even visible to the standard Parquet reader. This ensures complete backward compatibility of the file with existing Parquet readers in the Open Source. At the same time, by chasing and following the pointers from the hidden enhanced footer, the Enhanced reader is able to access all the extra “Enterprise” data pages and unlock the new features.

8.5 Atomization Based Compression

Novel buffer atomizer methods required by Anisotropic compression are integrated into buffers with Parquet data types in an innovative way. This enables multiple features, not only those discussed above, but also improved compression ratios and: a) on-disk materialization of Oracle Numbers for negligible additional disk footprint, b) redaction, column, row and field based fine-grained server-less in-file access control with negligible additional disk footprint, and c) grantable and retractable role and user-based access privileges to file data, without any file re-writes. Atomization occurs during compression, which needs raw values emitted by atomization. Each atom of raw data is extracted according to its Field width, but no field type is imposed (i.e. raw bits are uninterpreted).

For each column of data, whether it is in the primary/open Parquet partition or in the secondary/hidden Enterprise partition, anisotropic compression is used in such a manner as to allow each column to support multiple representations. This is done such that it is without change to the user schema. The existence of the additional representations does not foist upon the user additional superfluous or duplicated columns. The number of logical columns does not change. And also, it is important to note that the disk footprint of that column after compression is also substantially same. Instead, when a column data is uncompressed, depending on who is requesting the data, entirely different representations, encodings, or redacted and unredacted values may be returned from the same disk footprint.

Anisotropic Compression requires an annotation of the data buffer with an atomizer method. The way this method is implemented is such that it returns to the caller the necessary field and value boundaries in an inexpensive manner, without incurring additional CPU overhead. This has been innovatively done specifically for the particular data encodings in Parquet. For int32, int64, int96 and float, the atomizer function returns a constant offset unpacking plan, which is determined by the offset of the data type. For strings and binary data, the atomizer returns an offset and length operator in a manner suitable for use by the Anisotropic Compression algorithm. This integration is specific to Parquet data types such that Anisotropic Compression can actually be successfully integrated into Parquet.

8.6 Progressive Privacy

Redaction and Tokenization algorithms which allow the customer/user to select the tradeoff between complexity and security needed. This includes: a) simple redaction based on pattern substitution, and b) tokenization using an external service, which allows for secured reversibility by privileged users.

Depending on user specification, if any column redaction is specified, then an algorithm applies security and access control to all other representations of the same column. Note that since redaction is a “negative feature”, it removes something from the data, as opposed add new information, the “addition” of redaction to a column creates a representation which is poorer (i.e. lossy), and only the original representations need to be fully protected.

A major innovative aspect of the integration in this disclosure is an algorithm that from a simple user specification of redaction, which is expressed in declarative logic, an operational, imperative, and optimized plan is derived for which paired alternative representations would be actually secured.

In an innovative way, the user declares an external open database connectivity (ODBC) service, such as a Java database connectivity (JDBC) service, that can be used to maintain a persistent tokenization and de-tokenization logbook that records which naturally occurring identifiers within payload data are assigned which unique tokens for anonymization (i.e. privacy). This logbook mechanism is advantageous compared to all other mechanisms because it results in consistent and repeatable tokenization which can be simultaneously secure as well as reversible in a consistent manner when different files are written and read by different instances of writers and readers in a cluster or distributed data-center. For example, an opaque text or integer token may replace a sensitive personally identifiable field value such as a person's name, social security number, and/or postal address. That token can be globally (i.e. across multiple parquet files and/or external silos) used as a substitute identifier or relational key, such as a primary or foreign key.

8.7 Tamper Resistant Provenance

The enhanced metadata has a Provenance record with digital signatures and information of the ingest process and parameters. A digital signature uses asymmetric cryptography to provide creator authentication, non-repudiation, integrity (i.e. tampering detection). An embodiment may use the standard digital signature algorithm (DSA) or other digital signing techniques based on underlying technologies such as cryptographic hashing, cyclic redundancy code (CRC), checksum, and Rivest-Shamir-Adleman (RSA). Embodiments may sign payload data, metadata, or portions thereof.

8.8 Apache Parquet Standard File Format

Parquet is a hybrid-columnar file format optimized for big-data applications in the Hadoop ecosystem. Parquet is typically used with (and optimized for) a Hadoop filesystem (HDFS) or Cloud Object Stores. The Parquet file format is documented in the Apache Project pages. https://parquet.apache.org/documentation/latest/. The entire format described in the Parquet documentation is consistent with the column store, and therefore is incorporated here by reference. A brief synopsis of the Apache specification follows.

The file starts with a 4 byte magic string, in US-ASCII, with the value “PAR1”. Likewise, the file also ends with the same 4 byte signature, in US-ASCII, again with the value “PAR1”. Parquet files commonly reside in HDFS and Object Store file systems which are append-only, write-once, read-many file systems.

These file-systems typically do not allow a writer to seek backwards in the file during write. Therefore, Parquet has made the choice to write the metadata, which is traditionally written in a file header, instead into a file footer. Details of the Parquet file format are presented in related paper “APACHE PARQUET”.

8.9 Apache Parquet Metadata Block

The last and second to last words in the file each consist of four bytes. The second to last word from the end of the Parquet file, just before the four byte magic-number signature (“PAR1”), specifies a length of the file metadata.

Continuing in the order from the end of the file backwards to the beginning, the file metadata block then immediately precedes the file metadata block length word. A typical Parquet reader would open the file for reading in the following manner.

- 1. The reader seeks to the end of the file, to first verify the signature word “PAR1”.
- 2. The reader reads the next word of four bytes, and interprets that as an integer, giving the length of the metadata block.
- 3. The reader seeks backwards in the file by that many bytes, and reads the file metadata block.

All of this behavior is retained exactly so also in the column store, both in the location of the footer metadata, and also in the very fact that the primary footer is exactly a Parquet footer and no more, and no different.

The file metadata contains a Thrift encoded structure which details the schema with which the file was ingested, and pointers to the offsets of the column chunks within the file for each leaf in the schema. A leaf is any field in a schema that has a primitive type (i.e. not compound). The schema in Parquet allows hierarchical structures, and also allows elements in the schema to be either required or optional. Encoding of nested columns, such as for hierarchical content, is further discussed in related paper “DREMEL MADE SIMPLE WITH PARQUET”.

Parquet only supports a-priori fixed depth and shape of nesting, as this is limited by the ahead-of-time declared schema for the file. Therefore the number of leaves of the schema, and hence the number of columns are also fixed and strictly enumerable a-priori.

8.10 Apache Parquet Row Groups

Payload data in a Parquet file is organized into a series of rows in the given schema. The rows are logically concatenated with an implicit order, though generally no semantics is specified in the standard about the row-order. Rows in Parquet are grouped into Row Groups, such that all the data for each Row Group, for each Column Chunk within that Row Group, roughly fits into an expected Page Size.

The Page Size is typically matched to the expected block size in the underlying HDFS or other file-system, which is typically 64 MB, 128 MB, or 256 MB. This match is closely (but not strictly) honored, though there is no requirement for it to be exactly so for all row-groups. During Row Group assembly, the size of the currently accumulated and compressed Pages are tracked and the Row Group is closed when the Page sizes reaches the specified target threshold which matches the expected block size of the underlying HDFS file system.

8.11 Apache Parquet Column Chunks

Each Row Group contains a number of Column Chunks, one for each Column in the data. A Column in the data typically corresponds to each potential leaf in the schema associated with the data. This schema is known a-priori, during ingest time, and is embedded into the metadata in the file. That makes Parquet a purely Schema-On-Write file format, along with the fact that the data values are also binary encoded. This makes Parquet a “post-ETL” file format, and therefore cannot be used to support any Schema-On-Read queries or “unzip to original”, since the ETL process (in particular the E and T stages, or Extract and Transform) is information lossy, and discards parse information from Extract (including key order for key-value pair data, such as JSON) and pre-Transform original textual data representations.

A Column Chunk consists of a series of Pages, each Page roughly corresponds to the target Page Size. Each Page in a Column Chunk starts with a Page Header, and a concatenation of three blocks of data. They are the Repetition Level, Definition Level and a block containing all the Values (i.e. payload). Repetition Level and Definition Level data are optional and specified in the schema. The Values block is always required.

If a column is not nested (i.e. the path to the column has length 1), Parquet does not encode the repetition levels (it would always have the value 1). For data that is required, the definition levels are skipped (if encoded, it will always have the value of the max definition level). For example, in the case where the column is non-nested and required, the data in the page is only the encoded values.

The Column Chunk may be a concatenation of a series of Pages. Each Page is a unit of IO (e.g. disk block) and can be individually tracked from the metadata. Thus, Pages that are not required need not be read from disk. The metadata also can optionally contain storage indices, namely Minimum and Maximum Statistics for the actual values for that Column Chunk. In an embodiment, this applies only for Columns which have numeric data. This can be used to decide whether that Page has any Values that are in the range of interest for a given query, assuming such query pushdown is available.

8.12 Column Store Enhanced Partition

A major innovative aspect about the column store file wire-format involves an observation about Parquet format that supports introducing safely hidden extra pages. This is derived from the above structure of the Parquet file format, which allows that Padding is permitted in a Parquet file. Though most Parquet writers do not appear to introduce deliberate padding, however, all Parquet readers fully support such padding since their operation is strictly bound to the pointers in the Parquet footer. For example, a standard Parquet reader simply skips (i.e. ignores) padding.

The column store file contains a partition of column store extras. This extra column store metadata is hidden from the Parquet readers by using an auxiliary metadata structure.

The column store extra partition is a logical entity which is dispersed among normal Parquet Column Chunks; it is not necessarily a physically contiguous extent of the file in terms of byte ranges. Typically, the column store pages that correspond to the rows in a particular Parquet Row Group would be found co-located with the Pages that contain the Parquet Column Chunk for that given Row Group.

However, all the column store Pages and Column Chunks can only be accessed by following the offsets and pointers in the column store metadata footer. There are no pointers in the Parquet metadata footer which can point to any of these column store data Pages; therefore these Pages remain completely hidden, and might only superficially appear to a standard Parquet reader essentially as orphaned or unreachable and dead padding Pages within the Parquet file, which a standard Parquet reader can simply ignore.

The column store metadata is a strict superset of Parquet metadata; everything in the Parquet metadata is duplicated in the column store metadata, while the schema is extended by one more level and additional information is also added.

In an embodiment, the Parquet feature set and the column store feature set are kept completely separate. In another embodiment, the column store metadata is merged into Open Source Parquet metadata, and the two features sets can be combined and/or harmonized.

8.13 Apache Parquet Standard Partition

The Parquet Standard Partition consists of all the Column Chunks, and therefore Pages, which are reachable from the Parquet metadata footer. It does not include any of the byte ranges which are not reachable from the standard Parquet metadata footer. This partition strictly follows, without restriction, all the rules of standard Parquet encoding described in the section above. For Mode A access, i.e. standard mode backward-compatible Schema-on-Write access of data in a column store file, the Parquet partition suffices completely. It is read and serviced in the standard way, as in Parquet.

8.14 Column Store Enhanced Partition

The set of Column Chunks, and therefore Pages, which are not reachable from the standard Parquet metadata footer, but are in fact reachable from the column store metadata footer, constitute the logical column store partition. The column store partition is essential for Mode B (enhanced Schema-on-Write) and Mode C (unzip) access. However, it must be noted that the column store partition is not standalone, and it alone cannot be used for enhanced access. It is always used in addition to portions from the Parquet partition.

A major innovative aspect of column store arises from how Anisotropic Compression is used to eliminate redundancy between the Parquet partition and the column store partition. This means that the resulting file size is not a doubling of the file, counting the Parquet partition supporting Schema-on-Write, and the column store Extra partition supporting unzip and Schema-on-Read. Instead the resulting file is typically only about the same size as the original text file compressed using a comparable algorithm.

Anisotropic compression is innovatively applied between Parquet columns and those column store representations which they are paired with. This technique is used effectively so that any information (more specifically information entropy) that is already contained in the Parquet partition is not duplicated in the column store Extra partition.

Therefore, decompressing a page from a secondary or dependent column store Extra partition may require that the corresponding primary compressed stream from the Parquet partition be accessed as well. While this is an additional Page of data being read, the total amount of data blocks read from disk is roughly the same as the number of data blocks read from disk if the secondary representation were to be natively compressed as a single representation in a comparable standard compression codec.

8.15 Column Store Row Groups

Column store Row Groups are identical as, and one-to-one aligned with, Parquet Row Groups. The column store introduces additional Column Chunks for the same set of rows in any given Row Group. These additional Column Chunks are in the column store Extra partition and are hidden from the Parquet partition. These additional Column Chunks do not necessarily contain new Columns. Instead they typically contain additional secondary representations of the same Columns whose primary representations are in the Parquet partition. These secondary representations are compressed using Nymbl, and they are typically very small since they are dependent on the primary representation (which might be snappy compression format) in the Parquet partition.

It is permissible that a Representation in the column store partition does not have any primary representation in the Parquet partition. This would happen when a Column has not been ingested according to the Parquet schema, but still belongs to the column store schema, (which is a superset).

In general, by default, every Column in the Parquet partition would have at least one paired Representation in the column store partition which is the original text fragment from which the value was converted. This applies no matter what integer or other binary format the text fragment has converted into during Transform step of ETL in Parquet ingest. This representation is named the “zipzag” representation.

Innovatively, by default, there would always be found a “zipzag” representation for every column, and in fact every parseable leaf in the source file. Further, it is always the case that every octet in the source file is always to be found in one, exactly one and only one “zipzag” stream in the column store partition. The unzip and Schema-On-Read functionality is built upon this invariant assertion. However, the zipzag stream when compressed by Nymbl can potentially have a very small disk footprint since Nymbl shares entropy in this compression stream with the entropy in the primary representation already in the Parquet partition.

Note that it is permitted for the user to disable (i.e. prevent) the “zipzag” representations during ingest. Such a column store file would not be capable of Mode C (Schema-on-Read and unzip) access. Mode B or enhanced Schema-on-Write access would still be possible if additional binary representations (such as Oracle Numbers) are encoded. However, this is also optional. If both the above are absent, then the column store file is exactly identical in features and capabilities to Parquet (except perhaps there is an additional vestigial and likely useless metadata in the footer).

8.16 Column Store Extra Column Chunks

Column store Extra partition contains additional Column Chunks. As explained above these may or may not be dependent on corresponding primary Column Chunks in the Parquet partition.

8.17 Columns and Representations

Column store defines Columns and Representations in a specific way. Columns are vertical projections on fields in ingested data, which is in the context of some specified ingest Schema, being applied as Schema-On-Write. A Column is specified in the user schema, and is also a property of standard Parquet. Representations on the other hand are (rules or types for) concrete encodings of Field Values of a Column. For example, Parquet native data types such as int32 are representations, while the zipzag stream which contains the corresponding source text fragments is another potential representations of the same column. Oracle Numbers might be another common representation.

Typically, different Representations of one single Column are expected to be actually derived from one another, or very closely related to each other. But this is not a mandatory requirement, and can be violated without functional failures, but still it is a common and useful thing to do. Furthermore, Anisotropic compression with Nymbl gives high compression ratios only in such cases, because the relationship assures a high certainty of shared entropy between the different representations which are being compressed together.

8.18 Zipzag Representations

Zipzag Representation chunks are typically secondary to their corresponding primary column Representation in the Parquet partition. It is possible for the primary (ie parent) of a Zipzag Representation to be another representation in the column store partition. This would occur when some column is included in the column store schema, but not included in the Parquet schema. The other direction is not possible, because the column store schema is a strict super-set of the Parquet schema; any column in the Parquet schema is always present in the column store schema in one or more representations. The Zipzag representation is encoded in the wire content as a Parquet binary data type, or string type.

8.19 Chaff Column

Chaff is defined as the “junk” that is present between useful values in the original file. It is typically discarded by the Extract step in ETL processing during typical ingest. But in the column store, it is typically saved because it might not be chaff or junk from the point of view of the query schema during Schema-on-Read, and is certainly required for unzip. The Chaff Column is its own primary (parent). It typically does not have any secondary associated with it. The Chaff column is the same type as the Zipzag Representation of all other user Columns, i.e. Parquet Binary or String type.

8.20 Oracle Numbers Representation

Oracle number representation may be natively supported in the column store partition. Typically, it is expected than an Oracle Number representation would be a secondary to a corresponding primary representation in the Parquet partition, which might be encoded as one of the numerical types, INT32, INT64, FLOAT, or DOUBLE. Typically INT96 is used in Parquet only for timestamps, and there it typically maps to Oracle Date in the column store. But this is not mandated; indeed it is permissible for a secondary representation of any primary representation, even INT96 to be any type, even Oracle Number, or strings or indeed anything else without restriction.

The Precision and Scale of Oracle Numbers used during ingest in the column store is written into the annotation of the metadata.

The rounding properties of Oracle Numbers presents an interesting choice. Since Oracle Numbers has different numerical error, rounding, and truncation properties than any of the Parquet numerical data types (INT32, INT64, INT96, FLOAT, or DOUBLE), there exists a choice on how to handle this divergence. This choice depends on the user requirements. This is supported using additional informative annotation tags.

8.21 Oracle Dates Representation

Oracle Dates is an Oracle proprietary and powerful format for representing date stamps and time stamps. It would be commonly paired with INT96 in the Parquet world, which is commonly used for timestamps.

8.22 Secured Representations

The Nymbl compressed streams can be optionally encrypted. The encryption algorithm may be AES-128 or another encryption algorithm. User supplied implementations of AES-128 can be supported. In an embodiment, such as for special government customers, custom encryption algorithms can be supported. These representations are called Secured Representations.

8.23 Redaction, Masking, Tokenization and Other Derived User Features

Any Representation that is stored in Column Chunks in the column store partition can be secured in this fashion. If this Representation is a secondary to a primary representation in the Parquet partition, which is in the clear (i.e. unobscured), then they deliver one of various privacy functionalities such as Redaction, Masking, or Tokenization.

Which of those functionalities is delivered depends on the actual transformations done during ingest to produce the primary and secondary Representations. The wire format encoding of all forms of Secured Representations is the same. In particular, the wire-format or metadata only indicates that a particular representation is a Secured Representation, and does not indicated whether it Redacted, Masked or Tokenized or any such use visible feature. However, user annotation tags can be used to store such extra information; these opaque tags are simply carried as annotations within the file for access during inventory, and do not determine the reader functionality.

8.24 Column Store Metadata

Column store Metadata is a strict superset of Parquet metadata. It effectively extends the Parquet schema by one more level, with the last level being a system determined list of representations which have been actually ingested. The metadata is encoded as a Thrift structure which can be described as follows:

/**

* File format description for the column store metadata format

*/

namespace java com.oracle.nyral.enterprise.metadata

/**

* Supported encoding types for Column store.

*/

enum EPColumnEncoding {

// Plain data (no special encoding) PLAIN = 0;

// Dictionary encoding using plain data for dictionary page. DICT_PLAIN = 1;

}

/**

* Metadata structure for a column store column representation.

*/

struct EPColumnRepMetadata {

// Per-stream version number 1: required i32 version

// Representation path name 2: required string col_path;

// Encoding type

3: required EPColumnEncoding encoding;

// Offset of the data in the file 4: required i64 data_offset;

// Total length of the data written into the file for this representation. 5: required i64

written_length;

// Uncompressed size of the data 6: required i64 uncompressed_size;

}

/**

Metadata structure for a column store column, which contains

a set of representations.

*/

struct EPColumnMetadata {

// All representations of this column

1: required list<EPColumnRepMetadata> reps;

}

/**

Metadata structure for a column store row-group, which contains

a list of columns.

*/

struct EPRowGroupMetadata {

// Compression codec used for this row-group. 1: required string codec;

// Columns in this row-group.

2: required list<EPColumnMetadata> cols;

}

/**

Metadata structure of the Column store file metadata.

*/

struct EPFileMetadata {

// File version

1: required string version;

// Ingest file information

2: required string ingest_file;

// Ingest user information

3: required string ingest_user;

// Ingest timestamp

4: required i64 ingest_timestamp;

// Ingest schema (as a nyf json) 5: required string ingest_schema;

// All ingested Column store row-groups. 6: required list<EPRowGroupMetadata> row_groups;

}

8.25 Column Store Embedded Keystore

The column store may have an Embedded KeyStore. The Embedded KeyStore acts as a layer of indirection from user credentials (i.e. public key) to AES keys (i.e. private key) used to actually encrypt the data values. As referenced herein, public and private keys may or may not be for public key cryptography such as asymmetric cryptography. The Embedded KeyStore is serialized into the column store metadata. The Embedded KeyStore contains several hooks or slots, one for each User or Role which has been granted access to the Secured Data in the file. Each slot is encrypted using the public key corresponding to that User or Role, using the RSA two-key encryption algorithm.

Each slot item in turn contains a list of AES keys for all the Secured Representations. In particular, only Keys to those Secured Representations to which that particular User or Role has been granted access to is present in that slot. The order of these Representation keys is important, as it determines the search order for opening the Secured Representations in a user-specified deterministic sequence.

In an embodiment, each data column is encrypted by its own private key. Each role or user may be entitled to access a subset of columns and thus a corresponding subset of private keys. Somewhat different subsets of private keys may overlap (i.e. contain some same private keys). Each subset of private keys is encrypted with the corresponding public key of the user or role.

9.0 Database Overview

Embodiments of the present invention are used in the context of DBMSs. Therefore, a description of an example DBMS is provided.

Generally, a server, such as a database server, is a combination of integrated software components and an allocation of computational resources, such as memory, a node, and processes on the node for executing the integrated software components, where the combination of the software and computational resources are dedicated to providing a particular type of function on behalf of clients of the server. A database server governs and facilitates access to a particular database, processing requests by clients to access the database.

Users interact with a database server of a DBMS by submitting to the database server commands that cause the database server to perform operations on data stored in a database. A user may be one or more applications running on a client computer that interact with a database server. Multiple users may also be referred to herein collectively as a user.

A database comprises data and a database dictionary that is stored on a persistent memory mechanism, such as a set of hard disks. A database is defined by its own separate database dictionary. A database dictionary comprises metadata that defines database objects contained in a database. In effect, a database dictionary defines the totality of a database. Database objects include tables, table columns, and tablespaces. A tablespace is a set of one or more files that are used to store the data for various types of database objects, such as a table. If data for a database object is stored in a tablespace, a database dictionary maps a database object to one or more tablespaces that hold the data for the database object.

A database dictionary is referred to by a DBMS to determine how to execute database commands submitted to a DBMS. Database commands can access the database objects that are defined by the dictionary.

A database command (e.g. query) may be in the form of a database statement. For the database server to process the database statements, the database statements must conform to a database language supported by the database server. One non-limiting example of a database language that is supported by many database servers is SQL, including proprietary forms of SQL supported by such database servers as Oracle, (e.g. Oracle Database 11 g). SQL data definition language (“DDL”) instructions are issued to a database server to create or configure database objects, such as tables, views, or complex types. Data manipulation language (“DML”) instructions are issued to a DBMS to manage data stored within a database structure. For instance, SELECT, INSERT, UPDATE, and DELETE are common examples of DML instructions found in some SQL implementations. SQL/XML is a common extension of SQL used when manipulating XML data in an object-relational database.

A multi-node database management system is made up of interconnected nodes that share access to the same database. Typically, the nodes are interconnected via a network and share access, in varying degrees, to shared storage, e.g. shared access to a set of disk drives and data blocks stored thereon. The nodes in a multi-node database system may be in the form of a group of computers (e.g. work stations, personal computers) that are interconnected via a network. Alternately, the nodes may be the nodes of a grid, which is composed of nodes in the form of server blades interconnected with other server blades on a rack.

Each node in a multi-node database system hosts a database server. A server, such as a database server, is a combination of integrated software components and an allocation of computational resources, such as memory, a node, and processes on the node for executing the integrated software components on a processor, the combination of the software and computational resources being dedicated to performing a particular function on behalf of one or more clients.

Resources from multiple nodes in a multi-node database system can be allocated to running a particular database server's software. Each combination of the software and allocation of resources from a node is a server that is referred to herein as a “server instance” or “instance”. A database server may comprise multiple database instances, some or all of which are running on separate computers, including separate server blades.

9.1 Query Optimizer and Execution Plans

Generally, a query compiles a query statement and generates an internal query representation of the query statement. Typically, the internal query representation is a set of interlinked data structures that represent various components and structures of a query statement. The internal query representation may be in the form of a graph of nodes, each interlinked data structure corresponding to a node and to a component of the represented query statement. The internal representation is typically generated in memory for evaluation, manipulation, and transformation by a query optimizer.

The term query is used herein to refer to any form of representing a query, including a query in the form of a database statement or in the form of an internal query representation. A query optimizer may receive a query from another entity other than query parser, where the query received is in the form of an internal query representation.

A query optimizer generates one or more different candidate execution plans for a query. The query optimizer evaluates the one or more candidate execution plan to determine which should be used to compute the query.

Execution plans may be represented by a graph of interlinked nodes, referred to herein as operators, that each corresponds to a step of an execution plan, referred to herein as an execution plan operation. The hierarchy of the graphs (i.e., directed tree) represents the order in which the execution plan operations are performed and how data flows between each of the execution plan operations. Execution plan operations include, for example, a table scan, an index scan, hash-join, sort-merge join, nested-loop join, and filter.

Compiling a query by entail transforming the query. In general, transforming a query involves rewriting a query into another query that produces the same result and that can potentially be executed more efficiently, i.e. one for which a potentially more efficient and less costly execution plan can be generated. Examples of query transformation include view merging, subquery unnesting, filter predicate move-around and pushdown, common sub-expression elimination, outer-to-inner join conversion, materialized view rewrite, star transformation, and, join predicate push down. A query is rewritten by manipulating a deep copy of the query representation to form a transformed query representation representing a transformed query. The query as transformed is referred to herein as the transformed query; the query whose copy is transformed is referred to as the base query.

Query compilation may also perform more than one transformation for evaluation. Each transformed query generated for a query is referred to as a candidate transformed query or candidate query. A transformed query rewritten to generate another transformed query is referred to herein as a base query for the other transformed query. The query originally received by a query optimizer is referred to as the original query.

The original query an optimizer optimizes and the alternate transformed queries generated for the query are referred to individually as a “candidate query” and collectively as the “query search space.” The one or more candidate execution plans generated for each query in the query search space are collectively referred to as the “plan search space.”

Hardware Overview

According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

For example, FIG. 8 is a block diagram that illustrates a computer system 800 upon which an embodiment of the invention may be implemented. Computer system 800 includes a bus 802 or other communication mechanism for communicating information, and a hardware processor 804 coupled with bus 802 for processing information. Hardware processor 804 may be, for example, a general purpose microprocessor.

Computer system 800 also includes a main memory 806, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 802 for storing information and instructions to be executed by processor 804. Main memory 806 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 804. Such instructions, when stored in non-transitory storage media accessible to processor 804, render computer system 800 into a special-purpose machine that is customized to perform the operations specified in the instructions.

Computer system 800 further includes a read only memory (ROM) 808 or other static storage device coupled to bus 802 for storing static information and instructions for processor 804. A storage device 810, such as a magnetic disk, optical disk, or solid-state drive is provided and coupled to bus 802 for storing information and instructions.

Computer system 800 may be coupled via bus 802 to a display 812, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 814, including alphanumeric and other keys, is coupled to bus 802 for communicating information and command selections to processor 804. Another type of user input device is cursor control 816, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 804 and for controlling cursor movement on display 812. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Computer system 800 may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system 800 to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system 800 in response to processor 804 executing one or more sequences of one or more instructions contained in main memory 806. Such instructions may be read into main memory 806 from another storage medium, such as storage device 810. Execution of the sequences of instructions contained in main memory 806 causes processor 804 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical disks, magnetic disks, or solid-state drives, such as storage device 810. Volatile media includes dynamic memory, such as main memory 806. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid-state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge.

Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 802. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor 804 for execution. For example, the instructions may initially be carried on a magnetic disk or solid-state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 800 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus