tag:blogger.com,1999:blog-15861274.post116899419612369997..comments2017-02-21T12:39:54.044+00:00Comments on Oracle WTF: Performance Tuning and The Big OWilliam Robertsonhttp://www.blogger.com/profile/06976436975493102341noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-15861274.post-37378327828191893862010-06-22T19:52:51.611+01:002010-06-22T19:52:51.611+01:00actually, you can get roughly O(m+n), which is bet...actually, you can get roughly O(m+n), which is better than O(m*log(n)) by using a bucket system, or a hashing system with a sufficiently good hashing algorithm.sidewinderx2http://www.blogger.com/profile/17067287105028138859noreply@blogger.comtag:blogger.com,1999:blog-15861274.post-89772606577024721552007-04-12T17:07:00.000+01:002007-04-12T17:07:00.000+01:00Raymond is absolutely correct, a binary search wou...Raymond is absolutely correct, a binary search would yield a Log2(n) cost for each iteration.<BR/><BR/>The problem is that the original poster was given the problem by some pompous git who mistakenly thinks he knows a bit about Oracle.<BR/><BR/>Since Oracle does not (to my knowlege) employ a binary search, I leapt to the (apparently correct) assumption that the poster's mentor thinks b-Tree indexes are Binary-Tree, not Balanced-Tree.<BR/><BR/>The post was a tangled web of lies, half-truths, and unfounded assumptions. But for all that it had a kernal of an interesting problem that - if expressed properly - would have made for an interesting post rather than a painful one.Rosshttp://www.blogger.com/profile/04150159731064412110noreply@blogger.comtag:blogger.com,1999:blog-15861274.post-1170861810246204282007-02-07T15:23:00.000+00:002007-02-07T15:23:00.000+00:00One has to check for each record of table 2 whethe...One has to check for each record of table 2 whether or not it is in table 1.<BR/>For an array of numbers (of m numbers) that are sorted, finding out whether another number is in that array or not, the best algorithm uses o(log2(m)) time. (without using another index or anything.)<BR/><BR/>The algorithm works as following: look at the middle of the array. If the number to search for is bigger than than the number in the array, then repeat this process with the upper half of the array, otherwise with the lower half.<BR/><BR/>This gives us the required 0(n*log2(m)) limitation.Raymond Martensnoreply@blogger.comtag:blogger.com,1999:blog-15861274.post-1169076976914687502007-01-17T23:36:00.000+00:002007-01-17T23:36:00.000+00:00I thought that too, but apparently it is semi-real...I thought that too, but apparently it is semi-real. When I asked, the poster said:<BR/><BR/><I>"It IS a real world problem. The person who asked me to solve this worked for a telephone company and this was an actual problem he had to solve."</I>William Robertsonhttp://www.blogger.com/profile/06976436975493102341noreply@blogger.comtag:blogger.com,1999:blog-15861274.post-1169029468731417132007-01-17T10:24:00.000+00:002007-01-17T10:24:00.000+00:00It's clearly a homework assignment, so why bother ...It's clearly a homework assignment, so why bother answering.<BR/><BR/>If you where to bother anyway, there is really no point in the question, since it assumes that the database will use a specific algorithm (or class of algorithms) given even a so simple query. But the database doesn't.<BR/><BR/>Anyway, if we know the constant cardinality of both tables, almost any algorithm will be O(1) (ie. constant time), which is good but useless information in this case.Anonymousnoreply@blogger.com