Re: OT: Data structure design question: How do they count so fast?

Hi Brandon,

Thanks for your suggestion. I'll think about that one. Part of the
problem is also trying to figure out what the remaining set of
attributes and attribute values are, so that slows it down
considerably too. There are many many combinations of attribute
values that can be clicked on.

More work to do!

Thanks,

____________________________________________________________________
Brendan Duddridge | CTO | 403-277-5591 x24 | brendan(at)clickspace(dot)com

ClickSpace Interactive Inc.
Suite L100, 239 - 10th Ave. SE
Calgary, AB T2G 0V9

http://www.clickspace.com

On Apr 9, 2006, at 9:56 PM, Brandon Hines wrote:

> Brendan,
>
> I have a number of applications the require similar functionality.
> What I typically do is to create a count table that gets updated
> with a trigger. But instead of keeping absolute counts, I keep
> counts of the smallest necessary element. For example, I have a
> table with approx 12 million elements, each element belongs to one
> of a thousand classes of elements. The materialized view table
> with only about a thousand rows is small enough for sum() queries
> of various classes fast enough for web pages.
>
> -Brandon
>
> Brendan Duddridge wrote:
>> Hi,
>> First of all, the reason I'm posting on the PostgreSQL Performance
>> list is we have a performance issue with one of our applications
>> and it's related to the speed at which PostgreSQL can do counts.
>> But it's also related to the data structure we've designed to
>> develop our comparison shopping engine. It's very normalized and
>> the speed of our queries are slowing down considerably as we add
>> more and more data.
>> So I've been looking at some of the other comparison shopping
>> engines and I'm trying to figure out how they manage to get the
>> counts of their products for a set of attributes and attribute
>> values so quickly.
>> For example, on the following page, they have 1,260,658 products:
>> http://www.mysimon.com/Home-Furnishings/9000-10975_8-0.html?tag=glnav
>> They display 3 attributes with values on the page: Price Range,
>> Home Furnishing Type, and Store. Plus there are a selection of
>> other attributes not displaying the value choices.
>> For Price Range, they have the following values and product counts
>> (in brackets):
>> # Below $20 (204,315)
>> # $20 - $50 (234,694)
>> # $50 - $80 (188,811)
>> # $80 - $130 (182,721)
>> # $130 - $240 (222,519)
>> For Home Furnishing Type they have:
>> # Wall Art and Decor (438,493)
>> # Lighting (243,098)
>> # Bathroom Furnishings (132,441)
>> # Rugs (113,216)
>> # Decorative Accents (65,418)
>> And for Store they have:
>> # Art.com (360,933)
>> # HomeAnnex (130,410)
>> # AllPosters.com (72,529)
>> # HomeClick.com (61,423)
>> # 1STOPlighting Superstore (32,074)
>> Now, initially I thought they would just pre-compute these counts,
>> but the problem is, when you click on any of the above attribute
>> values, they reduce the remaining possible set of matching
>> products (and set of possible remaining attributes and attribute
>> values) by the amount displayed next to the attribute value
>> selected. You can click on any combination of attribute values to
>> filter down the remaining set of matching products, so there's a
>> large combination of paths you can take to arrive at a set of
>> products you might be interested in.
>> Do you think they are pre-computed? Or do you think they might use
>> a query similar to the following?:
>> select pav.attribute_value_id, count(p.product_id)
>> from product_attribute_value pav,
>> attribute a,
>> product p
>> where a.attribute_id in (some set of attribute ids) and
>> pav.product_id = p.product_id and
>> pav.attribute_id = a.attribute_id and p.product_id in
>> (select product_id
>> from category_product
>> where category_id = some category id) and
>> p.is_active = 'true'
>> group by pav.attribute_value_id;
>> It would seem to me that although the above query suggests a
>> normalized database structure, that joining with 3 tables plus a
>> 4th table in the sub-query with an IN qualifier and grouping to
>> get the product counts would take a VERY long time, especially on
>> a possible result set of 1,260,658 products. The other issue is
>> trying to figure out what the remaining set of possible attribute
>> and attribute values are in order to reach the remaining set of
>> products.
>> Does anyone have any insights into what kind of data structures
>> would be necessary to accomplish such a feat? I know that
>> PostgreSQL has performance issues with counting rows, so I can't
>> imagine being able to use the above kind of query to get the
>> results we need. I don't know what kind of database backend
>> mysimon is using either. It would also seem to be logical that
>> having a flattened data structure would seem to be necessary in
>> order to get the performance required. Their pages seem to load
>> pretty fast.
>> We are possibly considering some kind of pre-computed decision-
>> tree type data structure to get the counts of the set of products
>> that could be reached by selecting any combination of attributes
>> and attribute values. Does this seem like a reasonable idea?
>> Perhaps there's a better way?
>> I also apologize if this isn't the appropriate list to publish
>> this kind of question to. The reason I posted here was because it
>> is a performance related question, but not necessarily directly
>> related to PostgreSQL. It's just that we are using PostgreSQL for
>> our product comparison engine so I thought there could be some
>> PostgreSQL specific optimizations that could be made. If not,
>> please let me know and I'll move it elsewhere. Thanks very much,
>> *
>> *____________________________________________________________________
>> *Brendan Duddridge* | CTO | 403-277-5591 x24 |
>> brendan(at)clickspace(dot)com <mailto:brendan(at)clickspace(dot)com>
>> *
>> *ClickSpace Interactive Inc.
>> Suite L100, 239 - 10th Ave. SE
>> Calgary, AB T2G 0V9
>> http://www.clickspace.com
>
>