Patent Description:
JavaScript object notation (JSON) is a hierarchical data specification language. A JSON object is a hierarchically marked content object that comprises a collection of fields, each of which is a field name/value pair. A field name is in effect a tag name for a node in a JSON object. The name of the field is separated by a colon from the field's value. A JSON value may be:.

The following JSON object J is used to illustrate JSON. {
"CUSTOMER": "EXAMPLE LIMITED",
"CUSTOMER TYPE": "BUSINESS",
"ADDRESS": {
"STREETADDRESS": "<NUM>99TH STREET",
"CITY": "NORTH POLE",
"STATE": "AK",
"POSTALCODE": "<NUM>"
},
"PHONENUMBERS": [
"<NUM><NUM>-<NUM>",
"<NUM><NUM>-<NUM>"
]
}.

Object J contains fields CUSTOMER, CUSTOMER TYPE, ADDRESS, STREETADDRESS, CITY, STATE, POSTALCODE, and PHONENUMBERS. CUSTOMER and CUSTOMER TYPE have string values "EXAMPLE LIMITED" and "BUSINESS", respectively. ADDRESS is an object containing member fields STREETADDRESS, CITY, STATE, and POSTALCODE. PHONENUMBERS is an array comprising string values "<NUM><NUM>-<NUM>" and "<NUM><NUM>-<NUM>". A field such as POSTALCODE may be subsequently parsed as another primitive datatype such as an integer such as for: schematic validation, storage that is compact and/or strongly typed, and/or analytics or further processing such as arithmetic.

Within object J is a containment hierarchy of nested content enclosed in shown curly braces and arranged as a sequence of hierarchical levels. For example as shown above, ADDRESS operates as both a field itself in a previous level and an aggregation of nested fields in a next level. As explained later herein, levels are used for navigation within object J such as according to a multilevel path expression for identifying a nested field. Also as explained later herein, different JSON objects in a same data store may have a same or different count of levels that contain same or different fields. In other words, JSON objects may conform to a same structural schema that reflects structural similarity, including levels and contents of levels, or may be operated in a schema-less way and have structurally dissimilar contents. Techniques for inspecting and navigating multilevel objects are presented in related <CIT>.

Efficient querying is important to accessing JSON documents. Effective approaches for querying JSON documents include schema-based approaches. One schema-based approach is the schema-based relational-storage approach. In this approach, collections of JSON documents are stored as schema instances within tables of a database managed by a database management system (DBMS). That approach leverages the power of object-relational DBMS's to index and query data. In general, the schema-based relational-storage approach involves registering a schema with a DBMS, which generates tables and columns needed to store the attributes (e.g. elements, fields) defined by the schema.

Storing a collection of JSON documents as instances of a schema may require developing a schema that defines many if not all attributes found in any member of a collection. Some or many of the attributes defined by the schema may only occur in a relatively small subset of the collection members. The number of attributes defined by a schema may be many times larger than the number of attributes of many collection members. Many attributes may be sparsely populated. Managing schemas with a relatively large number of attributes, some or many of which may be sparsely populated, can be burdensome to a DBMS and administrators and users of the DBMS.

To avoid pitfalls of using schema-based approaches, schema-less approaches may be used. One schema-less approach is the partial projection approach. Under the partial projection approach, a set of commonly queried attributes of the collection are projected and copied into columns of additional tables; these tables exist to support DBMS indexing of the columns using, for example, binary tree or bit map indexing.

Being a minimalist semi-structured data model, JSON is a de-facto standard for schema-less development in database markets. Both RDBMS vendors and No-SQL vendors have supported JSON functionality to various degrees. The current status is that most RDBMS vendors support JSON text storage as whole documents and apply structured query language (SQL) and/or JSON operators over the JSON text, as is specified by the SQL/JSON standard. However, storing whole documents makes indexing more difficult and/or less useful. For example, existing JSON indices for relational databases limit how many fields and which fields are indexed by a same index, which limits general applicability and may encourage a proliferation of indices, even for a single query. For example in above JSON object J, typical index approaches are unable to index both of CUSTOMER TYPE and STATE fields because those fields occur at different levels in JSON object J. For example, execution of a query that seeks business customers in Alaska may need to use separate indices for filtering two fields at different levels such as CUSTOMER TYPE and STATE.

Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualifies as prior art merely by virtue of their inclusion in this section.

The manual by <NPL>, describes the use of JSON data that is stored in Oracle® Database. The manual covers how to store, generate, view, manipulate, manage, search, and query such data. According to one particular aspect, indexing multiple fields of a JSON object involves creating a composite B-tree index using multiple path expressions with SQL/JSON function json_value or dot-notation syntax.

Due account is to be taken of any element which is equivalent to an element specified in the claims.

In other instances, structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Techniques herein operate a multi-value, multi-field, multilevel, multi-position functional index over hierarchical data objects stored in a single column of a database table in a relational database management system (RDBMS). Hierarchical data objects may contain nested structures and arrays that are indexed in novel ways and novel granularities. For example, a multi-value, multi-field, and multi-level index may have two index keys, a first that is a field at one level and a second that is an array element at a position within the array.

Included herein are enhanced data definition language (DDL) for index creation and data manipulation language (DML) rewrite transformations to leverage the index. The index is maintained when performing DML operations on the indexed data. Index maintenance may be minimized or even avoided by analyzing path-based DML operation both at statement compile time and run time.

RDBMSs herein store application-level objects or documents as hierarchical data objects to support flexible schema management and, in some ways, schema-less operation. RDBMSs herein support native storage of hierarchical data objects such as JavaScript object notation (JSON), extensible markup language (XML), or other complex application-level objects, which may be aggregately stored in one large object (LOB) column. Indexing techniques herein include path navigation to efficiently support a range predicate query over scalar and array data fields that are embedded inside the hierarchical data objects. Indexes are defined using structured query language (SQL) table function definition, such as JSON TABLE( ) and XMLTABLE(), to express multi-value, multi-field, multilevel, multi-position functional indexing. In general, the table functions describe keys to index as output in relational form and from which fields or elements in hierarchical data objects to extract content for the output.

Approaches herein completely avoid materializing a copy of content in hierarchal data objects as relational data in so-called side tables. Consequently, index storage space and indexing maintenance time are decreased. The approached may also enable a simple migration path for users that already use a JSON_TABLE() materialized view to speed up a JSON_EXISTS() query or an XMLTABLE() materialized view to speed up an XMLEXISTS() query.

The approaches bridge the gap of classical functional indexing in an RDBMS that cannot index array values. Indexing solutions herein provide indexing at multiple levels in hierarchical data objects. JSON and XML path (XPath) navigational languages heavily depend on navigation of content at different levels in hierarchical data objects.

In an embodiment, an RDBMS stores, in a table, many hierarchical data objects that respectively contain multiple levels that respectively contain one or more fields. An index is generated for indexed values in fields in at least two of the multiple levels. The index is used to execute a database statement that references at least one of the indexed fields.

Approaches herein provide unprecedented acceleration in various ways as follows. Indices herein provide matching to more fields in more levels of hierarchical data objects thereby decreasing or eliminating further filtering by brute force after index access. For example, matching ordinal positions within an array field needs no further filtration after index access. Likewise, duplicate value counting within an array field may occur based solely on index access for acceleration. While other approaches may need multiple indices to handle multiple fields and/or multiple levels, a single index herein provides increased spatial locality of index entries for acceleration. Various ways of minimizing index maintenance for acceleration are described.

<FIG> is a block diagram that depicts an example database management system (DBMS) <NUM>, in an embodiment. DBMS <NUM> provides multilevel, multifield, multivalued indexing and query execution for hierarchical data objects <NUM>-<NUM> stored in table <NUM> in relational database <NUM>. DBMS <NUM> may be hosted by one or more computers such as a rack server such as a blade, a personal computer, a mainframe, a virtual computer, or other computing device.

DBMS <NUM> hosts and/or operates relational database <NUM>. For example, DBMS <NUM> may be a relational DBMS (RDBMS) that processes and administers content of relational database <NUM>. Relational database <NUM> contains table <NUM> that contains column <NUM>. Definitions of table <NUM> and/or column <NUM> may be stored in a database dictionary that stores schematic metadata in relational database <NUM>. Column <NUM> stores hierarchical data objects <NUM>-<NUM> that may be semi-structured documents such as JavaScript object notation (JSON) or extensible markup language (XML), a document object model (DOM), or nested data objects such as a logical tree or data containment hierarchy. Embodiments may store hierarchical data objects <NUM>-<NUM> in column <NUM> as text or binary data. For example, the datatype of column <NUM> may be a large object (LOB) such as a character LOB (CLOB) or binary LOB (BLOB). Each of hierarchical data objects <NUM>-<NUM> is stored in a separate respective row of table <NUM>.

Column <NUM> may contain numerous hierarchical data objects. Table <NUM> may contain other columns that do or do not store other hierarchical data objects. Each column may store content of a respective type. Relational database <NUM> may contain other tables that do or do not store other hierarchical data objects.

Hierarchical data object <NUM> contains a sequence of levels <NUM>-<NUM> that contain respective field(s). For example, level <NUM> contains fields <NUM>-<NUM> that may have same or different respective datatypes. As explained earlier herein, levels are used for navigation within hierarchical data object(s) such as according to a multilevel path expression for identifying a nested field. Essentially, a hierarchical data object may be operated as a logical tree data structure of interconnected nodes, where each node is a respective field in the hierarchical data object. The nodes of the tree are logically arranged into levels so that child nodes of a same parent node occur in a same level that is adjacent to the level of the parent node. In that structural way, multiple fields may be nested in an enclosing field. Nesting of fields provides a containment hierarchy, which causes a hierarchical data object to be hierarchical.

Although not shown, hierarchical data objects <NUM>-<NUM> may contain same or different counts of levels. In other words as logical trees, hierarchical data objects <NUM>-<NUM> may have different heights. Hierarchical data objects <NUM>-<NUM> may contain same or different fields at a same level. For example, same field <NUM> may be stored in different levels of hierarchical data objects <NUM>-<NUM> such as in first level <NUM> as shown in hierarchical data object <NUM> but in a different level or multiple levels in hierarchical data object <NUM>. Same field <NUM> may contain a same or different respective value in respective hierarchical data objects <NUM>-<NUM>. For example in hierarchical data object <NUM>, field <NUM> stores value <NUM> that may be a scalar such as a string or number or an array of multiple scalars. In an embodiment, a scalar may be stored and/or processed as if it were an array having only one element or vice versa.

In relational database <NUM>, DBMS <NUM> creates, populates, and maintains index <NUM> that indexes hierarchical data objects <NUM>-<NUM> based on respective field(s) in multiple levels such as levels <NUM>-<NUM>. For example, index <NUM> may index fields in three adjacent or non-adjacent levels of some many available levels such as five expected levels or an indefinite count of levels. If hierarchical data object <NUM> lacks a level that index <NUM> indexes, then index <NUM> does not index hierarchical data object <NUM>. Configuration and population of index <NUM> are discussed later herein.

At runtime and after population of index <NUM> based on column <NUM>, DBMS <NUM> may receive database statement <NUM> that accesses column <NUM> and refers to field(s) such as field <NUM> such as in a predicate in database statement <NUM>. Execution of database statement <NUM> is accelerated by using index <NUM>. Database statement <NUM> need not expressly reference index <NUM>. Database statement <NUM> need not reference all fields nor all levels that index <NUM> indexes. Examples of database statement <NUM> and statement execution and acceleration are presented later herein.

DBMS <NUM> uses index <NUM> to determine which of hierarchical data objects <NUM>-<NUM> satisfy a predicate in database statement <NUM> such as for filtration. For example, database statement <NUM> may read and/or write one, some, or all of hierarchical data objects <NUM>-<NUM>. In any case, database statement <NUM> may be data manipulation language (DML), structured query language (SQL), and/or query by example (QBE). SQL embodiments are discussed later herein. DBMS <NUM> may answer database statement <NUM> by sending a result that contains value(s), level(s), hierarchical data object(s), and/or computed value(s). The result may be encoded in a same or different format as used within column <NUM>. For example, column <NUM> may store binary encoded JSON, but database statement <NUM> and its response may instead contain text encoded JSON.

<FIG> is a flow diagram that depicts DBMS <NUM> providing, based on index <NUM>, multilevel, multifield, multivalued indexing and query execution for hierarchical data objects <NUM>-<NUM> stored in column <NUM> in table <NUM> in relational database <NUM> in an embodiment. <FIG> is discussed with reference to <FIG>.

Steps <NUM>-<NUM> may occur at various respective times in various scenarios. For example, step <NUM> may occur during initial data ingestion such as by extraction, transformation, and loading (ETL) or continuously such as when hierarchical data objects <NUM>-<NUM> arrive in a live stream. Step <NUM> may occur during system administration such as by a database administrator (DBA) or continuously with streaming. Step <NUM> may occur at runtime and may entail data manipulation language (DML) such as a query that is or is not ad hoc.

In column <NUM> in table <NUM> in relational database <NUM>, step <NUM> stores hierarchical data objects <NUM>-<NUM> that respectively contain levels such as levels <NUM>-<NUM> that respectively contain field(s) such as fields <NUM>-<NUM> that contain values such as values <NUM>-<NUM>. Each hierarchical data object is stored in a separate respective row in table <NUM>. For example, additional rows may be inserted into table <NUM> whenever new hierarchical data objects are received.

Step <NUM> generates index <NUM> for indexed values in fields in at least two levels in hierarchical data objects in column <NUM>. In an embodiment, index <NUM> contains references to rows of table <NUM> that contain hierarchical data objects that contain contents that satisfy indexing criteria of index <NUM>. A reference to a row may be a row identifier (ROWID), an array offset, a memory address pointer, or a file pointer such as having a logical block address (LBA) plus a byte offset. As explained later herein, indexing criteria may identify fields and/or levels, and/or may contain a predicate, a regular expression, and/or hierarchical traversal paths such as a JSON expression or an XML path (XPath). In an embodiment, index <NUM> contains the indexed values of fields. For example, indexing criteria may specify indexing of fields <NUM>-<NUM> in all hierarchical data objects in column <NUM>, in which case index <NUM> contains the indexed values of fields <NUM>-<NUM>. Data storage and structure within index <NUM> are discussed later herein. An example index creation DDL statement is presented later herein.

Based on index <NUM> for indexed values in fields in at least two levels, step <NUM> executes database statement <NUM> that references table <NUM> in relational database <NUM> and at least one indexed field in index <NUM>. For example, index <NUM> may index fields <NUM>-<NUM>, and database statement <NUM> references index field <NUM> and/or <NUM>. Step <NUM> may or may not entail updating contents of column <NUM>, table <NUM>, and/or index <NUM> according to scenarios discussed later herein. Example SQL queries that index <NUM> accelerates are presented later herein.

<FIG> is a flow diagram that depicts example index activities that DBMS <NUM> may implement for generating and using index <NUM>. <FIG> is discussed with reference to <FIG>.

As explained earlier herein, field <NUM> may be an array field such that hierarchical data object <NUM> has multiple values for same field <NUM>. For example, field <NUM> may contain many temperature numbers as time series data from a same thermometer. Per step <NUM>, database statement <NUM> indicates the ordinal position of a value that occurs in field <NUM>. For example, database statement <NUM> may contain the following ordinal WHERE clause. where json_exists(ja. temperature[<NUM>] > <NUM>').

The following terms have the following meanings in the above ordinal where clause:.

In a demonstrative embodiment, index <NUM> comprises a lookup table for indexing fields <NUM> and <NUM> in different respective levels <NUM>-<NUM>. Index <NUM> is multilevel because it indexes fields <NUM> and <NUM> that occur at different respective levels in hierarchical data objects. For demonstration, the above ordinal WHERE clause refers to only one level <NUM>. Applying index <NUM> to an example WHERE clause that instead refers to multiple levels is presented later herein.

In this example, field <NUM> may be a temperature array, and field <NUM> may be a thermometer manufacturer name. In a non-scalar embodiment, values <NUM>-<NUM> may occur together as a tuple that operates as a lookup key into index <NUM> to retrieve identifiers of matching hierarchical data objects in column <NUM>, even if value <NUM> or <NUM> is an array and not a scalar. For example, database statement <NUM> may ask which Oracle-made thermometers have no temperatures yet, and index <NUM> may provide ROWIDs of matching hierarchical data objects. In an embodiment, the lookup key tuple may contain an array and a string respectively for fields <NUM> and <NUM>. Each entry in the lookup table in index <NUM> may map one lookup key tuple to a list of ROWIDs of matching hierarchical data objects. As discussed later herein, index <NUM> may comprise a B+ tree instead of a lookup table, and both implementations may use a same lookup key tuple format.

In a scalar-tuple embodiment, the lookup key tuple instead contains only scalar values such as a number for field <NUM>, which is only one temperature even though field <NUM> is an array. In index <NUM>, step <NUM> generates multiple index entries with multiple respective lookup key tuples for same hierarchical data object <NUM>. Each of those lookup key tuples has a separate temperature value. For example in hierarchical data object <NUM>, if array field <NUM> has a value of [<NUM>, <NUM>, <NUM>] and field <NUM> has a value of Oracle, then three lookup key tuples may be [<NUM>, Oracle], [<NUM>, Oracle], and [<NUM>, Oracle] for three respective index entries. Each of those three index entries would map to a respective list of matching ROWIDs, and each of those three lists would contain at least the same ROWID of hierarchical data object <NUM>.

Using the scalar-tuple embodiment of index <NUM> may be enhanced as follows to accelerate evaluation of the above ordinal WHERE clause. In index <NUM>, step <NUM> indicates the ordinal position of a value in array field <NUM> by including the zero-based ordinal position in the lookup key tuple. For example, [<NUM>, <NUM>, Oracle] may be a lookup key tuple that indicates that <NUM> is the third temperature in the array. In that way, step <NUM> indexes the ordinal position in the same way as if it were another indexed field in index <NUM>.

As time series data, temperature field <NUM> may instead contain ten years of hourly temperatures, which is <NUM>,<NUM> values, many or most of which may be adjacent or non-adjacent duplicates. In the scalar-tuple embodiment, there are <NUM>,<NUM> ordinal positions and thus <NUM>,<NUM> different lookup key tuples for same hierarchical data object <NUM> because each ordinal position has its own index entry for a same array field of a same hierarchical data object, which may greatly inflate the size of index <NUM>.

A reduction in the size of index <NUM> is possible because semantics of json_exists() entails calculating exactly one Boolean true or false as a match result respectively for each hierarchical data object in column <NUM>. In other words, most json_exists usages do not need index <NUM> to index duplicate values, count duplicate values, nor have ordinal positions for values in an array field, such as with the following non-ordinal WHERE clause. where json_exists(ja. temperature[*] > <NUM>').

In the above non-ordinal WHERE clause, [*] is a wildcard that means any ordinal position in the temperature array. In the above non-ordinal WHERE clause, it does not matter that many or all temperature values may match the predicate, because the result is the same so long as at least one ordinal position has a temperature value that matches. In various embodiments, DBMS <NUM> automatically detects, or a database administrator (DBA) manually indicates, that index <NUM> will not be used in a way that needs duplicates nor ordinal positions and index <NUM> should create only one index entry per distinct value in array field <NUM> for a same hierarchical data object. For example, DBMS <NUM> may automatically analyze historical queries to detect that duplicates and ordinal positions in array field <NUM> are always ignored, such as with queries that ask for a maximum value in an array field or whether an array field contains a particular value. Without generating multiple index entries in index <NUM> for duplicate values in array field <NUM> of hierarchical data object <NUM>, step <NUM> generates only a single index entry for the same value in array field <NUM> of hierarchical data object <NUM>. For example, if temperature has only a single digit of precision, then there are only ten possible temperature values, and index <NUM> would have at most ten index entries for array field <NUM> of hierarchical data object <NUM>, even though array field <NUM> of hierarchical data object <NUM> may contain thousands of duplicate values.

As explained above, semantics of json_exists() entails calculating exactly one Boolean for hierarchical data object <NUM>. Even though an embodiment of index <NUM> may have only one index entry per distinct value in array field <NUM> of hierarchical data object <NUM>, array field <NUM> of hierarchical data object <NUM> may still have multiple matching values, such as when array field <NUM> contains [<NUM>, <NUM>, <NUM>], which causes three index entries for three distinct values. In that case for json_exists, computer <NUM> should ignore multiple matching index entries for same hierarchical data object <NUM>. In other words, json_exists should not return duplicate ROWIDs. Thus when the above non-ordinal WHERE clause matches multiple index entries for hierarchical data object <NUM>, step <NUM> still generates a same result as if the predicate in the above non-ordinal WHERE clause had matched only once in hierarchical data object <NUM>.

<FIG> illustrate an exemplary embodiment as follows. <FIG> depicts example complex JSON document <NUM>. <FIG> is discussed with reference to <FIG>. Column <NUM> of <FIG> may store JSON document <NUM> that contains many arrays and many levels as discussed below for <FIG>.

<FIG> depicts example DDL statement <NUM> in an embodiment. <FIG> is discussed with reference to <FIG> and <FIG>.

The following terms have the following meanings in DDL statement <NUM> that specifies creation of index <NUM>.

As explained above, JSON_TABLE is a table function. An embodiment may instead use XMLTABLE as a table function for XML documents. For example if column <NUM> instead contains XML documents, then index <NUM> may accelerate an XMLEXISTS() WHERE clause. In either case, the table function is responsible for flattening a whole hierarchical data object or a tree path or subtree from the hierarchical data object into one or more data rows in the table returned by the table function. Flattening and denormalization are complementary ways of rearranging hierarchical data into tabular data as follows.

An embodiment of the table function may return one or multiple rows per hierarchical data object as follows. Despite potentially coming from different levels in a same hierarchical data object, NESTED PATHs are flattened into a same row in the result of the table function. For example, columns bd and typec come from fields in different levels but occur in a same row for the table function.

Because each element of an array field referenced by [*] provides a separate row for the table function, denormalization is needed as follows. Denormalization entails duplicating data in multiple rows for the table function. Values from fields in a same or higher level as an array field are duplicated in each table row provided by the array field. For example, array field itemized[*] may contain two loan disbursements and provide two table rows. In both of those table rows, column bd will contain a same repeated value. In an embodiment, index <NUM> generates multiple respective index entries for the multiple rows that a table function returns for a same hierarchical data object. An embodiment may have other table functions that flatten other kinds of hierarchical data objects into data rows in different ways.

In the following demonstrative example, column <NUM> contains only JSON document <NUM>, in which case the following example table T shows rows that would be returned by the JSON_TABLE() table function in DDL statement <NUM>.

The following aspects are demonstrated in the above example table T. A column name need not be identical to its field name. For example, two fields in different levels have a same field name "amount" but the respective columns have different names. Although not shown, table T may contain a column that, in each row of table T, stores a respective identifier of the hierarchical data object that provided content for that row. For example, that column may store ROWIDs that identify hierarchical data objects. In an embodiment, an index entry may be generated for each row of table T and inserted into index <NUM>. Thus, an embodiment may use table T to populate index <NUM>. In any case, index <NUM> may outlive table T. For example as discussed later herein, index <NUM> may be a B+ tree that is populated based on rows of table T, after which table T may be discarded and index <NUM> may be retained to accelerate future queries.

Zero-based ordinal serial numbers in a child level reset to zero when an ordinal serial number of a parent level is incremented. For example when ord1 is incremented from zero to one, ord2 is reset to zero. Duplicate values caused by denormalization entirely or partially fill some columns. Flattening causes each row to contain values from fields that occur in different levels of JSON document <NUM>.

In an embodiment, table T contains only columns that are needed to populate index <NUM>, which are at least those columns that are populated from fields that are indexed by index <NUM>. Some fields and/or levels need not be indexed and do not contribute data to the above example table T. For example, field "name" has no column in the above example table T and is not indexed by index <NUM>. Although fields nested within an array field may correspond to columns, the array field itself need not have a column. For example, the LoanHistory field itself does not have a column. Whereas in another example table function not shown, the creditScore field in JSON document <NUM> may correspond to a score column and possibly also an ordinal column.

In an embodiment, only one or a few rows of table T are materialized at a time. For example, a buffer may store a few rows of table T that are used to generate index entries and are then discarded so that other rows of table T can be buffered. For example, table T may contain multiple rows from each of many hierarchical document objects, and only rows from one hierarchical data object may be buffered at any time. In an embodiment, pipeline parallelism facilitates buffering later rows while concurrently generating index entries for earlier rows of table T.

<FIG> is a flow diagram that depicts DBMS <NUM> generating indices in an embodiment. <FIG> is discussed with reference to <FIG> and <FIG>.

Step <NUM> receives DDL statement <NUM> that specifies creation of index <NUM>. In an embodiment, index <NUM> comprises a B+ tree. For persistence, a B+ tree is a search tree that is optimized for input/output (I/O) by minimizing link traversals between tree nodes. A B+ tree has high fan-out (children per parent), high width (leaf count), and low height (level count). Thus, tree descent paths are short such that any tree leaf can be reached from the tree root in very few traversals. In an embodiment, only leaf nodes store index entries. In an embodiment, all of the leaf nodes are daisy-chained together to form a linked list such that, after reaching any leaf node, subsequent leaf nodes can be scanned without repeated tree descent. In an embodiment, each leaf node stores many index entries such that the linked list of leaves is a segmented list. In an embodiment, each tree node is persisted in its own disk block.

As explained earlier herein, NESTED PATHs in DDL statement <NUM> configure index <NUM> to index fields in three levels in hierarchical data objects. Likewise, index <NUM> can accelerate DML statements that access any or all indexed fields respectively in any or all of those three levels. The following multilevel WHERE clause accesses indexed fields that occur in all three levels. where json_exists(ja. jcol, <MAT>.

In an embodiment, a path expression in a DML or DDL statement may contain *. " (without quotes) that is a double dot that indicates skipping any count of levels. That is, an expression that contains a double dot may have multiple matches at different levels in same or different hierarchical data objects. With or without level skipping, lookup key tuples may have a same format. For example, a same field may occur only once in each hierarchical data object but at different levels in different hierarchical data objects. A first value in a lookup key tuple may correspond to that field, even though different levels are involved for different hierarchical data objects. In other words, levels may be more or less irrelevant for lookup key tuples that are effectively flattened such as follows.

In an embodiment, lookup key tuples are one dimensional, even though DDL statement <NUM> has NESTED PATHs and JSON document <NUM> is multilevel. That is, a lookup key tuple is flat even though index <NUM> is multilevel, which means that index <NUM> indexes fields at different levels in hierarchical data objects. Whether or not an index is multilevel depends on the fields that it indexes and not the internal architecture of the index. A multilevel index does not mean that the index's internal structure has multiple levels such as levels in a B+ tree, even if index <NUM> has a B+ tree that has multiple tree levels. For example, a multilevel JSON document { A: a, B : { C : c, D : d } } may have a flat lookup key tuple that is [a, d] if multilevel index <NUM> indexes only fields A and D.

For example, each row in earlier example table T may: a) represent a distinct respective lookup key tuple, and/or b) correspond to a distinct respective index entry in index <NUM>. For example as discussed earlier herein, an index entry may be generated from each row of table T. In an embodiment, each index tree leaf contains at least one index entry that contains: a) one lookup key tuple, and b) a set of ROWIDs of matching hierarchical data objects. Because a lookup key tuple contains some indexed values, step <NUM> stores indexed values in B+ tree leaves in index <NUM>. In an embodiment, ROWID is instead treated as an indexed field such that any index entry, contained in an index tree leaf, contains exactly one ROWID.

As explained earlier herein, a ROWID corresponds to a distinct row in column <NUM>, not a distinct row in a row set provided by a table function such as the rows in earlier example table T. For example, a ROWID may identify JSON document <NUM>. If all of the rows in example table T are based on same JSON document <NUM>, then all of the index entries that correspond to the rows in example table T may be multiple index entries that contain a same ROWID.

Per DDL statement <NUM>, index <NUM> indexes only a subset of fields that occur in hierarchical data objects. For the same hierarchical data objects in column <NUM>, step <NUM> generates a different index for same or different fields in same or different levels as index <NUM> has. Thus, column <NUM> may have many multilevel indices. For example as shown, index <NUM> indexes field <NUM> in level <NUM> and field <NUM> in level <NUM>, which may accelerate a query that filters based on both fields <NUM>-<NUM>. A query that only filters field <NUM> that is at the deeper level may instead be more accelerated by a separate index that only indexes field <NUM> and possibly also indexes fields in a same or deeper level but not fields in an enclosing level such as level <NUM>.

<FIG> is a flow diagram that depicts continued maintenance of index <NUM> in an embodiment. <FIG> is discussed with reference to <FIG>.

A hierarchical data object may be inserted into or deleted from column <NUM> such that index <NUM> may need automatic maintenance such as insertion, deletion, or modification of B+ tree leaves. A consequence of using a search tree is that updating an indexed value in a hierarchical data object may cause the hierarchical data object's ROWID to move from one tree leaf to a different tree leaf, which may or may not further cause deletion or creation of a tree leaf. Additional complications are: a) multiple fields of the hierarchical data object may be updated by a same DML statement, and/or b) the hierarchical data object may have multiple index entries in index <NUM> such as for an array field. For example before receiving a SQL UPDATE statement, steps <NUM>-<NUM> respectively generate first and second index entries for a same hierarchical data object.

Executing the UPDATE statement may entail index maintenance as follows. Index maintenance may be complicated because the UPDATE statement may specify replacement of the whole hierarchical data object or a whole subtree in the hierarchical data object, even if only one or a few fields are actually changed. A straightforward embodiment may delete all of the hierarchical data object's index entries and then insert or reinsert index entries for the revised hierarchical data object, which may be suboptimal. For example, the straightforward embodiment may delete the hierarchical data object's ROWID from all B+ tree leaves and then add that ROWID to some leaves based on the revised hierarchical data object.

Various embodiments may more efficiently maintain index <NUM> based on detecting, in the following various ways, a subset of indexed fields of the hierarchical data object that actually changed. These ways entail respective strategies that apply in different respective scenarios. For example, two very different DML statements may change the value of a same field, and those two changes may be detected in different respective ways as follows.

The following different change detection mechanisms provide different respective balances between efficiency and flexibility. The more efficient is a change detection mechanism, the fewer scenarios are suitable for that mechanism. The least efficient change detection mechanism may be a general fallback mechanism that can accommodate any scenario.

In the general fallback mechanism, the original hierarchical data object and the revised hierarchical data object are more or less exhaustively compared and differenced to detect which indexed fields changed. In an embodiment, multiple sibling branches, subtrees, or tree paths in the original hierarchical data object are compared in parallel, such as with task parallelism on a multicore processor, to multiple respective branches in the revised hierarchical data object. In an embodiment, comparing original and revised document is based on a document object model (DOM) comparison even if hierarchical data objects are not stored in column <NUM> in a DOM format.

In a somewhat more efficient change detection mechanism, a redo log or undo log is scanned to detect which indexed fields changed. However, this mechanism is available only when logging is implemented and activated. Likewise, the log may need thread safety between writers and readers of the log that may decrease system throughput. For example, index <NUM> may have a log reader that performs index maintenance.

A SQL update statement may invoke JSON_TRANSFORM or JSON_MERGEPATCH to selectively add, remove, or modify portions of stored hierarchical data objects. An invocation of JSON _TRANSFORM or JSON_MERGEPATCH may specify activities such as addition or removal and specify locations such as nested fields and array offsets.

In various change detection mechanisms that are even more efficient, the above log interface or JSON_TRANSFORM or JSON_MERGEPATCH is instrumented to automatically report changed fields to index <NUM> for index maintenance. That is, the mechanism may be based on inversion of control such as with callbacks that DBMS <NUM> both invokes and handles. For example, a logging software layer may invoke the callbacks, and an indexing layer that maintains index <NUM> may handle the callbacks by performing index maintenance.

For example, callback instrumentation may accelerate index maintenance caused by the following example JSON_TRANSFORM.

For example for the above example JSON_TRANSFORM, a callback invocation may include arguments that indicate: a) the ROWID for po_document, b) the Phone array field, and c) insertion of a new phone number at the end of the array. JSON_TRANSFORM and JSON_MERGEPATCH are discussed later herein.

In the following index conditional maintenance scenarios that may occur in fulfillment of a callback invocation for the Phone array field, whether index entry(s) in index <NUM> need maintenance may depend on conditions such as: a) whether or not index <NUM> should index duplicate phone numbers that occur in the same array field of a same hierarchical data object, and b) whether or not the array field modification that caused the callback invocation also caused the array field to contain a different set of distinct values. For example when duplicates are not indexed, deletion of a duplicate value from an array should not modify the index because at least one other occurrence of the same value in the array survives.

In fulfilment of the callback invocation, the indexing layer may maintain index <NUM> in various ways. If the new phone number is not a duplicate of another element in the Phone array field, or if indexing of duplicates is intended, then a new index entry may be inserted into index <NUM> for the new phone number. If the new phone number is a duplicate and index <NUM> should not index duplicates within an array, then a new index entry is not inserted.

During a callback invocation for removal of a deleted phone number, similar conditional maintenance may or may not occur. For example if the deleted phone number is not a duplicate, or if indexing of duplicates is intended, an index entry may be deleted from index <NUM>. If the deleted phone number is a duplicate and index <NUM> should not index duplicates within an array, then an index entry is not deleted.

During a callback invocation for modification of a phone number, in which an old phone number is replaced with a replacement phone number, similar conditional maintenance may or may not occur. For example if replacement of the old phone number with the replacement phone number changes the set of distinct values in the Phone array field, or if indexing of duplicates is intended, an index entry is replaced in index <NUM>. If replacement of the old phone number with the replacement phone number does not change the set of distinct values in the Phone array field and index <NUM> should not index duplicates within the array, then index <NUM> does not need maintenance.

All of the change detection mechanisms discussed above occur at statement runtime, which may be during execution of an execution plan. Runtime change detection is flexible but with somewhat limited efficiency. For example, the flexibility of runtime change detection is well suited for distinguishing actual changes from nominal changes specified in a statement. For example, a statement may specify replacing the entirety of hierarchical data object <NUM> even though only the value of field <NUM> actually changes.

Runtime change detection mechanisms need not inspect the execution plan nor a statement parse tree such as an abstract syntax tree (AST) that contains statement semantic information. In limited cases that trade off some flexibility for increased efficiency, some or all change detection can be offloaded to statement compile time. Although runtime change detection mechanisms need not inspect the execution plan, a highly efficient change detection mechanism may be a compile-time change detection mechanism that does consult the parse tree or execution plan for an UPDATE statement to detect which indexed fields are changed as expressly specified in the statement.

For example, compile-time analytics may accelerate index maintenance caused by the above example JSON _TRANSFORM. For example, compile-time analysis may reveal: a) the ROWID for podocument, b) only the Phone array field is changing, c) a new phone number is being appended at the end of the Phone array field, and d) none of the existing elements of the Phone array field are modified, deleted, nor shifted.

If indexed field <NUM> in hierarchical data object <NUM> is an array field that contains multiple temperature values, then hierarchical data object <NUM> may have multiple index entries in index <NUM>. With any of the field change detection mechanisms discussed above, DBMS <NUM> can detect that changing the value array of field <NUM> from [<NUM>, <NUM>] to [<NUM>, <NUM>] means only the first ordinal position's value changed. That is one of various scenarios that cause step <NUM> to delete the first index entry without deleting the second index entry for the same hierarchical data object. Step <NUM> may instead be caused by changing the array value from [<NUM>, <NUM>] to [<NUM>].

With any of the field change detection mechanisms discussed above, DBMS <NUM> can detect that a second UPDATE statement only changes field <NUM>. By inspecting metadata of index <NUM>, such as in a database dictionary, without actually accessing index <NUM>, DBMS <NUM> detects that changed field <NUM> is not indexed by index <NUM>. In that case, step <NUM> revises the hierarchical data object in column <NUM> without accessing nor maintaining index <NUM>.

<FIG> is a flow diagram that depicts practical usage of index <NUM> in an embodiment. <FIG> is discussed with reference to <FIG>.

JSON_VALUE() is somewhat similar to JSON_EXISTS, except that JSON_VALUE extracts and returns actual field values from some or all hierarchical data objects in column <NUM>. To execute JSON_VALUE() step <NUM> may access multilevel index <NUM>. For example with either JSON)VALUE or JSON_EXISTS, if only indexed fields are accessed, then execution may be fulfilled by accessing only index <NUM> without needing to access column <NUM>.

DML operations may be respectively categorized as create, read, update, or delete (CRUD). JSON_VALUE and JSON_EXIST only facilitate selection and filtration, whether reading or writing. Update and delete operations of CRUD are performed by JSON_TRANSFORM(). JSON _TRANSFORM has complex syntax and semantics that are explained in related manual Oracle Database JSON Developer's Guide, 21c, part number F30948-<NUM>. To accelerate execution of JSON_TRANSFORM(), step <NUM> may access multilevel index <NUM>.

Although somewhat similar to JSONTRANSFORM, JSON_MERGEPATCH() may be more complex due to recursive operation. For example, a same spelling error may be repeated in various ordinal positions in an array field and/or in various levels of a JSON document. JSON_MERGEPATCH may recursively match and fix all of those spelling errors and/or make other changes. JSON_MERGEPATCH has complex syntax and semantics that are explained in related manual Oracle Database JSON Developer's Guide, 21c. To accelerate execution of JSON_MERGEPATCH(), step <NUM> accesses multilevel index <NUM>.

<FIG> is a block diagram of a basic software system <NUM> that may be employed for controlling the operation of computing system <NUM>. Software system <NUM> and its components, including their connections, relationships, and functions, is meant to be exemplary only, and not meant to limit implementations of the example embodiment(s). Other software systems suitable for implementing the example embodiment(s) may have different components, including components with different connections, relationships, and functions.

Software system <NUM> is provided for directing the operation of computing system <NUM>. Software system <NUM>, which may be stored in system memory (RAM) <NUM> and on fixed storage (e.g., hard disk or flash memory) <NUM>, includes a kernel or operating system (OS) <NUM>.

The OS <NUM> manages low-level aspects of computer operation, including managing execution of processes, memory allocation, file input and output (I/O), and device I/O. One or more application programs, represented as 1002A, 1002B, 1002C. 1002N, may be "loaded" (e.g., transferred from fixed storage <NUM> into memory <NUM>) for execution by the system <NUM>. The applications or other software intended for use on computer system <NUM> may also be stored as a set of downloadable computer-executable instructions, for example, for downloading and installation from an Internet location (e.g., a Web server, an app store, or other online service).

Software system <NUM> includes a graphical user interface (GUI) <NUM>, for receiving user commands and data in a graphical (e.g., "point-and-click" or "touch gesture") fashion. These inputs, in turn, may be acted upon by the system <NUM> in accordance with instructions from operating system <NUM> and/or application(s) <NUM>. The GUI <NUM> also serves to display the results of operation from the OS <NUM> and application(s) <NUM>, whereupon the user may supply additional inputs or terminate the session (e.g., log off).

OS <NUM> can execute directly on the bare hardware <NUM> (e.g., processor(s) <NUM>) of computer system <NUM>. Alternatively, a hypervisor or virtual machine monitor (VMM) <NUM> may be interposed between the bare hardware <NUM> and the OS <NUM>. In this configuration, VMM <NUM> acts as a software "cushion" or virtualization layer between the OS <NUM> and the bare hardware <NUM> of the computer system <NUM>.

VMM <NUM> instantiates and runs one or more virtual machine instances ("guest machines"). Each guest machine comprises a "guest" operating system, such as OS <NUM>, and one or more applications, such as application(s) <NUM>, designed to execute on the guest operating system. The VMM <NUM> presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems.

In some instances, the VMM <NUM> may allow a guest operating system to run as if it is running on the bare hardware <NUM> of computer system <NUM> directly. In these instances, the same version of the guest operating system configured to execute on the bare hardware <NUM> directly may also execute on VMM <NUM> without modification or reconfiguration. In other words, VMM <NUM> may provide full hardware and CPU virtualization to a guest operating system in some instances.

In other instances, a guest operating system may be specially designed or configured to execute on VMM <NUM> for efficiency. In these instances, the guest operating system is "aware" that it executes on a virtual machine monitor. In other words, VMM <NUM> may provide para-virtualization to a guest operating system in some instances.

A computer system process comprises an allotment of hardware processor time, and an allotment of memory (physical and/or virtual), the allotment of memory being for storing instructions executed by the hardware processor, for storing data generated by the hardware processor executing the instructions, and/or for storing the hardware processor state (e.g. content of registers) between allotments of the hardware processor time when the computer system process is not running. Computer system processes run under the control of an operating system, and may run under the control of other programs being executed on the computer system.

The term "cloud computing" is generally used herein to describe a computing model which enables on-demand access to a shared pool of computing resources, such as computer networks, servers, software applications, and services, and which allows for rapid provisioning and release of resources with minimal management effort or service provider interaction.

A cloud computing environment (sometimes referred to as a cloud environment, or a cloud) can be implemented in a variety of different ways to best suit different requirements. For example, in a public cloud environment, the underlying computing infrastructure is owned by an organization that makes its cloud services available to other organizations or to the general public. In contrast, a private cloud environment is generally intended solely for use by, or within, a single organization. A community cloud is intended to be shared by several organizations within a community; while a hybrid cloud comprise two or more types of cloud (e.g., private, community, or public) that are bound together by data and application portability.

Generally, a cloud computing model enables some of those responsibilities which previously may have been provided by an organization's own information technology department, to instead be delivered as service layers within a cloud environment, for use by consumers (either within or external to the organization, according to the cloud's public/private nature). Depending on the particular implementation, the precise definition of components or features provided by or within each cloud service layer can vary, but common examples include: Software as a Service (SaaS), in which consumers use software applications that are running upon a cloud infrastructure, while a SaaS provider manages or controls the underlying cloud infrastructure and applications. Platform as a Service (PaaS), in which consumers can use software programming languages and development tools supported by a PaaS provider to develop, deploy, and otherwise control their own applications, while the PaaS provider manages or controls other aspects of the cloud environment (i.e., everything below the run-time execution environment). Infrastructure as a Service (IaaS), in which consumers can deploy and run arbitrary software applications, and/or provision processing, storage, networks, and other fundamental computing resources, while an IaaS provider manages or controls the underlying physical cloud infrastructure (i.e., everything below the operating system layer). Database as a Service (DBaaS) in which consumers use a database server or Database Management System that is running upon a cloud infrastructure, while a DbaaS provider manages or controls the underlying cloud infrastructure and applications.

The above-described basic computer hardware and software and cloud computing environment presented for purpose of illustrating the basic underlying computer components that may be employed for implementing the example embodiment(s). The example embodiment(s), however, are not necessarily limited to any particular computing environment or computing device configuration. Instead, the example embodiment(s) may be implemented in any type of system architecture or processing environment that one skilled in the art, in light of this disclosure, would understand as capable of supporting the features and functions of the example embodiment(s) presented herein.

Embodiments of the present invention are used in the context of database management systems (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 may comprise multiple data structures that store database metadata. A database dictionary may for example, comprise multiple files and tables. Portions of the data structures may be cached in main memory of a database server.

A database dictionary comprises metadata that defines database objects contained in a database. In effect, a database dictionary defines much of a database. When a database object is said to be defined by a database dictionary, the database dictionary contains metadata that defines properties of the database object. For example, metadata in a database dictionary defining a database table may specify the column names and datatypes of the columns, and one or more files or portions thereof that store data for the table. Metadata in the database dictionary defining a procedure may specify a name of the procedure, the procedure's arguments and the return datatype and the datatypes of the arguments, and may include source code and a compiled version thereof.

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 object may be defined by the database dictionary, but the metadata in the database dictionary itself may only partly specify the properties of the database object. Other properties may be defined by data structures that may not be considered part of the database dictionary. For example, a user defined function implemented in a JAVA class may be defined in part by the database dictionary by specifying the name of the users defined function and by specifying a reference to a file containing the source code of the Java class (i.e., java file) and the compiled version of the class (i.e., class file).

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 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 nonlimiting 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 <NUM>). 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.

A query is an expression, command, or set of commands that, when executed, causes a server to perform one or more operations on a set of data. A query may specify source data object(s), such as table(s), column(s), view(s), or snapshot(s), from which result set(s) are to be determined. For example, the source data object(s) may appear in a FROM clause of a Structured Query Language ("SQL") query. SQL is a well-known example language for querying database objects. As used herein, the term "query" is used to refer to any form of representing a query, including a query in the form of a database statement and any data structure used for internal query representation. The term "table" refers to any source object that is referenced or defined by a query and that represents a set of rows, such as a database table, view, or an inline query block, such as an inline view or subquery.

The query may perform operations on data from the source data object(s) on a row by-row basis as the object(s) are loaded or on the entire source data object(s) after the object(s) have been loaded. A result set generated by some operation(s) may be made available to other operation(s), and, in this manner, the result set may be filtered out or narrowed based on some criteria, and/or joined or combined with other result set(s) and/or other source data object(s).

A subquery is a portion or component of a query that is distinct from other portion(s) or component(s) of the query and that may be evaluated separately (i.e., as a separate query) from the other portion(s) or component(s) of the query. The other portion(s) or component(s) of the query may form an outer query, which may or may not include other subqueries. A subquery nested in the outer query may be separately evaluated one or more times while a result is computed for the outer query.

Generally, a query parser receives 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.

Claim 1:
A method comprising:
storing (<NUM>), in a table (<NUM>) in a relational database (<NUM>), a plurality of hierarchical data objects (<NUM>, <NUM>), wherein each hierarchical data object (<NUM>, <NUM>) of the plurality of hierarchical data objects (<NUM>, <NUM>) contains a respective plurality of levels (<NUM>, <NUM>), and each level (<NUM>, <NUM>) of the plurality of levels (<NUM>, <NUM>) of the hierarchical data object (<NUM>, <NUM>) contains respective one or more fields (<NUM>, <NUM>, <NUM>);
generating (<NUM>) an index (<NUM>) for an indexed plurality of values (<NUM>, <NUM>) in a plurality of fields (<NUM>, <NUM>, <NUM>) in at least two levels (<NUM>, <NUM>) of the pluralities of levels (<NUM>, <NUM>) of the plurality of hierarchical data objects (<NUM>, <NUM>), wherein a particular field (<NUM>, <NUM>, <NUM>) in said plurality of fields (<NUM>, <NUM>, <NUM>) in said at least two levels (<NUM>, <NUM>) in a hierarchical data object (<NUM>, <NUM>) of said plurality of hierarchical data objects (<NUM>, <NUM>) contains a particular field plurality of values (<NUM>, <NUM>) in said indexed plurality of values (<NUM>, <NUM>), and wherein a lookup key of an index entry in the index (<NUM>) comprises a scalar value (<NUM>, <NUM>) for the particular field (<NUM>, <NUM>, <NUM>);
executing (<NUM>), based on said index (<NUM>) for said indexed plurality of values (<NUM>, <NUM>) in said plurality of fields (<NUM>, <NUM>, <NUM>) in said at least two levels (<NUM>, <NUM>), a database statement (<NUM>) that references said table (<NUM>) in the relational database (<NUM>) and at least the particular field (<NUM>, <NUM>, <NUM>) of said plurality of fields (<NUM>, <NUM>, <NUM>).