List:General Discussion« Previous MessageNext Message »
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?
View as plain text  
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 <peter.brawley@stripped>*
>
> 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 **_<peter.brawley@stripped>_* 
> <mailto:peter.brawley@stripped>
>
> 06/20/09 12:39 PM
> Please respond to_
> __peter.brawley@stripped <mailto:peter.brawley@stripped>
>
> 	
> To
> 	Mike Spreitzer/Watson/IBM@IBMUS
> cc
> 	_mysql@stripped <mailto: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 _<peter.brawley@stripped>_ 
> <mailto:peter.brawley@stripped>
> 06/20/09 08:56 AM
> Please respond to_
> __peter.brawley@stripped <mailto:peter.brawley@stripped>
>
>
> To
> Mike Spreitzer/Watson/IBM@IBMUS
> cc_
> __mysql@stripped <mailto: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_ <http://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_ <http://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_ <http://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
>
>   

Thread
how to efficiently query for the next in MySQL Community Edition 5.1.34?Mike Spreitzer20 Jun
  • Re: how to efficiently query for the next in MySQL Community Edition5.1.34?Peter Brawley20 Jun
    • Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?Johnny Withers20 Jun
    • Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?Mike Spreitzer20 Jun
      • Re: how to efficiently query for the next in MySQL Community Edition5.1.34?Peter Brawley20 Jun
        • Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?Mike Spreitzer20 Jun
          • Re: how to efficiently query for the next in MySQL Community Edition5.1.34?Peter Brawley20 Jun
            • Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?Mike Spreitzer21 Jun
              • Re: how to efficiently query for the next in MySQL Community Edition5.1.34?Peter Brawley21 Jun
                • Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?Mike Spreitzer21 Jun
        • Anyone using LVM for backing up?Timothy Little22 Jun
          • Re: Anyone using LVM for backing up?Thomas A. McGonagle22 Jun
          • Re: Anyone using LVM for backing up?Jim Lyons23 Jun
          • Re: Anyone using LVM for backing up?David Sparks23 Jun
          • Re: Anyone using LVM for backing up?Baron Schwartz4 Jul