MonetDB/X100: Hyper-Pipelining Query Execution
Data Archiving and Networked Services (DANS), 2005 · paper · Computer science
Investigates why database systems use modern CPUs inefficiently, then presents X100, a vector-processing query engine for MonetDB. On the 100GB TPC-H benchmark, its raw execution power is reported as one to two orders of magnitude above previous technology.
Checked: PDF from cidrdb.org, fetched 4 Oct 2026. Page numbers are those of that PDF.
5 findings
Substance Figure 4 (hand-coded UDF for Query 1) computes "entry->sum_charge += extprice*(1-p_tax[i]);", but Query 1 (Figure 3) defines sum_charge with "(1 + l_tax)".
- p. 6 Figure 4, last statement
entry->sum_charge += extprice*(1-p_tax[i]);
- p. 4 Figure 3
(1 + l_tax)) AS sum_charge
Judge's note: Page 6 image: Figure 4 clearly prints a minus sign, (1-p_tax[i]). Figure 3 on page 4 prints (1 + l_tax). Table 3 (r0 := [+](1.0,s5), where s5 is l_tax) and Figure 9 (+( flt('1.0'), l_tax)) on page 11 both use addition. The listing does not implement the query it is labelled as implementing. The obvious fix is (1+p_tax[i]).
Second check: another model agreed
Report a problem with this finding
Substance Table 3 SF=0.001 TOTAL is printed "2327" us, but the 20 per-statement us entries sum to 2590; the SF=1 ms column does sum to its printed 3724.
- p. 5 Table 3, SF=0.001 'us' column and TOTAL row
2327
- p. 5 Table 3, TOTAL row, SF=0.001 us column
3724 2327 TOTAL
Only the authors can say what is right here.
Judge's note: I read every value in Table 3 from the page 5 image and crop and re-added both columns. The SF=1 column sums exactly to 3724; the SF=0.001 column sums to 2590, not 2327. The text says the 20 invocations span more than 99% of elapsed time, so the total cannot be below their sum. The per-row bandwidths agree with their MB and us values (e.g. r0: 91MB/60us ≈ 1.5GB/s), so either the total or one of the entries is wrong. The text's 'almost twice as fast' rests on this total.
Second check: another model agreed
Report a problem with this finding
Substance "#ins/Instruction-Per-Cycle (IPC) = 38/0.8 = 49 cycles!" — 38/0.8 = 47.5; the 49 is reused ("rest of the 49 cycles", Section 5.1 "49 cycles per tuple").
- p. 5 Section 3.1, text after Table 2
= 38/0.8 = 49 cycles!
- p. 11 Section 5.1
49 cycles per tuple
- p. 5 Section 3.1, text after Table 2
(IPC) = 38/0.8 = 49 cycles!
- p. 11 Section 5.1, paragraph 2
the 49 cycles per tuple achieved by MySQL (see Section 3.1)
Only the authors can say what is right here.
Judge's note: Confirmed on the p5 and p11 images. Table 2 gives 38 instructions and IPC 0.80 for Item_func_plus::val. The printed equation gives 47.5, and even the extremes of rounding (38.5/0.795 ≈ 48.4) do not reach 49. The authors may have used unrounded profiler values, but the equation as printed does not hold.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [20] reads "In San Jose, USA, San Jose, CA, USA, May 1995.", which omits the proceedings name and gives the location twice.
- p. 13 Reference [20]
In San Jose, USA, San Jose, CA, USA, May 1995.
Only the authors can say what is right here.
Judge's note: The page 13 image of the reference list confirms the entry as quoted. The missing venue cannot be filled in from the files, so it goes to the authors.
Second check: another model agreed
Report a problem with this finding
Wording Table 3 statement "r3 := [*](s12,r0)" refers to an undefined BAT s12; the dataflow requires r2.
- p. 5 Table 3, row r3
r3 := [*](s12,r0)
Judge's note: The crop confirms 's12'. The trace defines only s0–s9 and r0–r9. sum_charge = extprice*(1-discount)*(1+tax) needs r2 (= [*](s3,r1)) times r0 (= [+](1.0,s5)), so the operand should be r2.
Second check: another model agreed
Report a problem with this finding
21 minor (typos and the like; most checked by the judge only)
Reference or label Reference venue locations look wrong: [16] reads "In Proc. SIGMOD, Madison, USA, 2000." and [21] reads "In Proc. VLDB, Toronto, Canada, 2003."
- p. 13 References [16]
Proc. SIGMOD, Madison, USA, 2000.
- p. 13 References [21]
Proc. VLDB, Toronto, Canada, 2003.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: SIGMOD 2000 was held in Dallas, USA (Madison hosted SIGMOD/PODS 2002), and VLDB 2003 was held in Berlin, Germany (Toronto hosted VLDB 2004). I opened both crops and confirmed the printed text of both entries on PDF page 13: [16] gives 'Madison, USA, 2000' and [21] gives 'Toronto, Canada, 2003'. Nothing in the files explains or corrects these entries, and the files contain no erratum. The venue facts cannot be checked from the files, so this goes to the authors as a query. It is a reference-label problem only: the cited works themselves are identifiable.
Second check: another model agreed
Report a problem with this finding
Wording Figure 2 code declares "int sel_lt_int_col_int_val(int n, int* res, int* in, int V)" but the body uses undeclared "src[i]" and "out[j]".
- p. 3 Figure 2 code
int sel_lt_int_col_int_val(int n, int* res, int* in, int V) {
- p. 3 Figure 2 code
if (src[i] < V)
Judge's note: The Figure 2 code on the page 3 image declares the parameters res and in. The loop body reads src[i] and writes out[j], so the identifiers do not match. This is an illustrative code listing, so the impact is minor.
Second check: another model agreed
Report a problem with this finding
Wording "SELECT oid FROM table WHERE col < X, where X is uniformly and randomly distributed over [0:100] and we vary the selectivity X": the distribution is attributed to X rather than col.
- p. 3 Section 2, Figure 2 description
where X is uniformly and randomly distributed over [0:100] and we vary the selectivity X between 0 and 100
Judge's note: Confirmed on the page 3 image. X is the constant that is varied to set selectivity, so the uniform distribution must belong to the column col. As written, X is given both roles. The intended meaning can be inferred.
Second check: another model agreed
Report a problem with this finding
Wording Table 1 lists DB2 UDB 8.1 (4 Itanium2 1.5GHz, SF=100) Q1 normalised cost "9.0", while Table 4 gives DB2 4CPU SF=100 Q1 = "229" s, which normalises to 9.16.
- p. 4 Table 1, DB2 UDB 8.1 row (4 Itanium2 1.5GHz, SF=100)
9.0
- p. 11 Table 4, Q1, DB2 4CPU SF=100
229
Only the authors can say what is right here.
Judge's note: Checked Table 1 (p4) and Table 4 (p11). All other values shared by the two tables agree: X100 SF=100 30.25 gives 0.30, X100 SF=1 gives 0.50 and 0.31, and MIL 3.72 gives 3.7. The DB2 value does not. Both tables appear to describe the same 4×1.5GHz Itanium2 DB2 8.1 system. Footnote 5 says the Table 4 numbers are stream 0 (power test), while Table 1 only says 'www.tpc.org', so Table 1 may come from a different run or stream. Only the authors can say which. The discrepancy is small.
Second check: another model agreed
Report a problem with this finding
Wording After the RISC example for "+(double src1, double src2)" (ADD), the text concludes "a MIPS processor can do one *(double,double) per 3 cycles".
- p. 5 Section 3.1, first line of left column
one *(double,double) per 3 cycles
- p. 4 Section 3.1
+(double src1, double src2)
Judge's note: The p4 image shows the example as an addition (ADD reg1,reg2,reg3), compared with Item_func_plus::val. The conclusion on p5 names multiplication instead, so the operator is mislabelled. The point would plausibly hold for either operation.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.3 says X100 "is able to get within a factor 2 of this hand-coded implementation", but in Table 1 the ratios are 0.50/0.22 (AthlonMP) and 0.31/0.14 (Itanium2), both slightly above 2.
- p. 7 Section 3.3, end
within a factor 2 of this hand-coded implementation
- p. 4 Table 1
MonetDB/X100 0.50
- p. 7 Section 3.3, final paragraph
is able to get within a factor 2 of this hand-coded implementation
- p. 4 Table 1, hand-coded and MonetDB/X100 rows
0.22
Judge's note: Page 4 image, Table 1: hand-coded 0.22 (AthlonMP) and 0.14 (Itanium2); MonetDB/X100 0.50 and 0.31. Both ratios are about 2.2 to 2.3, so 'within' overstates slightly. 'About a factor 2' would be accurate. Section 4.2 on page 9 also refers to 'this factor 2'.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.2 says "MonetDB/MIL then becomes almost twice as fast" at SF=0.001, but the Table 3 TOTAL row (3724 ms at SF=1 vs 2327 us at SF=0.001) gives a per-tuple ratio of about 1.6.
- p. 6 Section 3.2
MonetDB/MIL then becomes almost twice as fast.
- p. 5 Table 3 TOTAL row
3724
- p. 5 Table 3 totals
3724 2327
Only the authors can say what is right here.
Judge's note: Page 5 image, Table 3: the SF=1 ms column sums to 3724, matching its printed TOTAL. The SF=0.001 us column sums to 2590, not the printed 2327. Normalising for the 1000x data size, the speed-up is 1.60 using the printed total and 1.44 using the column sum. Neither reading is 'almost twice'. This is loose wording, and the authors should say which figure they meant. Separately, the 2327 total does not equal the 2590 sum of its column.
Second check: another model agreed
Report a problem with this finding
Wording Section 4.1.2 says "Order, TopN and Select return a Dataflow with the same shape as its input", but Figure 7 gives "Order(Table, List<OrdExp>, List<AggrExp>) : Table".
- p. 8 Section 4.1.2
Order, TopN and Select return a Dataflow with the same shape as its input.
- p. 9 Figure 7, last row
Order(Table, List<OrdExp>, List<AggrExp>) : Table
- p. 8 Section 4.1.2
Order, TopN and Select return a Dataflow with the
Only the authors can say what is right here.
Judge's note: Page 8 text and page 9 Figure 7 (crop C020-b) disagree on Order's input and output types. Figure 9 on page 11 applies Order to a Project(...), which is a Dataflow; that matches the text, not Figure 7. Only the authors can say which signature is intended.
Second check: another model agreed
Report a problem with this finding
Wording The example plans apply Select directly to "Table(lineitem)" (Section 4.1.1, Figure 9), whereas Figure 7 types "Select(Dataflow, Exp<bool>) : Dataflow" and "Table(ID) : Table", with Scan(Table) : Dataflow converting between them.
- p. 8 Section 4.1.1 example
Table(lineitem),
- p. 9 Figure 7
Select(Dataflow, Exp<bool>) : Dataflow
Judge's note: Pages 7 and 8 show the example, page 11 shows Figure 9, and page 9 shows Figure 7. Neither plan contains Scan, yet the text right after the example says 'The Scan operator retrieves data vector-at-a-time', and Figure 6 shows a SCAN stage. The example is called 'simplified', and Scan may be inserted implicitly, but the paper never says so. This is a minor notational inconsistency.
Second check: another model agreed
Report a problem with this finding
Wording In Figure 10 ("Query 1 performance w.r.t. vector-size"), the AthlonMP curve's minimum near 1K reads at about 0.64 s, whereas Tables 1 and 4 report MonetDB/X100 Q1 on AthlonMP at 0.50 s.
- p. 12 Figure 10, AthlonMP curve around vector size 1K
Figure 10: Query 1 performance w.r.t. vector-size
- p. 11 Table 4, Q1 X100 AthlonMP SF=1
0.50
Only the authors can say what is right here.
Judge's note: I measured crop C028-a on its log axis: 1 s is at about y=14 and 0.1 s at about y=181 (167 px per decade). The Itanium2 minimum at about y=100 reads 0.31 s, which matches Table 1/4. The AthlonMP minimum at about y=46 reads about 0.64 s. A value of 0.50 s would sit at about y=64, roughly 18 px lower than the plotted curve. The experiment may have run under different conditions, so this is an author query.
Second check: another model agreed
Report a problem with this finding
Typo Section 3: "this query is CPU-bound because on all RDBMSs we tested." is ungrammatical (stray 'because').
- p. 3 Section 3, first paragraph
this query is CPU-bound because on all RDBMSs we tested
Judge's note: The page 3 image shows the sentence exactly as quoted. 'because' has no clause to govern. A likely fix is 'this query is CPU-bound on all RDBMSs we tested.'
Second check: none (judge only)
Report a problem with this finding
Typo Missing full stop: "which instructions (or expressions) are independent Therefore, compiler optimizations".
- p. 3 Section 2
which instructions (or expressions) are independent Therefore, compiler
Judge's note: The page 3 image confirms there is no period after 'independent' before 'Therefore', so this is not a text-layer artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling "embarrasingly parallel" should be "embarrassingly parallel".
- p. 5 Section 3.1
“embarrasingly parallel”
Judge's note: The page 5 image and the C010 crop both show 'embarrasingly'.
Second check: none (judge only)
Report a problem with this finding
Typo Section 3.2 prints "performs the aggregations on the remaining 5.9M million tuples", which states the magnitude twice.
- p. 6 Section 3.2, right column
remaining 5.9M million tuples
Judge's note: The page 6 image shows '5.9M million tuples' in the right column. This should read '5.9M tuples' or '5.9 million tuples'.
Second check: none (judge only)
Report a problem with this finding
Typo The Conclusion says "We will also continue our work on the ColumnDB buffer manager", but the buffer manager is called ColumnBM everywhere else (Section 4, Figure 5, Section 4.3).
- p. 13 Section 7, paragraph 5
ColumnDB buffer manager
- p. 7 Section 4
ColumnBM buffer manager is still under development
- p. 13 Section 7, paragraph 3
We will also continue our work on the ColumnDB buffer manager
- p. 7 Section 4
the ColumnBM buffer manager is still under development
Judge's note: Page 13 prints 'ColumnDB buffer manager'. Pages 7 and 10 print 'ColumnBM buffer manager' and 'ColumnBM I/O subsystem', and Figure 5 labels it ColumnBM. The same component is meant.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.2 misspells the distance as "Mahanalobis distance"; the correct spelling is Mahalanobis.
- p. 9 Section 4.2, right column
Mahanalobis distance
Judge's note: The page 9 image, right column, shows 'Mahanalobis'. This is a plain misspelling.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 7 prints "HashAggr(Dataflow, List<Exp<*>>, List<AggrExp>])" with an unmatched ']' bracket.
- p. 9 Figure 7
List<AggrExp>])
- p. 9 Figure 7
HashAggr(Dataflow, List<Exp<*>>, List<AggrExp>])
Judge's note: Crop C023-b shows the stray ']' before ')'. The sibling OrdAggr and DirectAggr lines have no such bracket.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.2 has "hand-coded implementation of TPC-H Query in Table 1", with the query number (1) missing.
- p. 9 Section 4.2, right column
hand-coded implementation of TPC-H Query in Ta-
Judge's note: Page 9 image, right column: 'TPC-H Query in Ta-ble 1'. Table 1 covers only Query 1, so the fix is evident.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6 misspells "separate" in "to dedicate a seperate process to each query operator".
- p. 12 Section 6, second paragraph
dedicate a seperate process
- p. 12 Section 6, paragraph 2
to dedicate a seperate process to each query operator
- p. 12 Section 6
processsing a vector of tuples
- p. 9 Section 4.2
Mahanalobis distance
Judge's note: The page 12 image shows 'seperate'. This cluster's notes also mention 'processsing' and 'Mahanalobis'; those are judged under C026 and C022.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6 misspells "processing" with a triple s: "(i.e. processsing a vector of tuples".
- p. 12 Section 6, second paragraph
processsing a vector of tuples
- p. 12
(i.e. processsing a vector of tuples
Judge's note: The page 12 image, left column, shows 'processsing'.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6 repeats an adverb: "the possibility to dynamically remap NSM chunks into vertical chunks dynamically".
- p. 12 Section 6, right column top
to dynami-cally remap NSM chunks into vertical chunks dynam-ically
- p. 12 Section 6, paragraph 3 (continues into right column)
the possibility to dynamically remap NSM chunks into vertical chunks dynamically
Judge's note: The page 12 image, top of the right column (crop C028-a also shows it), prints 'dynami-cally ... dynam-ically' in one clause.
Second check: none (judge only)