{"id":2134,"date":"2013-05-04T11:09:23","date_gmt":"2013-05-04T15:09:23","guid":{"rendered":"http:\/\/hstore.cs.brown.edu\/?page_id=2134"},"modified":"2013-07-11T14:48:51","modified_gmt":"2013-07-11T18:48:51","slug":"query-planning","status":"publish","type":"page","link":"https:\/\/hstore.cs.brown.edu\/documentation\/development\/query-planning\/","title":{"rendered":"Query Planning & Execution"},"content":{"rendered":"

The following is meant to document the process of how the system processes query requests from transactions and executes them in on the appropriate partitions.<\/p>\n

When a transaction is running, the procedure’s control code can queue SQLStmts<\/tt> in a batch and then issue that batch for execution to the system. For example, the transaction shown below from YCSB will queue two invocations of the readStmt<\/tt> query in a batch and then have the DBMS execute them using voltExecuteSQL<\/tt>. The call to voltExecuteSQL<\/tt> will block the transaction’s control code until the results are retrieved and returned.<\/p>\n\n

SQLStmt readStmt =<\/span> new<\/span> SQLStmt(<\/span>"SELECT * FROM USERTABLE WHERE YCSB_KEY=?"<\/span>)<\/span>;<\/span>\npublic<\/span> VoltTable[<\/span>]<\/span> run(<\/span>long<\/span> id0, long<\/span> id1)<\/span> {<\/span>\n    voltQueueSQL(<\/span>readStmt, id0)<\/span>;<\/span>\n    voltQueueSQL(<\/span>readStmt, id1)<\/span>;<\/span>\n    return<\/span> (<\/span>voltExecuteSQL(<\/span>true<\/span>)<\/span>)<\/span>;<\/span>\n}<\/span><\/pre><\/td><\/tr><\/table><\/div>\n\n
There are several things that need to happen in order to execute these queries at the partitions that have the data that it needs and to get the results back to the transaction. The easiest thing to do is to just send the query to all partitions to look for the data, but this means that each transaction would need to lock the entire cluster every time (which would be horribly slow). Instead, H-Store will examine the queries and its input parameters to determine exactly where to send queries.<\/p>\n
It is important to note that H-Store does not do any query optimizations at runtime (e.g., predicate pushdowns). All of this is done when the project is compiled<\/a> using hstore-prepare<\/tt>.<\/p>\n
We now describe these steps in detail.<\/p>\n
<\/a><\/p>\n
Computing Query Target Partitions<\/h2>\n
After the transaction invokes voltExecuteSQL<\/tt>, the underlying logic in VoltProcedure<\/tt> computes a unique hash identifier of all of the SQLStmts in the current batch. It then retrieves (or creates) a Batch Planner<\/a><\/span> instance that is specific for that identifier at that partition. The Batch Planner<\/a><\/span> is responsible for examining each SQLStmt<\/tt> invocation and its input parameters in the batch to determine what partition(s) the query needs to be executed on. Note that each Batch Planner<\/a><\/span> is not shared between partitions, and thus it does not need any synchronization primitives.<\/p>\n
Each SQLStmt<\/tt> is linked to a Statement<\/tt> catalog object that contains the pre-compiled query plans. Each Statement<\/tt> has a separate query plan for single-partition execution and multi-partition execution. Thus, it is the Batch Planner<\/a><\/span>‘s job to determine which one it needs to use for each invocation. Although the two plans are logically the same, the multi-partition plan will have special nodes to transmit intermediate data between partitions and other optimizations needed for distributed query execution (e.g., computing AVG()<\/tt> by taking the weighted average from each partition).<\/p>\n
The main logic of determining where to send queries is in BatchPlanner.plan()<\/tt>. In there, it will iterate over each SQLStmt<\/tt> and use the PartitionEstimator<\/tt> to determine what partitions that it needs to touch. Each SQLStmt<\/tt> is assumed to be single-partitioned, and thus the Batch Planner<\/a><\/span> will use the PartitionEstimator<\/tt> to examine that SQLStmt<\/tt>‘s single-partition query plan. If the PartitionEstimator<\/tt> determines that the query needs to touch more than one partitions, then the Batch Planner<\/a><\/span> will switch to use the multi-partition query plan for that SQLStmt<\/tt>. Note that this is separate from checking whether a query needs to execute on the base partition for the transaction’s control code; a query can be single-partitioned even though it is executing on a remote partition.<\/p>\n
After this process is complete, each SQLStmt<\/tt> in the batch will have a mapping of PlanFragments<\/tt> that need to be executed on its behalf and the set of partitions that each of them need to be sent to. The Batch Planner<\/a><\/span> then determines how the system will need to execute the batch. There are three possibilities:<\/p>\n
    \n
  1.  If all of the queries are “local” (i.e., they only need to execute on the transaction’s base partition), then the Batch Planner<\/a><\/span> sends the queries directly to that partition’s PartitionExecutor<\/a><\/span> for immediate execution. This is the fastest and most efficient execution path in the system.\n
  2.  If one or more of the queries need to access a partition different than the transaction’s base partition, then the BatchPlanner will generate a dependency graph of WorkFragments<\/a> that the system will schedule for execution.\n
  3.  If at least one of the queries needs to access a partition that the transaction did not acquire the lock for before it started, then then a MispredictionException<\/tt> is thrown and the transaction is aborted. The transaction will be requeued and restarted with all of the locks for the partitions that it attempted to touch.\n<\/ol>\n
    We now discuss the second case, where queries need to be distributed to multiple partitions.<\/p>\n
    <\/a><\/p>\n
    Generating WorkFragments<\/h2>\n
    Each Plan Fragment<\/a><\/span> for a query contains a list of unique input and output dependency identifiers. An output dependency represents the VoltTable<\/tt> that is generated by a Plan Fragment<\/a><\/span> when it is executed in the C++ . An input dependency for a Plan Fragment<\/a><\/span> is an output dependency of another Plan Fragment<\/a><\/span> that needs to get executed first before it can be executed. The Batch Planner<\/a><\/span> uses this dependency information to generate a dependency graph (e.g., BatchPlanner.PlanGraph<\/tt>) for each SQLStmt<\/tt> that represents the order in which its PlanFragments<\/tt> need to be executed.<\/p>\n
    The dependency graph is then used by the Batch Planner<\/a><\/span> (i.e., BatchPlanner.createWorkFragmentsBuilders()<\/tt>) to generate all of the Protocol Buffer WorkFragments<\/tt> messages that are sent to the partitions in order to execute the PlanFragments<\/tt>. The Batch Planner<\/a><\/span> leaves the WorkFragments<\/tt> in their intermediate “Builder” form so that the PartitionExecutor<\/a><\/span> can perform additional optimizations later on.<\/p>\n
    Each WorkFragment<\/tt> contains a series of PlanFragments<\/tt> identifiers that need to be executed at a partition in a given “round”. A round represents all of the PlanFragments<\/tt> that can be executed once the previous round has finished (e.g., all of the input dependencies needed by that round have been generated by the previous round). If the PlanFragments<\/tt> do not have any input dependencies, then they will be in the first round and can be scheduled for execution immediately.<\/p>\n
    After generating the WorkFragments<\/tt> needed for the entire SQLStmt<\/tt> batch, the batch plan is then handed off to the PartitionExecutor<\/a><\/span> to schedule their dispatching and execution in the cluster.<\/p>\n
    <\/a><\/p>\n
    Dispatching & Executing WorkFragments<\/h2>\n
    The main logic for controlling how the WorkFragments<\/tt> are distributed to the appropriate partitions at runtime is found in PartitionExecutor.dispatchWorkFragments()<\/tt>. The high-level idea of this method is that it first submits all of the WorkFragments<\/tt> for the first round that can be executed immediately (i.e., they do not have any input dependencies) and then blocks until their output dependencies arrive back to the transaction. It is then awoken when all of the input dependencies for the next round have arrived and are now eligible for execution. This process repeats until there are no more WorkFragment<\/tt> rounds to dispatch and all of the output dependencies for the outstanding rounds have arrived.<\/p>\n
    There is one WorkFragment<\/tt> per partition in each round. All of the WorkFragments<\/tt> for partitions on the same Site are combined into a single TransactionWorkRequest<\/tt> that is sent over the network using the HStoreCoordinator<\/tt>. The HStoreCoordinator<\/tt> invokes the PartitionExecutor<\/a><\/span>‘s internal callback handle (PartitionExecutor.request_work_callback<\/tt>) to notify it when the corresponding TransactionWorkResult<\/tt> is returned for that request.<\/p>\n
    On remote partitions, when the HStoreCoordinator<\/tt> receives a TransactionWorkRequest<\/tt> for an active transaction, it wraps the embedded Protocol Buffer WorkFragments<\/tt> into a WorkFragmentMessage<\/tt> and queues the them in their target PartitionExecutor<\/a><\/span>. The PartitionExecutor<\/a><\/span> retrieves this WorkFragmentMessage<\/tt> and then executes the corresponding PlanFragments<\/tt> in its ExeutionEngine<\/tt> and then invokes the corresponding callback to transmit the results back to the transaction’s base partition.<\/p>\n","protected":false},"excerpt":{"rendered":"
    The following is meant to document the process of how the system processes query requests from transactions and executes them in on the appropriate partitions. When a transaction is running, the procedure’s control code can queue SQLStmts in a batch and then issue that batch for execution to the system. For example, the transaction shown […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":616,"menu_order":22,"comment_status":"closed","ping_status":"open","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/pages\/2134"}],"collection":[{"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/comments?post=2134"}],"version-history":[{"count":17,"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/pages\/2134\/revisions"}],"predecessor-version":[{"id":2230,"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/pages\/2134\/revisions\/2230"}],"up":[{"embeddable":true,"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/pages\/616"}],"wp:attachment":[{"href":"https:\/\/hstore.cs.brown.edu\/wp-json\/wp\/v2\/media?parent=2134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}