Implementing sorting in database systems

被引：76

作者：

Graefe, Goetz ^{[1
]}

机构：

[1] Microsft Inc, Redmond, WA 98052 USA

来源：

ACM COMPUTING SURVEYS | 2006年 / 38卷 / 03期

关键词：

algorithms; performance; key normalization; key conditioning; compression; dynamic memory resource allocation; graceful degradation; nested iteration; asynchronous read-ahead; forecasting; index operations;

D O I：

10.1145/1132960.1132964

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Most commercial database systems do ( or should) exploit many sorting techniques that are publicly known, but not readily available in the research literature. These techniques improve both sort performance on modern computer systems and the ability to adapt gracefully to resource fluctuations in multiuser operations. This survey collects many of these techniques for easy reference by students, researchers, and product developers. It covers in-memory sorting, disk-based external sorting, and considerations that apply specifically to sorting in database systems.

引用

页数：37

共 53 条

[11] DUPLICATE RECORD ELIMINATION IN LARGE DATA FILES [J].

BITTON, D ;

DEWITT, DJ .

ACM TRANSACTIONS ON DATABASE SYSTEMS, 1983, 8 (02) :255-265

[12] ENCODING METHOD FOR MULTI-FIELD SORTING AND INDEXING [J].

BLASGEN, MW ;

CASEY, RG ;

ESWARAN, KP .

COMMUNICATIONS OF THE ACM, 1977, 20 (11) :874-878

[13] RAID - HIGH-PERFORMANCE, RELIABLE SECONDARY STORAGE [J].

CHEN, PM ;

LEE, EK ;

GIBSON, GA ;

KATZ, RH ;

PATTERSON, DA .

ACM COMPUTING SURVEYS, 1994, 26 (02) :145-185

[14] UBIQUITOUS B-TREE [J].

COMER, D .

COMPUTING SURVEYS, 1979, 11 (02) :121-137

[15]

Conner W. M., 1977, IBM Technical Disclosure Bulletin, V20, P2832

[16]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[17]

ESTIVILLCASTRO V, 1992, COMPUT SURV, V24, P441, DOI 10.1145/146370.146381

[18]

Gassner P., 1993, IEEE DATA ENG B, V16, P4

[19] Compressing relations and indexes [J].

Goldstein, J ;

Ramakrishnan, R ;

Shaft, U .

14TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, PROCEEDINGS, 1998, :370-379

[20]

Graefe G., 1998, Proceedings of the Twenty-Fourth International Conference on Very-Large Databases, P86

← 1 2 3 4 5 6 →