<div dir="ltr">Hi Jake!<br><br>At first I thought: "This is the great idea, we definitely should add such index". But then I start to analyze for which queries the index specified on the discriminator column (that is, on the `classtype` column) can improve performance. And it turns out that for most queries this index would not be useful: either because full table scan would be cheaper, or because the table already has some better index.<br><br>Let's consider some straw-man example to illustrate this. Let's say we have three classes: Person, Student and Teacher, and both Student and Teacher classes are inherited from the Person class:<br><br> class Person(db.Entity):<br> id = PrimaryKey(int, auto=True)<br> name = Required(unicode)<br> age = Required(int)<br><br> class Student(Person):<br> group = Required(Group)<br> gpa = Required(float)<br><br> class Teacher(Person):<br> dept = Required(Department)<br> degree = Required(unicode)<br><br>I don't describe Group and Department classes here, because they are irrelevant to the discussion.<br><br>To have some specific numbers, let's say we have a database which consist of 100 000 student and 1000 teachers. Each physical database page holds 50 records of persons, and the record of Student have the same size as the record of Teacher. These numbers are simplification, and the goal is not to be entire realistic, but to get some general estimations. With these numbers, the database will have 2020 pages of data. The records of students and teachers will be intermixed in the same table. If teacher records were distributed completely evenly, then about 1000 pages will have teacher records, one teacher record on each page. But let's say the teacher records are stored more compactly, and reside in 100 database pages. Each of this pages holds 10 teacher records and 40 student records.<br><br>So, we have:<br>- 2020 pages of data;<br>- 50 records per page;<br>- Each page holds student records, and some pages holds teacher records also;<br>- 100 pages with teacher records (10 teacher records and 40 student records per page).<br><br>####################################################################<br><br>Now, I want to list some example queries, for which we can analyze if the index on the discriminator column will give any benefits:<br><br>1) Access by primary key<br><br> s = Student[123]<br> t = Teacher[456]<br><br>2) Retrieve all instances of the specific class:<br><br> select(s for s in Student)<div> select(t for t in Teacher)<br><br>3) Retrieve instances of specific class with using some additional criteria:<br><br> select(s for s in Student if s.group.number == 101)<br> select(s for s in Student if s.gpa > 4)<br> select(s for s in Student if s.group.number == 101 and s.gpa > 4)<br> select(t for t in Teacher if t.dept.number == 2)<br> select(t for t in Teacher if t.degree == "Professor" and t.age > 60)<br><br>4) Aggregations<br><br> # max gpa for each group of students<br> select((s.group.number, max(s.gpa)) for s in Student)<br><br> # average professor age for each department<br> select((t.dept.number, avg(t.age)) for t in Teacher if t.degree == "Professor")<br><br>Now, let's analyze which queries may get speedup from the additional index on the discriminator column.<br><br></div><div>####################################################################<br><br>1) Access by primary key. This type of queries will not be benefited from new index, because access by PK is already the most efficient.<br><br>2) Retrieve all instances of specific class<br><br> select(s for s in Student)<br><br>The student records are placed in all data pages. The most efficient way to retrieve all student is to perform full table scan. New index on the discriminator column will not speedup this query.<br><br> select(t for t in Teacher)<br><br>There are two ways to perform this query: (1) full table scan and (2) index-based access using the index on the discriminator column. The full table scan uses sequential access to the disk, and the index-based query uses random access. For traditional drives with rotated disks the random access is around 100 times slower then the sequential access. Because of this, in order to obtain benefits from the index-based scan, the pages with the teacher's records should represent less then 1% of all pages. In our case, the teacher records spread across 10% of all pages, so full table scan will be much faster then index-based query.<br><br>For SSD drives the difference between sequential and random access is not so big, the random access may be just 5-10 time slower then the sequential access. Hence, for SSD drives, index-based access starts to be more efficient when teacher records placed in less then 10-20% of the pages. In our example, teacher records placed in 10% of all pages, so, when using SSD drive, the index-based query may be a bit more efficient then the full-table scan.<br><br>3) Retrieve instances of specific class with using some additional criteria:<br><br> select(s for s in Student if s.group.number == 101)<br><br>The new index on discriminator column will not give any benefits here, because we already have much better index based on the `group_id` column.<br><br> select(s for s in Student if s.gpa > 4)</div><div><br></div><div>The most efficient way to do this query is to perform full-table scan. The index on the discriminator column will not be useful here.<br><br></div><div> select(s for s in Student if s.group.number == 101 and s.gpa > 4)<br></div><div><br></div><div>The existing index on `group_id` column will work very good for this query, and the index based on the discriminator column will be slower then the full-table scan.</div><div><br></div><div> select(t for t in Teacher if t.dept.number == 2)<br><br></div><div><div>The most efficient way to perform this query is to use existing index on the `dept_id` column.</div></div><div><br></div><div> select(t for t in Teacher if t.degree == "Professor" and t.age > 60)<br><br>The most efficient way to perform this query is to use specialized composite index based on columns `degree` and `age`. Without this index, the most efficient way for HDD drive will be the full-table scan, and for SSD the index based on the discriminator column may be a bit better then the full-table scan.<br><br>4) Aggregations<br><br> # max gpa for each group of students<br> select((s.group.number, max(s.gpa)) for s in Student)<br><br>The most efficient way is to use composite index based on columns `group_id` and `gpa`. This way the query may be performed as index-only scan. The next best way is to use existing index based on the `group_id` column.<br><br> # average professor age for each department<br> select((t.dept.number, avg(t.age)) for t in Teacher if t.degree == "Professor")<br><br>The most efficient way is to use composite index based on columns `dept_id` and `age`. This way the query may be performed as index-only scan. The next best way is to use existing index based on the `dept_id` column.<br><br>####################################################################<br><br></div><div>To summarize: this is the queries which *may* perform marginally better on SSD drives when the table have the index based on the discriminator column:<br><br>1) All instances of the specific subclass which have small total number of instances:<br><br> select(t for t in Teacher)<br><br>2) Filtering the subclass with small number of instances using the criteria based on some non-indexed columns:<br><br> select(t for t in Teacher if t.degree == "Professor" and t.age > 60)<br><br>But the additional index on discriminator column will benefit this queries only if records of this specific class are placed in less then 1% of total number of pages (for HDD drives), or less then 10% of total number of pages (for SSD drives).<br><br>All other analyzed queries will not benefit from the suggested index, either because full-table scan works better, or because the table already have much better index.<br></div><div><br>Looking on these numbers, I don't think that we should automatically index discriminator column - the benefit of this is just not too big, and maintaining additional index will slow down inserts. Anyway, if somebody want to add index based on the discriminator column it is relatively easy to do, you just need to define discriminator column explicitly and make it indexed. It may be done this way:<br><br> class Person(db.Entity):<br> id = PrimaryKey(int, auto=True)<br> classtype = Discriminator(str, index="classtype_idx")<br> name = Required(unicode)<br> age = Required(int)<br><br><br>Regards,<br>Alexander Kozlovsky<br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Sep 23, 2014 at 4:28 AM, Jake Austwick <span dir="ltr"><<a href="mailto:jake.austwick@gmail.com" target="_blank">jake.austwick@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div>
When you inherit one model from another within Pony, it uses the method of just having one table and storing the class type in the `class type` column. Would it not be sensible for this column to automatically be indexed? It's clearly going to be used in queries to separate out the different types of classes, otherwise inheritance wouldn't have been used in the first place.
</div><div><br></div><div>Thoughts?</div>
<div><div><br></div><div><span style="font-size:10pt">Thanks,</span></div><div><span style="font-size:10pt">------------------</span></div><div><span style="font-size:10pt">Jake</span></div><div><a href="http://jakeaustwick.me/" style="color:rgb(0,106,227);background-color:rgb(255,255,255)" target="_blank">http://jakeaustwick.me/</a></div><div></div><div></div></div>
<br>_______________________________________________<br>
ponyorm-list mailing list<br>
<a href="mailto:ponyorm-list@ponyorm.org">ponyorm-list@ponyorm.org</a><br>
<a href="/ponyorm-list" target="_blank">/ponyorm-list</a><br>
<br></blockquote></div><br></div></div>