A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization

Shashi Shekhar; Jaideep Srivastava; Soumitra Dutta

A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries[1]. This paper discusses the tradeoff between the two costs in the context of semantic query optimization, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The paper also contributes a practical model of semantic query optimization, and a discussion of its search ordering and termination problems.

Original language	English (US)
Title of host publication	VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases
Editors	Francois Bancilhon, David J. DeWitt
Publisher	Morgan Kaufmann Publishers, Inc.
Pages	457-467
Number of pages	11
ISBN (Electronic)	0934613753, 9780934613750
State	Published - 1988
Externally published	Yes
Event	14th International Conference on Very Large Data Bases, VLDB 1988 - Los Angeles, United States Duration: Aug 29 1988 → Sep 1 1988

Publication series

Name	VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases

Conference

Conference	14th International Conference on Very Large Data Bases, VLDB 1988
Country/Territory	United States
City	Los Angeles
Period	8/29/88 → 9/1/88

Bibliographical note

Publisher Copyright:
© VLDB 1987.All rights reserved.

Find It

Find It at U of M Libraries

Cite this

Shekhar, S., Srivastava, J., & Dutta, S. (1988). A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. In F. Bancilhon, & D. J. DeWitt (Eds.), VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases (pp. 457-467). (VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases). Morgan Kaufmann Publishers, Inc..

A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. / Shekhar, Shashi ; Srivastava, Jaideep; Dutta, Soumitra.
VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases. ed. / Francois Bancilhon; David J. DeWitt. Morgan Kaufmann Publishers, Inc., 1988. p. 457-467 (VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Shekhar, S , Srivastava, J & Dutta, S 1988, A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. in F Bancilhon & DJ DeWitt (eds), VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases. VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers, Inc., pp. 457-467, 14th International Conference on Very Large Data Bases, VLDB 1988, Los Angeles, United States, 8/29/88.

Shekhar S , Srivastava J, Dutta S. A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. In Bancilhon F, DeWitt DJ, editors, VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers, Inc. 1988. p. 457-467. (VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases).

Shekhar, Shashi ; Srivastava, Jaideep ; Dutta, Soumitra. / A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases. editor / Francois Bancilhon ; David J. DeWitt. Morgan Kaufmann Publishers, Inc., 1988. pp. 457-467 (VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases).

@inproceedings{3b287b527b194abdbf178b7a21208001,

title = "A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization",

abstract = "Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries[1]. This paper discusses the tradeoff between the two costs in the context of semantic query optimization, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The paper also contributes a practical model of semantic query optimization, and a discussion of its search ordering and termination problems.",

author = "Shashi Shekhar and Jaideep Srivastava and Soumitra Dutta",

year = "1988",

language = "English (US)",

series = "VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases",

publisher = "Morgan Kaufmann Publishers, Inc.",

pages = "457--467",

editor = "Francois Bancilhon and DeWitt, \{David J.\}",

booktitle = "VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases",

address = "United States",

}

TY - GEN

T1 - A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization

AU - Shekhar, Shashi

AU - Srivastava, Jaideep

AU - Dutta, Soumitra

PY - 1988

Y1 - 1988

N2 - Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries[1]. This paper discusses the tradeoff between the two costs in the context of semantic query optimization, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The paper also contributes a practical model of semantic query optimization, and a discussion of its search ordering and termination problems.

AB - Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries[1]. This paper discusses the tradeoff between the two costs in the context of semantic query optimization, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The paper also contributes a practical model of semantic query optimization, and a discussion of its search ordering and termination problems.

UR - https://www.scopus.com/pages/publications/105029736108

UR - https://www.scopus.com/pages/publications/105029736108#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:105029736108

T3 - VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases

SP - 457

EP - 467

BT - VLDB 1988 - Proceedings of the 14th International Conference on Very Large Data Bases

A2 - Bancilhon, Francois

A2 - DeWitt, David J.

PB - Morgan Kaufmann Publishers, Inc.

T2 - 14th International Conference on Very Large Data Bases, VLDB 1988

Y2 - 29 August 1988 through 1 September 1988

ER -

A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this