4

I have a huge table with nearly 50 million records that represent words and their positions (pos) in documents (doc).

I'm trying to migrate from mysql to postgresql. I am trying to find left and right collocations of a node word between 5 distance. And then calculate some statistic formulas.

The following query is working, but it is too slow. For example, wordid=15 has 200k rows in the whole table and it is so slow.

I want to optimize it. I made indexes for doc and pos. I'm new to Postgres and I'm trying to learn its powers.

What would you recommend for optimization?

SELECT 
    node.wordid AS node,
    neigh.wordid AS neigh,
    node.doc,
    node.pos,
    (node.pos - neigh.pos) AS distance,
FROM collocations node
    JOIN collocations neigh ON ( neigh.pos >= (node.pos - 5) AND neigh.pos <= (node.pos + 5) )
WHERE 
((node.wordid = 15) AND 
(node.doc = neigh.doc) AND 
(node.pos <> neigh.pos)

Edit 1: Create Table Statement

CREATE TABLE "public"."collocations" (
  "doc" int2,
  "pos" int4,
  "wordid" int4,
  "sentenceid" int4
)
;
CREATE INDEX "collocations_doc_pos_idx" ON "public"."collocations" USING btree (
  "doc" "pg_catalog"."int2_ops" ASC NULLS LAST,
  "pos" "pg_catalog"."int4_ops" ASC NULLS LAST
);
CREATE INDEX "collocations_doc_idx" ON "public"."collocations" USING btree (
  "doc" "pg_catalog"."int2_ops" ASC NULLS LAST
);
CREATE INDEX "collocations_pos_idx" ON "public"."collocations" USING btree (
  "pos" "pg_catalog"."int4_ops" ASC NULLS LAST
);
CREATE INDEX "collocations_wordid_idx" ON "public"."collocations" USING btree (
  "wordid" "pg_catalog"."int4_ops" ASC NULLS LAST

);

Edit 2 : Server Informations

  • Ubuntu 16.04
  • psql (PostgreSQL) 9.5.9
  • 64 GB Ram

Edit 3 : Query Explain&Analyse I select a frequency id for quick result. frequency of word 256 in 50 million .

[
  {
    "Plan": {
      "Node Type": "Nested Loop",
      "Join Type": "Inner",
      "Startup Cost": 34.03,
      "Total Cost": 1294443.52,
      "Plan Rows": 3368139,
      "Plan Width": 18,
      "Actual Startup Time": 4.481,
      "Actual Total Time": 1992.817,
      "Actual Rows": 2476,
      "Actual Loops": 1,
      "Shared Hit Blocks": 16334,
      "Shared Read Blocks": 24734,
      "Shared Dirtied Blocks": 0,
      "Shared Written Blocks": 0,
      "Local Hit Blocks": 0,
      "Local Read Blocks": 0,
      "Local Dirtied Blocks": 0,
      "Local Written Blocks": 0,
      "Temp Read Blocks": 0,
      "Temp Written Blocks": 0,
      "Plans": [
        {
          "Node Type": "Bitmap Heap Scan",
          "Parent Relationship": "Outer",
          "Relation Name": "collocations",
          "Alias": "node",
          "Startup Cost": 33.47,
          "Total Cost": 6301.99,
          "Plan Rows": 1665,
          "Plan Width": 10,
          "Actual Startup Time": 0.173,
          "Actual Total Time": 1.321,
          "Actual Rows": 248,
          "Actual Loops": 1,
          "Recheck Cond": "(wordid = 47905)",
          "Rows Removed by Index Recheck": 0,
          "Exact Heap Blocks": 222,
          "Lossy Heap Blocks": 0,
          "Shared Hit Blocks": 75,
          "Shared Read Blocks": 152,
          "Shared Dirtied Blocks": 0,
          "Shared Written Blocks": 0,
          "Local Hit Blocks": 0,
          "Local Read Blocks": 0,
          "Local Dirtied Blocks": 0,
          "Local Written Blocks": 0,
          "Temp Read Blocks": 0,
          "Temp Written Blocks": 0,
          "Plans": [
            {
              "Node Type": "Bitmap Index Scan",
              "Parent Relationship": "Outer",
              "Index Name": "collocations_wordid_idx",
              "Startup Cost": 0.00,
              "Total Cost": 33.05,
              "Plan Rows": 1665,
              "Plan Width": 0,
              "Actual Startup Time": 0.111,
              "Actual Total Time": 0.111,
              "Actual Rows": 248,
              "Actual Loops": 1,
              "Index Cond": "(wordid = 47905)",
              "Shared Hit Blocks": 0,
              "Shared Read Blocks": 5,
              "Shared Dirtied Blocks": 0,
              "Shared Written Blocks": 0,
              "Local Hit Blocks": 0,
              "Local Read Blocks": 0,
              "Local Dirtied Blocks": 0,
              "Local Written Blocks": 0,
              "Temp Read Blocks": 0,
              "Temp Written Blocks": 0
            }
          ]
        },
        {
          "Node Type": "Index Scan",
          "Parent Relationship": "Inner",
          "Scan Direction": "Forward",
          "Index Name": "collocations_doc_idx",
          "Relation Name": "collocations",
          "Alias": "komsu",
          "Startup Cost": 0.56,
          "Total Cost": 753.88,
          "Plan Rows": 1472,
          "Plan Width": 10,
          "Actual Startup Time": 3.777,
          "Actual Total Time": 8.026,
          "Actual Rows": 10,
          "Actual Loops": 248,
          "Index Cond": "(doc = node.doc)",
          "Rows Removed by Index Recheck": 0,
          "Filter": "((node.pos <> pos) AND (pos >= (node.pos - 5)) AND (pos <= (node.pos + 5)))",
          "Rows Removed by Filter": 19419,
          "Shared Hit Blocks": 16259,
          "Shared Read Blocks": 24582,
          "Shared Dirtied Blocks": 0,
          "Shared Written Blocks": 0,
          "Local Hit Blocks": 0,
          "Local Read Blocks": 0,
          "Local Dirtied Blocks": 0,
          "Local Written Blocks": 0,
          "Temp Read Blocks": 0,
          "Temp Written Blocks": 0
        }
      ]
    },
    "Planning Time": 0.795,
    "Triggers": [
    ],
    "Execution Time": 1993.060
  }
]
  • It would be good to also add (by editing the question) the CREATE TABLE statement and your version of Postgres and the execution plan of your query EXPLAIN (ANALYZE, BUFFERS) SELECT ... ;. – ypercubeᵀᴹ Oct 23 '17 at 13:09
  • Is there a unique constraint on (doc, pos)? – ypercubeᵀᴹ Oct 23 '17 at 13:12
  • @ypercubeᵀᴹ Thanks, I updated question with your request, there is no unique const about doc,pos – Yilmazerhakan Oct 23 '17 at 13:35
  • An execution plan in "plain text" is usually preferred over the JSON format. – a_horse_with_no_name Nov 2 '17 at 11:19
1
+50

I would rewrite the query using LATERAL JOIN. In this form it is easier to see what indexes should be there.

SELECT
    node.wordid AS node_wordid,
    neighbour.neighbour_wordid,
    node.doc,
    node.pos,
    neighbour.distance
FROM
    collocations AS node
    INNER JOIN LATERAL
    (
        SELECT
            neigh.wordid AS neighbour_wordid,
            node.pos - neigh.pos AS distance
        FROM collocations AS neigh
        WHERE
            neigh.doc = node.doc
            AND neigh.pos >= node.pos - 5
            AND neigh.pos <= node.pos + 5
            AND neigh.pos <> node.pos
    ) AS neighbour ON true
WHERE
    node.wordid = 15
;

The most important part is indexes. Ideally there should be the following indexes.

The table should have an index on wordid, because we search for a specific value.

We also need values from doc and pos columns. If it was SQL Server, I would specify doc and pos as INCLUDED, but I don't think Postgres has this feature, so they should be just part of the index. Having these columns in the index would allow engine to read all data it needs from the index itself without extra look-ups. wordid must be first in the index. doc and pos can go in any order.

CREATE INDEX "collocations_wordid_doc_pos_idx" ON "public"."collocations" 
(
    "wordid",
    "doc",
    "pos"
);

There should also be an index on (doc, pos, wordid). We need to search for specific value of doc and then on the range of values of pos.

If it was SQL Server, I would specify wordid as INCLUDED, but I don't think Postgres has this feature, so it should be just part of the index. Having wordid in the index would allow engine to read all data it needs from the index itself without extra look-ups.

CREATE INDEX "collocations_doc_pos_wordid_idx" ON "public"."collocations" 
(
    "doc",
    "pos",
    "wordid"
);

I would also try to delete or disable all other indexes (at least during tests) to eliminate the chance that optimizer would choose a wrong index.


I expect to see in the plan that there is a seek in the index collocations_wordid_doc_pos_idx for a given word id. It will be loop joined to the seek in the index collocations_doc_pos_wordid_idx. For each row in the table with the given word id there will be a seek in the index collocations_doc_pos_wordid_idx.

  • 1
    Your solution/answer is great. I rewrite all with your recommends and tested it. Result is incredible!!! My Solution : 9.394 sec for 25587 record. 24.738 sec for 65737 record Your Solution : 0.070 sec for 25587 record 0.188 sec for 65737 record I understood the power of indexes with your answer. Thank you so much. – Yilmazerhakan Nov 2 '17 at 13:44
  • You are welcome @Yilmazerhakan. Quite often, suitable indexes is the most important part of the query performance. – Vladimir Baranov Nov 5 '17 at 23:36
0

Right off the bat, I wonder if you're not going about it wrong. I'm not sure what you're trying to store, but a tsvector holds positional information. You can also configure it to basic things like stubbing very easily. There is a lot of overhead in a database to store 50 million single words with one word per row. I think you'd be better off storing one tsvector for each document and parsing it, or doing this work outside of the database with tool even more tailored to lexeme processing.

If your formulas are in C, or could be made in C perhaps you could just accept the tsvector and work with the WordEntryPos? See tsvectorsend()

  * Binary Input / Output functions. The binary format is as follows:
 *
 * uint32   number of lexemes
 *
 * for each lexeme:
 *      lexeme text in client encoding, null-terminated
 *      uint16  number of positions
 *      for each position:
 *          uint16 WordEntryPos
 */

Just write your function in C, and call SELECT My_TSVector_proc( to_tsvector(document)) ) FROM myTable; or whatever.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.