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

Hugo Kornelis wrote:

Thanks for the additional info, Hugo.

Some comments and some snippage below :)

> On Mon, 24 May 2004 02:33:10 GMT, Nick Landsberg wrote:
>
> Hi Nick,
>
> (snip)
>

>>Thanks Hugo,
>>
>>The reason why I posed the query is not so much to
>>make work for you, but to get a flavor of how the
>>two technolgies compare /as they are now/.

This would be underpowered for a commercial setup from a CPU standpoint and from a memory standpoint. As a reference point, what I use at work is a 12 CPU Sparc _at_ 1.28 GHz with 64 GB of memory. (But the 12 CPU's don't help much with query analysis since that has to be single threaded. They DO help on other respects). No, we don't run SQL-server.

> * Two 40GB 7200 rpm IDE Harddisks. The LOG file for my test DB is on one
> of them. The DATA file for my test DB, plus the DATA and LOG file for
> tempdb (used by SQL Server to store intermediate result sets) is on the
> other harddisk. My Windows page file is on that hard disk as well (though
> on another partition).

Good partitioning. But with only 256 MB RAM you were beating the living spit out of the disks, which may explain some of the exponential behaviour you noted below. Those disks have an average latency of about 6-8 ms. per random I/O. I have no idea whether or not SQL-server would write to both data and log files for tempdb at the same time, but this may have increased the latency with many (almost) random seeks.

> * I made sure that both the test database (DATA and LOG!!) and tempdb were
> large enough to hold all intermittant data and the result. SQL Server will
> automatically allocate extra disk space if a database needs more room, but
> repeatedly allocating extra disk space is a performance killer (for the
> first execution only!!), so I decided to preallocate the space.

OK

> * For all tests, I first recreated the tables and procedure, filled the
> tables with the original data and then added extra rows in the things and
> hierarchies tables.

This eliminates the effects of caching, but is also a worst case. From a performance paranoids perspective this is "a good thing." :)

> * The results below show: number of rows in the things and hierarchies
> table (indicating input volume), number of rows in ancestors and
> NCancestor tables (indicating size of intermediate and output table) and
> time elapsed for one execution of the stored procedure.
> * I did some minor tweaking to the procedure after carrying out these
> tests but before posting Neo the code (see other message). I think that
> the improvement is only marginal - at least not enough to warrant
> repeating all tests again.
>
>
> Here are the results I gathered:
>
> things hierarchies ancestors NCancestor elapsed
> ----------- ----------- ----------- ----------- --------------
> 18 31 81 153 00:00:00:017
> 108 210 1307 5778 00:00:00:513
> 208 505 4566 21528 00:00:02:407
> 408 1101 16938 83028 00:00:14:377
> 608 1700 36619 184528 00:00:51:877
> 1008 2900 94318 507528 00:05:03:577
>
>
> And two larger tests in a very a-typical setup (running SQL Server in
> single-user mode - normally only used for maintenance, but apparantly also
> quicker)
>
> things hierarchies ancestors NCancestor elapsed
> ----------- ----------- ----------- ----------- --------------
> 1000 2883 94255 499500 00:04:00:250
> 2500 7381 464258 3123750 01:02:13:580
>
> As you can see, elapsed time grows exponentially as the size of the input
> increases.

Yes, it does. I am still wondering tho, about how much of that elapsed time was disk I/O latency vs. CPU time. It depends on the size of the in-memory cache (which I said above was small for commercial implementations) and the effectiveness of the caching algorithm, usually LRU.

>
> Can the above performance be improved upon? Yes, of course. If I had
> unlimited money to spare, I'd start with the following setup:

Wouldn't we *ALL* love to have unlimited money. :)

>
> * Have SQL Server run on a dedicated server. Enable only the services that
> SQL Server needs, shut down everything else.

Typical commercial installations of any DBMS do this.

> * Fastest processor currently available. Though SQL Server can use
> multiple processors, I don't think they would help for this particular
> query (but if money is not an issue, I'd still try, just to be sure).

That depends on the implementation, but I believe you're right that it probably would not help for this particular query.

> * As much RAM as the server will hold. Over 2GB is only used by SQL Server
> Enterprise Edition, so get a license for that version as well.

See comment about 64 GB RAM above. I'm spoiled.

> * At least five seperate I/O devices: two stripe sets (for test DB Data
> and tempdb Data) (the more physical disks in the stripe set, the better),
> and three non-striped disks (one for test DB Log, one for tempdb Log and
> one for operating system, including pagefile).

Absolutely! A RAID array with non-volatile cache might help, assuming that you're I/O limited rather than CPU limited. If you're CPU limited this might not help.

> * I'd hire a tuning expert. Though I do know a few tricks, I'm definitely
> not an expert on fine-tuning SQL Server.

My experience has been that fine tuning gets you maybe 20-25% improvement at best. (Unless you've really screwed up in the beginning.) Your exponential response with size of data will stay exponential. Sorry.

> * And I'd buy Joe Celko's latest book on trees and hierarchies in SQL. His
> alternative approach I hinted at in an earlier message will not do
> unfortunately - I expect it to be blindingly fast, but it can only handle
> hierarchies where each thing has at most one parent. But maybe he's got
> some other neat tricks in his book that I might want to steal.

In this business, stealing from a respected author is considered an honorable thing to do. :)

>
> Another thing I'd consider is moving some work from the stored procedure
> to an insert trigger. I didn't do this for the challenge, of course, but
> if this were to become a real production system, I'd definitely try to
> find out if insert/update/delete performance for typical daily data entry
> tasks would be acceptable if I move some preparations for this report to
> the trigger.

This is what I'm most concerned about the difference in the two approaches. From experience (and many, many tests), I can predict what the performance of single-record inserts, updates, deletes, etc. will take for any given schema within tolerable limits given an RDBMS. Generally speaking, fine-tuning report generation forces you to pay a penalty when doing individual transactions and vice-versa. (But we all know that, don't we? :)

>
>
> But I'm also sure that there's no way that I would ever get this procedure
> to perform adequately (unless I'd find a completely different approach in
> Celko's book). All performance gains that better hardware can buy are
> linear; the performance hit for extra input data is exponential. That
> means that there's no way to keep the performance aceptable as the data
> continues to grow.

I wouldn't be too sure that the gains from better hardware are just linear. There are multiple factors involved here. If you are limited by memory (as you are), then, by necessity, you increase the I/O rates to disk, which limit you even further. You don't have gobs of money to spend on RAID arrays and memory in your position. If possible, a breakdown of those elapsed time numbers as to pysical I/O vs. CPU time would let someone extrapolate.

>
> Is this a surprise to me? No, it isn't. Frankly, I've never considered a
> relational database as a good tool for storing and traversing trees. There
> are many other tools out there more suited for that task.
>
> I never entered this discussion to prove that the relational model is well
> suited for tree-structures, because frankly, I think it isn't.I only
> entered this discussion because Neo set a challenge and I decided to take
> it on - and succeeded.

[SNIP]
>
>
> Thanks, Nick!
>
> Best, Hugo

And thanks for your replies!

-- 
"It is impossible to make anything foolproof
because fools are so ingenious"
  - A. Bloch