Wsrtjtyk

This question is a bit complicated to me, and I can't explain it in one sentence so the title may seem quite ambiguous.

I have 3 tables in my MySQL database, their structure is shown below:

1. word_list (5 million rows)

    +-----+--------+

    | wid | word   |

    +-----+--------+

    |   1 | foo    |

    |   2 | bar    |

    |   3 | hello  |

    +-----+--------+

2. paper_word_relation (10 million rows)

    +-----+-------+

    | pid | word  | 

    +-----+-------+

    |   1 |    1  | 

    |   1 |    2  | 

    |   1 |    3  | 

    |   2 |    1  | 

    |   2 |    3  | 

    +-----+-------+

3. paper_citation_relation (80K rows)

    +----------+--------+

    | pid_from | pid_to | 

    +----------+--------+

    |        1 |     2  | 

    |        1 |     3  | 

    |        1 |     4  |

    |        2 |     1  |

    |        2 |     3  |

    +----------+--------+

I want to find out how many papers contain word W, and cite the papers also contain word W.(for each word in the list)

I use two inner join to do this job but it seems extremely slow when the word is popular - above 50s (quite fast if the word is rarely used - below 0.1s), here is my code

    SELECT COUNT(*) FROM (

    SELECT a.pid_from, a.pid_to, b.word FROM paper_citation_relation AS a 

    INNER JOIN paper_word_relation AS b ON a.pid_from = b.pid

    INNER JOIN paper_word_relation AS c ON a.pid_to = c.pid

    WHERE b.word = 2 AND c.word = 2) AS d

How can I do this faster? Is my query not efficient enough or it's the problem about the amount of data?

I can only come up with one solution that I delete the words which occur less than 2 in the paper_word_relation table. (About 4 million words only occur once)

Thanks!

If you are only concerned with getting the Count, you should not be first getting the results into a Derived Table, and then Count the rows out. This may create unnecessary temporary tables storing lots of data in-memory. You can directly count the number of rows.

I also think that you need to count unique number of papers. Because of Many-to-Many relationships in paper_citation_relation table, duplicate rows may be coming for a single paper.

SELECT COUNT(DISTINCT a.pid_from) 

FROM paper_citation_relation AS a 

INNER JOIN paper_word_relation AS b ON a.pid_from = b.pid

INNER JOIN paper_word_relation AS c ON a.pid_to = c.pid

WHERE b.word = 2 AND c.word = 2

For performance, you will need following indexing:

• Composite Index on (pid_from, pid_to) in the paper_citation_relation table.


• Composite Index on (pid, word) in the paper_word_relation table.

We may also possibly optimize the query further by reducing one join and use conditional AND/OR based filtering in HAVING. You will need to benchmark it though.

SELECT COUNT(*) 

FROM (

      SELECT a.pid_from  

      FROM paper_citation_relation AS a 

      INNER JOIN paper_word_relation AS b 

        ON (a.pid_from = b.pid OR 

            a.pid_to = b.pid)  

      GROUP BY a.pid_from 

      HAVING SUM(a.pid_from = b.pid AND b.word = 2) AND 

             SUM(a.pid_to = b.pid AND b.word = 2)

     )

After the first 1:n join you get the same pid_to multiple times and your next join is no longer 1:n but n:m, creating a possibly huge intermediate result before the final DISTINCT. It's similar to a CROSS JOIN and it's getting worse for popular words, e.g. 10*10 vs. 1000*1000 rows.

You must remove the duplicates before the join, this should return the same number as @MadhurBhaiya's answer

SELECT Count(*) -- no more DISTINCT needed

FROM 

 (

    SELECT DISTINCT cr.pid_to -- reducing m to 1

    FROM paper_citation_relation AS cr

    JOIN paper_word_relation AS wr 

      ON cr.pid_from = wr.pid

    WHERE wr.word = 2

 ) AS dt

JOIN paper_word_relation AS wr

  ON dt.pid_to = wr.pid  -- 1:n join again

WHERE wr.word = 2

If you want to count the number of papers which have been cited you need to get a distinct list of pid (either pid_from or pid_to) from paper_citation_relation first and then join to the specific word.

SELECT Count(*)

FROM

( -- get a unique list of cited or citing papers

    SELECT pid_from AS pid -- citing

    FROM paper_citation_relation

    UNION -- DISTINCT by default

    SELECT pid_to          -- cited

    FROM paper_citation_relation 

) AS dt

JOIN paper_word_relation AS wr

  ON wr.pid = dt.pid

WHERE wr.word = 2 -- now check for the searched word

The number returned by this might be slightly higher (it counts a paper regardless if cited or citing).