From: Peter Brawley Date: June 20 2009 10:56pm Subject: Re: how to efficiently query for the next in MySQL Community Edition 5.1.34? List-Archive: http://lists.mysql.com/mysql/217927 Message-Id: <4A3D690A.6070206@earthlink.net> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------070602020405030505030801" --------------070602020405030505030801 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Mike, >Oops, I did not read your original query closely enough. >You actually meant to group by S, not I, right? No, it's a query for next i values with matching s values, so it groups by i. >I can get S, I, and J with >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.s For this dataset ... drop table if exists t; create table t(i int,s char(1)); insert into t values(1,'a'),(2,'b'),(3,'c'),(4,'a'),(5,'a'),(6,'d'),(7,'e'),(8,'d'); are these the correct next values of i? +------+------+ | i | j | +------+------+ | 1 | 4 | | 4 | 5 | | 6 | 8 | +------+------+ Your query doesn't return that. PB ----- Mike Spreitzer wrote: > > Oops, I did not read your original query closely enough. You actually > meant to group by S, not I, right? I can get S, I, and J with > > > 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.s > > Right? > > My integers are not unique; a given integer can be paired with several > strings. > > Thanks, > Mike Spreitzer > SMTP: mspreitz@stripped, Lotus Notes: Mike Spreitzer/Watson/IBM > Office phone: +1-914-784-6424 (IBM T/L 863-) > AOL Instant Messaging: M1k3Sprtzr > > > *Peter Brawley * > > 06/20/09 03:59 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? > > > > > > > > > > >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 > > > ------------------------------------------------------------------------ > > > 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 > > --------------070602020405030505030801--