Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Having trouble indexing and executing a query in O (log n) time.

The query includes an INNER JOIN, an ORDER BY, and an equality operation. If I understand the laws of databases correctly, a query can be indexed and executed in O (log n) time (or thereabouts) if a non-equality operator is not used on more than one column. In this case, I believe the INNER JOIN does count as an equality operator and the non-equality operator would be the ORDER BY portion of the query. This table has upwards of 10,000,000 rows and needs to handle several reads and writes per second.

Using PostgreSQL. This is what the table looks like. As you can see, the column 'Names' is a list property and it is the column that the INNER JOIN goes against:

Age Names                       Date
34  ['carla', 'john', 'sam']    3/13/2011
26  ['json', 'cindy', 'joel']   3/13/2011
72  ['beth', 'amber', 'susie']  3/13/2011
14  ['john', 'jim', 'debie']    3/13/2011

This is the query that we are trying to do:

SELECT * FROM the_table WHERE Age==26 AND Names=='john' ORDER BY Date

My background is from using App Engine's Big Table, so I've used equality operators here to indicate that 'john' should be one of the names in the Names column. This would be an acceptable query in GAE's big table, it would execute in O (log N) time as all Big Table queries are reqyured to do. I am assuming there is a way to do this in PostgreSQL as well since PostgreSQL accepts list data types as columns.

Is this possible to do in PostgreSQL?

If so, how should the index be set up (we can't figure out how to set up an index that takes into account the three properties)?

share|improve this question
1  
The equality operator in SQL is = not == –  a_horse_with_no_name May 20 '13 at 22:23

2 Answers 2

This is possible for PostgreSQL 8.4 or later. In order to create a multi-column GIN index, you need to install the additional module btree_gin.
Simple types like integer or date are usually better off with a (default) B-Tree index, so that's not installed with standard PostgreSQL. But for a case like this a multi-column index is fastest, so you need the additional index methods for the plain types.

In PostgreSQL 9.1 or later you can install it with CREATE EXTENSION:

CREATE EXTENSION btree_gin;

In older versions you would run as privileged system user (like postgres):

psql -d dbname -f SHAREDIR/contrib/btree_gin.sql

For a PostgreSQL 8.4 installation on Debian,this might be:

psql -d mydb -f /usr/share/postgresql/8.4/contrib/btree_gin.sql

Then, given this table:

CREATE TEMP TABLE tbl (age int, names text[], thedate date);

... you can create this multi-column GIN index:

CREATE INDEX tbl_gin_idx ON tbl USING GIN (names, age, thedate);

... which can be used by a query like:

SELECT * FROM tbl
WHERE  age = 26
AND    '{json}'::text[] <@ names
ORDER  BY thedate;

Note that a GIN index caries a non-trivial cost for write operations.
But that's hardly worth mentioning in comparison to what a SELECT on 10 million rows without index would do to you.

share|improve this answer

Have you tried with:

SELECT * from the_table WHERE Age = 26 AND array['john'] && Names ORDER BY Date

Using an index like:

CREATE INDEX the_table_idx ON the_table USING GIN (Names, Age, Date);

Or at least an index like

CREATE INDEX the_table_idx ON the_table USING GIN (Names, Age);
share|improve this answer
    
Yeah, we tried that. You can't use non-array columns on a GIN index. –  Chris Dutrow Apr 2 '13 at 19:21
    
@ChrisDutrow what do you mean by this? At least you can create and use such an index in PG 9.0 –  dezso Apr 3 '13 at 10:16
    
@dezso: You need the additional module btree_gin for that. –  Erwin Brandstetter Apr 3 '13 at 13:11
    
@ErwinBrandstetter Ah! this happens if you have nearly all extensions listed in PG docs installed :) –  dezso Apr 4 '13 at 8:53
    
The equality operator in SQL is = not == –  a_horse_with_no_name May 20 '13 at 22:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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