From: Peter Brawley Date: June 20 2009 7:59pm Subject: Re: how to efficiently query for the next in MySQL Community Edition 5.1.34? List-Archive: http://lists.mysql.com/mysql/217925 Message-Id: <4A3D3F95.4050602@earthlink.net> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------080205040602020103080708" --------------080205040602020103080708 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit >I do not follow why you suggested a join to get the associated S, >that can be done in the original query (and I did NOT say a given >integer I is associated with only one string S): A Group By query returns arbitrary values for a column which (i) does not Group By, (ii) does not aggregate, and (iii) does not have a 1:1 relationship with the grouping expression. PB ----- Mike Spreitzer wrote: > > Ah, yes, the MIN should be very helpful. Can I expect that ordering > the storage by (S, I) or having an (S, I) index will make that MIN > take O(1) time, for both MyISAM and InnoDB? > > I do not follow why you suggested a join to get the associated S, that > can be done in the original query (and I did NOT say a given integer I > is associated with only one string S): > > SELECT a.s, a.i, MIN(b.i) AS j > FROM t AS a > JOIN t AS b ON b.i > a.i AND a.s = b.s > GROUP BY a.i > > Thanks, > Mike Spreitzer > > > > *Peter Brawley * > > 06/20/09 12:39 PM > Please respond to > peter.brawley@stripped > > > > To > Mike Spreitzer/Watson/IBM@IBMUS > cc > mysql@stripped > Subject > Re: how to efficiently query for the next in MySQL Community Edition > 5.1.34? > > > > > > > > > > Mike, > >Yes, for each (S, I) pair the goal is to efficiently find the next > largest > >integer associated with S in T. For the highest integer I associated > with > >S in T, there is no next larger. > Here's a more efficient query for the next i values with matching s > values: > > SELECT a.i, MIN(b.i) AS j > FROM t AS a > JOIN t AS b ON b.i > a.i AND a.s = b.s > GROUP BY a.i > > To fetch the matching s values, join the above to the original table: > > SELECT n.i, t.s, n.j > FROM ( > SELECT a.i, MIN(b.i) AS j > FROM t AS a > JOIN t AS b ON b.i > a.i AND a.s = b.s > GROUP BY a.i > ) AS n JOIN t USING (i); > > PB > > ----- > > Mike Spreitzer wrote: > Yes, for each (S, I) pair the goal is to efficiently find the next > largest > integer associated with S in T. For the highest integer I associated > with > S in T, there is no next larger. > > Thanks, > Mike Spreitzer > > > > > Peter Brawley __ > > 06/20/09 08:56 AM > Please respond to > _peter.brawley@stripped > > > To > Mike Spreitzer/Watson/IBM@IBMUS > cc > _mysql@stripped > Subject > Re: how to efficiently query for the next in MySQL Community Edition > 5.1.34? > > > > > > > Mike > > > J holding the next integer that T has for S > > > You mean for each i, the next value of i with that s? > > > (U having no row for the last integer of each string). > > > I do not understand that at all. > > PB > > > Mike Spreitzer wrote: > Suppose I have a table T with two column, S holding strings (say, > VARCHAR(200)) and I holding integers. No row appears twice. A given > string appears many times, on average about 100 times. Suppose I have > millions of rows. I want to make a table U holding those same columns > plus one more, J holding the next integer that T has for S (U having no > row for the last integer of each string). I could index T on (S,I) and > write this query as > > select t1.*, t2.I as J from T as t1, T as t2 > where t1.S=t2.S and t1.I < t2.I > and not exists (select * from T as t12 where t12.S=t1.S and t1.I < t12.I > and t12.I < t2.I) > > but the query planner says this is quite expensive to run: it will > enumerate all of T as t1, do a nested enumeration of all t2's entries for > S=t1.S, and inside that do a further nested enumeration of t12's entries > for S=t1.S --- costing about 10,000 times the size of T. There has to be > a better way! > > Thanks, > Mike Spreitzer > > > > > > No virus found in this incoming message. > Checked by AVG - _www.avg.com_ > Version: 8.5.364 / Virus Database: 270.12.80/2187 - Release Date: > 06/19/09 > 06:53:00 > > > > > > ------------------------------------------------------------------------ > > > No virus found in this incoming message. > Checked by AVG - _www.avg.com_ > Version: 8.5.364 / Virus Database: 270.12.81/2189 - Release Date: > 06/20/09 06:15:00 > > > ------------------------------------------------------------------------ > > > No virus found in this incoming message. > Checked by AVG - www.avg.com > Version: 8.5.364 / Virus Database: 270.12.81/2189 - Release Date: 06/20/09 06:15:00 > > --------------080205040602020103080708--