Relation indexing using a single list property - proposal

[Juraj Vitko]

On a query with equality filter on a list property, would it be
possible to:

1) _not_ discard the sort order on that property,
2) allow for inequality test on smallest/highest value of that list
property (similar to ordering)

That way it would be possible to implement "relation indexes" using a
table with a single list property (no custom indexes required!)

The property would look something like: [ a.val:unique, filter1,
filter2, filterN, z.val:unique ]

The two 'val' is the same value to be lexicographically ordered (so
numeric types must be converted to appropriate strings).
The a. and z. prefixes would be actually the lowest and highest
printable ascii chars, just so that they are always the lowest and
highest value of the list property, and can be used in asc and desc
ordering.
The filters would be used for equality filtering.

Then this query would be possible:
select from kind where prop == filter1 && prop == filter2 && prop >
'a.someval:unique' order by prop asc
(the optional greater-than operator is there to support paging)

The sort order would _not_ be dropped only if specifically requested
by the user, as to not incur needless overhead on current queries.

A real-use example of a relation index table shared by multiple kinds:

select from RelationIndex where f == 'roleA' && f == 'registered' && f
== '{User}' && f == '(lastName') && v > 'Smith:xJ8mFc9r' order by v
asc;

- filter column is named 'f', value is named 'v'
- the { and } are used to distinguish a kind name filter
- the ( and ) are used to distinguish a column name filter
- the 'v' always contains value belonging to that table/column
- 'xJ8mFc9r' is the unique suffix

The benefits of the "relation indexes" technique using a single list
property:
1) single-query forward/backward bookmark paging (no equality restarts
needed),
2) asc/desc ordering on any number of columns (one column at a time)
3) no custom indexes required (hard-limited to 100 per app)

One could argue that it is simpler to implement relation indexes using
a table with 2 columns: "filters" and "value" - however:
1. this table needs a custom index
2. due to the custom index, max. 4 filters can be queried on at the
same time (tested)
3. this custom index must enumerate all the filters (filter asc,
filter asc, filter asc, filter asc, value asc + the same for value
desc) - otherwise custom index space is wasted with permutations
4. due to point 3., each row in the index table must contain a 'dummy'
filter value that is used to "park" the unused filters, only so that
the query always matches the custom index definition, ie. "where
filter == 'abc' && filter == 'def' && filter == 'dummy' && filter ==
'dummy'"
5. both runtime and storage overhead of this approach are much higher
than the single-property approach (due to the list property being
multiplied by 2 for indexing)

Your opinions?
J.

[Juraj Vitko]

sorry! correction of: "filter column is named 'f', value is named 'v'"

the 'f' and 'v' are actually a the same property now, so:

select from RelationIndex where f == 'roleA' && f == 'registered' && f

== '{User}' && f == '(lastName') && f > 'a.Smith:xJ8mFc9r' order by f
asc;

like that.

[Juraj Vitko]

So guys thanks for the good IRC chat:)

Basically even if this was implemented, it would be too costly on
resources.

What I needed, was to change my thinking to better fit App Engine. The
good thing is, that if one optimizes for App Engine, then his app will
run faster _everywhere_.

Basically, the best method for being able to show filtered data in a
Grid that can be sorted _and_ paged on any column, one needs to pre-
filter the data (upon created/update/delete) into separate kinds. This
filtered kind then can be sorted on using the default indexes, because
filter was already applied. Also, the data stored in this filtered
kind is not the exact copy of the original data, but rather its string
representation with unique suffixes to support lexicographical
ordering and no-equality-restart pagination.
The advantage of this is also that a much more sophisticated filtering
can be used, not just the built-in query operators.
One has to add logic to support recomputation of the filtered kind if
the filter code or sorting-enabled columns change as the app is
evolving, but that's a one time job and can be reused if done
properly.

[Philippe]

looks interesting, but I do not understand all.
how do you get back to your data (if I understood, you query on
specific kinds that are your pre-filtered value).
Do you get your data using ancestor ?

If you have time to give a short example, it will be great !
thank you,
Philippe

[Juraj Vitko]

Hi, yes, exactly - using filteredTableEntry.getKey().getParent() --
that way they can be updated in a single transaction too.

The filteredTableEntry can be created like new Entity
('FT_User_isClient', parentUserKey).

When any of the primary record (User in this example) data changes
(eg. the isClient field, or a value in one of the sortable columns), I
assume the fastest way to update the filtered entry is to overwrite it
with a new one, instead of fetching it first (I may be wrong here).
The only caveat is that when you generate a new unique suffix for the
new entry (which overwrites the previous one), the record might 'jump'
in the UI, ie in a Grid that is currently paged through.

[Philippe]

imagine you have a 100 000 data set.
each data has got 4 properties that you would like to use for
filtering.

then, you will have one Kind with your data, and 4 children Kinds for
the properties to be filtered.

you can then query each children kind in different queries. in this
case, 4 queries.
each query will give a maximum of 1000 entities.

for each query result, you will get the parent. and then, associate
those 4 lists of parents (remove duplicate, apply logic, ...).
if you want to get a complete result, you will add extra query to
solve the 1000 entities limit.

is this correct ?

On appengine, it seems to be the best way to use complex filter. but
requires a lot of queries.

[Juraj Vitko]

hi, this is unrelated to getting around the 1000 query results limit -
this is to get around the composite indexes limit.

re 4 filters: I would say you need to store permutations, so that you
don't have to do the post processing steps you mentioned, ie. if there
is filterA and filterB, let's say booleans, and there will be 3 grids
in the UI, one showing true,true, second true,false, and third
false,true, then you need 3 prefiltered tables (with each index
permutation).
Obfiously with too many permutations, the use of composite indexes +
dynamic filtering will be much cheaper, but you need to fit into the
100 indexes per app limit.