Storage and retrieval of concurrent query language execution results

Methods, systems, and articles for receiving, by a computing device, execution results of a plurality of query language expressions are described herein. In various embodiments, the plurality of query language expressions may be concurrently executed, and the receiving may be contemporaneous with production of the execution results. Also, in various embodiments, the computing device may store a result item of the execution results for at least a first of the query language expressions in a memory block allocated exclusively for the first of the query language expressions while the first of the query language expressions is being executed, or in a result handle associated with the first of the query language expressions.

TECHNICAL FIELD

Embodiments relate to the field of data processing, in particular, to efficient storing and retrieving of execution results of concurrently processed query language expressions.

BACKGROUND

Simultaneous execution of processes has become increasingly common. This has allowed for more efficient evaluation of multiple query language expressions, such as XPath expressions. Previously, such expressions had to be executed serially, with the thread executing the expressions making one pass through of a document for each expression. Thus, evaluation of a large collection of expressions could be time consuming. Simultaneous execution of the expressions, on the other hand, requires only a single traversal of a document for all of the expressions, allowing for evaluation of such expressions with greater efficiency.

The collective execution results of such simultaneously executed query language expressions are often stored in a stack or some other similar data structure, with portions of execution results of the multiple expressions being interleaved together. For example, if the results of a first expression are 1, 2, 3 and a second are A, B, C, they may be stored as 1, A, B, 2, 3, C. To retrieve results of any one expression, then, often requires substantial post-processing and review of the entire stack. Such post-processing is unnecessarily time consuming and reduces the advantage of simultaneous execution of multiple expressions.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

Illustrative embodiments include, but are not limited to, methods and apparatuses for receiving, by a computing device, execution results of a plurality of query language expressions. In various embodiments, the plurality of query language expressions may be concurrently executed, and the receiving may be contemporaneous with production of the execution results. Also, in various embodiments, the computing device may store a result item of the execution results for at least a first of the query language expressions in a memory block allocated exclusively for the first of the query language expressions while the first of the query language expressions is being executed, or in a result handle associated with the first of the query language expressions.

FIG. 1illustrates an overview of various embodiments of the disclosure. As illustrated, a storage system100may include a plurality of query language expressions102being concurrently or simultaneously executed (hereinafter, “concurrently executed” refers to concurrent and/or simultaneous execution) by a plurality of processors of one or more computing devices (such as the computing device illustrated inFIG. 6). The query language expressions102may concurrently query the same document and retrieve portions of the document (or different documents). The retrieved portions may then comprise the execution results104of storage system100. In various embodiments, the computing device(s) executing the query language expressions102may store their execution results104in storage106of storage system100contemporaneously with the production of the results104. Thus, storage of a result104of a single expression102may begin before that expression has completed execution and may continue intermittently or continuously while the expression102executes.

As illustrated, storage106may comprise a plurality of result handles108, some or all of result handles108each pointing to one or more memory or storage blocks110(hereinafter, “memory blocks110”). As a portion of a result104for an expression102is first produced, logic associated with storage106may create a result handle108for that expression102. If the portion is small and comprises the entire result104, the result104may be stored in the result handle108. If not, the logic associated with storage106may allocate a memory block110and set the result handle to point to the memory block110. If, as storage continues, the memory block110becomes filled, the logic associated with storage106may allocate an additional memory block110and set the last allocated existing memory block110to point to the new memory block110, creating a linked list of memory blocks110for results104of an expression102.

In various embodiments, storage system100may support dual reclamation models for the results104stored in storage106. In a first model (hereinafter “stack lifetime”), all results104may be reclaimed from storage106simultaneously or substantially simultaneously. In a second model (hereinafter “global lifetime”), results104for a single expression102or for a portion of such results102(such as result items of one memory block110) may be reclaimed individually. After being reclaimed, the memory blocks corresponding to the reclaimed results104/result items may be placed on a list of reclaimed memory blocks112of storage system100. Memory blocks listed on list112may be reused by logic associated with storage106, in some embodiments.

In various embodiments, the computing device(s) (not shown) implementing storage system100may be any sort of computing device(s) known in the art, except for logic (not shown), such as instructions622(described in greater detail herein), other logic adapted to perform the operations described more fully herein, and storage of the computing device(s), such as storage106. The computing device(s) may be personal computers (PC), workstations, servers, routers, mainframes, modular computers within blade servers or high-density servers, personal digital assistants (PDA), entertainment centers, set-top boxes, or mobile devices. An exemplary computing device is illustrated byFIG. 6, and will be described in greater detail herein.

In some embodiments, storage system100may be implemented on separate, remotely disposed computing devices. In various embodiments, where computing devices of storage system100are remotely disposed from each other, the computing devices may be communicatively connected to each other. In some embodiments, the computing devices may be connected by a networking fabric (not illustrated). Such a networking fabric may include one or more of a local area network (LAN), a wide area network (WAN), and the Internet, as is known in the art. In one embodiment, the networking fabric may comprise a private network or a virtual private network (VPN) which may utilize tunneling.

In various embodiments, query language expressions102may be any sort of expressions known in the art. In some embodiments, query language expressions102may be XPath expressions for extracting portions of a document, such as an Extensible Markup Language (XML) document. Further, the query language expressions102may comprise a collection of expressions that a user or program wishes to evaluate. As noted above, such expressions102may be concurrently executed by one or more processors of computing device(s) of storage system100. In one embodiment, the collection of expressions may belong to an Extensible Stylesheet Transformations Language (XSLT) document, or the like.

As illustrated, concurrently executed expressions102may produce execution results104. Because expressions102are concurrently executed, results104may be produced in an interleaved manner over time. For example, if three expressions102, such as expressions A, B, and C, each produce results104(such as A1, A2, and A3for A; B1, B2, and B3for B; and C1, C2, and C3for C), the results104may be produced in the following order (or in any alternative order): B1, C1, C2, A1, B2, A2, C3, A3, and B3. In various embodiments, each item or portion of a result104for an expression102may be a fragment of an XML, HyperText Markup Language (HTML), or like document.

In various embodiments, storage106may be any sort of storage, such as database(s) or file(s) stored in a storage device or devices, such as system memory604or mass storage606(illustrated inFIG. 6), except for result handles108, memory blocks110, and any logic associated with storage106.

In some embodiments, logic associated with storage106may store results104contemporaneously with their production. Returning to the above example, this means that logic associated with storage106may store result B1before C1is produced, and C2before A1is produced. In various embodiments, the logic associated with storage106is configured to recognize expressions102and to create/allocate a result handle108for each executing expression102as results104for each expression are first produced. An exemplary result handle is shown inFIG. 4and described in greater detail below. In some embodiments, result handles108may store metadata describing results104of their corresponding expressions102. Such metadata may include a homogenous type (such as string) to which all items of results104for an expression102belong, a type of a homogenous context which applies to all results104for an expression102, and/or indicators of whether results104are inlined (i.e., stored in the result handle108), whether the results104have a homogenous type or are heterogeneous, whether the results104include a result context, whether results104are stored in one memory block110or multiple memory blocks110, and/or whether results104are associated with a first or a second reclamation model (i.e., with a stack lifetime or a global lifetime). In various embodiments, result handles108may either store results104inline or include additional fields specifying a memory location of a first of the memory blocks110pointed to by the result handles and a size/number of items of results104stored in the memory blocks110.

In various embodiments, the metadata stored in result handles108may be acquired by the logic associated with storage106in a number of ways. In one embodiment, the query language expressions102may include characteristics or values describing the results104they are to produce. In such an embodiment, upon first recognizing an executing expression102and creating/allocating its result handle108, the logic associated with storage106may read the characteristics/values and set various fields of the result handle108to those characteristics/values. In another embodiment, the logic associated with storage106may determine the metadata for an expression102as the expression102executes.

In some embodiments, the logic associated with storage106may store a first result item/portion104for an expression102within the result handle108. Upon receiving an additional item/portion of results104which, when combined with the first item104, exceeds the available memory for the result handle108, the logic associated with storage106may reserve a memory block110and store the first and additional result items/portions104in the memory block110. The portion of the result handle108formerly storing the results104may then be set to point to the memory location/address of the memory block110and to count the number of result items/portions104stored for the expression102corresponding to the result handle108.

In various embodiments, as mentioned above, each resource handle108may point to one or more memory blocks110. As illustrated inFIG. 3, and described further below, each memory block may comprise a header portion and a series of result items104. In some embodiments, the header portion may include a link to a subsequent memory block110, a size of the memory block110to which it belongs, a context for the memory block110, and/or a context type. The series of result items104may comprise simply the result items104, if they belong to a homogenous type, or the result items104and their corresponding item types, if the results104are heterogeneous. If comprising both the items104and their corresponding types, each type may be stored contiguously with its corresponding item104.

In some embodiments, upon receiving additional result items/portions104for an expression102, the logic associated with storage106may determine if there is sufficient room in the memory block(s)110that have been reserved for that expression102to store the additional result item104. If there is not sufficient room, the logic may reserve a new memory block110and set the most recently reserved memory block110for the expression to point to the new memory block110, thereby creating a linked list of memory blocks110. In another embodiment, if there is not sufficient room and there is free space in storage106that is in conjunction with memory block110, the logic may grow itself instead of reserving a new memory block110. If there is sufficient room, then the logic may simply store the result item104in the existing memory blocks110. In various embodiments, the logic associated with storage106may repeat the determining, reserving and storing operations for an expression102until the expression has finished producing results.

In various embodiments, as mentioned above, memory blocks110may store a context for results104of a query language expression102. In some embodiments the context may indicate that results104for an expression102are context sensitive or that they are going to be filtered according to the context. For example, for the following expression102, “a[1]/d”, all of the child elements ‘d’ for the elements ‘a’ may be collected during processing of the expression102. The “[1]” fragment of the expression102, however, may indicate that only child elements of the first element ‘a’ are valid results. Thus, the “[1]” fragment may be considered a context and stored with the memory blocks110to facilitate filtering when the results104are reclaimed. In some embodiments, the logic associated with storage106may be configured with rules for detecting and storing result contexts.

In various embodiments, logic associated with storage106may support dual models for reclaimed results104from storage106, such as the stack lifetime and global lifetime mentioned above.FIG. 2illustrates these two models in greater detail. In some embodiments, as discussed above, the result handle for each expression102may include an indication of which of the models the results104of the expression102should be associated with.

In some embodiments, each expression102belonging to a collection, such as a collection of an XSLT, will be considered as belonging to a stack lifetime. For results104associated with a stack lifetime, the results104may be reclaimed from storage106simultaneously or substantially simultaneously. In a stack lifetime model, the results104may reside in a logically continuous memory area of storage106and thus can be reclaimed with a single operation, such as bumping a pointer. Thus, rather than reclaiming results104serially, in an expression-by-expression fashion, all results104belonging to a collection of expressions102and having their result handles108indicating a stack lifetime may be reclaimed at the same time, or contemporaneously.

In various embodiments, if it is desirable for results104to be reclaimed one expression102at a time, the global lifetime may be used. When using the global lifetime, results104for a single expression102or for a portion of such results102(such as result items of one memory block110) may be reclaimed individually. That is, results104stored in some or all memory blocks for an expression102may be reclaimed at the same time, allowing for expression-by expression retrieval, or even retrieval of simply a portion of the results104for an expression102. After being reclaimed, the memory blocks corresponding to the reclaimed results104/result items may be placed on a list of reclaimed memory blocks112of storage system100. Memory blocks listed on list112may be reused by logic associated with storage106, in some embodiments, and be reserved for results104of other expressions102. In various embodiments, the list112may be any sort of data structure known in the art, except for its contents, and may or may not be part of storage106.

FIG. 2illustrates dual reclamation models of various embodiments. As illustrated, a plurality of result handles point to linked lists of memory blocks, the blocks themselves being part of larger memory chunks. Further, the memory chunks are shown inFIG. 2as being associated with a result lifetime of one of two models: a stack lifetime model and a global lifetime model. In various embodiments, the result handles of the query language expressions may contain values for identifying the model or models to which the results of those expressions belong. As mentioned above, in one embodiment, the query language expressions may comprise a collection of XPath expressions of an XSLT. In such an embodiment, each result handle of each expression of the collection may have its value set to indicate that the result lifetime of the results is a stack lifetime. For such results belonging to a stack lifetime model, all blocks of memory may be reclaimed at the same time (or at approximately the same time). Thus, as illustrated, all blocks in the left memory chunks may be reclaimed at the same time.

In various embodiments, a result handle may instead indicate that the results of a query language expression have a global lifetime. If result items of a memory block having a global lifetime are reclaimed, those blocks may be placed on a list of reclaimed memory blocks, as discussed above. The memory blocks corresponding to the listed memory blocks may then be reused, but the reclaimed memory blocks may not be cleared of their contents until they are reused. InFIG. 2, memory blocks corresponding to listed, reclaimed memory blocks are shown in a darker gray than the other memory blocks.

FIG. 3illustrates a diagram of memory blocks of various embodiments. InFIG. 3, three sets of memory block are shown, each set including two memory block. In the first set, a homogenous result without a result context is illustrated. In such a result, each block storing the result may include a result head/header portion and a series of result items. As mentioned above, each result item may have a uniform size, and each memory block or set of memory blocks may have a variable size. Also, as shown, each header portion may include links to other memory blocks and a memory block size. By allowing each block to store a reference to a block or blocks that it points to, a linked list of memory blocks can be created.

In the second set, a homogenous result with a result context is illustrated. As is shown, such memory blocks may be identical to the above described blocks without context, with the only addition being a context field to the header portion to store a result context.

In the third set, a heterogeneous result with a result context is illustrated. As illustrated, such memory blocks may include an additional result context type field (shown as “CType”) in the header portion to indicate the type of the result context. Also, in various embodiments, a result item type (shown as “IType”) for each result item may be stored contiguously with the result items. As mentioned above, if all result items have the same type (i.e., the result is homogenous), the type may be stored in the result handle (as shown inFIG. 4), thereby saving storage space.

FIG. 4illustrates elements of a result handle of various embodiments. As illustrated, a result handle may include a number of fields to store metadata about an execution result of a specific query language expression. In some embodiments, the result handle may include a context type (shown as “CType”) for the result context of the execution results if the results are homogenous. Also, in various embodiments, the result handle may include a type (shown as “IType”) for the result items of the execution results if the results are homogenous.

As is further shown, the result handle may also include a number of flag fields. In various embodiments, a first of these fields (shown as “IL”) may provide an indication of whether result items of a query language expression are stored in the result handle (i.e., “inlined”). In some embodiments, a second of these fields (shown as “CF”) may provide an indication of whether the execution results of a query language expression include a result context. In further embodiments, a third of these fields (shown as “HG”) may provide an indication of whether result items of a query language expression are homogenous or heterogeneous. In some embodiments, a fourth of these fields (shown as “CT”) may provide an indication of a number of memory blocks (one or multiple) storing result items of a query language expression. In various embodiments, a fifth of these fields (shown as “SM”) may provide an indication of a result lifetime for result items of a query language expression.

In various embodiments, as shown, the result handle may also include fields for a start address of the referenced memory blocks and/or a number of result items stored in the memory blocks. In some embodiments, these fields may also be used to store an execution result in the result handle when the execution result is small, as described above.

In some embodiments, the result handle may have only some or all of the fields shown, and the fields may be arranged in any order and possess any size.

FIG. 5illustrates a flow chart view of selected operations of the methods of various embodiments. As illustrated, a computing device may receive execution results of a plurality of query language expressions, block502, the plurality of query language expressions being concurrently executed, and the receiving being contemporaneous with production of the execution results. In one embodiment, the query language expressions may be XPath expressions for extracting portions of an XML document. Upon receiving the results, the computing device may store a result item of the execution results for at least a first of the query language expressions in a memory block allocated exclusively for the first of the query language expressions while the first of the query language expressions is being executed, or in a result handle associated with the first of the query language expressions, block504. In some embodiments, the computing device may store metadata about the first of the query language expressions and references to a linked list of memory blocks in the result handle, block506, the memory blocks being employed for storing the result item. Further, in some embodiments, the computing device may store a context for result items of the first of the query language expressions in the memory block, block508.

In various embodiments, each memory block may include a header portion, the header portion having at least one of links to other memory blocks, a memory block size, a result context, or a result context type. Also, in some embodiments, the metadata to be stored in the result handle may include at least one ofan indication of a number of memory blocks storing result items of the first of the query language expressions,an indication of a result lifetime for result items of the first of the query language expressions,an indication of whether result items of the first of the query language expressions are homogenous or heterogeneous,an indication of whether the execution results of a query language expression include a result context,an indication of whether result items of the first of the query language expressions are stored in the result handle,a type of result items of the first of the query language expressions,a context type of result items of the first of the query language expressions,a start address of the referenced memory blocks, ora number of result items stored the memory blocks.

As is further illustrated, the computing device may then, in some embodiments, determine whether the memory block storing the result item includes room to store another result item of the execution results for the first of the query language expressions, block510. If the memory block does not have room, the computing device may then add and link another memory block to the memory block or grow the memory block, block512. In various embodiments, the computing device may then store the other result item in the memory block or the other memory block, block514.

In various embodiments, the computing device may also reclaim the result item from the memory block or the result handle, block516. If the first of the query language expressions is associated with a first result lifetime, the computing device may simultaneously reclaim the results of the plurality of query language expressions, block518, the plurality of query language expressions forming a collection. Also, if the first of the query language expression is associated with a second result lifetime and if the computing device has reclaimed the memory block by reclaiming the result item and the other result items stored in the memory block, the computing device may add the reclaimed memory block to a list of reclaimed memory blocks, block520.

FIG. 6illustrates an example computer system suitable for use to practice aspects of various embodiments. As shown, computing system600includes a number of processors or processor cores602, and system memory604. For the purpose of this application, including the claims, the terms “processor” and “processor cores” may be considered synonymous, unless the context clearly requires otherwise. Additionally, computing system600includes mass storage devices606(such as diskette, hard drive, compact disc read only memory (CDROM), a disc storage device, and so forth), input/output devices608(such as display, keyboard, cursor control and so forth) and communication interfaces610(such as network interface cards, modems and so forth). The elements are coupled to each other via system bus612, which represents one or more buses. In the case of multiple buses, they are bridged by one or more bus bridges (not shown).

Each of these elements performs its conventional functions known in the art. In particular, system memory604and mass storage606may be employed to store a working copy and a permanent copy of the programming instructions implementing one or more aspects of the above described teachings to practice the various embodiments, herein collectively denoted as622. The various components may be implemented by assembler instructions supported by processor(s)602or high-level languages, such as, for example, C, that can be compiled into such instructions.

The permanent copy of the programming instructions may be placed into permanent storage606in the factory, or in the field, through, for example, a distribution medium (not shown), such as a compact disc (CD), or through communication interface610(from a distribution server (not shown)). That is, one or more distribution media having an implementation of the agent program may be employed to distribute the agent and program various computing devices.

The constitution of these elements602-612are known, and accordingly will not be further described.

In embodiments of the present invention, an article of manufacture (not illustrated) may be employed to implement one or more methods as disclosed herein. For example, in exemplary embodiments, an article of manufacture may comprise a storage medium and a plurality of programming instructions stored on the storage medium and configured to program an apparatus to reclaim a first result item associated with an execution of a first query language expression from a memory block or a result handle, concurrently with reclaiming at least one other result item associated with another execution of a second query language expression, the first and second query language expressions forming a collection, if the first query language expression is associated with a first result lifetime.