On 7/29/13 9:45 PM, Kostas Jakeliunas wrote:

Hi Karsten,

(not sure whom to CC and whom not to, I have a couple of fairly specific technical questions / comments (which (again) I should have delved into earlier), but then again, maybe the scope of the tor-dev mailing list includes such cases..)

@tor-dev: This is in regard to the Searchable metrics archive project, intersected with Onionoo stuff.

I originally wanted to ask two questions, but by the time I reached the middle of the email, I wasn't anymore sure if they were questions, so I think these are simply my comments / observations about a couple of specific points, and I just want to make sure I'm making general sense. :)

..So it turns out that it is very much possible to avoid Postgres sequential scans - to construct such queries/cases which are best executed using indexes (the query planner thinks so, and it makes sense as far as I can tell) and whatever efficient (hm, < O(n)?) search algorithms are deemed best - for the metrics search backend/database; the two things potentially problematic to me seem to be:

• when doing ORDER BY, making sure that the resulting SELECT covers /

would potentially return a relatively small amount of rows (from what I've been reading / trying out, whenever a SELECT happens which may cover > ~10-15% of all the table's rows, sequential scan is preferred, as using indexes would result in even more disk i/o, whereas the seq.scan can read in massive(r) chunks of data from disk because it's, well, sequential). This means that doing "ORDER BY nickname" (or fingerprint, or any other non-unique but covering-a-relatively-small-part-of-all-the-table column in the network status table) is much faster than doing e.g. "ORDER BY validafter" (where validafter refers to the consensus document's "valid after" field) - which makes sense, of course, when you think about it (ordering a massive amount of rows, even with proper LIMIT etc. is insane.) We construct separate indexes (e.g. even if 'fingerprint' is part of a composite (validafter + fingerprint) primary key), and all seems to be well.

I've been looking into the Onionoo implementation, particularly into ResourceServlet.java [1], to see how ordering etc. is done there. I'm new to that code, but am I right in saying that as of now, the results (at least for /summary and /details) are generally fairly unsorted (except for the possibility of "order by consensus_weight"), with "valid_after" fields appearing in an unordered manner? This of course makes sense in this case, as Onionoo is able to return *all* the results for given search criteria (or, if none given, all available results) at once.

This is correct. Onionoo only allows ordering by consensus_weight, because I only added features when we came up with new use cases.

The obvious problem with the archival metrics search project (argh, we are in need of a decent name I daresay :) maybe I'll think of something.. no matter) is then, of course, the fact that we can't return all results at once. I've been so far assuming that it would therefore make sense to return them, whenever possible (and if not requested otherwise, if "order" parameter is later implemented), in "valid_after" descending order. I suppose this makes sense? This would be ideal, methinks. So far, it seems that we can do that, as long as we have a WHERE clause that is restricting-enough.

select * from (select distinct on (fingerprint) fingerprint, validafter,

...

nickname from statusentry where nickname like 'moria1' order by fingerprint, validafter desc) as subq order by validafter desc limit 100;

, for example, works out nicely, in terms of efficiency / query plan, postgres tells me. (The double ORDER BY is needed, as postgres' DISTINCT needs an ORDER BY, and that ORDER BY's leftmost criterion has to match DISTINCT ON (x))

Now, you mentioned / we talked about what is the (large, archival metrics) backend to do about limiting/cutoff? Especially if there are no search criteria specified, for example. Ideally, it may return a top-most list of statuses (which in /details include info from server descriptors), sorted by "last seen" / "valid after"? Thing is, querying a database for 100 (or 1000) of items with no ORDER BY Is really cheap; introducing ORDER BYs which would still produce tons of results is considerably less so. I'm now looking into this (and you did tell me this, i.e. that, I now think, a large part of DB/backend robustness gets tested at these particular points; this should have been more obvious to me).

But in any case, I have the question: what *should* the backend return (when no search parameters/filters specified, or very loose ones (nickname LIKE "a") are?

What would be cheap / doable: ORDER BY fingerprint (or digest (== hashed descriptor), etc.) It *might* (well, should) work to order by fingerprint, limit results, and *then* reorder by validafter - with no guarantee that the topmost results would be with highest absolute validafters. I mean, Onionoo is doing this kind of reordering / limiting itself, but it makes sense as it can handle all the data at once (or I'm missing something, i.e. the file I linked to already interacts with a subset of data; granted, I haven't thoroughly read through.) In our/this case, it makes sense to try and outsource all relational logic to ORM (but of course if it turns out we can cheaply get 100 arbitrary results and more easily juggle with them ourselves / on the (direct) python side, then sure.)

But would such arbitrary returned results make sense? It would look just like Onionoo results, but - a (small) subset of them.

Can you rephrase this question, say, in a sentence or two? I'm having a hard time getting what you're asking for.

Making a few random statements here, in case one of them addresses the issue you're having:

- Ordering is important even if no WHERE statement is given or if the WHERE statement matches a lot of rows. Think of the relay-search application when you look for all relays with nickname U* (like in "Unnamed" which is very frequent). You want to be sure to find the last relays in the database, not a random subset.

- You might want to look into multi-key indexes, e.g., an index on (validafter, nickname). It could be that PostgreSQL uses them instead of a sequential search.

- It might make sense to write a set of test selects and check them against your expected query strategies. Maybe there are tools for this, but if there are no tools, simply run each query using EXPLAIN ANALYZE and parse the output for keywords indicating sequential scan, index scan. Then create indexes and re-run your test script to find out if they improve things or not.

- Also look into insertion speed when you create lots of indexes. That is, once you're happy with query speed, import another month of data to see if that still happens in reasonable time.

Ramble #2: Onionoo is doing more or less direct (well, compiled, so efficient) regexps on fingerprint, nickname, etc. By default, "LIKE %given_nickname_part%" is again (sequentially) expensive; Postgres does offer full text search extensions (would need to build additional tables, etc.), and I think this makes sense to be done; it would cover all our "can supply a subset of :param" bases. I'll see into this. (It's also possible to construct functional(istic) indexes, e.g. with regexp, but need to know the template - I wonder if using Onionoo's regexpressions would work / make sense - will see.) For now, LIKE/= exact_string is very nice, but of course the whole idea is that it'd be possible to supply substrings. Of note is the fact that in this case, LIKE %substring% is O(n) in the sense that query time correlates with row count, afaict. As of now, full text search extensions would solve the problem I think, even if they may look a bit like an overkill at first.

Again, not sure if I understand the question. A few possible answers:

- Feel free to restrict searches to things you can implement efficiently. It's better to exclude an expensive query and force the user to think about a better way to query, than to offer that search option and let the user sit waiting for a long time.

- You can prepare columns for searching to make queries much faster. For example, you could store LOWER(nickname) in addition to nickname if you're going to do lower-case searches for nickname anyway; that's what relay search does. Or you can store the first 16 bits of IP addresses in a separate column to narrow down search results quickly; that's what ExoneraTor in metrics-web.git does. Or you can store descriptors in monthly tables to keep indexes small; that's what relay search does.

End of an email without a proper direction/point. :)

Well, now looking into your other mails in this thread.

(Hint: in general, if you want me to reply quickly, please write a single mail with clear comments or questions, not one that you need to correct/extend three times within an hour. Maybe simply leave it sitting in your drafts folder for an hour until you're sure it's what you want to say. Thanks!)