Skip to content

"Mitilini" (15.01.2016)

Choose a tag to compare

@mathiasrw mathiasrw released this 15 Jan 20:03
· 1597 commits to develop since this release
  • Fix: SELECT can use functions from GROUP BY list
  • Fix: Bug in NUMERIC type conversion
  • Fix: Bug with primary key after DELETE all
  • Fix: Added String() to UPPER() and LOWER() functions
  • Fix: COLLATE and UNIQUE KEY words for CREATE TABLE (see issue #452)
  • Fix: Added params to SEARCH WHERE function
  • Fix: Bug with MATRIX modifier
  • Fix: Bug with undefined content variable with IN operation (issue #501)
  • Fix: Bug with wrong realizaion of REPLACE INTO (issue #505)
  • Fix: >> for binary operation and graphs collisions
  • Fix: Added DEFAULT clause to INSERT SELECT statement
  • Fix: browser tests, IndexedDB tests, DROP TABLE callback for external engines
  • Added: functions CEIL/CEILING and FLOOR
  • Added: CONCAT to the list of standard functions
  • Added: PIVOT and UNPIVOT functionality
  • Added: REPLACE INTO command (see issue #467)
  • Added: ON UPDATE - column constraint
  • Added: TRIGGERs
  • Added: >>,<<,&,| - binary operations
  • Added: || - string concatenation (issue #514)
  • Added: GLOB operator
  • Added: SELECT * FROM INSERTED (for T-SQL like triggers)
  • Added: expression NOT NULL operator (issue #507)
  • Added and Fix: REINDEX and fixed CREATE INDEX (issues #509, #470)
  • Added: DATETIME2 type for compatibility with T-SQL
  • Added: DATEADD() and DATEDIFF() functions in T-SQL style
  • Added: CONCAT_WS() function
  • Added: OF() selector for SEARCH statement

sqllogictest, January 2016

AlaSQL v0.2.2-pre-develop+151231.53429 ran the sqllogictest suite two weeks before the 0.2.2 release.

  • 5,945,362 tests. 5,200,319 passing (87.47%). Failed and skipped both count as not passing.
  • Run time - 5.9 hours.
  • 621 of the 622 test files. select5.test is left out, as it is "taking days to complete".

Focus on select5.test

  • 64 tables, 10 rows each. 732 queries, 12 for each join width from 4 to 64 tables.
  • Tables are listed with commas in FROM. The join conditions are in WHERE. Every query returns one row.
  • Started 2016-01-02T03:00:43Z on develop at db30da417.
  • Stopped by hand while step 783 of 1,436 was running, after 14.69 hours (52,889,906 ms).
  • The log is results/Details on select5.2016.test.md in the alasql-sqllogictest repo.

Median time for one query

Tables Median
4 33 ms
5 131 ms
6 701.5 ms
7 6,337 ms
8 67,331.5 ms
9 719,930 ms
10 7,495,922.5 ms (6 of 12 queries done)

Slowest single query - 9,005,743 ms (2.50 hours), 10 tables.

Each extra table multiplies the time by about ten. The last three steps are 10.63, 10.69 and 10.41.

Extrapolation

A join of $n$ tables builds $10^n$ row combinations and visits $n$ tables for each.

$$T(n) = c \cdot n \cdot 10^n \qquad\Rightarrow\qquad c = \frac{T(n)}{n \cdot 10^n}$$

At $n = 8$, $9$ and $10$ this gives $c$ = 84.16 ns, 79.99 ns and 74.96 ns. The last one is used.

All 732 queries, 12 for each width from 4 to 64

$$\sum_{n=4}^{64} 12 \cdot c \cdot n \cdot 10^n \;\approx\; 851.85 \cdot c \cdot 10^{64} \;\approx\; 6.4 \times 10^{59}\ \text{s}$$
  • That is $2.0 \times 10^{52}$ years (a year is 31,557,600 s).
  • The universe is $13.8 \times 10^9$ years old. The file needs $1.5 \times 10^{42}$ times that.
  • One 20-table query - $1.5 \times 10^{14}$ s (4.75 million years). One 25-table query - $1.9 \times 10^{19}$ s (43 times the age of the universe).
  • Check - from the 9-table median the model predicts 8,000 s for 10 tables. Measured - 7,496 s. The model runs 7% high per step.
  • Lower bound without the factor $n$, so $T(n) = k \cdot 10^n$ with $k$ = 749.59 ns - $1.0 \times 10^{59}$ s. Same conclusion.

UPDATE, November 2026 - the same suite ten years later (AlaSQL 4.21.0)

Same runner, same rules, same files (select5.test still excluded).

  • 5,323,624 of 5,945,362 passing (89.54%), up from 87.47%. AlaSQL itself gained 123,305 passing tests in ten years.
  • select4.test did not finish in 4 hours with the 2016 runner. It ran with the 2016 comparison rules and a 2-second limit per test instead. 983 of its queries hit the limit and count as failing. In 2016 AlaSQL crashed while setting up select4.test after 3 seconds, and the runner skipped the rest of the file.
  • In 2016 AlaSQL crashed while setting up 25 test files, and the runner then counted every remaining record in those files as not passing. In 19 of those files, the remaining records included 6,916 written for other databases (MS SQL Server statements and halt lines). 4.21.0 does not crash there, so the runner skips those records as it should. The line above counts them as failing, to match 2016.
  • The runner also compared values wrongly. It ignored the column type each test declares, and it sorted rowsort results as one joined string instead of value by value. Fixed on 29 October 2026.
  • Runner fixed, the 6,916 left out - 5,545,079 of 5,938,446 passing (93.38%). The runner fix alone is worth 221,455 tests.
  • select5.test is still left out.

select5.test on 4.21.0, Node.js 22, a 4-core cloud server (AMD EPYC 9575F), 12 queries per width, all answers right. Median time for one query

Tables Median
4 12.7 ms
5 25 ms
6 99 ms
7 728 ms
8 8.0 s
9 88.3 s

Still about ten times per extra table.

$$c = \frac{88.3\ \text{s}}{9 \cdot 10^9} = 9.81\ \text{ns} \qquad 851.85 \cdot c \cdot 10^{64} \approx 8.4 \times 10^{58}\ \text{s}$$
  • That is $2.6 \times 10^{51}$ years, or $1.9 \times 10^{41}$ times the age of the universe.
  • The 2016 build on the same machine - 37.9 s at 9 tables, $c$ = 4.21 ns, $3.6 \times 10^{58}$ s for the file.
  • 4.21.0 is 2.3 times slower than the 2016 build on this file. The gain since 2016 is hardware and Node.js.

UPDATE 2, November 2026 (AlaSQL 4.22.0)

  • Issue (#2910): b1 = a2, was not recognised as a join condition. Only t1.b1 = t2.a2 was. select5.test uses bare names in shuffled order, so all $10^n$ row combinations were built before WHERE filtered anything.
  • Fix (#2911): bare columns are now resolved to their tables, and the join order is chosen instead of taken from FROM. The table pinned by a constant goes first, then the first table in FROM order that a condition ties to the tables already placed.

select5.test on 4.22.0, same machine as the first UPDATE 1

  • Full test run of select5.test, setup included took 5.1 s (three runs of 5.13 s, 5.14 s, 5.46 s).
  • 732 of 732 answers confirmed correct.
  • Median time for one query, over the three runs: 1.4 ms at 4 tables, 1.9 ms at 9, 10.5 ms at 64.
  • The time no longer multiplies by ten per table, so the model above does not apply. The measured time is the number.
  • SQLite (bun:sqlite), same machine, same file - 0.44 s. AlaSQL is about 12 times slower.
  • In the suite runner, select5.test now passes all 1,436 tests in 2.5 s.

Suite on 4.22.0, now with select5.test - 5,547,165 of 5,939,882 passing (93.39%).