Patent Document

BACKGROUND 
     Automated physical design tuning involves a database management system (DBMS) recommending a set of physical structures that increase the performance of an underlying database. Physical design has been formulated as a problem statement, traditionally: Given a workload W and a storage budget B, find the set of physical structures, or configuration, that fits in B and results in the lowest execution cost for W. Most modern commercial DBMS&#39;s have some facilities for automated design tuning. In general, however, it has not been possible to include in the tuning process information beyond the basic information of the design tuning problem statement. 
     For instance, it has not been possible to tune a given workload for maximum performance under a storage constraint while at the same time ensuring that no query degrades by more than 10% with respect to the original configuration. As another example, it has not been possible to enforce that the clustered index on a table T cannot be defined over certain columns of T that would introduce hot-spots (without specifying which of the remaining columns should be chosen). As yet another example, in order to decrease contention during query processing, there is no way to avoid any single column from a table from appearing in more than, say, three indexes (the more indexes a column appears in, the more contention arises due to exclusive locks during updates). While some new approaches allow more flexibility in the specification of a physical design tuning problem, existing solutions require that the whole specification to be provided upfront, without possibility of interaction. 
     Described herein are techniques for flexible and interactive physical design tuning. 
     SUMMARY 
     The following summary is included only to introduce some concepts discussed in the Detailed Description below. This summary is not comprehensive and is not intended to delineate the scope of the claimed subject matter, which is set forth by the claims presented at the end. 
     An architecture for providing interactive sessions for physical database design is described, allowing users to readily try different options, identify problems, and obtain physical designs in a flexible way. Embodiments based on a .NET assembly and modifications to a database management system (DBMS) are also described. 
     Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description. 
         FIG. 1  shows a physical design tuning tool. 
         FIG. 2  shows a layered architecture for physical design tuning. 
         FIG. 3  shows a transcript of an example interactive tuning session. 
         FIG. 4  shows an XML representation of a portion of a simplified version of a hierarchy exposed by a provider. 
         FIG. 5  shows a transcript of an example interactive tuning session using a provider. 
         FIG. 6  shows an example visualization. 
         FIG. 7  shows an example PowerShell session with two example cmdlets. 
         FIG. 8  shows an example script. 
         FIGS. 9-11  show a sample interactive physical database design tuning session. 
         FIG. 12  shows a process of interactive design tuning. 
         FIG. 13  shows a diagram illustrating user interaction possible for design tuning. 
     
    
    
     DETAILED DESCRIPTION 
     Overview 
     Embodiments discussed below relate to interactive physical design tuning of databases. For background,  FIG. 1  shows a physical design tuning tool  130 . The tuning tool  130  is an application used by a DBA to explore alternate configurations of a database  131  managed by a DBMS. Different storage boundaries  132  (e.g., memory limits) and physical configurations and workloads  134  (sets of queries) can be tested for performance results. The tuning tool  130  may function as a database client that communicates with the DBMS through an interface (an API provided by the database) to submit “what-if” scenarios that the DBMS explores, tests, and provides feedback on without necessarily executing the queries. In other words, the DBMS  102  can give feedback on how well a query optimizes or performs according to a possible configuration. As a result, the tuning tool  130  may output some configuration  136  (e.g., some set of indexes I 1  . . . Im) deemed to be ideal for the given boundaries  132  and workload  134 . Generally, the tuning tool  130  may test many configurations for a query before deciding which configuration is optimal. Regarding what-if facilities or instrumentation of a DBMS, description is provided elsewhere, for example, see “Self-Tuning Database Systems: A Decade of Progress”, VLDB &#39;07, ACM 978-1-59593-649-Mar. 7, 2009. 
     The scenarios mentioned in the Background above show that the state-of-the-art techniques for physical design tuning are inflexible. Referring to  FIG. 1 , the typical approach has been to specify a simple scenario, submit same to the DBMS, and receive a recommended configuration. Flexible and interactive refinement has not been possible. The inventors have observed that goals or constraints of tuning the physical design of a database system are often not fully specified upfront, but instead become apparent through experimentation, feedback, analysis, etc. Current physical design tools are monolithic, expose tuning options that are set at the beginning, and generate, without further user input, a final configuration to deploy into a production system. 
     Embodiments described below shift the design approach and allow tuning sessions to be highly interactive. Current monolithic architectures in physical design tools force users to specify the whole problem upfront and prevent users from making changes a posteriori or in general interacting with the system. Explanation will begin with description of an architecture for interactive sessions, followed by a review of Windows PowerShell as an infrastructure component that can support the architecture. Explanation will proceed with description of interactive tuning processes, followed by presentation of illustrative examples. 
     Layered Architecture for Physical Design Tuning 
       FIG. 2  shows a layered architecture  148  for physical design tuning. A Core DBMS layer  150  is a lowest layer within the DBMS (e.g., SQL Server  152 ) and provides native support for operations such as what-if optimization, which may be facilitated in party by a SQL Server Optimizer  154 , for example. What-if optimization support in a DBMS is described in other sources, such as “Configuration-parametric query optimization for physical design tuning” (In Proceedings of the ACM International Conference on Management of Data (SIGMOD), 2008, and “Autoadmin ‘What-if’ index analysis utility” (In Proceedings of the ACM International Conference on Management of Data (SIGMOD), 1998). This layer provides what-if optimization (i.e., the ability to obtain expected costs of queries for varying physical designs without the requirement that the physical designs being implemented). Additionally, this layer enables rich information after regular optimization (see low layer API), such as sets of access path requests that can be later used to understand the set of possible indexes that could be useful for a given query. It does so by piggybacking on top of regular optimization and identifying access path requests. It may not actually expose functions, but instead may enable functionality that can be exposed in the low-level APIs. 
     A low-level API layer  156  may expose, in formats that are simple to consume (e.g., XML), the functionality of the Core DBMS layer  150  (and also the DBMS itself). As an example, they may expose primitives to manipulate a what-if mode of the DBMS and also may expose rich explain modes which, after optimizing queries, surface optimization information use at higher levels of the DBMS. The explain mode may provide useful information about the optimization of a query, such as the final plan obtained by the optimizer, cardinality estimates for intermediate results, access path requests, etc. (it may be thought of as an extension to existing modes in relational systems, such as showplans in Microsoft SQL Server). The low level API layer  156  may also encapsulate existing DBMS functionality, such as mechanisms that monitor and gather workloads. 
     A High-level API layer  158  if provided to facilitate access to the lower level APIs  156  and Core DBMS layer  150 . Physical design tools were previously built on top of the low-level APIs only exposed a rigid functionality (e.g., point to a workload, set the storage constraint, and optimize). The high-level API layer  158  exposes the internal representations and mechanisms in a modular way. Basic concepts such as queries, indexes, databases, tables, and access-path requests are exposed as instantiable classes. In addition to these data structures, the high-level API layer  158  exposes composable and simple algorithms sometimes found in previous tuning tools. For instance, this layer may expose mechanisms to merge two indexes, or to obtain the best set of indexes for a single query. These primitive data structures and algorithms are not necessarily meant to be consumed by DBAs, but instead provide a foundational abstraction for applications to be built on top, as explained next. In one embodiment, described later, the high-level API layer  158  may be implemented as a .NET assembly  160 , which is executed by a .NET VM  162  (Virtual Machine), sometimes called a managed code environment. 
     Front-ends  164  are based on both the low-level APIs  156  and high-level APIs  158  and deliver functionality to end users. One example of a front-end  164  is an interactive scripting platform to interact with physical database designs. The scripting language understands and works with the data structures and algorithms exposed by the underlying layers and allows users to write interactive scripts to tune the physical design of a database. Common tasks, such as minimizing the cost for a single storage constraint (or other functionality provided by previous physical design tools), can be implemented as pre-existing scripts that can be accessed using graphical user interfaces by relatively inexperienced DBAs. 
     As mentioned, a front-end  164  can be implemented by a scripting environment. For example, Windows Powershell  166  (tm), available from Microsoft Corporation is a scripting language that can be used as a front-end  164  in the architecture. A prototype implementation of the architecture using Windows Powershell  166  will also be described. 
     Windows Powershell 
     Windows PowerShell is an interactive, extensible scripting language that integrates with the Microsoft .NET Framework. It provides an environment to perform administrative tasks by execution of cmdlets (i.e., commandlets, which are basic operations), scripts (which are composition of cmdlets), stand-alone applications, or by directly instantiating regular .NET classes. The main features of Windows PowerShell include tight integration with .NET, strict naming conventions, object pipelines, and data providers. 
     Windows PowerShell integrates with the .NET framework and leverages the .NET framework to represent data. Windows PowerShell understands .NET classes natively, as illustrated below. Thus, new classes written in the .NET framework are easily available as first-class citizens in Windows PowerShell. 
     Windows PowerShell uses strict naming conventions. Cmdlets in Windows PowerShell follow a verb-noun naming convention, and parameters are passed in a unified manner. Some examples of such built-in cmdlets are Start-Service, which starts an OS (operating system) service in the current machine, Get-Process, which returns a list of processes currently executing, Clear-Host, which clears the screen, and Get-ChildItem which, if located in a file system directory, returns all its subdirectories or files. There are also aliases for the common cmdlets. 
     PowerShell also provides facilities to construct object pipelines. Similar to Unix shells, cmdlets can be pipelined using the “|” operator. However, unlike Unix shells, which typically pipeline strings, Windows PowerShell pipelines .NET objects. For instance, the script: 
                                             &gt; Get-Process | Sort-Object -Property Handles -Desc |           Select-Object -first 5 | Stop-Process                        
obtains the list of all running processes, pipes the result (which is a list of System.Diagnostics.Process .NET objects) to the Sort-Object cmdlet, which understands the semantics of the objects and sorts them by the property Handles in descending order. In turn, the result of this cmdlet (i.e., an ordered list of processes) is passed to the Select-Object cmdlet, which takes the first five processes and passes them to the next cmdlet in the pipeline, Stop-Process, which terminates them. The following script returns the number of lines that contains the word “constraint” in any LATEX file in the current directory that is below 100,000 bytes long:
 
                                 &gt; Get-ChildItem -Path *.tex | Where-Object -FilterScript { $ .Length -It       100000 } | Foreach-Object -Process { Get-Content $ | Select-String       constraint } | Measure-Object Count : 404                    
which gets all files in the current path that have a “tex” extension and keeps only those that are smaller than 100,000 bytes. Then, each file is processed by first getting its content (which returns a list of string .NET classes), selecting only those that contain the work constraints. The combined result of this subscript is a list of strings, which is measured and the count is returned. To shorten a script, aliases (e.g., Get-ChildItem becomes “dir”, Where-Object becomes “?”, Foreach-Object becomes %), and positional cmdlet parameters can be used. For instance it is not necessary to explicitly write—Path after dir. An equivalent script is shown below:
 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 &gt; dir *.tex | ? { $ .Length -It 100000 } | % { gc $ | Select-String 
               
               
                   
                 constraint } | measure Count : 404 
               
               
                   
                   
               
             
          
         
       
     
     PowerShell has the ability to expose hierarchical data models by means of data providers, which are then accessed and manipulated using a common set of cmdlets. As an example, the file system is one such provider. When situated in some node inside the file system provider, Get-ChildItem can be used to obtain the subdirectories or files in the current location, access contents of elements using Get-Content, and navigate the provider using Set-Location (aliased as cd). However, Windows PowerShell natively exposes the registry and the environment variables as providers. There also are third party providers that give a unified surface to access, query, and modify Active Directory, SharePoint and SQL Server, among others. 
     The next section describes how take advantage of the different features of Windows PowerShell to provide an interactive experience for physical design tuning. 
     Interactive Physical Design Tuning 
     A prototype implementation that enables interactive physical design tuning sessions will now be described. The architecture of this implementation is described first, followed by discussion of examples of how the implementation can be used.  FIG. 2  shows how the different layers of architecture  148  map to the implementation. An implementation of each layer of the architecture  148  will be described in detail. 
     Low-Level APIs 
     The Core DBMS  150  and Low-level APIs  156  are implemented by instrumenting a database server, for instance Microsoft SQL Server  152 . Some components (e.g., what-if optimization) are already part of this particular database server, while others (e.g., access-path request interception) were added. 
     High-Level APIs 
     The high-level API layer  158  is implemented by introducing a new .NET assembly  160  that encapsulates and exposes classes and algorithms relevant to physical design tuning. Among the classes that the assembly exposes are Database, Table, Index, Column, Query, Configuration, and Request classes. These are rich in functionality, so for instance the Index class may have methods that return merged and reduced indexes and methods that create hypothetical versions of the index in the database. The Query class may have methods that evaluate (optimize) it under a given configuration, and methods that return its set of access-path requests. 
     Additionally, as part of the .NET assembly  160 , a sophisticated caching mechanism may be built to avoid optimizing the same query multiple times in the database server. Instead, each query remembers previous optimizations and, if asked again to optimize itself with a previously seen configuration, it returns the cached values without doing the expensive work again. 
     Because these classes are exposed in an assembly, the definitions thereof can be loaded directly into Windows PowerShell which may be used to explore, in interactive form, the physical design of a database, as illustrated in  FIG. 3 . 
       FIG. 3  shows a transcript  180  of an example interactive tuning session. First, a user created  182  a new database object; an object implemented by the .NET assembly but instantiated via user input typed at the PowerShell command prompt (“&gt;”). Then, the user explored the database object by typing its variable name  184 , in response to which various information about the corresponding data is displayed (such information having been obtained from “nicolasb02” DBMS hosting the “tpch01g” database). Specific information about tables of the database is then displayed by invoking  186  appropriate properties of the $db database object. A new query object is then instantiated  188 , and then the user evaluates the query  190  according to the “base” or default configuration of the database. 
     Front-End 
     While the example above is useful, call the .NET methods directly can be inefficient. Also, using such methods directly may be a time consuming way to accomplish tuning a database design. Using the capabilities of Windows PowerShell, functionally such as a provider, visualizations, cmdlets, and scripts can be used. 
     PowerShell providers are .NET programs that allow a user to work with data stores as though they were mounted drives or file systems, which simplifies accessing external data outside the PowerShell environment. A PowerShell provider can be implemented that exposes the information about a tuning session in a hierarchical and intuitive object model.  FIG. 4  shows an XML representation  210  of a portion of a simplified version of a hierarchy exposed by a provider. By using this provider, the state of a tuning session can be easily manipulated and navigated as shown in  FIG. 5 .  FIG. 5  shows a transcript  230  of an example interactive tuning session using a provider. Note that file system style commands such as “cd” and “dir” can be used to navigate and view database information, tuning information, configuration information, and so on. 
       FIG. 6  shows an example visualization  250 . Use of a composable, interactive script language can allow inclusion of third-party add-ins that offer specific functionality. For example, the PowerGadgets web site provides simple cmdlets to display data graphically. One such cmdlet is Out-Chart, of which visualization  250  is an instance. The Out-Chart cmdlet displays a chart of the data that is pipelined in. The example visualization  250  graphically displays the relative sizes of all tables in a database by using the command  252 . 
     In addition to a provider, the bare .NET classes and methods of the .NET assembly may be provided with composable cmdlets.  FIG. 7  shows an example PowerShell session with two example cmdlets  270  and  272 . 
     Scripts are another feature of the implementation.  FIG. 8  shows an example script  290 . The script is a simplified implementation of a common operation called refinement, in which a given input configuration is repeatedly “relaxed” via merging and reduction operations until it fits in the available storage, so that the expected cost of the resulting configuration is as low as possible. At each iteration, all possible transformations are calculated (using a cmdlet) and the one that is expected to result in the smaller execution cost is obtained. This process is repeated until a valid configuration is reached: 
     Other common algorithms may be similarly implemented, such as the relaxation based tuning approach in “Automatic physical database tuning: A relaxation-based approach” (N. Bruno and S. Chaudhuri., In Proceedings of the ACM International Conference on Management of Data (SIGMOD), 2005). One embodiment implements a version that handles constraint language, described in “Constrained physical design tuning” (N. Bruno and S. Chaudhuri, In Proceedings of the International Conference on Very Large Databases (VLDB), 2008). This script is called TuneConstrained-Workload and takes as inputs a workload, a timeout, and a set of constraints. Such a script may be implemented by using the .NET classes exported by the high-level APIs and may be implemented as a PowerShell script in fewer than 100 lines of code. 
     A Sample Interactive Tuning Session 
       FIGS. 9-11  show a sample interactive physical database design tuning session  310 . Session  310  illustrates an interactive approach that provides flexibility and control during physical design tuning. The example uses the provider, cmdlets and scripts described earlier, as well as additional visualizations, among others. Advanced DBAs or other users may create their own scripts to further customize the physical design tuning experience. Moreover, native PowerShell features, such as remoting (which allows users to execute commands in other machines) or eventing and automation can surely complement tuning scripts and provide added flexibility. The comments in session  310  explain the actions taken by the user. 
       FIG. 12  shows a process of interactive design tuning. The steps of  FIG. 12  can occur in any arbitrary order; the order shown is for illustration only. Using an implementation of the architecture described above, a user may con figure 330  a scenario by selecting workloads, setting parameters such as space constraint, and others. Eventually the user invokes a command (e.g., “Refine-Configuration”) that communicates  332  the current scenario or configuration to a low-level API algorithm implemented by a DBMS. The DBMS may load  334  a workload, set parameters, and analyze the workload to find an optimal physical design, indicia of which (e.g., graphs, text) is outputted  336  to the user. The user may decide  338  to perform additional steps, again, in arbitrary order. 
       FIG. 13  shows a diagram illustrating the free-form manner of user interaction possible for design tuning. The user continuously enters user input  360 , which may be specification commands  362  that specify the scenario such as a configuration, a workload or queries, databases, etc. Generally, specification commands are handled by the shell, front-end, high-level API (e.g., assembly), etc., rather than the DBMS. The user may also provide user input  360  in the form of commands  364  that invoke what-if functionality and other design functionality provided by the DBMS via the low-level API and/or core DBMS. While a command line shell/interpreter implementation has been described, graphical user interfaces can also be used, either as programs directly interfacing with the low-level API and high-level API, or by interfacing with another front-end such as a character-based shell environment. 
     CONCLUSION 
     Embodiments and features discussed above can be realized in the form of information stored in volatile or non-volatile computer or device readable media. This is deemed to include at least media such as optical storage (e.g., CD-ROM), magnetic media, flash ROM, or any current or future means of storing digital information. The stored information can be in the form of machine executable instructions (e.g., compiled executable binary code), source code, bytecode, or any other information that can be used to enable or configure computing devices to perform the various embodiments discussed above. This is also deemed to include at least volatile memory such as RAM and/or virtual memory storing information such as CPU instructions during execution of a program carrying out an embodiment, as well as non-volatile media storing information that allows a program or executable to be loaded and executed. The embodiments and features can be performed on any type of computing device, including portable devices, workstations, servers, mobile wireless devices, and so on.

Technology Category: g