Patent Publication Number: US-2023153303-A1

Title: Database Query Optimization Via Parameter-Sensitive Plan Selection

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This U.S. patent application claims priority under 35 U.S.C. § 119(e) to U.S. Provisional Application 63/264,172, filed on Nov. 16, 2021. The disclosure of this prior application is considered part of the disclosure of this application and is hereby incorporated by reference in its entirety. 
    
    
     TECHNICAL FIELD 
     This disclosure relates to optimizing database queries via parameter-sensitive plan selection. 
     BACKGROUND 
     Cloud database systems are increasingly used to store and query vast quantities of data. Conventional database query engines, when receiving a query from a user, build query plans to execute the received query. The query plan describes how a query is converted into a “program” that returns the requested data. The selection of the query plan determines the runtime (i.e., the latency) that the query incurs. Query latency is the primary user-visible performance metric for databases and users. 
     SUMMARY 
     One aspect of the disclosure provides a computer-implemented method for database query optimization that when executed by data processing hardware causes the data processing hardware to perform operations. The operations include receiving a database query requesting a database to conditionally return one or more data blocks stored at the database. The database is stored on memory hardware in communication with the data processing hardware and the database query includes a plurality of respective parameters characterizing the database query. The operations include generating a set of query plans. Each query plan in the set of query plans is configured to execute the database query using a different order of operations. The operations include training a model using historical database queries and generating, using the trained model, a query plan score for each query plan in the set of query plans based on the plurality of respective parameters. The operations include selecting, using the query plan score of each query plan in the set of query plans, a query plan from the set of query plans. The operations also include executing the database query using the selected query plan. 
     Implementations of the disclosure may include one or more of the following optional features. In some implementations, the database query includes a Structured Query Language (SQL) query. Optionally, generating the set of query plans includes using a database query planner. In some examples, selecting the query plan is based on an amount of memory available or an amount of cache available. Selecting the query plan may be based on a predicted latency of each query plan of the set of query plans. The predicted latency may include a tail latency. 
     In some implementations, selecting the query plan is based on a predicted resource usage of each query plan of the set of query plans. Each query plan of the set of query plans may include a hint string and selecting the query plan may be based on the hint string of each query plan of the set of query plans. In some examples, the operations further include, prior to generating the set of query plans, selecting a query template from a set of query templates. Generating the set of query plans includes using the selected query template. Selecting the query plan may be based on a state of the data processing hardware. 
     Another aspect of the disclosure provides a system for database query optimization. The system includes data processing hardware and memory hardware in communication with the data processing hardware. The memory hardware stores instructions that when executed on the data processing hardware cause the data processing hardware to perform operations. The operations include receiving a database query requesting a database to conditionally return one or more data blocks stored at the database. The database is stored on memory hardware in communication with the data processing hardware and the database query includes a plurality of respective parameters characterizing the database query. The operations include generating a set of query plans. Each query plan in the set of query plans is configured to execute the database query using a different order of operations. The operations include training a model using historical database queries and generating, using the trained model, a query plan score for each query plan in the set of query plans based on the plurality of respective parameters. The operations include selecting, using the query plan score of each query plan in the set of query plans, a query plan from the set of query plans. The operations also include executing the database query using the selected query plan. 
     This aspect may include one or more of the following optional features. In some implementations, the database query includes a Structured Query Language (SQL) query. Optionally, generating the set of query plans includes using a database query planner. In some examples, selecting the query plan is based on an amount of memory available or an amount of cache available. Selecting the query plan may be based on a predicted latency of each query plan of the set of query plans. The predicted latency may include a tail latency. 
     In some implementations, selecting the query plan is based on a predicted resource usage of each query plan of the set of query plans. Each query plan of the set of query plans may include a hint string and selecting the query plan may be based on the hint string of each query plan of the set of query plans. In some examples, the operations further include, prior to generating the set of query plans, selecting a query template from a set of query templates. Generating the set of query plans includes using the selected query template. Selecting the query plan may be based on a state of the data processing hardware. 
     The details of one or more implementations of the disclosure are set forth in the accompanying drawings and the description below. Other aspects, features, and advantages will be apparent from the description and drawings, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG.  1    is a schematic view of an example system for optimizing database queries. 
         FIG.  2    is a schematic view of exemplary components of a query optimizer of the system of  FIG.  1   . 
         FIG.  3    is a schematic view of exemplary components of a query planner of the query optimizer of  FIG.  2   . 
         FIG.  4    is a flowchart of an example arrangement of operations for a method of optimizing a database query using parameter-sensitive plan selection. 
         FIG.  5    is a schematic view of an example computing device that may be used to implement the systems and methods described herein. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
     Cloud database systems are increasingly used to store and query vast quantities of data. Conventional database query engines, when receiving a query from a user, build query plans to execute the received query. The query plan describes how a query is converted into a “program” that returns the requested data. The selection of the query plan determines the runtime (i.e., the latency) that the query incurs. Query latency is the primary user-visible performance metric for databases and users. However, conventional query planners, while strong in many scenarios, may fail at identifying and/or selecting the optimal query plan, especially for complex queries. These failures can be quite expensive computationally or temporally. Modern query planners rely on decades of research and expertise to choose or select the optimal query plan from the set of plans generated to execute a given query. Nonetheless, conventional techniques still may fail to select the most optimal (e.g., relative to latency, resource usage, etc.) query plan from the set, even when the query planner is successful at generating quality query plans. 
     Users often repeatedly execute similar queries that only change one or more predicates. For example, a query “SELECT foo from bar WHERE foo&gt;@param0” is a query where an application or user may perform the query multiple times with different values of “@param0” across different instances or executions. The optimal (i.e., fastest) query plan to execute the query may vary based on the bound predicate or parameter values, which in turn affect selectivities, join order decisions, join algorithms, and more. Determining the optimal query plan given the bound parameter values requires overcoming compounding cardinality estimation and cost-estimation errors. Moreover, changes to conventional query planners and optimizers introduce concerns regarding plan stability. Even when a new version of a planner is generally an improvement, certain queries that users rely on may actually regress (e.g., in latency). 
     Implementations herein are directed toward a query optimizer that leverages conventional query planners and machine learning to identify and select an optimal query plan from a set of query plans to execute a database query. The query optimizer generates plans for a given query template and uses machine learning (e.g., neural networks) to build a function that, for example, ranks the plans given query parameters. Alternatively, the query optimizer learns a latency estimate given the query parameters and selects the plan with the lowest latency. The query optimizer then executes the selected query plan to retrieve the requested data. 
     Referring to  FIG.  1   , in some implementations, a database query optimizer system  100  includes a remote system  140  in communication with one or more user devices  10  via a network  112 . The remote system  140  may be a single computer, multiple computers, or a distributed system (e.g., a cloud environment) having scalable/elastic resources  142  including computing resources  144  (e.g., data processing hardware) and/or storage resources  146  (e.g., memory hardware). A data store  150  (i.e., a remote storage device) may be overlain on the storage resources  146  to allow scalable use of the storage resources  146  by one or more of the clients (e.g., the user device  10 ) or the computing resources  144 . The data store  150  is configured to store a plurality of data blocks  152 ,  152   a - n  within one or more databases  158 ,  158   a - n  (i.e., a cloud database). The data store  150  may store any number of databases  158  at any point in time. 
     The remote system  140  is configured to receive a database query  20  (i.e., a request) from a user device  10  associated with a respective user  12  via, for example, the network  112 . The user device  10  may correspond to any computing device, such as a desktop workstation, a laptop workstation, or a mobile device (i.e., a smart phone). The user device  10  includes computing resources  18  (e.g., data processing hardware) and/or storage resources  16  (e.g., memory hardware). The user  12  may construct the database query  20  using a Structured Query Language (SQL) interface  14 , although other interfaces are contemplated. The database query  20  requests the remote system  140  to query one or more of the databases  158  to conditionally return one or more data blocks  152  stored at the queried databases  158 . As discussed in more detail below, the database query  20  includes (explicitly or implicitly) one or more parameters  214 ,  214   a - n  that characterize the database query  20 . 
     The remote system  140  executes a query optimizer  160  that receives the database query  20 . The query optimizer  160  may include a query planner  220  that, using the database query  20 , generates a set of query plans  230 ,  230   a - n . Each query plan  230  in the set of query plans  230  are configured to execute the database query using a different order of operations. That is, each query plan  230  is a different “program” that provides specific instructions and ordering for operations (e.g., join operations, scan operations, merge operations, etc.) the query optimizer  160  may perform or execute to retrieve the data blocks  152  requested by the database query  20 . Each database query  20  may be executed in any number of ways (i.e., with any number and order of different operations). The set of query plans  230  represents at least a portion of the different ways the query optimizer  160  may perform operations to retrieve the requested data blocks  152 . 
     In some implementations, the query optimizer  160  includes a model trainer  310 . The model trainer  310  trains a model  162  using, for example, historical database queries  20 H (i.e., database queries  20  previously executed by the query optimizer  160  or other processing systems). The trained model  162  receives the set of query plans  230  and generates a query plan score  167  or otherwise ranks each query plan  230 . The trained model  162  generates or predicts the query plan scores  167  based on the training using the historical database queries  20 H and/or other features, such as the parameters  214 . For example, the trained model  162  generates the query plan score  167  based on a predicted amount of latency the corresponding query plan  230  will incur during execution. In other examples, the trained model  162  generates the query plan score  167  based on an amount of resources (e.g., processing resources, memory resources, bandwidth resources, etc.) required to execute the corresponding query plan  230 . The query plan score  167  may be based on a number of different factors (e.g., a combination of latency and required resources). The trained model  162  may generate multiple query plan scores  167  for each query plan  230  to correspond to different predicted aspects of the query plan  230  (i.e., a first score for latency and a second score for resources consumed). 
     A plan selector  170  receives the query plan scores  167  for the set of query plans  230  and selects a query plan  230 S from the set of query plans  230  based on or using the query plan scores  167 . In some implementations, the plan selector  170  selects the query plan  230 S based on one or more configurable user preferences  174 . For example, the user  12  specifies (e.g., via the database query  20 ) that latency is the most important factor when executing the database query  20 , and thus the plan selector  170  selects the query plan  230  with the query plan score  167  that reflects the lowest predicted latency. A plan executor  180  may execute the selected query plan  230 S and return one or more data blocks  152  to the user device  10  based on the results of execution of the selected query plan  230 S. 
     Referring now to  FIG.  2   , a schematic view  200  includes exemplary components of the query optimizer  160 . Here, a query template generator  210  receives the database query  20  and generates or populates or otherwise provides a template  212  to the query planner  220 . The template  212  includes the parameters  214  received or derived from the database query  20 . In some examples, the parameters  214  are directly extracted from the database query  20 . In other examples, the database query  20  is not parameterized, but instead includes predicates that the query optimizer  160  converts into one or more parameters  214 . For example, the query optimizer (e.g., the query template generator  210 ) may convert a database query  20  that includes the query “r.r_name=‘Europe’” into “r.r_name=@param0”, where ‘@param0’ represents a parameter  212 . As another example, the query optimizer  160  may convert the query “c.c_mktsegment=‘BUILDING’” into “c.c_mktsegment=@param1” where ‘@param1’ represent another parameter  214 . 
     In some implementations, the query template generator  210  receives the database query  20  and populates an existing template  212  with parameters extracted from the database query  20  or generates a new template  212  (e.g., when no existing template  212  is appropriate for the database query  20 ). The query planner  220  then generates the set of query plans  230  using the template  212  populated with the parameters  214  (i.e., an instance of the template  212 ). The query planner  220  may be a conventional query planner used in typical database systems that leverages previous experience in generating quality query plans  230 . The query planner  220  may be configured to generate any number of query plans  230 . 
     Additionally or alternatively, the query optimizer  160  uses other means to generate the set of query plans  230 . For example, the query optimizer  160  randomly generates the set of query plans  230  from the set of all possible query plans  230 . In other examples, the query optimizer  160  generates the entire possible set of query plans  230  (e.g., when the database query  20  is sufficiently simple to produce a manageable number of possible query plans  230 ). In yet other examples, a machine learning model may be trained to produce the query plans  230 . 
     Regardless how the query plans  230  are generated, the trained model  162  receives each generated query plan  230  and may, for each respective query plan  230 , generate a respective query plan score  167 . In these examples, the query plan score  167  predicts one or more aspects of the respective query plan  230 , such as a predicted latency to execute the query plan  230 , predicted resource consumption, etc. Latency may refer to one or more different aspects of the time required to execute the query plan  230 . For example, the latency may refer to the mean latency (i.e., the average latency) and/or a tail latency (i.e., a high-percentile latency). In some use cases, one type of latency may be more important than a different type of latency. For example, some users may tolerate a higher mean latency in order to improve a tail latency. The model  162  may be trained based on the desired latency performance. In other examples, the trained model  162  ranks the query plans  230  using the query parameters  214 . 
     Portions or all of the query template generator  210  may be implemented on a system remote to the remote system  140 . For example, an external system may parameterize queries and/or programmatically issue queries with a common template to the remote system  140 . The query planner  220  may recognize or identity a known template received from the query template generator  210  and fetch a model  162  accordingly (i.e., fetch the model  162  that corresponds to the identified template). 
     Referring back to  FIG.  1   , the plan selector  170  receives the query plan scores  167  from the trained model  162  and selects an optimal query plan  230  from the set of query plans  230  based on the provided query plan scores  167 . The plan selector  170 , for example, selects the query plan  230  that the trained model  162  predicts will have the lowest latency (e.g., median latency, tail latency, etc.). In some examples, the plan selector  170  selects the query plan  230  based at least in part on current available resources of the remote system  140 . For example, the plan selector  170  determines an amount of available memory and/or cache and bases the query plan selection on the determined amounts. Specifically, the plan selector  170  may weight a query plan  230  that is predicted to consume less resources higher than query plans  230  that consume more resources. On the other hand, when the amount of resources available is high, the plan selector  170  may apply little weight to the predicted amount of resources consumed when selecting the optimal query plan  230 . In some implementations, the query optimizer  160  trains a separate model  162  for each template  212 . In these implementations, each model  162  is trained on historical database queries  20 H that apply to the respective template  212  of the model  162 . Alternatively, the query optimizer  160  trains a general model  162  that is applicable to multiple templates  212 . 
     Additionally or alternatively, the user  12  provides one or more user preferences  174 . The user preferences  174  may influence the query plan  230  the plan selector  170  selects by providing weight to preferences such as importance of types of latencies (median, tail, etc.), resource limits, etc. 
     Referring now to  FIG.  3   , a schematic view  300  includes the model trainer  310  and the model  162 . Here, the model trainer  310 , when training the model  162 , retrieves training samples from the data store  150 . The training samples include, for example, annotated historical database queries  20 H and the query plan used to execute the respective historical database query  20 H. The annotated historical database queries  20 H may include the query, the query plan used, the actual latency of the query plan used, the amount of resources used, etc. The training samples may be formed of one or more templates  212  generated by the query template generator  210  ( FIG.  2   ). The training samples may include any number of features  312 ,  312   a - n . Exemplary features of the training samples include, but are not limited to, the actual latency  312   a  of the corresponding historical database query  20 H, the actual resource usage  312   b , the resource availability  312   c  when the query plan was executed, and one or more hint strings  312   d . Hint strings  312   d  refer to configuration parameters provided to query planners to guide or control query plan creation and selection. For example, a hint string  312   d  may be a simple description of special form integrated into the SQL query text. Thus, in some implementations, each query plan  230  includes a hint string  312   d  and the plan selector  170  selects the query plan  230 S based at least in part on the hint strings  312   d  (e.g., via the hint strings  312   d  influencing the query plan score  167  or based on the selection by the plan selector  170 ). During training, the model  162  provides predictions (i.e., generates the query plan scores  167 ) and adjusts weights or other parameters based on the training samples. 
     The query optimizer  160  may generate the query plans  230  and train the model(s)  162  “offline.” That is, the query optimizer  160  may train a large number of models  162 , each model  162  trained on database queries  20  fit to a specific template  212 . For example, a first model  162  is trained on many database queries  20  that each “fit” a first template  212 . The first model  162 , once trained, will be selected (e.g., by the query planner  220 ) when a database query  20  from a user  12  that fits the corresponding template  212 . A second model  162  may be trained on database queries  20  that fit a different template  212 . This second model, once trained, will be selected when a database query  20  from a user  12  fits the template  212  that corresponds to the second model  162 . 
     Thus, the query optimizer  160  employs machine learning techniques and empirical query execution latencies (i.e., actual latencies  310   a  measured from historical database queries  20 H) to overcome shortcomings in conventional query optimizer cost models and cardinality estimates. The query optimizer  160  may leverage decades of database expertise by using a conventional database query planner  220  to generate the query plans  230  while refining the query plan selection using observed, actual behavior. The query optimizer  160  improves plan stability as the model  162  adjusts to capture improvements in query planners  220  while avoiding optimizer regressions. 
       FIG.  4    is a flowchart of an exemplary arrangement of operations for a method  400  that, when executed by data processing hardware  144 , causes the data processing hardware to perform operations to optimize a database query via parameter-sensitive plan selection. The method  400 , at operation  402 , includes receiving a database query  20  requesting the data processing hardware  144  query a database  158  stored on memory hardware  146  in communication with the data processing hardware  144 . The database query  20  includes a plurality of parameters  214  characterizing the database query  20 . At operations  404 , the method  400  includes generating a set of query plans  230 . Each query plan  230  in the set of query plans  230  is configured to execute the database query  20  using a different order of operations. The method  400 , at operation  406 , includes training a model  162  using historical database queries  20 H. At operation  408 , the method  400  includes generating, using the trained model  162 , a query plan score  167  for each query plan  230  in the set of query plans  230 . At operation  410 , the method  400  includes selecting, using the query plan score  167  of each query plan  230  in the set of query plans  230 , a query plan  230 S from the set of query plans  230 . At operation  412 , the method  400  includes executing the database query  20  using the selected query plan  230 . 
       FIG.  5    is schematic view of an example computing device  500  that may be used to implement the systems and methods described in this document. The computing device  500  is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document. 
     The computing device  500  includes a processor  510 , memory  520 , a storage device  530 , a high-speed interface/controller  540  connecting to the memory  520  and high-speed expansion ports  550 , and a low speed interface/controller  560  connecting to a low speed bus  570  and a storage device  530 . Each of the components  510 ,  520 ,  530 ,  540 ,  550 , and  560 , are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor  510  can process instructions for execution within the computing device  500 , including instructions stored in the memory  520  or on the storage device  530  to display graphical information for a graphical user interface (GUI) on an external input/output device, such as display  580  coupled to high speed interface  540 . In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices  500  may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system). 
     The memory  520  stores information non-transitorily within the computing device  500 . The memory  520  may be a computer-readable medium, a volatile memory unit(s), or non-volatile memory unit(s). The non-transitory memory  520  may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by the computing device  500 . Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes. 
     The storage device  530  is capable of providing mass storage for the computing device  500 . In some implementations, the storage device  530  is a computer-readable medium. In various different implementations, the storage device  530  may be a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. In additional implementations, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory  520 , the storage device  530 , or memory on processor  510 . 
     The high speed controller  540  manages bandwidth-intensive operations for the computing device  500 , while the low speed controller  560  manages lower bandwidth-intensive operations. Such allocation of duties is exemplary only. In some implementations, the high-speed controller  540  is coupled to the memory  520 , the display  580  (e.g., through a graphics processor or accelerator), and to the high-speed expansion ports  550 , which may accept various expansion cards (not shown). In some implementations, the low-speed controller  560  is coupled to the storage device  530  and a low-speed expansion port  590 . The low-speed expansion port  590 , which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet), may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter. 
     The computing device  500  may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server  500   a  or multiple times in a group of such servers  500   a , as a laptop computer  500   b , or as part of a rack server system  500   c.    
     Various implementations of the systems and techniques described herein can be realized in digital electronic and/or optical circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device. 
     A software application (i.e., a software resource) may refer to computer software that causes a computing device to perform a task. In some examples, a software application may be referred to as an “application,” an “app,” or a “program.” Example applications include, but are not limited to, system diagnostic applications, system management applications, system maintenance applications, word processing applications, spreadsheet applications, messaging applications, media streaming applications, social networking applications, and gaming applications. 
     These computer programs (also known as programs, software, software applications or code) include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms “machine-readable medium” and “computer-readable medium” refer to any computer program product, non-transitory computer readable medium, apparatus and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor. 
     The processes and logic flows described in this specification can be performed by one or more programmable processors, also referred to as data processing hardware, executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     To provide for interaction with a user, one or more aspects of the disclosure can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube), LCD (liquid crystal display) monitor, or touch screen for displaying information to the user and optionally a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user&#39;s client device in response to requests received from the web browser. 
     A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the disclosure. Accordingly, other implementations are within the scope of the following claims.