Fetching words, definitions... and linked words from a many-to-many in a single query

[bugboy]

I'm a beginner at this and am confused...

I have three tables:

1. words / wordpk, word
2. definitions / definitionspk and definition
3. associations / wordpk, definitionspk

'words' holds words, 'definition' holds definitions for the words and 'associations' holds the pk associations between words and definitions because words can have many related definitions and definitions can many related words... many to many.

I'm trying to figure out a query that when run against a word will not only return that words definition but also return all the other words from the same word table that are also associated with that definition.

To reiterate: i want to find the definition for a given word from the words table (easy) but with the same query i also want returned all the other words associated with the found definition.

Thanks!

bugboy

[pbmods]

Heya, Bugboy. Welcome to TSDN!

Changed thread title to better describe the problem (did you know that threads whose titles do not follow the Posting Guidelines actually get FEWER responses?).

You can't get both sets of information in the same query, because the subsequent rows are dependent on the first row (or rows, in the case of multiple definitions), which implies at least two queries.

Your best bet would really be to run two queries: One to fetch the word and all definitions that match its id, then a second query to fetch all words that match at least one of the definition ids.

For the second query, the MySQL IN keyword will be your friend. Remember to put your definition ids in sorted order so that MySQL can use a binary search on your IN subclause.

[bugboy]

Thanks!

Is it considered wastefull to run two queries? would it use less resources to make 'word1, word2 etc..' columns of associated words in the definitions table? I know this would be duplicating the words and break the normalization but would it still be more efficent use of resources than two queries?

Does MySQL automatically use a binary search algorithm on sorted columns?
That's cool!

BugBoy

[pbmods]

Heya, BugBoy.

The problem with doing it in one query is that you'd have to either know how many words are linked to the definitions (because for each linked word you'd have to JOIN the links table against the result set), or you'd have a *lot* of data duplication.

The only way to reliably do it in one query would require the use of a subquery anyway, so you wouldn't be saving a whole lot:

SELECT
        `words`.*,
        `definitions`.*,
        IF
        (
            `wordid` = '{$wordid}',
            1,
 
        )
            AS `match`
    FROM
    (
            `definitions`
        LEFT JOIN
            `links`
                USING
                    (`definitionid`)
        LEFT JOIN
            `words`
                USING
                    (`wordid`)
    )
    WHERE
        `definitions`.`definitionid`
            IN
            (
                SELECT
                    DISTINCT
                        `definitionid`
                    FROM
                        `links`
                    WHERE
                        `wordid` = '{$wordid}'
                    GROUP BY
                        `definitionid`
                    ORDER BY
                        `definitionid` ASC
            )
    ORDER BY
        `match` DESC,
        `wordid` ASC
 

Adding the `match` field will put your 'target' word at the top of the result set; otherwise you'd have to run through your results on the PHP side and compare `wordid`s.

[bugboy]

That's awesome pbmods! Thanks for your help! This code is quite beyond my current ability so i've been studying it trying to figure out what you've done and have a couple questions if/when you have the time.

1. In lines 7,8 (lines 3,4 below) you add a 1,0 after the wordid.. what are these for? Oh.. i just figured out that it sets the "MATCH" number.. how do you get the matched wordID to be 1 and the unmatched wordID to be 0? I can't see where you put them together...
[PHP]
(
`wordid` = '{$wordid}',
1,
0
)[/PHP]

2. in line 20 you use "USING" in the LEFT JOIN. Is this instead of "ON" ..and does it do something different than "ON"? (i can't find "USING" in any of my books.)

3. I've played around trying to alter the code so that i don't need to know the wordID first.. only the word it's self... with no luck. Is it possible?

Thank!
BugBoy

[bugboy]

UPDATE:

well i quickly figured out how to get the word instead of wordID duh..

Thanks again for your help.
BugBoy

[pbmods]

Heya, BugBoy.

1. In lines 7,8 (lines 3,4 below) you add a 1,0 after the wordid.. what are these for? Oh.. i just figured out that it sets the "MATCH" number.. how do you get the matched wordID to be 1 and the unmatched wordID to be 0? I can't see where you put them together...
[PHP]
(
`wordid` = '{$wordid}',
1,
0
)[/PHP]

For this to make sense, you also need to include line 6:

IF
(
    `wordid` = '{$wordid}',
    1,
 
)
 

The IF function takes a conditional as its first parameter and returns the second parameter if true, or the third parameter if false. In other words, if `wordid` matches the target, `match` will be 1. Otherwise, `match` will be 0.

2. in line 20 you use "USING" in the LEFT JOIN. Is this instead of "ON" ..and does it do something different than "ON"? (i can't find "USING" in any of my books.)

USING(`field`)
 

is more or less just an alias for:

ON
(
    `table1`.`field` = `table2`.`field`
)
 

It only works in the context of a JOIN clause. Have a look here, down by join_condition:
http://dev.mysql.com/doc/refman/5.1/en/join.html

3. I've played around trying to alter the code so that i don't need to know the wordID first.. only the word it's self... with no luck. Is it possible?

To do that, you merely need to change the two references to '{$wordid}' to whatever variable holds the word itself, and then change the matching `wordid` references to `wordname` or whatever is written on the field's birth certificate.

For best results, you'll also want to make sure that your `words` table has an index on the word name field:

ALTER
    TABLE
        `words`
    ADD
        UNIQUE
        KEY
            (`wordname`);
 

In order for the above query to work, of course, you can't have any duplicate words in your `words` table.

[bugboy]

Thanks for you help Pbmods! it works great!

[pbmods]

Heya, BugBoy.

Glad to hear you got it working! Good luck with your project, and if you ever need anything, post back anytime :)

[bugboy]

Ok Now i'm trying to figure out why it's so slow. I've started adding records and it's getting slower and slower. I only have 6000 words and the query takes 25 seconds! (Every column queried is indexed.)

Am i doing something wrong? or is it that i have a slow server? (shared hosting at godaddy)

Surely a many to many with only 6000 words and 6000 definitions with 8000 cross links is small?.. i need to get into the millions eventually..

[PHP]SELECT `def`.`defID` , `def`.`title` , IF( `word` = 'test', 1, 0 ) AS `MATCH`
FROM (
`def`
LEFT JOIN `links`
USING ( `defID` )
LEFT JOIN `words`
USING ( `wordID` )
)
WHERE `def`.`defID`
IN (

SELECT DISTINCT `defID`
FROM `links`
WHERE `word` = 'test'
GROUP BY `defID`
ORDER BY `defID` ASC
)
ORDER BY `MATCH` DESC , `wordid` ASC [/PHP]

Thanks for your advice!

[pbmods]

Heya BugBoy.

What does this outupt:

EXPLAIN SELECT `def`.`defID` , `def`.`title` , IF( `word` = 'test', 1, 0 ) AS `MATCH`
FROM (
`def`
LEFT JOIN `links`
USING ( `defID` )
LEFT JOIN `words`
USING ( `wordID` )
)
WHERE `def`.`defID`
IN (
 
SELECT DISTINCT `defID`
FROM `links`
WHERE `word` = 'test'
GROUP BY `defID`
ORDER BY `defID` ASC
)
ORDER BY `MATCH` DESC , `wordid` ASC
 

[bugboy]

Here sorry it's not formatted very clearly... "qidb" is the database name.

id select_type table type possible_keys key key_len ref rows Extra

1 PRIMARY defs ALL NULL NULL NULL NULL 6614 Using temporary; Using filesort

1 PRIMARY links ref defID defID 4 qidb.defs.defID 1

1 PRIMARY words eq_ref PRIMARY PRIMARY 4 qidb.links.wordID 1 Using where

2 DEPENDENT SUBQUERY links index NULL defID 4 NULL 6606 Using where; Using index

[bugboy]

Ok.. i've just been reading here:

http://dev.mysql.com/doc/refman/5.0/en/explain.html

...and it looks like the 'type' 'ALL' is bad.. but every column in the table is indexed!!... i don't get why it wouldn't just use an indexed colunm.. maybe i don't get it...

It looks to me that i need to some how get it to use different indexed columns than what it's using now.. they sure don't make it easy! i think that's why i'm so fascinated with sql. ha!

[pbmods]

Heya, BugBoy.

Your subquery is selecting all definitions in the `links` table. Since every definition probably has at least one matching term (I suppose deleting a couple of links might have resulted in a few orphans), MySQL won't bother to use the index, since it knows that it will need to fetch all (or mostly all) of the definitions anyway.

The problem you're having is probably caused by performing a join on a large data set.

My recommendation would be to run two queries. The first query would fetch all words that match (in this case) 'test'. Because you're matching against a unique key, there should be very few matching rows, and your query should execute very quickly.

For the non-matching words, add a LIMIT clause to your subquery. You don't really need to fetch all 6000 words each time, do you?

If you want to be able to sort by the number of links, my recommendation would be to create a table to "index" this information, and then run a periodic script or MySQL event to automatically update it once per interval.

[bugboy]

Thanks pbmods!

My recommendation would be to run two queries. The first query would fetch all words that match (in this case) 'test'. Because you're matching against a unique key, there should be very few matching rows, and your query should execute very quickly.

Do you mean i should search my 'words' table first to get the wordID that matches my word, then use it to make more specific searches on 'links' and 'def'?

I thought maybe if i had my wordID then i could just search my links table for matches and not even need the def table.. but my subquery doesn't work because the wordID matches several definitions.. so it gives me the error:

"ERROR #1242 - Subquery returns more than 1 row"

SELECT wordID FROM links where defid = (select defid from links where wordid = '67')

For the non-matching words, add a LIMIT clause to your subquery. You don't really need to fetch all 6000 words each time, do you?

nope i don't need all 6000 words. Only the ones that match the same defID as my word. when you say fetch all 6000, do mean that a db can narrow in on only a few records in a column without reading (fetching) all of them? is this what an index allows?

pbmods, sorry, i'm feeling dumb here i'm not sure i get it. I think maybe i just don't understand how db's think (yet ), I must be missing some base principals ...i do really appreciate your help.