2

I'm using Postgres 9.1 I have two tables I am joining:

wikidb=> \d page
                         Table "public.page"
        Column         |     Type      |          Modifiers           
-----------------------+---------------+------------------------------
 page_id               | bigint        | not null
 page_namespace        | integer       | not null default 0
 page_title            | text          | not null default ''::text
 [...]
Indexes:
    [...]
    "page_page_namespace_page_title_idx" UNIQUE, btree (page_namespace, page_title)

wikidb=> \d pagelinks
                 Table "public.pagelinks"
      Column       |  Type   |         Modifiers          
-------------------+---------+----------------------------
 pl_from           | bigint  | not null default 0::bigint
 pl_namespace      | integer | not null default 0
 pl_title          | text    | not null default ''::text
 [...]
Indexes:
    [...]
    "pagelinks_pl_namespace_pl_title_pl_from_idx" btree (pl_namespace, pl_title, pl_from)

Notice how both have indices on the (namespace, title) columns. I am interested in finding out how many (pl_namespace,pl_title) pairs in the pagelinks table do not show up in the page table as (page_namespace, page_title).

If I use a join, then I get the following plan:

wikidb=> explain SELECT COUNT(*)
FROM pagelinks
LEFT OUTER JOIN page
  ON page.page_namespace = pagelinks.pl_namespace AND
     page.page_title = pagelinks.pl_title
WHERE page.page_namespace IS NULL AND page.page_title IS NULL;
                                                   QUERY PLAN                                                    
-----------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1310748.56..1310748.57 rows=1 width=0)
   ->  Merge Anti Join  (cost=1189384.02..1310748.56 rows=1 width=0)
         Merge Cond: ((pagelinks.pl_title = page.page_title) AND (pagelinks.pl_namespace = page.page_namespace))
         ->  Sort  (cost=1144343.89..1164498.31 rows=8061768 width=19)
               Sort Key: pagelinks.pl_title, pagelinks.pl_namespace
               ->  Seq Scan on pagelinks  (cost=0.00..219551.68 rows=8061768 width=19)
         ->  Sort  (cost=45038.32..45975.52 rows=374880 width=20)
               Sort Key: page.page_title, page.page_namespace
               ->  Seq Scan on page  (cost=0.00..10331.80 rows=374880 width=20)
(9 rows)

Which, as you can see, sorts each of both tables and merges them. I don't understand why it does this if the indices already contain both columns in sorted order.

Any explanations?

3

I don't understand why it does this if the indices already contain both columns in sorted order.

I'm using Postgres 9.1.

Most importantly, index-only scans are a major performance feature added to Postgres 9.2. Details in the Postgres Wiki.

Consider upgrading to a current version, Postgres 9.1 is getting old anyway.

In older versions, Postgres has to visit the table either way, so indexes must offer much more performance improvements to beat the added overhead. And the UNIQUE index tells us, there is at most a single row per (page_namespace, page_title), so your indexes are not going to help much - if at all, while you count the whole table.

One minor improvement:

SELECT COUNT(*) AS ct
FROM   pagelinks l
LEFT   JOIN page p ON p.page_namespace = l.pl_namespace
                  AND p.page_title = l.pl_title
WHERE  p.page_namespace IS NULL;
AND    p.page_title IS NULL;

Testing just one column already proves everything there is to prove.

Otherwise your query is pretty much the optimum. Maybe NOT EXISTS can compete:

SELECT count(*) AS ct
FROM   pagelinks l
WHERE  NOT EXISTS (
   SELECT 1
   FROM   page 
   WHERE  page_namespace = l.pl_namespace
   AND    page_title = l.pl_title
   );

A join or NOT IN on a row expression (pl_namespace,pl_title) are typically slower.

Basic techniques:

4

PostgreSQL thinks the sort merge is faster. And in my hands on 9.1 it actually is faster than walking both indexes. You can try it for yourself by set enable_sort to off; and see what plan it gives, and how long that one takes to run.

Sorting is pretty efficient. Walking indexes is inefficient in 9.1 because it still has to visit the table to make sure the row is actually visible. Indexes don't store visibility information. 9.2 introduced index-only scans, which gets around part of that problem.

Also, the index leaf pages are not necessarily logical order, so walking the index in logical order can lead to a lot of random IO. (Of course, checking the table for visibility off of an index scan will as well.)

There have been a lot of improvements made since 9.1.

2

OK, so you've listed a few questions here, so I'll try my best to answer them.

Is your query correct?

First, you said:

"I am interested in finding out how many (pl_namespace,pl_title) pairs in the pagelinks table show up in the page table as (page_namespace, page_title)."

Is the query you're performing correct for that, or did I misunderstand the description? If you run

EXPLAIN SELECT COUNT(*)
FROM pagelinks
LEFT OUTER JOIN page
ON page.page_namespace = pagelinks.pl_namespace AND
  page.page_title = pagelinks.pl_title
WHERE page.page_namespace IS NULL AND page.page_title IS NULL;

Then you are going to JOIN such that every row entry in pagelinks is preserved, and NULL will be present for page row entries when they weren't found in page. You are then filtering to find the NULLs, and then counting.

As such, you're counting the number of entries in the pagelinks table for which there was no match in the page table.

Are you actually trying to perform this query?

EXPLAIN SELECT COUNT(*)
FROM pagelinks
JOIN page
ON page.page_namespace = pagelinks.pl_namespace AND
  page.page_title = pagelinks.pl_title;

Sort Merge Join

So, the planner has decided that a sort merge join is the best plan for joining the data, so some form of sort is necessary to complete that action. However, I understand your point, that is that the namespace and title fields are already sorted due to indexing.

In this case, however, the planner is using a sequential scan on both the page and pagelinks tables to access all the entries, and as such will treat them as unsorted since they are being read sequentially of of the table heap.

I'm not 100% sure this will fix your problem, but try giving the query planner a hint at what you're trying to do by modifying your ON portion of the JOIN:

EXPLAIN SELECT COUNT(*)
FROM pagelinks
JOIN page
ON (page.page_namespace,page.page_title) = (pagelinks.pl_namespace,pagelinks.pl_title);

Or possibly:

EXPLAIN SELECT COUNT(*)
FROM pagelinks
WHERE (pl_namespace,pl_title) IN 
(SELECT page_namespace, page_title FROM page);

Honestly, there's probably lots of ways to rewrite this query, and I'd work on it until the planner yields what you want.

Sequential Scan

In your last question, you ask why the COUNT(*) even has to touch the table. Well, the database has to get this count from somewhere, so it either needs to scan through the entire index and count the number of entries, or scan through the whole table and count the number of entries. It just so happens that a table scan is the faster way of completing this operation.

EDITED for more query options

Based on your feedback, you might also try:

SELECT COUNT(*) FROM pagelinks WHERE ctid NOT IN(
  SELECT ctid FROM pagelinks
  WHERE (pl_namespace,pl_title) IN 
    (SELECT page_namespace, page_title FROM page));

or

WITH page_data AS(
SELECT page_namespace, page_title FROM page
)
SELECT COUNT(*) FROM pagelinks WHERE ctid NOT IN(
  SELECT ctid FROM pagelinks
  WHERE (pl_namespace,pl_title) IN 
    (SELECT page_namespace, page_title FROM page_data));

Just trying to brainstorm a couple ideas which might jump-start the query planner into using a better query plan. I can't be sure if they'll work any better because I don't have your data.

  • Thanks for the answer. I've clarified the 'in' vs 'not in' part of the query (had a typo there), and removed the last question to keep the whole thing on one topic. Sorry if that breaks your answer a bit. – orm Sep 17 '15 at 22:40
  • Are you still having trouble? I can add some material to my answer which might help address the problem, if you haven't solved it already. – Chris Sep 17 '15 at 23:21
  • I've solved the problem by using an IN nested query like you have, this one runs faster. It still scans the tables, but does not sort them. In terms of the question though, I guess what I want is understanding whether postgres does not do index only joins, for example. – orm Sep 17 '15 at 23:33
  • It won't do "index only joins" quite so explicitly, but the reason i used the IN and sub-query was to try an make use of at least one index if possible. Think about it this way: the sub-query is scanning the whole table, so no index will be used. Then, it applies these values and guesses if the index onpagelinks will be useful (from collected statisitics from ANALYZE) If it looks like scanning the whole table will be better, it will choose to do so. The planner, however, is not always right. If you still need to improve your performance, I can still hypothesize a couple ideas. – Chris Sep 17 '15 at 23:41
  • I added a couple possible alternatives which may (or may not) lead to a better query plan. – Chris Sep 17 '15 at 23:47

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.