Re: Nearest Common Ancestor Report (XDb1's $1000 Challenge)

From: Neo <>
Date: 9 Jun 2004 10:55:50 -0700
Message-ID: <>

> How does it scale? Hugo has posted (and admitted) that
> his model seems to be exponential with the number of
> records in the hierarchy (not surpising to me, since I
> know a tad about the innards of the relational implementations
> and query processing).

See below measurements for a Larger Report (276,620 result rows) created from a 400 Goat Hierarchy (10 generations x 40 goats/gen)

Solution Time(ms) Platform Notes
------------- -------- ----------------- ----------------------------
RM#5 SqlSrvr7 105 min 500 Mhz Srvr, NT Avg of 2, Not normalized
XDb1 4.5.10    44 min  500 Mhz Srvr, NT  Avg of 2, Not normalized
XDb1 4.5.10    57 min  450 Mhz PC, 98    1 run, Normalized to symbols
XDb1 4.5.10   195 min  233 Mhz PocketPC  1 run, Normalized to symbols

Note: If one would like to verify or provide additional measurements, the SQL Server scripts are available from website.

XDb1's exe is 540 KB. The database to hold the above 400 goats can be compacted to under 40 KB. The compacted db is fully functional expect no further data can be added, without resizing the db. The exe and db would fit on a low-density floppy disk. XDb1's memory useage during report generation according to Window's Task Manager was a steady 5,268 KB. XDb1's memory requirements do not grow with number of things in hierarchy. Besides inconsequential variables and an adjustable buffer (0-64KB) to avoid writting to disk as frequently, XDb1's algorithm only requires 4 x the hierarchy depth worth of memory (ie 40 integers for the above report). The report is written to a 1,277 KB text file on the HD.

With Sql Server, for the first run, I started with 10 MB db. At the end of the report generation, the db had grown to 69 MB. For the second run, I started with a 100 MB db. At the end of the run, it had grown to 150 MB. Shrinking the db brought it down to 40 MB. Truncating logs brought it down to 20 MB. Dropping the report table (T_NCancestors) and intermediate report table (T_Ancestor) brought it down to 8.18 MB. According to Task Manager, Sql Server's initial memory useage started at 25,480 MB and was continoulsy growing, however I only monitored for a short time. Received on Wed Jun 09 2004 - 19:55:50 CEST

Original text of this message