List:General Discussion« Previous MessageNext Message »
From:Mike Spreitzer Date:June 20 2009 10:44pm
Subject:Re: how to efficiently query for the next in MySQL Community Edition 5.1.34?
View as plain text  
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> 
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 <peter.brawley@stripped> 
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

 

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