OK, I just watched Brett Slatkin's I/O talk [1] and he mentions "cross product" a couple of times, so it seems that the use of the word "permutation" in the docs is incorrect; the number of index entries is indeed proportional to the Cartesian product, rather than "permutations" which would lead to a factorial (n!) number of index entries.
I've filed a doco issue here [2]. Karl [1] http://code.google.com/events/io/2009/sessions/BuildingScalableComplexApps.html [2] http://code.google.com/p/googleappengine/issues/detail?id=3003 On Mar 22, 11:50 am, kostmo <[email protected]> wrote: > It is still unclear to me exactly how many index entries will be > produced by including multiple ListProperty's in an entity. In one > post [1], between the inquiring user and the Google rep, the > possibilities for the number of index entries included the power set, > Cartesian product, or the "number of unique combinations" (this was > the rep's answer, without mention of "permutations"). > > I'd like to verify that the correct combinatorics terminology is being > used in the documentation on exploding indexes [2]. > > Quote: > "the index table must include a row for every permutation of the > values of every property for the index" > This is followed by the example: > e2 = MyModel() > e2.x = ['red', 'blue'] > e2.y = [1, 2] > "the index must store 12 property values: 2 each for the built-in > indexes on x and y, and 2 for each of the 4 permutations of x and y in > the custom index". > > The example does not make me completely confident about what type of > combinatoric expression is truly being used, since the sum of the > number of permutations for each property happens to equal the > cardinality of the Cartesian product of the two properties. The > enumeration given in this post [3] seems to suggest that it is > actually the Cartesian product at work. > > To clarify this issue, we could use Python 2.6 to illustrate an > example:>>> from itertools import product, permutations > >>> x = ['red', 'blue', 'green'] > >>> y = [1, 2, 3] > >>> list(permutations(x)) + list(permutations(y)) > > [('red', 'blue', 'green'), ('red', 'green', 'blue'), ('blue', 'red', > 'green'), ('blue', 'green', 'red'), ('green', 'red', 'blue'), > ('green', 'blue', 'red'), (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), > (3, 1, 2), (3, 2, 1)]>>> list(product(x, y)) > > [('red', 1), ('red', 2), ('red', 3), ('blue', 1), ('blue', 2), > ('blue', 3), ('green', 1), ('green', 2), ('green', 3)] > > Is the number of custom index entries that will be generated by an > entity with the two 3-valued properties given above proportional to > the sum of permutations (there are 12) or the Cartesian product (there > are 9)? > > Thanks, > Karl > > [1] "Efficient way to structure my data > model"http://groups.google.com/group/google-appengine/browse_thread/thread/... > [2]http://code.google.com/appengine/docs/python/datastore/queriesandinde... > [3] "Size of index in case of exploding > index"http://groups.google.com/group/google-appengine/browse_thread/thread/... -- You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.
