Certain example embodiments concern a computer-implemented method of processing a relational query in a database system. The relational query addresses a plurality of data objects linked by one or more relationships. For each data object addressed by the relational query, at least one result is computed in accordance with at least one index structure, with the index structure being stored in a storage device of the database system. The results computed are merged in accordance with at least one translation data structure to produce a final result of the relational query, with the translation data structure representing the one or more relationships between the data objects and being stored in a memory of the database system.
5367675 November 1994 Cheng et al.
5802357 September 1998 Li et al.
5848408 December 1998 Jakobsson et al.
6411951 June 2002 Galindo-Legaria et al.
6505189 January 2003 On Au et al.
6505205 January 2003 Kothuri et al.
6546394 April 2003 Chong et al.
6615206 September 2003 Jakobsson et al.
6748392 June 2004 Galindo-Legaria et al.
7451144 November 2008 Koudas et al.
7472130 December 2008 Stern et al.
7483890 January 2009 Zhou et al.
7565342 July 2009 Fuh et al.
7761477 July 2010 Luo et al.
7895189 February 2011 Balmin et al.
8103658 January 2012 Flatz et al.
8219552 July 2012 Deng et al.
8498973 July 2013 Gutti et al.
2003/0167272 September 2003 Sinnott, Jr.
2005/0198001 September 2005 Cunningham et al.
2005/0198019 September 2005 Cunningham et al.
2006/0136388 June 2006 Steinau et al.
2008/0033914 February 2008 Cherniack et al.
2008/0065590 March 2008 Castro et al.
2010/0205351 August 2010 Wiener et al.
2010/0306212 December 2010 Tsirogiannis et al.
2012/0084322 April 2012 Goldstein et al.
2012/0096054 April 2012 Egan et al.
2012/0109981 May 2012 Graefe et al.
2012/0124096 May 2012 Krishnamurthy et al.
2012/0310917 December 2012 Sheinin et al.
2012/0330988 December 2012 Christie et al.
2013/0013890 January 2013 Manner et al.
2013/0117255 May 2013 Liu et al.
2013/0151568 June 2013 Ellison et al.
2013/0325902 December 2013 Bachar et al.
Valduriez, Patrick. "Join indices." ACM Transactions on Database Systems (TODS) 12, No. 2 (1987): 218-246. cited by examiner .
Kocberber, Onur, Boris Grot, Javier Picorel, Babak Falsafi, Kevin Lim, and Parthasarathy Ranganathan. "Meet the Walkers." (2013). cited by examiner .
Norton et al., Indexing every col. In a table 9 Jul 10, stackexchange.com, stackoverflow.com/questions/3211108/indexing-every-column-in-a-table. cited by examiner .
McKeeman, A Short Course in Compilers--Symbol Tables and Type 2007, Dartmouth, http://www.cs.dartmouth.edu/.about.mckeeman/cs48/mxcom/doc/Symbols.html. cited by examiner .
Knuth, The Genesis of Attribute Grammars date unknown, Dartmouth, http://www.cs.dartmouth.edu/.about.mckeeman/cs48/mxcom/doc/AttributeGramm- arHistory.pdf. cited by examiner .
Relational Query, http://enclopedia2.thefreedictionary.com/relational+query; Retrieved Jul. 5, 2012. 2 pages. cited by applicant .
Inverted Index, http://en.wikipedia.org/wiki/Inverted.sub.--index; Retrieved Jul. 5, 2012, 3 pages. cited by applicant .
P. Valduriez, "Join Indices," ACM Transactions on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 218-246. cited by applicant .
J. A. Blakeley, et al., "Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis," Proceedings of the International Conference on Data Engineering, IEEE, Feb. 5-9, 1990, pp. 256-263. cited by applicant .
P. O'Neil, et al., "Multi-Table Joins Through Bitmapped Join Indices," SIGMOD Record, vol. 24, No. 3, Sep. 1995, pp. 8-11, XP-002141931. cited by applicant .
Query Processing, COMP3017 Advanced Databases 2012-2013, Nicholas Gibbons, University of Southampton, Date of publication unknown, retrieved from http://www.edshare.soton.ac.uk/id/document/278685 on Oct. 6, 2014. cited by applicant.
1. A computer-implemented method of processing a relational query in a database system that includes volatile memory and non-volatile storage, the non-volatile storage storing a database of the database system, wherein the relational query, which is represented as a query tree, addresses a plurality of data objects linked by one or more relationships that are included in the database, the method comprising: a. for each data object addressed by the relational query, computing, in connection with a processor, at least one result in accordance with at least one index structure, the index structure being stored in a storage device of the database system; and b. merging, in connection with a or the processor, the results computed in (a) in accordance with at least one translation data structure to produce a final result of the relational query, where each edge between nodes of the query tree includes a corresponding translation data structure that represents the one or more relationships between the data objects, the translation data structure being stored in a memory of the database system, wherein the merging further comprises at least two passes: performing a first merging as part of a first pass of processing the query tree, wherein the first pass is performed recursively on nodes of the query tree, where results of a child node of a first node are merged, using a corresponding translation data structure included with the edge of the query tree between the first node and the child node, into results of the first node to obtain intermediate results for the first node, and performing a second merging as part of a second pass, after the first pass, of processing the query tree, wherein the second pass is performed recursively on nodes of the query tree, where the obtained intermediate results of the first node are merged, using a corresponding translation data structure included with the edge of the query tree between the first node and the child of the first node, into results of the child node to obtain results for the child node.
2. The method of claim 1, wherein the first merging comprises merging the results of each child node into the results of a corresponding parent node(s).
3. The method of claim 1, wherein the second merging comprises merging the results of each node into the results of a corresponding child node.
4. The method of claim 1, wherein the first pass and/or the second pass of processing the query tree traverses the query tree starting at the root node in a depth-first manner.
5. The method of claim 1, wherein for two given data objects which are addressed by the relational query and which are linked by a relationship, the translation data structure comprises a mapping of an identifier of the first data object to an identifier of the second data object in accordance with the relationship.
6. The method of claim 5, wherein, if the relationship is represented as a data object in a database of the database system, the translation data structure comprises a mapping of an identifier of the first data object to an identifier of the second data object and to an identifier of the relationship.
7. The computer-implemented method of claim 1, wherein during processing the relational query, data on the non-volatile storage is only accessed in indexed form for reading results for individual query conditions.
8. A non-transitory computer readable storage medium tangibly storing a computer program for processing a relational query, which is represented as a query tree, in a database system that includes at least one processor, wherein the relational query addresses a plurality of data objects linked by one or more relationships, the stored instructions comprising instructions that are configured to cause the processing system to: for each data object addressed by the relational query, compute at least one result in accordance with at least one index structure, the index structure being stored in a storage device of the database system; and merge the results computed in (a) in accordance with at least one translation data structure to produce a final result of the relational query, where each edge between nodes of the query tree is linked to a corresponding translation data structure that represents the one or more relationships between the data objects, the translation data structure being stored in a memory of the database system, wherein the merging further comprises: perform a first merging as part of a first pass of processing the query tree, wherein the first pass is performed recursively on nodes of the query tree, where results of a child node of a first node of the query tree are merged, using a translation data structure linked to the edge that is between the child node and the first node of the query tree, into results of the first node to obtain intermediate results for the first node, and perform a second merging as part of a second pass, after the first pass, of processing the query tree, wherein the second pass is performed recursively on nodes of the query tree, where the intermediate results of the first node are merged, using a corresponding translation data structure linked to the edge of the query tree that is between the first node and the child of the first node, into results of the child node to obtain results for the child node.
9. A database system, comprising: a. an interface configured to receive relational queries which address a plurality of data objects linked by one or more relationships; b. a storage device configured to store at least one index structure; c. a memory configured to store at least one translation data structure representing the one or more relationships between the data objects; d. control logic that, in connection with at least one processor, is configured to at least: as part of a first pass, for each data object addressed by the relational query, compute at least one result of a first node in a query tree of the relational query in accordance with the at least one translation index structure, where each edge between nodes of the query tree is linked to a corresponding translation index structure that is stored in the memory; as part of the first pass, merge, using a corresponding translation index structure that is linked to the edge between a child of the first node and the first node, the computed results of the child of the first node into results with results of the first node to produce an intermediate result of the relational query for the first node; as part of a second pass that is performed after the first pass, merge, using the corresponding translation index structure that is linked to the edge between the child of the first node and the first node, the computed intermediate results of the first node into results of the child node to obtain results for the child node.
10. The database system of claim 9, wherein the first pass is performed recursively for each node of the query tree.
11. The database system of claim 9, wherein the second pass is performed recursively for each node of the query tree.
12. The database system of claim 10, wherein the first pass and/or the second pass of processing the query tree traverses the query tree starting at the root node in a depth-first manner.
This application claims priority to EP 12 174 908.9 filed 4 Jul. 2012, the entire contents of which is hereby incorporated by reference.
Certain example embodiments of the present invention relate to a method of processing relational queries in a database system, as well as to a corresponding database system.
Nowadays, data-intensive computer systems typically store their data in databases and database systems are provided which allow storing the data into the database, as well as accessing the stored data.
Accessing data of a database is typically performed by formulating queries in a query language and having the database system process the query. Since complex databases typically store excessive amounts of data, sometimes even millions of individual data objects, many approaches have been developed for increasing the performance of the query processing to allow users to retrieve the searched data as fast as possible.
The most common conventional database systems are so-called relational database management systems (RDBMS). A common language for interacting with data stored in such RDMBS is the Structured Query Language (SQL) commonly known in the art. The theoretical concept of a relational database is based on a set of mathematical terms, wherein the most important is called relation. A relation is a mathematical description of a table and a relational database may be considered as a set of tables. Each row (also referred to as tuple) of a table comprises a data record (hereinafter also referred to as "data object" or "database object"), wherein the record comprises one or more attributes. The attributes correspond to the columns of the table. FIG. 7 shows a simple example of a relational database having a table "Book". As can be seen, the table "Book" stores in this example five data objects (rows) representing five books. Each book has an ID, a name and a genre code, which are stored in the columns of the table.
In order to retrieve data from such a relational database, queries are typically formulated in a declarative manner. This means that the query does not specify the steps the RDBMS is supposed to perform in order to retrieve the desired result. Rather, the query only specifies, in the form of a pattern, the properties of the desired result by means of one or more search conditions. A simple example of a query would thus be "Give me all books which have the term `history` in their name". As known in the art, more complex queries can be formulated on multiple attributes, which may be combined using logical operators.
Besides simple queries involving search conditions directed only to one type of object (i.e. to one single database table), more complex queries oftentimes involve multiple objects having relations defined therebetween. As an example, consider the query "Give me all books which have the term `history` in their name and the genre `Science`". As can be seen, this query involves two separate tables of the exemplary database of FIG. 7 (namely the tables "Book" and "Genre"), wherein each data object in "Book" is related to one or more data objects in "Genre" and vice versa. Such queries involving multiple objects and the relations therebetween are hereinafter referred to as "relational queries."
Large databases are typically stored on hard drives or other suitable permanent storage devices. As a result, traditional relational databases typically suffer from the relatively slow disk storage access for processing queries to the database. One main reason for the hard drive access being so slow is the random access to the tables. In other words, entries of the tables are typically not accessed in sequence, but rather in random order (depending on the information searched), which requires many movements of the head of the hard disk.
Some traditional relational databases try to improve performance by reading entire blocks from disk to a cache memory, hoping other entries in the block might be needed later on. However, because following relations in a query typically results in random access to the database tables, this strategy performs poorly on larger databases with many small rows.
Other commercially available products employ so-called No-SQL databases. Most vendors of such databases do not offer any support for relational queries at all. Others try to resolve relationships by creating special indexes for each relational query which can possibly be performed. This approach, however, is limited to scenarios with a small and fixed set of conceivable relational queries and is hardly practical in more complex scenarios.
Lastly, also in-memory databases exist, which can quickly process relationships because all data is loaded in a fast memory, such as a cache or random access memory (RAM). However, this approach requires large quantities of memory, which greatly limits the scalability do to the hardware limitations in modern computer systems.
Relational database systems (RDBMS) can be considered to be the most prominent architecture used nowadays. While RDBMS are generally able to perform complex relational queries, there are scenarios in which they deliver poor results. In particular, performance breaks down as soon as the system has to perform random disk access(es). This is typically the case when the following criteria are met: data involved in querying does not fit into memory (e.g. RAM), queries operate on many rows, and/or queries use joins across multiple tables.
Under these conditions, the person skilled in the art will appreciate that a RDBMS will have to resolve many foreign keys using row lookups in a non-cached table, causing a large number of random disk accesses. On mechanical hard drives, this will cause slow head movements, resulting in long query execution times and poor disk access efficiency.
It is therefore the technical problem underlying certain example embodiments to provide an approach for processing queries (in particular relational queries which take into account relationships between the data objects to be retrieved) which is more efficient and allows a faster retrieval of the searched data, thereby at least partly overcoming the above explained disadvantages of the prior art.
This problem is according to one aspect of the invention solved by a computer-implemented method of processing a relational query. In the embodiment of claim 1, the relational query addresses a plurality of data objects linked by one or more relationships and the method comprises the following steps: a. for each data object addressed by the relational query, computing at least one result in accordance with at least one index structure, the index structure being stored in a storage device of the database system; and b. merging the results computed in step a. in accordance with at least one translation data structure to produce a final result of the relational query, the translation data structure representing the one or more relationships between the data objects and being stored in a memory of the database system.
Accordingly, the embodiment defines a particularly efficient approach for processing relational queries, which is on the one hand based on traditional indexing technologies. Such index technologies are used in certain example embodiments for computing the results of the individual data objects addressed by the relational query. Preferably, the at least one index structure of certain example embodiments is an inverted index, which is used to store attributes of data objects and allows a quick retrieval of all objects which have specific values in specific attributes. Such inverted indexes are known in the prior art (cf. e.g. Wikipedia "Inverted index". Furthermore, each data object stored in the database preferably comprises a unique identifier (ID), which is returned as result of the index lookup operation.
The above-described indexing technologies allow performing search queries with conditions on multiple attributes of a single data object which can be combined using logical operators. These queries are typically resolved by splitting them up into individual index lookups. Object identifiers returned by the individual lookups are then merged, as indicated by the logical operators in the query to get the final result (e.g. if the query connects two search conditions with a logical "AND", the merged result is the intersecting set of the partial results of the index lookups, a logical "OR" corresponds to union set of the partial results, and so on).
As the skilled person will appreciate, these queries can be executed with good performance, since indexes can quickly produce all object identifiers for a given value and the merging of object identifiers according to the query structure requires no additional disk access. However, these search queries are limited to combinations of attributes of one single object. They especially cannot handle scenarios where a plurality of objects which have relationships between them are involved and wherein these relationships have to be considered in the query, i.e. they cannot handle relational queries, as concerned by certain example embodiments.
The mechanism proposed by certain example embodiments solves this problem by combining, i.e. merging, multiple search queries as described above by defining relational conditions between them, thus allowing to perform sub-graph searches heeding the relationships as well as object attributes.
This is achieved by introducing a translation mechanism which can translate object identifiers across relations. This translation mechanism is used in the merging step of certain example embodiments, where the computed results corresponding to the individual data objects are combined/merged in accordance with special translation data structures, which represent the relationships between the data objects stored in the database. As the person skilled in the art in database programming will appreciate, the term "computing at least one result" also encompasses the "empty set" as a result, since a database query might well produce no results for any query node or even the entire query.
Translation allows converting results from query conditions across relationships defined in the query, making them easily comparable and therefore searchable. Importantly, the translation data structures are kept in memory of the database system and only describe which object is related to which other object. Preferably, the translation data structures utilize primitive and compact identifiers and space efficient lookup techniques, such as binary search. Because no object data is kept in memory (note that the corresponding index structures are stored in a storage device of the database system), the translation structure is much smaller than the on-disk index in many scenarios.
In summary, certain example embodiments advantageously combine the advantages of storage devices (e.g. a hard disk of the underlying computer system, or any other type of permanent storage) and memory (i.e. fast memory, such as a random access memory (RAM) of the underlying computer system) while at the same time avoiding the disadvantages of both types of storage/memory. As the person skilled in the art of computer science will appreciate, the advantage of storage devices is its huge capacity and decent data streaming performance. Its disadvantage is its slow seek time, delivering poor random I/O performance. Memory, on the other hand, has limited capacity, but outstanding random I/O performance. In certain example embodiments, object data only exists on the storage device (by means of the index structures) and all random access is moved to the memory at the same time.
Accordingly, during processing the relational query, data on disk is only accessed in its indexed form for reading results for individual query conditions. This means that disk data access cost is almost linear to the number of query conditions, just like in conventional index search algorithms (good disk data streaming performance greatly reduces the impact of larger data graphs where each index entry has more result object identifiers stored). On the other hand, the handling of the random access pattern caused by following relationships is completely left to the translation mechanism. This mechanism is isolated from any object data and solely performs object ID translations according to the translation data held in memory.
In one aspect of the present invention, the method comprises the further step of representing the relational query as a query tree, wherein each data object addressed by the relational query is represented as a node of the query tree and wherein each relationship between the data objects is represented by an edge in the query tree. Representing the relational query in a tree format is a prerequisite of particularly advantageous aspects for processing the query, as will be explained further below. Most relational queries can be directly represented as query trees. However, if the relational query corresponds to a more generic connected graph, the method preferably produces a spanning tree based on the connected graph, as will be explained in the detailed description further below.
Preferably, the method further comprises the step of performing the above-described computing step and/or the merging step as part of a first pass of processing the query tree, wherein the first pass is performed recursively for each node of the query tree. During the first processing pass, the merging step preferably comprises merging the results of the current node with the results of the child node(s) of the current node. Most preferably, the method also comprises performing a second merging step as part of a second pass of processing the query tree, wherein the second pass is performed recursively for each node of the query tree, and wherein the second merging step preferably comprises merging the results of the current node with the results of the parent node of the current node. Accordingly, in a preferred embodiment of the invention, the query tree is traversed two times (i.e. in a first and a second pass), wherein the partial results of the individual data objects are first merged in the direction of the parent node and then in the direction of the respective child nodes. Moreover, the first pass and optionally the second pass of processing the query tree may traverse the query tree starting at the root node in a depth-first manner. This approach guarantees that at first, valid results are obtained for parent nodes of leaf nodes and afterwards for their parent and so forth all the way to the root node during the first pass. Determining the result for a parent based on its children delivers a result which is only missing the relation from the parent of the parent. Once the root node is reached, however, the result for it is complete and correct, because the root node has no parent of its own. The second pass will simply apply the missing parent relation to the children going downward from the root node. It is noted that the second pass may be performed equally well in a depth-first manner or a breadth-first manner.
Alternatively or additionally, for two given data objects which are addressed by the relational query and which are linked by a relationship, the translation data structure may comprise a mapping of an identifier of the first data object to an identifier of the second data object in accordance with the relationship. If the relationship is represented as a data object in a database of the database system, the translation data structure may comprise a mapping of an identifier of the first data object to an identifier of the second data object and to an identifier of the relationship. As already mentioned above, the provided translation data structures, by means of mapping the identifiers (IDs) of the respective data objects and/or relationships, is particularly compact, yet efficient.
Certain example embodiments also concern a computer program comprising instructions for implementing any of the above-described methods. Lastly, also a database system is provided, the database system comprising an interface, adapted for receiving relational queries which address a plurality of data objects linked by one or more relationships; a storage device, adapted for storing at least one index structure; a memory, adapted for storing at least one translation data structure, the translation data structure representing the one or more relationships between the data objects; and a control logic, adapted for, for each data object addressed by the relational query, computing at least one result in accordance with the at least one index structure, and for merging the computed results in accordance with the at least one translation data structure to produce a final result of the relational query.
Further advantageous modifications of embodiments of the database system of certain example embodiments are defined in further dependent claims.
FIG. 12: A block diagram illustrating a database system in accordance with an embodiment of the invention.
In the following, a presently preferred embodiment of the invention is described with respect to a method as schematically shown in FIG. 1, which illustrates the steps of the query processing (including pre-processing steps (cf. the steps 100 and 150) and post-processing steps (300 and 400)). The described method is preferably performed by a processing logic 60 within a database system 1 schematically shown in FIG. 12. As can be seen, the database system 1 comprises an interface 10 for receiving relational queries 20, as well as a database 30, in which the data objects to be searched are stored. Further, the inventive database system 1 comprises two helper structures, namely index structures 45 and translation data structures 55, the purpose of which will be described in more detail further below. Importantly, the index structures 45 are stored in a storage device 40 of the database system 1, whereas the translation data structures 55 are stored in a memory 50 of the database system 1.
Returning to FIG. 1, the relational query 20 is initially analysed in step 100 to determine whether it already is in tree form.
Generally, a query (such as queries formulated in a declarative language, as used herein) can be represented as a graph in the mathematical sense, i.e. as a set of objects where some pairs of the objects are connected by links. The interconnected objects are referred to as vertices or nodes of the graph, and the links that connect pairs of nodes are called edges. A graph may comprise any number of nodes and edges.
When a query is represented as a graph, zero or more search conditions may be attached to each node and edge. Preferably, each node and edge also has a unique name. On a single node/edge, multiple search conditions may be combined using logical operators (such as AND, OR, XOR, and the like). The search conditions describe which data object(s) stored in the database should be considered as result(s) for the individual nodes and edges. The way in which the edges connect the nodes defines the relations which must also be fulfilled by the result.
As used herein, a query 20 received by the database system 1 of certain example embodiments may have one of three typical appearances which are relevant to the search implementation. The three appearances are schematically shown in FIGS. 4a-c, and include an exemplary query with only a single node in FIG. 4a (called "simple/non-relational"), an exemplary query with three nodes A, B, C and edges between A-B and A-C, respectively in FIG. 4b (called "tree"), and an exemplary query with three nodes A, B, C and edges between A-B, A-C and B-C in FIG. 4c (called "connected graph").
Returning to step 100 in FIG. 1, the analysis of the query 20 would result in the determination that the query in FIG. 4b already is in tree form (in mathematical graph theory, a tree is a connected graph without cycles). Simple queries without any relations, such as the one shown in FIG. 4a, are also treated as tree (namely a tree with only one node, the root node, and zero edges). Thus, if the query has a tree structure, the method proceeds to step 200 (relational search; see below).
The query in FIG. 4c is not in tree form, but forms a more generic connected graph. In this case, the method proceeds to step 150, where the query graph is converted into a spanning tree, which is then used for the actual relational search in step 200 (see below). Ideally, the generated spanning tree has many leaves with highly selective criteria and therefore few results, as this reduces the number of translations needed in the first pass of the algorithm. Unconnected query graphs, i.e. queries comprising multiple sub-graphs which are not connected by an edge (in the mathematical sense of a forest) can be handled by performing a separate search for each individual connected graph.
In step 200, the actual relational search takes place. Generally speaking, a result tree is in this step filled with matching objects using the mechanisms described further below. The result tree has the same node and edge structure as the query and preferably also uses the same unique name(s) as specified in the query. Each node and edge is equipped with a set of result items which reflect the matching objects for this node or edge. The result item comprises the object identifier and a reference to all related nodes including the edge through which this relation is established.
The relational search on the query tree (step 200) is preferably performed in two passes, which are described in the following with reference to FIGS. 2 and 3. Both passes preferably process the query tree recursively, depth first (in the mathematical sense of a Depth-First Search; DFS) and start at the root node of the query tree. Alternatively, the second pass may be performed in a Breadth-First manner. The respective node which is currently investigated (i.e. the root node in the first processing iteration, the first child of the root node in the second processing iteration, etc.) is hereinafter referred to as "current node" or "context node".
The steps of the first pass are schematically shown in FIG. 2. Step 210 involves finding the result(s) for the condition(s) which the query defines for the current node. The object identifiers of database objects matching the condition(s) of the current query node are computed, preferably using traditional inverted index 45 search technologies. As the person skilled in the art will appreciate, the matching database objects could alternatively also be determined by scanning the database, however, at the cost of efficiency. In the subsequent step 220, the child node(s) of the current node is/are identified. If the current node does not have any child nodes (i.e. it is a leaf node of the query tree), the first pass ends. If, on the other hand, the current node has one or more child nodes, the first pass is now performed for each child node (step 230)--hence the recursivity of the relational search of certain example embodiments. In step 240, the results from the search on the current node are merged with the results from the children, which is performed using object identifier translation techniques described further below.
The steps of the second pass are schematically shown in FIG. 3. In step 250, the results for the current node which were obtained in the first pass are now merged with the results for its parent node using object identifier translation techniques described further below. This step is skipped for the root node (since by definition the root node has no parent node). In the subsequent step 260, the child node(s) of the current node is/are identified. If the current node does not have any child nodes (i.e. it is a leaf node of the query tree), the second pass ends. If, on the other hand, the current node has one or more child nodes, the second pass is now performed for each child node (step 270)--hence the recursivity of the relational search of certain example embodiments.
In summary, a preferred embodiment of the present search method traverses the query tree two times starting from the root node in a recursive depth-first manner. In the first pass, the merging operation is performed in the direction from the leave nodes to the root node. In the second pass, the merging is performed in the direction from the root node to the child nodes.
Referring again to FIG. 1, if the query was originally not in tree form (see above), missing relations are added in step 300. By using the object translator mechanisms disclosed herein, matching relations are added to the result for all relations from the original query which are not part of the spanning tree created above. Subsequently, the method proceeds to step 400, where unwanted results are filtered, i.e. all objects which do not match the original query are removed from the result. Note that this operation can be performed completely in-memory 50, as all necessary data was already put together by the relational search and the previous step.
The merging steps (cf. step 240 in the first pass of FIG. 2 and step 250 in the second pass of FIG. 3) are crucial steps in the above-described two query processing passes.
The merge step is always performed in the context of a single node. It is based on the current results of this node, which originate from the results for the node condition(s). It only considers those relations which are marked as required for the context node.
In order to be able to process results of related nodes together with results for the context node, the results of the related nodes have to be translated. In this step, the translator looks up matching relations using the result object identifiers from a related node. Using these relations it can easily find out the object identifier on the other side of the relation. These identifiers are passed on to the merger.
The merger removes all object identifiers from the result of the context node which do not appear in all translator results. As a result of this, only those results remain which fulfil all required relations. The respective dataflow of this process is schematically shown in FIG. 5.
In order to look up matching relations, the translator uses certain translation data structures 55 provided by certain example embodiments. Here, two cases have to be looked at: relations which are not explicitly represented by objects in the database (e.g. relations defined by using foreign key techniques), and relations which are explicitly represented in the database by means of dedicated objects.
The translation data structure 55 for relations which are not represented by objects is schematically shown in FIG. 6a. As can be seen, a relation table is created, which couples the object identifiers of the respective source and target objects, thereby, providing a "helper" data structure in the database which explicitly represents the relation between the objects.
If the relation itself is already represented by an object in the data graph, the translation data structure 55 is generated as schematically shown in FIG. 6b. As can be seen, each source/target object ID couple is also correlated with the identifier of the respective relation involved.
The above-described translation data structures 55 (also referred to as "lookup data structures" or "relation tables") allow to quickly identify in which rows of the relation table relations involving a specific object identifier can be found. Depending on the nature of the object identifiers, they may be implemented as lookup tables, hash tables, using binary search or any other suitable mechanism.
In the following, concepts of certain example embodiments are explained along a simple example involving a concrete search query 20. Further, it will be described how this search query 20 would be handled in the prior art, thereby highlighting the especially advantageous technical effects of certain example embodiments.
The example involves a database 30 comprising the tables shown in FIG. 7. As the person skilled in the art will appreciate, a relational database generally stores any number of tables, which can be understood as "datatypes" of the data stored in the database. Each table may store any number of rows, wherein each row corresponds to an individual database object (i.e. a data record). Further, each table has a number of columns, which represent the attributes of the data objects.
As can be seen in FIG. 7, the exemplary database 30 comprises a table "Book", which stores data objects representing books. Each individual book data object is represented in a row of the table. The table "Book" has three columns, which represent the attributes of the books, namely an ID (identifier) a name and a genre code. The different genres are stored in a table called "Genre", wherein each genre is defined by an ID (identifier), name and genre code. The database 30 further comprises a table "Publisher" storing data objects representing publishers with the attributes ID (identifier) and name. Lastly, a table "BookByPublisher" is provided, which stores tuples of BookID and PublisherID elements along with an ID (identifier).
The tables "Book" and "Genre" show an example of a relationship which is not explicitly defined by an own table in the database. Rather, the "Book" objects store a GenreCode attribute, thus relating the respective "Book" object to a corresponding "Genre" object. For example, the "Book" object with the name "Chemistry Cookbook" is related to the "Genre" object with the Name "Science" (due to the matching GenreCode attributes).
Furthermore the table "BookByPublisher" is an example of a junction table which relates to two other tables ("Book" and "Publisher") by containing references to their ids ("BookID" and "PublisherID").
"BookByPublisher" allows for instance to link "Chemistry Cookbook" and "Random Books" using a row containing "BookID" "1" and "PublisherID" "1".
"Which books (including genre and publisher) of the genres "Crime" and "Science" have been published by a publisher who has the word "books" in his name?"
As can be seen, this query 20 searches for data which is distributed across multiple tables of the database 30, wherein the relationships between the individual objects (e.g. books, genres and publishers) have to be taken into account. Therefore, this query is a so-called relational query.
If the tables and references (relations) between them are expressed as a data graph as described further above, the query graph for this question would look as schematically shown in FIG. 8 (using the same aliases as in the SQL statement). As can be seen, in accordance with the conceptual description further above, each object in the query is represented by a node in the query graph and each relation is represented by an edge in the query graph.
Importantly, the node requirement is assumed to be "required" in this example (see the explanations concerning the merge and translation techniques above) for all edges and their nodes in order to achieve an "inner join" behavior. This simplifies the merge step in this example to be a simple AND operation for the different translation and condition results.
When the exemplary database 30 shown above is handled by a preferred embodiment of the present invention, certain indexes 45 and translation tables 55 are defined in a preparatory step, i.e. before the query is actually processed.
More precisely, inverted indexes 45 are defined for the following table columns, wherein the indexes 45 are stored on the permanent storage 40 (e.g. a hard disk) of the database system 1: Book.Name, Book.GenreCode, Publisher.Name, Genre.Name, Genre.GenreCode. Generally speaking, the table columns to be indexed may be configured, i.e. preferably all columns on which certain criteria are to be applied should be indexed.
In addition to the above indexes, the database system 1 creates certain translation tables 55, which are stored in a fast memory 20 (e.g. a cache or the random access memory; RAM) of the database system 1. These translation tables are schematically shown in FIG. 9. Similar to foreign key definitions in conventional databases, also the relations and thus the translation tables to be generated are configurable in certain embodiments.
As already described further above, these translation tables 55 can be navigated in both directions. For example, the translation table 55 "Book.GenreCode<->Genre.GenreCode" allows to determine which "Book" objects are related to a specific "Genre" object based on the "GenreCode" attribute. The same table 55 also allows determining the "Genre" object relating to a specific "Book" object.
Once the above-described "helper" data structures (i.e. the indexes 45 and the translation data structures 55) are provided in the database system 1, the actual query processing can take place.
For the provided example, the pre and post processing is rather simple. Accordingly, the "Analyze Query" step (cf. step 100 in FIG. 1) determines that the query 20 (see above) already is in tree form and thus the method can proceed directly to the "Relational Search" step (cf. step 200 in the left branch of FIG. 1), more precisely to the first pass shown in FIG. 2.
As already described above, the first pass starts with the root node, which is for the given exemplary query graph the node B (cf. FIG. 8). Step 210 ("Find results for conditions of current node") does not need to do anything because node B has no conditions attached. Step 220 ("Identify child node") finds the child nodes of node B, which are the nodes G and BBP. Because there are child nodes, step 230 ("Child nodes pass 1") is now started for these child nodes one by one.
Accordingly, the first pass now starts for node G. Step 210 ("Find results for conditions of current node") determines that node G has the condition "Name in `Crime`, `Science`" attached and thus, the genres with ID "1" and "3" are the results of this step, since these genres match the condition of having either the name "Crime" or "Science". Further, step 220 ("Identify child nodes") finds that there are no child nodes to be processed for node G. Therefore, the first pass ends for node G.
The first pass now starts for node BBP. Step 210 "(Find results for conditions of current node") does not need to do anything because node BBP has no conditions attached. Step 220 ("Identify child nodes") finds the child node P. Because there are child nodes, step 230 ("Child nodes pass 1") is now started for these child nodes one by one.
Accordingly, the first pass now starts for node P. Step 210 ("Find results for conditions of current node") finds the publishers with ID "1" and "3", which match the condition attached to node P, namely the condition of containing the word "Books". Step 220 ("Identify child nodes") finds that there are no child nodes to be processed. Therefore, the first pass ends for node P.
At this point, the first pass (cf. FIG. 2) has been started for all nodes in the query tree and all initialization was done. The result graph currently looks as shown in FIG. 10a (note that bold result elements in the Figure indicate values changed in the respective pass and "*" indicates that all objects match). As can be seen, the structure of the result tree resembles that of the query tree (as explained further above) and the intermediate results of the individual node conditions defined in the query tree are attached to the respective nodes of the result tree. For example, since the genres "1" and "3" were found to be results for node G (see above), node G of the result tree contains "(1; 3)", and so on.
The first pass now continues for node BBP. Step 240 ("Merge with results from children using translation"; cf. FIG. 2) does the following: The results for P (which is a child of BBP) are translated into results for BBP using the translation table 55 for the relation "BookByPublisher.PublisherID<->Publisher.ID" (cf. FIG. 9), which was defined in the query. This yields the entries 1, 2, 4 and 6. These entries are also the new result for BBP, because the node did not have any results restrictions yet. This ends the first pass for node BBP.
The first pass now continues for node B. Step 240 ("Merge with results from children using translation") now does the following: The translation table "Book.GenreCode<->Genre.GenreCode" used for the edge between G and B yields 1, 2, 4 and 5. The translation table "Book.ID<->BookByPublisher.BookID" used for the edge between B and BBP yields 1, 3 and 5. The current result is not restricted, and thus the new results for B are all those entries which are contained in both translation results, namely 1 and 5. The first pass has now been completed and the current result graph looks as shown in FIG. 10b. The result for the root node B is already final, all child nodes, however, can still change.
The second pass (cf. FIG. 3) now starts for the root node B. Because there is no parent node for the root node B, step 250 ("Merge with results from parent using translation") does not do anything. Step 260 ("Identify child nodes") finds two child nodes G and BBP. Thus, step 270 ("Child nodes pass 2") is now started for these child nodes one by one.
Accordingly, the second pass now starts for node G. Step 250 ("Merge with results from parent using translation") now does the following: The translation table "Book.GenreCode<->Genre.GenreCode" used for the edge between B and G, which yields 3. Merged with the current result for G, this creates the new result 3. Step 260 ("Identify child nodes") finds that there are no child nodes to be processed. Therefore, the second pass ends for node G.
The second pass now starts for node BBP. Step 250 ("Merge with results from parent using translation") now does the following: The translation table 55 "Book.ID<->BookByPublisher.BookID" is used for the edge between B and BBP, which yields 1, 2 and 6. Merged with the current result for BBP, this creates the new result 1, 2 and 6. Step 260 ("Identify child nodes") finds that there is one child node P. Because there are child nodes, step 270 ("Child nodes pass 2") is now started for this child node.
Accordingly, the second pass now starts for node P. Step 250 ("Merge with results from parent using translation") now does the following: The translation table 55 "BookByPublisher.PublisherID<->Publisher.ID" is used for the edge between BBP and P, which yields 1 and 3. Merged with the current result for P, this creates the unchanged result 1, 3. Step 260 ("Identify child nodes") finds that there are no child nodes to be processed. Therefore, the second pass ends for node G.
The second pass now continues and ends for node BBP. The second pass now continues for node B and ends. At this point, the final result of the relational search has been calculated, which is shown in FIG. 10c. Accordingly, the result tree in FIG. 10c shows that the result of the exemplary query 20 explained above ("which books of the genres "Crime" and "Science" have been published by a publisher who has the word "books" in his name?") is the books with IDs 1 and 5, i.e. the books "Chemistry Cookbook" and "History of Mankind".
It is important to note that using certain example embodiments, the given example only performs three index lookups in the first pass, namely two index lookups to find results matching the conditions for node G (one for each word) and one more for node P. All the other results are computed using only the translation tables 55. As described above, since these translation tables 55 are stored in a fast memory 20 of the database system 1, the query processing in accordance with certain example embodiments is exceptionally fast, in particular faster than executing the query 20 in accordance with conventional techniques known from the prior art, which will be shown in the following.
In the following, the exemplary query shown further above is processed using a conventional SQL database.
It is assumed that all columns used for lookups are indexed. Furthermore, it is assumed that row keys are used for internal data handling. These row keys are assumed to start from 1 and increase by one for each row given in the example table above (therefore, they correspond to the numeric value of the ID column by chance).
The execution plan described hereinafter is only an example. The plan built by actual database servers depends on many factors and varies between vendors. However, the problem of the many random disk accesses remains.
Step 1--Determine Books for Genres: At first, two index lookups are performed on the "Genre" table (cf. FIG. 7) for the genres "Crime" and "Science". The resulting rows 1 and 3 are read to determine the "GenreCode" for each found genre C and S. Furthermore, two index lookups are performed on the "Book" table to resolve the "GenreCodes" into rows 1, 2, 4 and 5 of the "Book" table. The intermediate result looks like shown in FIG. 11a.
Step 2--Determine Books for Publishers: An index lookup is now performed on the "Publisher" table to obtain rows matching "books". The resulting rows 1 and 3 are read to obtain the IDs 1 and 3. Now, two index lookups are performed on the "BookByPublisher" table for PublisherID 1 and 3. The resulting rows 1, 2, 4 and 6 are read to obtain the BookIDs 1, 3 and 5. On the "Book" table, three lookups are used to find the rows containing the IDs. These rows are 1, 3 and 5.
Step 3--Join Results: Finally, the rows for the "Book" table are merged together. The end result looks like shown in FIG. 11b.
As the person skilled in the art of database programming will appreciate, the above-described prior art approach of handling the exemplary query needs 3 lookups again to resolve the conditions. In addition, 7 index lookups and 8 read operations are required to perform the joins on the tables. Because the relations from other tables can typically not be reflected in the order of rows of a table, these additional lookups are randomly distributed across the index and data space and therefore show poor disk access behavior.
In conclusion, it can be seen in the example that the approach proposed by certain example embodiments delivers improved performance even in this simple example. It is noted that the more data is actually processed, the bigger the advantage gets. This is because the inventive approach only needs index lookups to resolve query conditions. In other words, it only needs to stream more data per condition on large databases, but it does not need more disk seeks (note that streaming is fast, but seeking is slow). On the other hand, the traditional prior art approach typically needs an additional index lookup and row read per additional row to be considered in a relation.
While the concepts of certain example embodiments have been described in the context of an exemplary database storing books, it will be appreciated that the invention is not limited to this exemplary application scenario. Rather, certain example embodiments may well be used e.g. in the context of analyzing and searching business process modeling data. In addition, the same approach can be applied in many different areas where data can be represented in a relational model and relational queries need to be carried out. Certain example embodiments allow one to quickly identify all contents including relations which match a certain pattern. The pattern itself is represented as related items. Each item in the query can have criteria defined, and only matching contents are considered as instances of this item. Some example use cases include process models, which can be transformed into different representations on-the-fly by identifying all item instances which have specific relation patterns to a context node, indicating a certain semantic, users doing complex process data analysis by finding all sub-graphs which match a certain pattern graph, or relational queries performed on a NoSQL data store.
As disclosed herein, one concept of certain example embodiments is that an efficient translation mechanism is provided for handling the random access patterns involved in processing relational queries. The mechanism is isolated from the actual object data and is performed on accumulated translation data held in quickly accessible memory.
It will be appreciated that as used herein, the terms system, subsystem, service, module, control logic, program logic, programmed logic circuitry, engine, and the like may be implemented as any suitable combination of software, hardware, firmware, and/or the like. The systems described herein may include, for example, processing resources such as, for example, at least one processor and a memory, that may at least partially control software and/or other modules, etc. It also will be appreciated that the storage locations/repositories herein may be any suitable combination of disk drive devices, memory locations, solid state drives, CD-ROMs, DVDs, tape backups, storage area network (SAN) systems, and/or any other appropriate non-transitory tangible computer readable storage medium. For instance, data may be exported to a non-transitory computer readable storage medium. It also will be appreciated that the techniques described herein may be accomplished by having at least one processor execute instructions and/or applications that may be tangibly stored on a non-transitory computer readable storage medium. Similar statements apply with respect to clients, servers, and/or other elements in various network arrangements.


text:
Nbntkf
A Business Traveler's Guide To Houston (2023)
Dos & Don'ts in Houston DO: DON'T: Five Tips To Master Houston Transportation 1. Take advantage of METRORail 2. Cab around downtown. 3. Rent a BCycle. 4. Walk once you reach your neighborhood. 5. Know what names refer to what highways. Your Houston Soundtrack Best Hotels For Business In Houston Marriott Marquis Omni Houston JW Marriott Houston Downtown Magnolia Hotel Houston Royal Sonesta Houston Galleria Hotel Alessandra Best Houston Happy Hours To Wow A Client OKRA Charity Saloon Pitch 25 1751 Sea & Bar BB Lemon Kau Ba Saigon Kitchen Riel The Pink Elephant Room Houston Bleisure Travel Done Right Get breakfast tacos. Hang out in the Discovery Green. Visit the Museum District. Buffalo Soldiers National Museum The Health Museum Houston Museum of Natural Science Watch the bats at the Waugh Drive Bridge. Catch a game. Close the night with live music. Stuff Your Face in Houston Whataburger Georgia James Jackson Street BBQ Chocolate Craftory Explore Chinatown Videos
Dos & Don'ts in Houston
Don't mess with Texas. Let's get that one out of the way. Here are some other dos and don'ts to keep in mind as you head to Houston.
Mind your manners. Texans will greet you with respect, and it's best to return it.
Come hungry, because Houston is a foodie's dream, from barbeque to ethnic cuisines.
Take advantage of Houston's green spaces. The city has a reputation as an urban sprawl, but also features acres of parks.
Loop Texas in with the South. It's geographically a southern state, but Texas is a cultural epicenter unto itself.
Complain about the weather. Houston's humidity is legendary. Everyone deals with it.
Call your preferred soft drink soda or pop. It's a Coke, even if it's not a Coke.
Five Tips To Master Houston Transportation
Houston is massive. With 628 square miles, it's the ninth-biggest city in the United States, in total area. Is getting around Houston easy? It depends on where you are and your preferred method of transportation. Before you go, keep these tips in mind:
1. Take advantage of METRORail
With just three lines, Houston's rail system doesn't provide the same coverage as other big cities, but it is inexpensive. The fare is $1.25, so if your destination is close to a stop, the METRORail is the way to go.
2. Cab around downtown.
Moving around downtown Houston at the wrong time of year—the heart of humidity season—isn't the most fun thing for business travelers, especially those in suits. Skip walking or waiting for an Uber, and hail a cab instead. The city instituted a flat taxi rate of $6 for downtown, regardless of the number of passengers.
(Video) Houston Vacation Travel Guide | Expedia
3. Rent a BCycle.
If you want to add exercise to your commute, download the BCyle app and get riding. Houston has miles of bike trails and has made an effort to make the car-dominant city more bike-friendly. BCycle bike-sharing is a good start. A $13 monthly membership (that you can cancel at any time) gets you unlimited rides for up to 60 minutes. Otherwise, $3 buys you 30 minutes of biking.
4. Walk once you reach your neighborhood.
For all its sprawl, Houston is walkable on micro-levels. Once you reach your destination, you'll likely find a variety of establishments within walking distance. So bring your walking shoes!
Houston to New York flights: Connecting two populous US cities
5. Know what names refer to what highways.
You don't necessarily have to rent a car while in Houston, but if you do, it's important to know the road system. Interstate 45 South is known as the Gulf Highway. Texas 288 is the South Freeway or the Nolan Ryan Expressway, depending on where you're headed. There's a helpful guide at the bottom of this post on VisitHoustonTexas, so when you get directions, you'll know exactly where to go.
Your Houston Soundtrack
Houston can stake its claim as a home of country music, a hotbed of hip-hop, and an influencer on Southern rock, soul, gospel, jazz, and rhythm & blues. In other words, the Houston sound is a little bit of everything, and it means something different to different listeners.
Best Hotels For Business In Houston
When it comes to choosing your home away from home, Houston has rooms for all types of business travelers. Here are six to consider booking for your trip:
Marriott Marquis
The Marriott Marquis has swanky furniture in its lobby, NASA-inspired decor everywhere, and a skywalk to the George R. Brown Convention Center. But let's be honest: The pool area sets this hotel apart from all others. In addition to a jacuzzi and infinity pool, there's a Texas-shaped lazy river that lights up at night. The Marriott Marquis also neighbors the Discovery Green, a wonderful, activity-filled city park.
Omni Houston
Fresh off a $30 million renovation, the Omni Houston offers business travelers all the usual amenities—free Wi-Fi, spacious rooms with a variety of choices, full lounge—as well as some bonuses. The fitness room is open 24 hours, and there are two outdoor pools.
JW Marriott Houston Downtown
The JW Marriott Houston Downtown puts you in a place of luxury while making you feel at home. Each room is equipped with an iPad you can use to order room service or reserve spa treatment. And you can book your room based on need. Have to get work done? The Presidential Suite comes with a private office. Want to relax after a long day? The Spa Inspired King features a tub as well as a spa lounger next to the bed.
(Video) Houston Texas Travel Guide: Best Things To Do in Houston
Magnolia Hotel Houston
The building once housed the Houston Post Dispatch newspaper and later served as the corporate office for Shell Oil. It's since been renovated to now host business travelers and tourists seeking chic lodging in a historic setting. In addition to luxurious rooms, the Magnolia features a rooftop pool, 24-hour fitness center, and a business center with high-speed internet.
Royal Sonesta Houston Galleria
The Royal Sonesta in Houston's Uptown neighborhood has similar offerings as the aforementioned hotels, with a more laid back feel. If they're available, secure a concierge guest room, which will give you access to the concierge lounge. Take in sweeping views of Houston while winding down from your business trip.
This is business traveling in luxury, and then some. The Hotel Alessandra is a short walk from the George R. Brown Convention Center and METRORail, but if you want to really move in style, then you'll love the Maserati—yes, Maserati—car service. The spacious rooms are great, too, with tablets to place room service orders. You can also treat yourself to a spa day.
Best Houston Happy Hours To Wow A Client
What's better? A meeting in a lobby or casual conversation over drinks and appetizers? That's what we figured. Impress your clients or fellow business travelers by hitting these spots once the workday is done.
OKRA Charity Saloon
If you can only get to one happy hour during your trip to Houston, make it the OKRA Charity Saloon. Patrons will receive a vote for each drink they purchase, which they can then cast for one of four local charities selected by OKRA's members. At the end of the month, OKRA makes a donation to the charity with the most votes. It's an easy way to support a great prize. The drinks and food—like fried pickled okra—are tasty, too.
Soccer's popularity is on the rise in the United States, as is that of soccer pubs. Pitch 25 is an east downtown Houston beer garden across from BBVA Compass Stadium (home to Major League Soccer's Houston Dynamo and National Women's Soccer League's Houston Dash) that features spacious indoor and outdoor setting, and, for your purposes, more than 100 beers on draft.
1751 Sea & Bar
Houston's proximity to the Gulf of Mexico makes fresh seafood a welcome departure from the heavy meats of Texas cuisine. At 1751 Sea & Bar, happy hour goers can enjoy gulf oysters for $1, a raw bar featuring crudo and poke, and half-priced gin and tonics.
BB Lemon
If you'd like comfort food in a casual setting, BB Lemon's "Lemon Hour" is for you. Grab $8 craft cocktails to wash down Houston favorites like Frito pie (made with house-made beer cheese), chicken fried pickles, wagyu hot dogs, and pistachio-crusted fried shrimp.
(Video) HOUSTON TRAVEL GUIDE 2022 - BEST PLACES TO VISIT IN HOUSTON TEXAS IN 2022
Kau Ba Saigon Kitchen
Celebrity chef Nikki Tran (featured on Netflix's "Ugly Delicious") has introduced Viejun, a mashup of Vietnamese and cajun dishes, to Houston. It's a combination that makes sense. After all, Houston is home to a large Vietnamese population. Sip half-priced wine and cocktails while sampling some Vietnamese street food with Viejun spices.
Are you in Houston on a Monday? If so, head to Riel, a bar that starts the workweek right with an all-night happy hour. Select beers are $4, but the appeal here is in the tasty, exotic menu. Try the gator karaage or chicken skin yakitori.
The Pink Elephant Room
This is one of Houston's newer establishments, but it's making an early dent. The Pink Elephant Room presents a welcoming, understated atmosphere in a historic building. Sample local craft beers on draft or indulge on $2.50 Lone Stars. Business travelers who work a bit later than usual can unwind here, where the "happier hour" runs until 7 p.m.
Houston Bleisure Travel Done Right
If you're lucky enough to have a bleisure day in Houston, you may want to prioritize the Johnson Space Center. It's a fairly decent hike (25 miles) from downtown, however, and you'll want to spend all day there. That's one option for bleisure. Here are several more suggestions to make a day of it in Houston.
Get breakfast tacos.
Tex-Mex extends to all three meals, with breakfast, arguably, the hidden gem. Wake up with coffee and the savory goodness of breakfast tacos, served at stands and restaurants all over Houston, such as Texas Tacos & BBQ, Tacodeli, Villa Arcos, Luna Y Sol Mexican Grill, and Brothers Taco House. You really can't go wrong.
Hang out in the Discovery Green.
Smack dab in the middle of Houston is a vibrant city park with activities that range from leisurely to athletic. Rent a kayak on Kinder Lake for $5, or go skating: The outdoor ice rink is open November to February. In need of some relaxation? There's plenty of lawn space, as well as a 4,700-square-foot deck under the oak trees. It's a perfect place to catch up on reading.
Visit the Museum District.
Houston's Museum District—some four miles from downtown—is home to 19 museums, which cover everything from modern art to cultural histories. It's a walkable, leafy neighborhood that deserves your time. Explore the offerings, and check out these three stops in particular:
Buffalo Soldiers National Museum
The Buffalo Soldiers National Museum honors the all African-American military units that were formed following the American Civil War. The museum educates visitors about an often-forgotten portion of American history that helped define the West.
The Health Museum
An interactive science center, the Health Museum invites visitors to learn about themselves. "You: The Exhibit" uses modern technology to give visitors an inside look at their physical and mental selves.
(Video) Things to Do in Houston: Ultimate Houston Travel Guide (from an insider's POV)
There's a little bit of everything at the Houston Museum of Natural Science: a planetarium, butterfly center, and more than a dozen permanent exhibits including a collection of dinosaur fossils.
If you like what you find in the Museum District and want more, consider an excursion to the Art Car Museum or the National Museum of Funeral History.
Watch the bats at the Waugh Drive Bridge.
You don't have to be a chiropterologist, or even a Dracula-enthusiast, to be awed by the flying mammals at the Waugh Drive Bridge in Buffalo Bayou Park. Mexican free-tailed bats call the concrete bridge home, and thousands break out in the early evening for an insect feast.
Catch a game.
Houston is a haven for sports fans. You have the Houston Astros (Major League Baseball), Dynamo (Major League Soccer), and Dash (National Women's Soccer League), all of which play in downtown stadiums, to choose from during the summer. Then there's the Texans (National Football League) and Rockets (National Basketball Association), in addition to four NCAA Division I athletic programs (Houston, Rice, Houston Baptist, and Texas Southerns). And if you're free on a Friday, check out the famous Friday night lights of Texas high school football. In other words, there's always a game to catch in town.
Close the night with live music.
It's Houston. You can't leave town without jamming or do-si-doing to some live music. The Firehouse Saloon is a true honky tonk that's become one of the most popular country music venues in Texas. Fitzgerald's is a Houston landmark that houses up-and-comers and established acts alike. And for an authentic experience, travel to Dosey Doe in The Woodlands, a little more than a half-hour drive north of Houston, which hosts country music and dancing in an old tobacco barn.
Stuff Your Face in Houston
There is no shortage of quality bites in the Space City. Bring your appetite when you head to Houston, so you can get your fill at these renowned restaurants.
No establishment embodies "Everything's bigger in Texas" better than Whataburger, the ubiquitous fast-food burger joint. The chain dishes out healthy portions of unhealthy food 24 hours a day.
Georgia James
Chef Chris Shepherd made headlines with his previous restaurant, Underbelly, and he's at it again with Georgia James. Located in Montrose, Georgia James is an upscale, fun steakhouse that epitomizes the best of Houston flavors.
(Video) One Day in Houston: BBQ, Tacos, & Things to Do!
Jackson Street BBQ
Legit Texas barbeque has a home in downtown Houston, thanks to Jackson Street BBQ. As always in Texas, skip the pork products and dive into the brisket. Tasty sides include fried mac and cheese and dirty rice.
Chocolate Craftory
This requires a car and a little drive northwest from Houston to Tomball, but the payoff is worth it. Chocolate Craftory supplements pit barbeque favorites with handcrafted chocolate. Sweet and savory, indeed.
Explore Chinatown
Houston's Chinatown is really Asiatown, a neighborhood filled with culinary delights from China, Vietnam, Korea, India, Malaysia, and more. Crawfish & Noodles' name tells its story; customers can sample pho and boiled crawfish. Fung's Kitchen is an excellent choice for dim sum, while Tiger Den promises exceptional ramen.
1. Houston USA. Largest City in Texas. Sights, People and Economy
(CoolVision)
2. Houston - City Video Guide
(Expedia.com.au)
3. Travel Guide || Most amazing top 10 things to do in Houston Texas 2021
(Camy On The Go)
4. FREE Things To Do in Houston- Texas. Travel Guide #houstontexas #houstontravel
(Saloua Ibaline | Digital Nomad )
5. Houston Texas: Cool Things To Do // Destinations Explained
(Venture Addicts)
6. How YOU can Travel Full Time, Not Break The Bank, & Make Money Online (A Step-by-Step Guide)
(The Table With AO)
30 Side Hustles Perfect for College Students
9 Body Parts You Can Legally Sell for Cash - Low Income Relief
TABLÓN DE ANUNCIOS .COM - sin papeles. trabajo limpieza mantenimiento sin papeles. Ofertas de empleo de trabajo limpieza mantenimiento sin papeles
Texas Remote Work Resources
Best Delta-9 Gummies 2022: Buy Strongest Delta-9 THC Edibles Online
FIFA 23 Spieler-Eigenschaften: Die besten Traits erklärt | EarlyGame
Protests spread across the US after the Supreme Court overturns the constitutional right to abortion | CNN
Calls for calm as protests are planned over Tyre Nichols bodycam video
List of Cities Rioting and States Where National Guard Has Been Deployed
January 26, 2023 - 5 former officers indicted in death of Tyre Nichols
Author: Fr. Dewey Fisher
Name: Fr. Dewey Fisher
Address: 917 Hyun Views, Rogahnmouth, KY 91013-8827
Job: Administration Developer
Hobby: Embroidery, Horseback riding, Juggling, Urban exploration, Skiing, Cycling, Handball
Introduction: My name is Fr. Dewey Fisher, I am a powerful, open, faithful, combative, spotless, faithful, fair person who loves writing and wants to share my knowledge and understanding with you.
enknen.best
Nbntkf is a website that writes about many topics of interest to you, a blog that shares knowledge and insights useful to everyone in many fields.
© 2023 Nbntkf. All Rights Reserved.

redpajama_set_name: RedPajamaCommonCrawl


text:
Divers Doth Use All Study Guides Homework Help Lesson Plans
Divers Doth Use
by Sir Thomas Wyatt
As much as Wyatt's personae complain about female behavior, his poems often reflect more poignantly on male attitudes and actions. In a promiscuous court such as Henry VIII's, in which the men and women all seem to indulge in rather loose expression of sexual desires, why is it that men react so vehemently and emotionally, so irrationally, to infidelity, especially given their own participation in and enjoyment of this state of affairs?
In writing about love, a great many poets suggest that behavior in romantic situations has much to do with who lovers imagine their beloveds to be. Such a powerful emotion as love often leads people to create elaborate, imaginative conceptions of others, conceptions that are not usually very truthful or accurate. When a lover discovers that his beloved is not the person he imagined her to be, the consequent disillusionment can lead to bitter reactions. Witness, for example, the disillusionment of the speaker in William Shakespeare's Sonnet 147 ("My love is as a fever, longing still"): "For I have sworn thee fair and thought thee bright,/ Who art as black as hell, as dark as night." This bitter derision of the beloved seems an echo of the kind of responses of which Wyatt's speaker complains.
Yet one might ask whether the attitude of Wyatt's persona is any better. In subtle ways, Wyatt suggests that this man's manner of dealing with infidelity is also literary—that is, that his manner mimics a popular poetic or proverbial expression that may not accurately reflect the real experience, the actual situation. Although he says he will not call the woman false, he goes on to do just that, and the proverb he picks up to support his own stoic attitude does worse than simply insult the individual woman: It insults all women as innately false.
Does the sonnet "Divers Doth Use" by Sir Thomas Wyatt have any connotations?
Latest answer posted November 4, 2008, 1:39 am (UTC)
Reading poetry from a different age and culture presents two fundamental questions: To what extent does the poet's thinking differ from present-day thinking? To what extent does it differ from that of his contemporaries? Viewing this poem as is done here implies that Wyatt was able to distance himself from the conventional misogyny of his age enough to see male attitudes toward women as the creation of their own false expectations and double standards. The whole body of Wyatt's love poetry substantiates this conclusion; Wyatt shows himself again and again to be a keen observer of sexual politics among sophisticated courtiers, and of the literary conventions that misled those literate men and women about the identities of others and of themselves.
"Divers Doth Use - Themes and Meanings" Critical Guide to Poetry for Students Ed. Philip K. Jason. eNotes.com, Inc. 2002 eNotes.com 31 Jan. 2023 <https://www.enotes.com/topics/divers-doth-use#themes-themes-and-meanings>
Download the entire Divers Doth Use study guide as a printable PDF!
What is the poet saying in Sir Thomas Wyatt's sonnet "Divers doth use"?
The Open Window
by Saki
by Ray Bradbury
Where Are You Going, Where Have You Been?
by Joyce Carol Oates
by Charlotte Perkins Gilman
by Nathaniel Hawthorne
by Alice Walker
by Edgar Allan Poe
The Gift of the Magi
by O. Henry
by Flannery O'Connor
Whoso List to Hunt
The Poetry of Wyatt and Surrey
by Henry Howard, earl of Surrey, Sir Thomas Wyatt
They Flee from Me
In mourning wise since daily I increase
It was my choice, it was no chance


I WILL ANSWER ALL YOUR QUESTIONS AMA! CHECK OUT THIS EPIC VLOG!
Today Carter Sharer will be reading through all the Sharer Fam questions and answering all of them. First Carter ran to the store to buy a Xbox One S gaming console. After he got got home he started to answer the Sharer Fam questions. He answered all kinds of different questions. Get to know Carter Sharer better by asking him questions to answer. Comment #Carter if you loved this vlog!


For my SPSC training in GPSC, I visited this Institute regarding the course.The course fees were reasonable. Faculties are good and responsible.I have attended the demo classes in this institute for the training. I am very much satisfied with this institute.


Welcome to the SMJ index page.
From here you can find your way to all the pages on the website.
Station Pages - Each station along the line has its own page. Please feel free to sign up and add what you know.


text:
Q: Edit browser's history API with Angular router I have an application where we construct a series of temporary data points all with an ID of 0. I reference all these points individually by keying them as 01, 02, 03, etc. My route is /details/:id. If a user saves one of these data points our API creates a real ID. So the process looks something like this to the user:
Go to temp item at /details/0123
Save changes to item 0123.
Receive the new item in the response with an id of 456.
Angular reroutes to /details/456 and the user doesnt notice the transition unless they were paying attention to the URL.
However, if a user hits the Back Button on their browser they will route to /details/0123.
Question: Can I edit the browser history via the Angular router (or some other reliable means) to prevent navigating to /details/0123?

A: You can replace the route /details/0123 with the route /details/456 in the browser history by adding replaceUrl: true in the NavigationExtras.
Example:
this.router.navigate(['/details/456'], { replaceUrl: true });

A: What I would do is use Angular's Location and subscribe to the popstate. Something like this:
import {Subscription} from 'rxjs/Subscription';

export class ABC implements OnDestroy {
location: Location;
private subscription: Subscription;

      constructor(location: Location, router: Router) {
        this.subscription = location.subscribe(val => this.router.navigate(/*anywhere*/)
      }
      ngOnDestroy(){
          this.subscription.unsubscribe() //Make sure you do this :)
      }
}

I think that should work for you. Let me know.

redpajama_set_name: RedPajamaStackExchange


text:
#ifndef __I915_GEM_GTT_H__
#define __I915_GEM_GTT_H__

struct drm_i915_file_private;

typedef uint32_t gen6_pte_t;
typedef uint64_t gen8_pte_t;
typedef uint64_t gen8_pde_t;
typedef uint64_t gen8_ppgtt_pdpe_t;
typedef uint64_t gen8_ppgtt_pml4e_t;

#define gtt_total_entries(gtt) ((gtt).base.total >> PAGE_SHIFT)

/* gen6-hsw has bit 11-4 for physical addr bit 39-32 */
#define GEN6_GTT_ADDR_ENCODE(addr)	((addr) | (((addr) >> 28) & 0xff0))
#define GEN6_PTE_ADDR_ENCODE(addr)	GEN6_GTT_ADDR_ENCODE(addr)
#define GEN6_PDE_ADDR_ENCODE(addr)	GEN6_GTT_ADDR_ENCODE(addr)
#define GEN6_PTE_CACHE_LLC		(2 << 1)
#define GEN6_PTE_UNCACHED		(1 << 1)
#define GEN6_PTE_VALID			(1 << 0)

#define I915_PTES(pte_len)		(PAGE_SIZE / (pte_len))
#define I915_PTE_MASK(pte_len)		(I915_PTES(pte_len) - 1)
#define I915_PDES			512
#define I915_PDE_MASK			(I915_PDES - 1)
#define NUM_PTE(pde_shift)     (1 << (pde_shift - PAGE_SHIFT))

#define GEN6_PTES			I915_PTES(sizeof(gen6_pte_t))
#define GEN6_PD_SIZE		        (I915_PDES * PAGE_SIZE)
#define GEN6_PD_ALIGN			(PAGE_SIZE * 16)
#define GEN6_PDE_SHIFT			22
#define GEN6_PDE_VALID			(1 << 0)

#define GEN7_PTE_CACHE_L3_LLC		(3 << 1)

#define BYT_PTE_SNOOPED_BY_CPU_CACHES	(1 << 2)
#define BYT_PTE_WRITEABLE		(1 << 1)

/* Cacheability Control is a 4-bit value. The low three bits are stored in bits
 * 3:1 of the PTE, while the fourth bit is stored in bit 11 of the PTE.
 */
#define HSW_CACHEABILITY_CONTROL(bits)	((((bits) & 0x7) << 1) | \
					 (((bits) & 0x8) << (11 - 3)))
#define HSW_WB_LLC_AGE3			HSW_CACHEABILITY_CONTROL(0x2)
#define HSW_WB_LLC_AGE0			HSW_CACHEABILITY_CONTROL(0x3)
#define HSW_WB_ELLC_LLC_AGE3		HSW_CACHEABILITY_CONTROL(0x8)
#define HSW_WB_ELLC_LLC_AGE0		HSW_CACHEABILITY_CONTROL(0xb)
#define HSW_WT_ELLC_LLC_AGE3		HSW_CACHEABILITY_CONTROL(0x7)
#define HSW_WT_ELLC_LLC_AGE0		HSW_CACHEABILITY_CONTROL(0x6)
#define HSW_PTE_UNCACHED		(0)
#define HSW_GTT_ADDR_ENCODE(addr)	((addr) | (((addr) >> 28) & 0x7f0))
#define HSW_PTE_ADDR_ENCODE(addr)	HSW_GTT_ADDR_ENCODE(addr)

/* GEN8 legacy style address is defined as a 3 level page table:
 * 31:30 | 29:21 | 20:12 |  11:0
 * PDPE  |  PDE  |  PTE  | offset
 * The difference as compared to normal x86 3 level page table is the PDPEs are
 * programmed via register.
 *
 * GEN8 48b legacy style address is defined as a 4 level page table:
 * 47:39 | 38:30 | 29:21 | 20:12 |  11:0
 * PML4E | PDPE  |  PDE  |  PTE  | offset
 */
#define GEN8_PML4ES_PER_PML4		512
#define GEN8_PML4E_SHIFT		39
#define GEN8_PML4E_MASK			(GEN8_PML4ES_PER_PML4 - 1)
#define GEN8_PDPE_SHIFT			30
/* NB: GEN8_PDPE_MASK is untrue for 32b platforms, but it has no impact on 32b page
 * tables */
#define GEN8_PDPE_MASK			0x1ff
#define GEN8_PDE_SHIFT			21
#define GEN8_PDE_MASK			0x1ff
#define GEN8_PTE_SHIFT			12
#define GEN8_PTE_MASK			0x1ff
#define GEN8_LEGACY_PDPES		4
#define GEN8_PTES			I915_PTES(sizeof(gen8_pte_t))

#define I915_PDPES_PER_PDP(dev) (USES_FULL_48BIT_PPGTT(dev) ?\
				 GEN8_PML4ES_PER_PML4 : GEN8_LEGACY_PDPES)

#define PPAT_UNCACHED_INDEX		(_PAGE_PWT | _PAGE_PCD)
#define PPAT_CACHED_PDE_INDEX		0 /* WB LLC */
#define PPAT_CACHED_INDEX		_PAGE_PAT /* WB LLCeLLC */
#define PPAT_DISPLAY_ELLC_INDEX		_PAGE_PCD /* WT eLLC */

#define CHV_PPAT_SNOOP			(1<<6)
#define GEN8_PPAT_AGE(x)		(x<<4)
#define GEN8_PPAT_LLCeLLC		(3<<2)
#define GEN8_PPAT_LLCELLC		(2<<2)
#define GEN8_PPAT_LLC			(1<<2)
#define GEN8_PPAT_WB			(3<<0)
#define GEN8_PPAT_WT			(2<<0)
#define GEN8_PPAT_WC			(1<<0)
#define GEN8_PPAT_UC			(0<<0)
#define GEN8_PPAT_ELLC_OVERRIDE		(0<<2)
#define GEN8_PPAT(i, x)			((uint64_t) (x) << ((i) * 8))

enum i915_ggtt_view_type {
	I915_GGTT_VIEW_NORMAL = 0,
	I915_GGTT_VIEW_ROTATED,
	I915_GGTT_VIEW_PARTIAL,
};

struct intel_rotation_info {
	unsigned int height;
	unsigned int pitch;
	unsigned int uv_offset;
	uint32_t pixel_format;
	uint64_t fb_modifier;
	unsigned int width_pages, height_pages;
	uint64_t size;
	unsigned int width_pages_uv, height_pages_uv;
	uint64_t size_uv;
	unsigned int uv_start_page;
};

struct i915_ggtt_view {
	enum i915_ggtt_view_type type;

	union {
		struct {
			u64 offset;
			unsigned int size;
		} partial;
		struct intel_rotation_info rotation_info;
	} params;

	struct sg_table *pages;
};

extern const struct i915_ggtt_view i915_ggtt_view_normal;
extern const struct i915_ggtt_view i915_ggtt_view_rotated;

enum i915_cache_level;

/**
 * A VMA represents a GEM BO that is bound into an address space. Therefore, a
 * VMA's presence cannot be guaranteed before binding, or after unbinding the
 * object into/from the address space.
 *
 * To make things as simple as possible (ie. no refcounting), a VMA's lifetime
 * will always be <= an objects lifetime. So object refcounting should cover us.
 */
struct i915_vma {
	struct drm_mm_node node;
	struct drm_i915_gem_object *obj;
	struct i915_address_space *vm;

	/** Flags and address space this VMA is bound to */
#define GLOBAL_BIND	(1<<0)
#define LOCAL_BIND	(1<<1)
	unsigned int bound : 4;

	/**
	 * Support different GGTT views into the same object.
	 * This means there can be multiple VMA mappings per object and per VM.
	 * i915_ggtt_view_type is used to distinguish between those entries.
	 * The default one of zero (I915_GGTT_VIEW_NORMAL) is default and also
	 * assumed in GEM functions which take no ggtt view parameter.
	 */
	struct i915_ggtt_view ggtt_view;

	/** This object's place on the active/inactive lists */
	struct list_head mm_list;

	struct list_head vma_link; /* Link in the object's VMA list */

	/** This vma's place in the batchbuffer or on the eviction list */
	struct list_head exec_list;

	/**
	 * Used for performing relocations during execbuffer insertion.
	 */
	struct hlist_node exec_node;
	unsigned long exec_handle;
	struct drm_i915_gem_exec_object2 *exec_entry;

	/**
	 * How many users have pinned this object in GTT space. The following
	 * users can each hold at most one reference: pwrite/pread, execbuffer
	 * (objects are not allowed multiple times for the same batchbuffer),
	 * and the framebuffer code. When switching/pageflipping, the
	 * framebuffer code has at most two buffers pinned per crtc.
	 *
	 * In the worst case this is 1 + 1 + 1 + 2*2 = 7. That would fit into 3
	 * bits with absolutely no headroom. So use 4 bits. */
	unsigned int pin_count:4;
#define DRM_I915_GEM_OBJECT_MAX_PIN_COUNT 0xf
};

struct i915_page_dma {
	struct page *page;
	union {
		dma_addr_t daddr;

		/* For gen6/gen7 only. This is the offset in the GGTT
		 * where the page directory entries for PPGTT begin
		 */
		uint32_t ggtt_offset;
	};
};

#define px_base(px) (&(px)->base)
#define px_page(px) (px_base(px)->page)
#define px_dma(px) (px_base(px)->daddr)

struct i915_page_scratch {
	struct i915_page_dma base;
};

struct i915_page_table {
	struct i915_page_dma base;

	unsigned long *used_ptes;
};

struct i915_page_directory {
	struct i915_page_dma base;

	unsigned long *used_pdes;
	struct i915_page_table *page_table[I915_PDES]; /* PDEs */
};

struct i915_page_directory_pointer {
	struct i915_page_dma base;

	unsigned long *used_pdpes;
	struct i915_page_directory **page_directory;
};

struct i915_pml4 {
	struct i915_page_dma base;

	DECLARE_BITMAP(used_pml4es, GEN8_PML4ES_PER_PML4);
	struct i915_page_directory_pointer *pdps[GEN8_PML4ES_PER_PML4];
};

struct i915_address_space {
	struct drm_mm mm;
	struct drm_device *dev;
	struct list_head global_link;
	u64 start;		/* Start offset always 0 for dri2 */
	u64 total;		/* size addr space maps (ex. 2GB for ggtt) */

	struct i915_page_scratch *scratch_page;
	struct i915_page_table *scratch_pt;
	struct i915_page_directory *scratch_pd;
	struct i915_page_directory_pointer *scratch_pdp; /* GEN8+ & 48b PPGTT */

	/**
	 * List of objects currently involved in rendering.
	 *
	 * Includes buffers having the contents of their GPU caches
	 * flushed, not necessarily primitives. last_read_req
	 * represents when the rendering involved will be completed.
	 *
	 * A reference is held on the buffer while on this list.
	 */
	struct list_head active_list;

	/**
	 * LRU list of objects which are not in the ringbuffer and
	 * are ready to unbind, but are still in the GTT.
	 *
	 * last_read_req is NULL while an object is in this list.
	 *
	 * A reference is not held on the buffer while on this list,
	 * as merely being GTT-bound shouldn't prevent its being
	 * freed, and we'll pull it off the list in the free path.
	 */
	struct list_head inactive_list;

	/* FIXME: Need a more generic return type */
	gen6_pte_t (*pte_encode)(dma_addr_t addr,
				 enum i915_cache_level level,
				 bool valid, u32 flags); /* Create a valid PTE */
	/* flags for pte_encode */
#define PTE_READ_ONLY	(1<<0)
	int (*allocate_va_range)(struct i915_address_space *vm,
				 uint64_t start,
				 uint64_t length);
	void (*clear_range)(struct i915_address_space *vm,
			    uint64_t start,
			    uint64_t length,
			    bool use_scratch);
	void (*insert_entries)(struct i915_address_space *vm,
			       struct sg_table *st,
			       uint64_t start,
			       enum i915_cache_level cache_level, u32 flags);
	void (*cleanup)(struct i915_address_space *vm);
	/** Unmap an object from an address space. This usually consists of
	 * setting the valid PTE entries to a reserved scratch page. */
	void (*unbind_vma)(struct i915_vma *vma);
	/* Map an object into an address space with the given cache flags. */
	int (*bind_vma)(struct i915_vma *vma,
			enum i915_cache_level cache_level,
			u32 flags);
};

/* The Graphics Translation Table is the way in which GEN hardware translates a
 * Graphics Virtual Address into a Physical Address. In addition to the normal
 * collateral associated with any va->pa translations GEN hardware also has a
 * portion of the GTT which can be mapped by the CPU and remain both coherent
 * and correct (in cases like swizzling). That region is referred to as GMADR in
 * the spec.
 */
struct i915_gtt {
	struct i915_address_space base;

	size_t stolen_size;		/* Total size of stolen memory */
	size_t stolen_usable_size;	/* Total size minus BIOS reserved */
	u64 mappable_end;		/* End offset that we can CPU map */
	struct io_mapping *mappable;	/* Mapping to our CPU mappable region */
	phys_addr_t mappable_base;	/* PA of our GMADR */

	/** "Graphics Stolen Memory" holds the global PTEs */
	void __iomem *gsm;

	bool do_idle_maps;

	int mtrr;

	/* global gtt ops */
	int (*gtt_probe)(struct drm_device *dev, u64 *gtt_total,
			  size_t *stolen, phys_addr_t *mappable_base,
			  u64 *mappable_end);
};

struct i915_hw_ppgtt {
	struct i915_address_space base;
	struct kref ref;
	struct drm_mm_node node;
	unsigned long pd_dirty_rings;
	union {
		struct i915_pml4 pml4;		/* GEN8+ & 48b PPGTT */
		struct i915_page_directory_pointer pdp;	/* GEN8+ */
		struct i915_page_directory pd;		/* GEN6-7 */
	};

	struct drm_i915_file_private *file_priv;

	gen6_pte_t __iomem *pd_addr;

	int (*enable)(struct i915_hw_ppgtt *ppgtt);
	int (*switch_mm)(struct i915_hw_ppgtt *ppgtt,
			 struct drm_i915_gem_request *req);
	void (*debug_dump)(struct i915_hw_ppgtt *ppgtt, struct seq_file *m);
};

/* For each pde iterates over every pde between from start until start + length.
 * If start, and start+length are not perfectly divisible, the macro will round
 * down, and up as needed. The macro modifies pde, start, and length. Dev is
 * only used to differentiate shift values. Temp is temp.  On gen6/7, start = 0,
 * and length = 2G effectively iterates over every PDE in the system.
 *
 * XXX: temp is not actually needed, but it saves doing the ALIGN operation.
 */
#define gen6_for_each_pde(pt, pd, start, length, temp, iter) \
	for (iter = gen6_pde_index(start); \
	     length > 0 && iter < I915_PDES ? \
			(pt = (pd)->page_table[iter]), 1 : 0; \
	     iter++, \
	     temp = ALIGN(start+1, 1 << GEN6_PDE_SHIFT) - start, \
	     temp = min_t(unsigned, temp, length), \
	     start += temp, length -= temp)

#define gen6_for_all_pdes(pt, ppgtt, iter)  \
	for (iter = 0;		\
	     pt = ppgtt->pd.page_table[iter], iter < I915_PDES;	\
	     iter++)

static inline uint32_t i915_pte_index(uint64_t address, uint32_t pde_shift)
{
	const uint32_t mask = NUM_PTE(pde_shift) - 1;

	return (address >> PAGE_SHIFT) & mask;
}

/* Helper to counts the number of PTEs within the given length. This count
 * does not cross a page table boundary, so the max value would be
 * GEN6_PTES for GEN6, and GEN8_PTES for GEN8.
*/
static inline uint32_t i915_pte_count(uint64_t addr, size_t length,
				      uint32_t pde_shift)
{
	const uint64_t mask = ~((1 << pde_shift) - 1);
	uint64_t end;

	WARN_ON(length == 0);
	WARN_ON(offset_in_page(addr|length));

	end = addr + length;

	if ((addr & mask) != (end & mask))
		return NUM_PTE(pde_shift) - i915_pte_index(addr, pde_shift);

	return i915_pte_index(end, pde_shift) - i915_pte_index(addr, pde_shift);
}

static inline uint32_t i915_pde_index(uint64_t addr, uint32_t shift)
{
	return (addr >> shift) & I915_PDE_MASK;
}

static inline uint32_t gen6_pte_index(uint32_t addr)
{
	return i915_pte_index(addr, GEN6_PDE_SHIFT);
}

static inline size_t gen6_pte_count(uint32_t addr, uint32_t length)
{
	return i915_pte_count(addr, length, GEN6_PDE_SHIFT);
}

static inline uint32_t gen6_pde_index(uint32_t addr)
{
	return i915_pde_index(addr, GEN6_PDE_SHIFT);
}

/* Equivalent to the gen6 version, For each pde iterates over every pde
 * between from start until start + length. On gen8+ it simply iterates
 * over every page directory entry in a page directory.
 */
#define gen8_for_each_pde(pt, pd, start, length, iter)			\
	for (iter = gen8_pde_index(start);				\
	     length > 0 && iter < I915_PDES &&				\
		(pt = (pd)->page_table[iter], true);			\
	     ({ u64 temp = ALIGN(start+1, 1 << GEN8_PDE_SHIFT);		\
		    temp = min(temp - start, length);			\
		    start += temp, length -= temp; }), ++iter)

#define gen8_for_each_pdpe(pd, pdp, start, length, iter)		\
	for (iter = gen8_pdpe_index(start);				\
	     length > 0 && iter < I915_PDPES_PER_PDP(dev) &&		\
		(pd = (pdp)->page_directory[iter], true);		\
	     ({ u64 temp = ALIGN(start+1, 1 << GEN8_PDPE_SHIFT);	\
		    temp = min(temp - start, length);			\
		    start += temp, length -= temp; }), ++iter)

#define gen8_for_each_pml4e(pdp, pml4, start, length, iter)		\
	for (iter = gen8_pml4e_index(start);				\
	     length > 0 && iter < GEN8_PML4ES_PER_PML4 &&		\
		(pdp = (pml4)->pdps[iter], true);			\
	     ({ u64 temp = ALIGN(start+1, 1ULL << GEN8_PML4E_SHIFT);	\
		    temp = min(temp - start, length);			\
		    start += temp, length -= temp; }), ++iter)

static inline uint32_t gen8_pte_index(uint64_t address)
{
	return i915_pte_index(address, GEN8_PDE_SHIFT);
}

static inline uint32_t gen8_pde_index(uint64_t address)
{
	return i915_pde_index(address, GEN8_PDE_SHIFT);
}

static inline uint32_t gen8_pdpe_index(uint64_t address)
{
	return (address >> GEN8_PDPE_SHIFT) & GEN8_PDPE_MASK;
}

static inline uint32_t gen8_pml4e_index(uint64_t address)
{
	return (address >> GEN8_PML4E_SHIFT) & GEN8_PML4E_MASK;
}

static inline size_t gen8_pte_count(uint64_t address, uint64_t length)
{
	return i915_pte_count(address, length, GEN8_PDE_SHIFT);
}

static inline dma_addr_t
i915_page_dir_dma_addr(const struct i915_hw_ppgtt *ppgtt, const unsigned n)
{
	return test_bit(n, ppgtt->pdp.used_pdpes) ?
		px_dma(ppgtt->pdp.page_directory[n]) :
		px_dma(ppgtt->base.scratch_pd);
}

int i915_gem_gtt_init(struct drm_device *dev);
void i915_gem_init_global_gtt(struct drm_device *dev);
void i915_global_gtt_cleanup(struct drm_device *dev);

int i915_ppgtt_init(struct drm_device *dev, struct i915_hw_ppgtt *ppgtt);
int i915_ppgtt_init_hw(struct drm_device *dev);
int i915_ppgtt_init_ring(struct drm_i915_gem_request *req);
void i915_ppgtt_release(struct kref *kref);
struct i915_hw_ppgtt *i915_ppgtt_create(struct drm_device *dev,
					struct drm_i915_file_private *fpriv);
static inline void i915_ppgtt_get(struct i915_hw_ppgtt *ppgtt)
{
	if (ppgtt)
		kref_get(&ppgtt->ref);
}
static inline void i915_ppgtt_put(struct i915_hw_ppgtt *ppgtt)
{
	if (ppgtt)
		kref_put(&ppgtt->ref, i915_ppgtt_release);
}

void i915_check_and_clear_faults(struct drm_device *dev);
void i915_gem_suspend_gtt_mappings(struct drm_device *dev);
void i915_gem_restore_gtt_mappings(struct drm_device *dev);

int __must_check i915_gem_gtt_prepare_object(struct drm_i915_gem_object *obj);
void i915_gem_gtt_finish_object(struct drm_i915_gem_object *obj);

static inline bool
i915_ggtt_view_equal(const struct i915_ggtt_view *a,
                     const struct i915_ggtt_view *b)
{
	if (WARN_ON(!a || !b))
		return false;

	if (a->type != b->type)
		return false;
	if (a->type != I915_GGTT_VIEW_NORMAL)
		return !memcmp(&a->params, &b->params, sizeof(a->params));
	return true;
}

size_t
i915_ggtt_view_size(struct drm_i915_gem_object *obj,
		    const struct i915_ggtt_view *view);

#endif

redpajama_set_name: RedPajamaGithub


From the beautiful, quiet moments during preparations, to the joyful love and celebrations of your wedding ceremony and reception, we are there to capture every sweet moment on your wedding day.
We want to hear all about the two of you - how you met, your love story, and all the unique details of your wedding day. We will capture the best and most beautiful moments on your wedding day and tell your love story through the most beautiful photographs and video!
All Photo Rights Released - print, post, & share away!
We offer a variety of wedding video and wedding photography packages to suit your day perfectly. From tiny weddings and elopements to huge celebrations, we have the package just for you!
Email Meredith@cinejot.com for availability and our current specials.
"Great service and beautiful filming!"
"Adam and Meredith were so great to work with! They were helpful, professional and did a wonderful job filming my sister's wedding. I'll definitely work with them again!"
"Thank you so much for our beautiful photos and video from our wedding day!! We have enjoyed watching our wedding video every day and share it all the time! We loved Adam and Meredith capturing our special day!
We are now booking couples for 2017 and 2018 wedding photography and wedding video. We book less than 25 clients each year to give every one of our amazing couples our full creative attention and time. Fill out the contact form below to check our availability. Meredith will usually respond within an hour or two of your submission!
Thank you! Meredith will be in touch with you soon!
Yes! Our service area includes Austin, San Antonio, Houston, and in between! We also travel all over Texas and the Southwest. Contact us for availability.
Do you offer a discount if we book multiple services from you?
Yes! We offer discounts when you book any two or more of our wedding day packages. Contact us for availability to book!
Yes! We offer a discount to Military families on all of our photography and video services. Please contact us with you wedding date and information and mention you are a Military family and we will take care of you!
We love capturing the sweet, candid moments between couples and while celebrating with loved ones on your big day. We take great portraits, too, but we love the "in the moment" moments. We offer a mix of candid and posed photos. Tell us what you want, and we will accommodate.
We definitely want to book you! What's the next step?
GREAT! We are excited to meet you! The first step is to schedule an in-person meeting with you to go over your wedding day details and collect deposit. The deposit holds the entire day for your for your wedding and we don't book more than one wedding per day. The deposit is applied toward the total cost of services. We offer discounts for combining two or more photography or video packages. Email Meredith (meredith@cinejot.com) for more info!