Database system with subquery optimizer

In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising rows of data records, each data record storing information in database columns, a method for executing a database query for selecting particular ones of said data records, the method comprising:

• (a) receiving a database query specifying selection of particular ones of said data records, said database query comprising an expression specifying a query condition and further comprising at least one database subquery nested within the database query, said subquery comprising an expression specifying a subquery result which is determined before evaluation of the expression for the database query is undertaken, the expression for the subquery being dependent upon at least one input value from a database column of said database;
• (b) creating a subquery cache in said memory for storing subquery results computed for corresponding input values from said database, wherein said subquery cache is divided into a plurality of cache rows, each row for storing a subquery result computed for corresponding input values, said cache rows being arranged from top to bottom of said subquery cache, said top of said subquery cache storing a most-recently computed subquery result, said subquery cache having a size;
• and
• (c) executing said database query by:
• (i) scanning each said data records of said database for evaluating whether the data record being scanned meets the query condition;
• (ii) as each data record is scanned, if said at least one input value is already stored in said subquery cache, evaluating said expression for the subquery by retrieving the corresponding subquery result;
• (iii) storing cache statistics in said memory describing how often said expression for the subquery is determined by retrieving the corresponding subquery result from said subquery cache;
• and
• (iv) adjusting said size of said subquery cache based on said cache statistics such that if all cache hits occur at the top of said subquery cache after scanning a pre-selected number of times, said size of said subquery cache is adjusted to one row.

In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising rows of data records, each data record storing information in database columns, a method for executing a database query for selecting particular ones of said data records, the method comprising:

• (a) receiving a database query specifying selection of particular ones of said data records, said database query comprising an expression specifying a query condition and further comprising at least one database subquery nested within the database query, said subquery comprising an expression specifying a subquery result which is determined before evaluation of the expression for the database query is undertaken, the expression for the subquery being dependent upon at least one input value from a database column of said database;
• (b) creating a subquery cache in said memory for storing subquery results computed for corresponding input values from said database, wherein said subquery cache is divided into a plurality of cache rows, each row for storing a subquery result computed for corresponding input values, said cache rows being arranged from top to bottom of said subquery cache, said top of said subquery cache storing a most-recently computed subquery result, said subquery cache having a size;
• and
• (c) executing said database query by:
• (i) scanning each said data records of said database for evaluating whether the data record being scanned meets the query condition;
• (ii) as each data record is scanned, if said at least one input value is already stored in said subquery cache, evaluating said expression for the subquery by retrieving the corresponding subquery result;
• (iii) storing cache statistics in said memory describing how often said expression for the subquery is determined by retrieving the corresponding subquery result from said subquery cache;
• and
• (iv) adjusting said size of said subquery cache based on said cache statistics such that if all cache hits occur within a certain row depth from the top of said subquery cache after scanning a pre-selected number of times, said size of said subquery cache is adjusted based on said row depth.

In a database system comprising a processor, a memory, and a storage device, said storage device storing a database comprising rows of data records, each data record storing information in database columns, an improved query execution unit comprising:

• means for receiving a database query having at least one database subquery nested within the database query, said subquery comprising an expression specifying a subquery result which is determined before evaluation of the expression for the database query is completed, the expression for the subquery being dependent upon at least one input value from a database column of said database;
• a subquery cache in said memory for caching subquery results computed for corresponding input values from said database wherein said cache rows are arranged from toy to bottom of said subquery cache, said top of said subquery cache storing a most recently computed subquery result;
• means for monitoring performance of said subquery cache during query execution, said means for monitoring including
• means for storing a least-recently-used depth value,
• means for storing a hit counter, and
• means for storing a miss counter:
• means for executing said database query by scanning each said data records of said database for evaluating whether the data record being scanned meets the query condition;
• and
• means, responsive to said monitoring means, for dynamically adjusting the size of said subquery cache based on said performance of said subquery cache for input values scanned from said data records during query execution.

In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising rows of data records, each data record storing information in database columns, a method for executing a database query for selecting particular ones of said data records, the method comprising:

• receiving a database query specifying selection of particular ones of said data records, said database query comprising an expression specifying a query condition and further comprising at least one database subquery nested within the database query, said subquery comprising an expression specifying a subquery result which is determined before evaluation of the expression for the database query is undertaken, the expression for the subquery being dependent upon at least one input value from a database column of said database;
• creating a subquery cache in said memory for storing subquery results computed for corresponding input values from said database, wherein
• said subquery cache is divided into a plurality of cache rows, each row for storing a subquery result computed for corresponding input values,
• said cache rows are arranged from top to bottom of said subquery cache,
• said top of said subquery cache stores a most-recently computed subquery result;
• initially setting said subquery cache to have a size equal to a maximum size;
• initializing cache statistics including a hit counter, a miss counter, and a maximum depth value;
• executing said database query by scanning said data records of said database for evaluating whether the data record being scanned meets the query condition, and for each data record encountered until said subquery cache is filled once, performing substeps of:
• (a) if said at least one input value is already stored in said subquery cache,
• evaluating said expression for the subquery by retrieving the corresponding subquery result,
• increasing the hit counter, and
• updating the maximum depth value if the hit is at a location in said subquery cache that is greater than the current value of the maximum depth counter, and
• (b) if said at least one input value is not already stored in said subquery cache,
• evaluating said expression for the subquery, and
• storing the corresponding subquery result in said subquery cache;
• if said subquery cache is filled and all hits are in the first row, setting said subquery cache size to one for the duration of the query;
• if said subquery cache is filled and there are no hits,
• setting said subquery cache size to one,
• continuing execution of the query for a particular number of data records, and
• if there are still no hits, ceasing use of said subquery cache;
• and
• if said subquery cache is filled and there are hits beyond the first row, continuing to execute the query and adjusting the size of said subquery cache based on said cache statistics.

In a client/server database system, an improved method for executing a database query submitted by a client to a database server, said database query including a subquery, the method comprising:

• storing a cache of a particular size in memory for caching a subquery result computed from input values to the subquery;
• executing the query for providing a query result to the client;
• storing computed subquery result values in said cache with cache rows arranged from top to bottom of said subquery cache, said top of said subquery cache storing a most-recently computed subquery result;
• while executing the query, updating statistics describing use of said subquery cache during query execution, said statistics including a number of hits, a number of misses, and a number indicating the maximum depth in said subquery cache a hit has occurred;
• and
• while executing the query, adjusting size of said subquery cache based on said statistics.