{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:08Z","timestamp":1773481928871,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Query scheduling, a fundamental problem in database management systems, has recently received a renewed attention, perhaps in part due to the rise of the \"database as a service\" (DaaS) model for database deployment. While there has been a great deal of work investigating different scheduling algorithms, there has been comparatively little work investigating what the scheduling algorithms can or should know about the queries to be scheduled. In this work, we investigate the efficacy of using histograms describing the distribution of likely query execution times as input to the query scheduler. We propose a novel distribution-based scheduling algorithm, Shepherd, and show that Shepherd substantially outperforms state-of-the-art point-based methods through extensive experimentation with both synthetic and TPC workloads.<\/jats:p>","DOI":"10.14778\/2536360.2536367","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"673-684","source":"Crossref","is-referenced-by-count":11,"title":["Distribution-based query scheduling"],"prefix":"10.14778","volume":"6","author":[{"given":"Yun","family":"Chi","sequence":"first","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hakan","family":"Hac\u00edg\u00fcm\u00fc\u015f","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wang-Pin","family":"Hsiung","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey F.","family":"Naughton","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, University of Wisconsin-Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","first-page":"13","article-title":"Deploying database appliances in the cloud","volume":"32","author":"Aboulnaga A.","year":"2009","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_2_1","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974","edition":"1"},{"issue":"3","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/65.844498","article-title":"A workload characterization study of the 1998 World Cup Web site","volume":"14","author":"Arlitt M.","year":"2000","journal-title":"Network, IEEE"},{"issue":"4","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/1721654.1721672","article-title":"A view of cloud computing","volume":"53","author":"Armbrust M.","year":"2010","journal-title":"Commun. ACM"},{"issue":"1","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S1389-1286(00)00087-6","article-title":"Integrating user-perceived quality into web server design","volume":"33","author":"Bhatti N.","year":"2000","journal-title":"Comput. Netw."},{"key":"e_1_2_1_6_1","volume-title":"FOCS","author":"Brodal G.","year":"2002"},{"key":"e_1_2_1_7_1","volume-title":"Scheduling algorithms","author":"Brucker P.","year":"2007","edition":"5"},{"issue":"9","key":"e_1_2_1_8_1","first-page":"563","article-title":"iCBS: Incremental cost-based scheduling under piecewise linear SLAs","volume":"4","author":"Chi Y.","year":"2011","journal-title":"PVLDB"},{"issue":"6","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/1323293.1294281","article-title":"Dynamo: Amazon's highly available key-value store","volume":"41","author":"DeCandia G.","year":"2007","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"e_1_2_1_10_1","volume-title":"SIGMOD","author":"Duggan J.","year":"2011"},{"key":"e_1_2_1_11_1","volume-title":"WWW","author":"Elnikety S.","year":"2004"},{"key":"e_1_2_1_12_1","volume-title":"ICDE","author":"Ganapathi A.","year":"2009"},{"key":"e_1_2_1_13_1","volume-title":"Adaptive quality of service management for enterprise services. TWEB, 2(1)","author":"Gmach D.","year":"2008"},{"key":"e_1_2_1_14_1","volume-title":"ICDE","author":"Guirguis S.","year":"2009"},{"key":"e_1_2_1_15_1","volume-title":"EDBT","author":"Gupta C.","year":"2009"},{"key":"e_1_2_1_16_1","volume-title":"SERVICES","author":"Hacig\u00fcm\u00fcs H.","year":"2010"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF01232184","article-title":"Value-based scheduling in real-time database systems","volume":"2","author":"Haritsa J. R.","year":"1993","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_18_1","volume-title":"SOCC","author":"He Y.","year":"2012"},{"issue":"2","key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1561\/1900000002","article-title":"Architecture of a database system","volume":"1","author":"Hellerstein J. M.","year":"2007","journal-title":"Foundations and Trends in Databases"},{"key":"e_1_2_1_20_1","volume-title":"SIGMOD","author":"Hong D.","year":"1993"},{"key":"e_1_2_1_21_1","volume-title":"HPDC","author":"Irwin D. E.","year":"2004"},{"issue":"11","key":"e_1_2_1_22_1","first-page":"1555","article-title":"Robust estimation of resource consumption for SQL queries using statistical techniques","volume":"5","author":"Li J.","year":"2012","journal-title":"PVLDB"},{"key":"e_1_2_1_23_1","volume-title":"ACM Conference on Electronic Commerce","author":"Liu Z.","year":"2001"},{"issue":"2","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","article-title":"Maintenance of configurations in the plane","volume":"23","author":"Overmars M. H.","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"issue":"23","key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"2559","DOI":"10.1016\/S1389-1286(99)00120-6","article-title":"Scheduling and admission control for integrated-services networks: the priority token bank","volume":"31","author":"Peha J. M.","year":"1999","journal-title":"Computer Networks"},{"issue":"2","key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1109\/26.486612","article-title":"Cost-based scheduling and dropping algorithms to support integrated services","volume":"44","author":"Peha J. M.","year":"1996","journal-title":"IEEE Transactions on Communications"},{"key":"e_1_2_1_28_1","volume-title":"Supercomputing","author":"Popovici F. I.","year":"2005"},{"issue":"2","key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.4018\/jdm.1996040101","article-title":"Where do deadlines come from and where do they go?","volume":"7","author":"Ramamritham K.","year":"1996","journal-title":"Journal Of Database Management"},{"issue":"2","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1023\/B:TIME.0000045317.37980.a5","article-title":"Real-time databases and data services","volume":"28","author":"Ramamritham K.","year":"2004","journal-title":"Real-Time Syst."},{"key":"e_1_2_1_31_1","volume-title":"NSDI","author":"Schroeder B.","year":"2006"},{"key":"e_1_2_1_32_1","volume-title":"Dagstuhl Workshop on Data Structures","author":"Sedgewick R.","year":"2008"},{"key":"e_1_2_1_33_1","volume-title":"ICDE","author":"Tozer S.","year":"2010"},{"issue":"3","key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","article-title":"Np-complete scheduling problems","volume":"10","author":"Ullman J. D.","year":"1975","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_35_1","volume-title":"PVLDB","author":"Wu W.","year":"2013"},{"key":"e_1_2_1_36_1","volume-title":"ICDE","author":"Wu W.","year":"2013"},{"key":"e_1_2_1_37_1","volume-title":"SOCC","author":"Xiong P.","year":"2011"},{"key":"e_1_2_1_38_1","volume-title":"ICSOC","author":"Zhang L.","year":"2004"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536360.2536367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:51:19Z","timestamp":1672221079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536360.2536367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":37,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.14778\/2536360.2536367"],"URL":"https:\/\/doi.org\/10.14778\/2536360.2536367","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}