System and method for graceful degradation of a database query

Details System and method for graceful degradation of a database query System and method for graceful degradation of a database query

2004-07-22

2009-08-25

Alam, Hosain T (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07580920

ABSTRACT:
A method to achieve acceptable query performance even when a database query optimizer chooses an inefficient query plan due to poor cardinality (row count) estimation includes generating a batch sort query plan which includes a row count operation and a reorder operation. The batch sort, and in particular the reorder operation, is not required to satisfy the query but without these operations the query plan may prove to be inefficient. When the row count operation determines that the query plan is inefficient, the row reordering operation reorders rows for more I/O efficient processing. The results of both the row count operation and the reorder operation are used to produce the desired rowset to satisfy the input query without discarding any retrieved rows. The combination of the row count operation and reorder operation allows a graceful degradation of query performance where the original query plan selected by a query optimizer without the batch sort or reorder operation would execute in an I/O inefficient manner.

REFERENCES:
patent: 6424967 (2002-07-01), Johnson et al.
patent: 6907422 (2005-06-01), Predovic
patent: 7010516 (2006-03-01), Leslie
patent: 7171408 (2007-01-01), Zuzarte
patent: 2004/0010488 (2004-01-01), Chaudhuri et al.
patent: 2005/0097078 (2005-05-01), Lohman et al.
patent: 2005/0267866 (2005-12-01), Markl et al.
V. Raman, B. Raman, and J. M. Hellerstein, “Online dynamic reordering”, The VLDB Journal, Jun. 23, 2000 pp. 247-260.
Arge, L. et al., “Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems”,Symposium on Discrete Algorithms, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 685-694.
Bruno, N. et al., “Exploiting Statistics on Query Expressions for Optimization”,International Conference on Management of Data, Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002, 263-274.
Cole, R.L. et al., “Optimization of Dynamic Query Evaluation Plans”,International Conference on Management of Data, Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994, 150-160.
Graefe, G. et al., “Dynamic Query Evaluation Plans”,International Conference on Management of Data, Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, 1989, 358-366.
Graefe, G., “Query Evaluation Techniques for Large Databases”, Based on a survey with the same title published inACM Computing Surveys, Jun. 1993, 73-170.
Hsu, C-N. et al., “Reformulating Query Plans for Multidatabase Systems”,Conference on Information and Knowledge Management, Proceedings of the 2ndInternational Conference on Information and Knowledge Management, 1993, 423-432.
Ioannidis, Y.E. et al., “On the Propagation of Errors in the Size of Join Results”,International Conference on Management of Data, Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, 1991, 268-277.
Kabra, N. et al., “Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans”,international Conference on Management of Data, Proceedings of the 1998, ACM SIGMOD International Conference on Management of Data, 1998, 106-117.
Reiss, F.R. et al., “A Characterization of the Sensitivity of Query Optimization to Storage Access Cost”,International Conference on Management of Data, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003, 385-396.

Affiliated with

Also associated with

Rating

System and method for graceful degradation of a database query does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for graceful degradation of a database query, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for graceful degradation of a database query will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4098625