Znusgy Znusgy - 10 months ago 107
SQL Question

Painfully slow Postgres query using WHERE on many adjacent rows

I have the following psql table. It has roughly 2 billion rows in total.

id word lemma pos textid source
1 Stuffing stuff vvg 190568 AN
2 her her appge 190568 AN
3 key key nn1 190568 AN
4 into into ii 190568 AN
5 the the at 190568 AN
6 lock lock nn1 190568 AN
7 she she appge 190568 AN
8 pushed push vvd 190568 AN
9 her her appge 190568 AN
10 way way nn1 190568 AN
11 into into ii 190568 AN
12 the the appge 190568 AN
13 house house nn1 190568 AN
14 . . 190568 AN
15 She she appge 190568 AN
16 had have vhd 190568 AN
17 also also rr 190568 AN
18 cajoled cajole vvd 190568 AN
19 her her appge 190568 AN
20 way way nn1 190568 AN
21 into into ii 190568 AN
22 the the at 190568 AN
23 home home nn1 190568 AN
24 . . 190568 AN
.. ... ... .. ... ..


I would like to create the following table, which shows all "way"-constructions with the words side-by-side and some data from the columns "source", "lemma" and "pos".

source word word word lemma pos word word word word word lemma pos word word
AN lock she pushed push vvd her way into the house house nn1 . she
AN had also cajoled cajole vvd her way into the home home nn1 . A
AN tried to force force vvi her way into the palace palace nn1 , officials


Here you can see the code I use:

copy(
SELECT c1.source, c1.word, c2.word, c3.word, c4.word, c4.lemma, c4.pos, c5.word, c6.word, c7.word, c8.word, c9.word, c9.lemma, c9.pos, c10.word, c11.word

FROM

orderedflatcorpus AS c1, orderedflatcorpus AS c2, orderedflatcorpus AS c3, orderedflatcorpus AS c4, orderedflatcorpus AS c5, orderedflatcorpus AS c6, orderedflatcorpus AS c7, orderedflatcorpus AS c8, orderedflatcorpus AS c9, orderedflatcorpus AS c10, orderedflatcorpus AS c11

WHERE

c1.word LIKE '%' AND
c2.word LIKE '%' AND
c3.word LIKE '%' AND
c4.pos LIKE 'v%' AND
c5.pos = 'appge' AND
c6.lemma = 'way' AND
c7.pos LIKE 'i%' AND
c8.word = 'the' AND
c9.pos LIKE 'n%' AND
c10.word LIKE '%' AND
c11.word LIKE '%'

AND

c1.id + 1 = c2.id AND c1.id + 2 = c3.id AND c1.id + 3 = c4.id AND c1.id + 4 = c5.id AND c1.id + 5 = c6.id AND c1.id + 6 = c7.id AND c1.id + 7 = c8.id AND c1.id + 8 = c9.id AND c1.id + 9 = c10.id AND c1.id + 10 = c11.id

ORDER BY c1.id
)
TO
'/home/postgres/Results/OUTPUT.csv'
DELIMITER E'\t'
csv header;


The query takes almost 9 hours to execute for the two billion rows (the result has about 19,000 rows).

What could I do to improve performance?

The word, pos and lemma columns already have btree indices.

Should I stick to my code and simply use a more powerful server with more cores/a faster CPU and more RAM (mine has only 8 GBs of RAM, a mere 2 cores and 2.8 GHz) ? Or would you recommend a different, more efficient SQL query?

Thanks!

Answer Source

Step1:use a window function to obtain adjacent records, avoiding the painful self-join (12 tables is very close to the limit where geqo takes over):


copy(
WITH stuff AS (
    SELECT   c1.id , c1.source, c1.word
    , LEAD ( c1.word, 1) OVER (www) AS c2w
    , LEAD (c1.word, 2) OVER (www) AS c3w
    , LEAD ( c1.word, 3) OVER (www) AS c4w
    , LEAD (c1.lemma, 3) OVER (www) AS c4l
    , LEAD (c1.pos, 3) OVER (www) AS c4p
    , LEAD (c1.pos, 4) OVER (www) AS c5p
    , LEAD (c1.word, 4) OVER (www) AS c5w
    , LEAD (c1.word, 5) OVER (www) AS c6w
    , LEAD (c1.lemma, 5) OVER (www) AS c6l
    , LEAD (c1.word, 6) OVER (www) AS c7w
    , LEAD (c1.pos, 6) OVER (www) AS c7p
    , LEAD (c1.word, 7) OVER (www) AS c8w
    , LEAD (c1.word, 8) OVER (www) AS c9w
    , LEAD (c1.lemma, 8) OVER (www) AS c9l
    , LEAD (c1.pos, 8) OVER (www) AS c9p
    , LEAD (c1.word, 9) OVER (www) AS c10w
    , LEAD (c1.word, 10) OVER (www) AS c11w
    FROM orderedflatcorpus AS c1
    WINDOW www AS (ORDER BY id)
    )
SELECT id ,  source, word
    , c2w
    , c3w
    , c4w
    , c4l
    , c4p
    , c5w
    , c6w
    , c7w
    , c8w
    , c9w
    , c9l
    , c9p
    , c10w
    , c11w
FROM stuff
WHERE 1=1
AND c4p LIKE 'v%'
AND c5p = 'appge'
AND c6l = 'way'
AND c7p LIKE 'i%'
AND c8w = 'the'
AND c9p LIKE 'n%'
ORDER BY id
)
-- TO '/home/postgres/Results/OUTPUT.csv' DELIMITER E'\t' csv header;
TO '/tmp/OUTPUT2.csv' DELIMITER E'\t' csv header;

Step 2: [data model] The {word,lemma, pos} columns appear to be a low-cardinality group, you could squeeze them out into a separate token/lemma/pos-table:


    -- An index to speedup the unique extraction and final update
    -- (the index will be dropped automatically
    -- once the columns are dropped)
    CREATE INDEX ON tmp.orderedflatcorpus (word, lemma, pos );

    ANALYZE tmp.orderedflatcorpus;
    -- table containing the "squeezed out" domain
    CREATE TABLE tmp.words AS
     SELECT DISTINCT  word, lemma, pos
     FROM tmp.orderedflatcorpus
            ;
    ALTER TABLE tmp.words
     ADD COLUMN id SERIAL NOT NULL PRIMARY KEY;

    ALTER TABLE tmp.words
     ADD UNIQUE (word , lemma, pos );

    -- The original table needs an FK "link" to the new table
    ALTER TABLE tmp.orderedflatcorpus
      ADD column words_id INTEGER -- NOT NULL
      REFERENCES tmp.words(id)
      ;
    -- FK constraints are helped a lot by a supportive index.
    CREATE INDEX orderedflatcorpus_words_id_fk ON tmp.orderedflatcorpus (words_id)
     ;
    ANALYZE tmp.orderedflatcorpus;
    ANALYZE tmp.words;
    -- Initialize the FK column in the original table.
    --  we need NOT DISTINCT FROM here, since the joined
    --  columns could contain NULLs , which MUST compare equal.
    -- ------------------------------------------------------
    UPDATE tmp.orderedflatcorpus dst
       SET  words_id = src.id
      FROM tmp.words src
     WHERE src.word IS NOT DISTINCT FROM dst.word
       AND dst.lemma IS NOT DISTINCT FROM src.lemma
       AND dst.pos IS NOT DISTINCT FROM src.pos
            ;
    ALTER TABLE tmp.orderedflatcorpus
     DROP column word
     , DROP column lemma
     , DROP column pos
            ;

And the new query, with a JOIN to the words-table:


copy(
WITH stuff AS (
    SELECT   c1.id , c1.source, w.word
    , LEAD ( w.word, 1) OVER (www) AS c2w
    , LEAD (w.word, 2) OVER (www) AS c3w
    , LEAD ( w.word, 3) OVER (www) AS c4w
    , LEAD (w.lemma, 3) OVER (www) AS c4l
    , LEAD (w.pos, 3) OVER (www) AS c4p
    , LEAD (w.pos, 4) OVER (www) AS c5p
    , LEAD (w.word, 4) OVER (www) AS c5w
    , LEAD (w.word, 5) OVER (www) AS c6w
    , LEAD (w.lemma, 5) OVER (www) AS c6l
    , LEAD (w.word, 6) OVER (www) AS c7w
    , LEAD (w.pos, 6) OVER (www) AS c7p
    , LEAD (w.word, 7) OVER (www) AS c8w
    , LEAD (w.word, 8) OVER (www) AS c9w
    , LEAD (w.lemma, 8) OVER (www) AS c9l
    , LEAD (w.pos, 8) OVER (www) AS c9p
    , LEAD (w.word, 9) OVER (www) AS c10w
    , LEAD (w.word, 10) OVER (www) AS c11w
    FROM orderedflatcorpus AS c1
    JOIN words w ON w.id=c1.words_id
    WINDOW www AS (ORDER BY c1.id)
    )
SELECT id ,  source, word
    , c2w , c3w
    , c4w , c4l , c4p
    , c5w
    , c6w
    , c7w
    , c8w
    , c9w , c9l , c9p
    , c10w
    , c11w
FROM stuff
WHERE 1=1
AND c4p LIKE 'v%'
AND c5p = 'appge'
AND c6l = 'way'
AND c7p LIKE 'i%'
AND c8w = 'the'
AND c9p LIKE 'n%'
ORDER BY id
)
-- TO '/home/postgres/Results/OUTPUT.csv' DELIMITER E'\t' csv header;
TO '/tmp/OUTPUT3.csv' DELIMITER E'\t' csv header;

Note: I get two lines in the output, because I relaxed the conditions a bit too much ...


Update :the first query, avoiding the CTE


copy(
SELECT id ,  source, word
        , c2w
        , c3w
        , c4w
        , c4l
        , c4p
        , c5w
        , c6w
        , c7w
        , c8w
        , c9w
        , c9l
        , c9p
        , c10w
        , c11w
FROM (
        SELECT   c1.id , c1.source, c1.word
        , LEAD ( c1.word, 1) OVER (www) AS c2w
        , LEAD (c1.word, 2) OVER (www) AS c3w
        , LEAD ( c1.word, 3) OVER (www) AS c4w
        , LEAD (c1.lemma, 3) OVER (www) AS c4l
        , LEAD (c1.pos, 3) OVER (www) AS c4p
        , LEAD (c1.pos, 4) OVER (www) AS c5p
        , LEAD (c1.word, 4) OVER (www) AS c5w
        , LEAD (c1.word, 5) OVER (www) AS c6w
        , LEAD (c1.lemma, 5) OVER (www) AS c6l
        , LEAD (c1.word, 6) OVER (www) AS c7w
        , LEAD (c1.pos, 6) OVER (www) AS c7p
        , LEAD (c1.word, 7) OVER (www) AS c8w
        , LEAD (c1.word, 8) OVER (www) AS c9w
        , LEAD (c1.lemma, 8) OVER (www) AS c9l
        , LEAD (c1.pos, 8) OVER (www) AS c9p
        , LEAD (c1.word, 9) OVER (www) AS c10w
        , LEAD (c1.word, 10) OVER (www) AS c11w
        FROM orderedflatcorpus AS c1
        WINDOW www AS (ORDER BY id)
        ) stuff
WHERE 1=1
AND c4p LIKE 'v%'
AND c5p = 'appge'
AND c6l = 'way'
AND c7p LIKE 'i%'
AND c8w = 'the'
AND c9p LIKE 'n%'
ORDER BY id
)
-- TO '/home/postgres/Results/OUTPUT.csv' DELIMITER E'\t' csv header;
TO '/tmp/OUTPUT2a.csv' DELIMITER E'\t' csv header;

[a similar transformation could be performed on the second query]


UPDATE2 The subquery version for the two table variant.


-- copy(
-- EXPLAIN ANALYZE
SELECT c1i, c1s, c1w
        , c2w , c3w
        , c4w , c4l , c4p
        , c5w
        , c6w
        , c7w
        , c8w
        , c9w , c9l , c9p
        , c10w
        , c11w
FROM (
        SELECT c1.id AS c1i
        , c1.source AS c1s
        , w1.word AS c1w
        , LEAD (w1.word, 1) OVER www AS c2w
        , LEAD (w1.word, 2) OVER www AS c3w
        , LEAD (w1.word, 3) OVER www AS c4w
        , LEAD (w1.lemma, 3) OVER www AS c4l
        , LEAD (w1.pos, 3) OVER www AS c4p
        , LEAD (w1.pos, 4) OVER www AS c5p
        , LEAD (w1.word, 4) OVER www AS c5w
        , LEAD (w1.word, 5) OVER www AS c6w
        , LEAD (w1.lemma, 5) OVER www AS c6l
        , LEAD (w1.word, 6) OVER www AS c7w
        , LEAD (w1.pos, 6) OVER www AS c7p
        , LEAD (w1.word, 7) OVER www AS c8w
        , LEAD (w1.word, 8) OVER www AS c9w
        , LEAD (w1.lemma, 8) OVER www AS c9l
        , LEAD (w1.pos, 8) OVER www AS c9p
        , LEAD (w1.word, 9) OVER www AS c10w
        , LEAD (w1.word, 10) OVER www AS c11w
        FROM orderedflatcorpus c1
        JOIN words w1 ON w1.id=c1.words_id
        WHERE 1=1
/*      These *could* to prune out unmatched items, but I could not get it to work ...
        AND EXISTS (SELECT *FROM orderedflatcorpus c4 JOIN words w4 ON w4.id=c4.words_id
                WHERE c4.id = 3+c1.id -- AND w4.pos LIKE 'v%'
                )  -- OMG
        AND EXISTS (SELECT *FROM orderedflatcorpus c5 JOIN words w5 ON w5.id=c5.words_id
                WHERE c5.id = 4+c1.id -- AND w5.pos = 'appge'
                ) -- OMG
        AND EXISTS (SELECT *FROM orderedflatcorpus c7 JOIN words w7 ON w7.id=c7.words_id
                WHERE c7.id = 6+c1.id -- AND w7.pos LIKE 'i%'
                ) -- OMG
        AND EXISTS (SELECT *FROM orderedflatcorpus c9 JOIN words w9 ON w9.id=c9.words_id
                WHERE c9.id = 8+c1.id -- AND w9.pos LIKE 'n%'
                ) -- OMG
        AND EXISTS (SELECT *FROM orderedflatcorpus c8 JOIN words w8 ON w8.id=c8.words_id
                WHERE c8.id = 7+c1.id -- AND w8.word = 'the'
                )  -- OMG
*/
         WINDOW www AS (ORDER BY c1.id ROWS BETWEEN CURRENT ROW AND 10 FOLLOWING)
        ) stuff
WHERE 1=1
AND c4p LIKE 'v%'
AND c5p = 'appge'
AND c6l = 'way'
AND c7p LIKE 'i%'
AND c8w = 'the'
AND c9p LIKE 'n%'
ORDER BY c1i
        ;
   -- )
-- TO '/home/postgres/Results/OUTPUT.csv' DELIMITER E'\t' csv header;
-- TO '/tmp/OUTPUT3b.csv' DELIMITER E'\t' csv header;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download