Reconsidering access paths for index ordering… a dangerous optimization… and a fix!

MySQL has had an interesting optimization for years now1, which has popped up from time to time: in certain circumstances, it may choose to use an index that is index-wise less efficient, but provides the resulting rows in order, to avoid a filesort of the result.

What does this typically look like in production? A query that seems simple and easy takes much longer than it should, sometimes. (Perhaps in production, the query gets killed by pt-kill or exceeds the max_execution_time provided.) The query could be very simple indeed:

SELECT ... WHERE `other_id` = 555 ORDER BY `id` ASC LIMIT 1

There’s an index on other_id, and running the query with an appropriate USE INDEX, the query is fast. Even weirder, changing the query to use LIMIT 10 causes it to run lightning-fast! If anything, the LIMIT 1 should be faster… so, what gives?

Looking at the EXPLAIN, you may notice that the LIMIT 1 version is using access type index on the PRIMARY key (in this case id), whereas the LIMIT 10 version is using ref on a secondary key. Access type index means a full-index scan… on the primary key… which is the clustered key… which is a full table scan.

The optimization is hoping that the LIMIT n with a small enough limit will allow execution to be completed early, without scanning many rows, once the LIMIT is satisfied. This hope is often misplaced: there is no guarantee that there will be any matching rows in the first m rows of the table when ordered by the unwisely-chosen index. Hope is not a strategy.

Although the underlying issue had been reported several times already, under various circumstances, since there were so many individual bugs reported, I filed a new bug with a summary of the situation… and a patch: MySQL Bug 97001.

On MySQL Bug 97001, I proposed a solution (and provided a patch, submitted to Oracle under the NDA) introducing a new optimizer_switch flag named reconsider_index_for_order (defaulting to on to duplicate the current behavior). Although this optimization might benefit some queries, it’s too dependent on the actual data in the involved tables, so it’s not a good candidate for a general optimizer feature in my opinion. Maybe the default could eventually be off allowing users to opt into this optimization when they want it but providing compatible default behavior.

1 The underlying optimization actually appears to be have roots in some very old code, most importantly probably one specific commit in 5.1.

Wireless Programming for FTC Robots

Last Updated: September 11, 2017

[An abbreviated version of this concept was presented at the 2017-2018 FTC season kickoff in Reno, Nevada on September 9, 2017. The slides are available.]

What is the problem?

Programming an FTC robot normally requires the user to connect the robot’s Android device (phone) to the computer via USB and press the “Run” [▶] button in Android Studio. This means getting up from the comfy chair, removing the device from the robot, plugging it into the computer, and then reconnecting it to the robot. This is slow and inefficient. This also means repeatedly unplugging and plugging the Micro-B USB connectors, which are fragile and easily broken. What if that wasn’t necessary?

How-to

To get straight to the “how-to” and skip the explanation of how or why this works (and if it’s okay to lose Internet access on the PC while programming or debugging the robot), see the following three most important sections:

  1. Simple: Join the WiFi Direct network from the PC
  2. Add several useful “External Tools” for ADB to Android Studio
  3. Connect wirelessly to program and debug an FTC robot

To avoid losing WiFi internet access on the PC while programming or debugging the robot, see the following additional sections:

  1. Appendix: USB WiFi Models – Acquire a small WiFi adapter.
  2. More elegant: Add a second WiFi adapter to the PC

Otherwise, on to the explanation!

What is ADB?

The Android Debug Bridge (ADB) protocol allows Android Studio to communicate via the adb program with the device, normally attached via USB. ADB allows programs to be stopped and started, files to be copied to or from the device, new APKs to be installed, running processes’ CPU and memory to be monitored, and logs to be accessed (amongst many other actions). When pressing the “Run” [▶] button in Android Studio, adb is used to copy the resulting APK file to the device and install it.

Using ADB over a network

The ADB protocol can be used over a network, so long as it is enabled on the device, via USB, after each time the device has been rebooted. This can be accomplished by running an adb tcpip command to enable TCP/IP (network) access to ADB on the device. This is normally accomplished by running the adb tcpip command (specifying which TCP/IP port to listen on) from the command-line1, while the device is attached via USB:

adb tcpip 5555

Once ADB over TCP/IP has been enabled (in this case on TCP port 5555), any computer can be connected to it over the network by running an adb connect command (and accepting access on the device when prompted):

adb connect 1.2.3.4:5555

The IP address “1.2.3.4” must be replaced with the IP address2 of the Android device being connected to. Once the device is connected over TCP/IP, Android Studio can be used exactly as though it were connected via USB.

A big snag: The FTC Robot Controller uses WiFi Direct

This is where things get somewhat interesting, and specific to FTC robots. The FTC Driver Station and Robot Controller apps use WiFi Direct to communicate with each other. (And normally are disconnected from all other WiFi networks.) This establishes a private WiFi network between the two devices – so, normally, the two devices are not on the same wireless network as the PC where Android Studio is running. There are two solutions to this, but both involve getting the PC onto the same network with the Android devices.

Simple: Join the WiFi Direct network from the PC

It is possible to join the WiFi Direct network created by the FTC Robot Controller app from a PC. The name of the WiFi Direct network is usually known by the team because it’s based on the device name, which is visible in the FTC apps: something like “DIRECT-xy-1234-RC”3. If an attempt is made to join the network from a PC, though, a password is needed to do so. This password can be found using the “Program & Manage” screen in the Robot Controller app’s main menu.

Once the passphrase has been obtained, any PC (or other device) can join its network by selecting the Robot Controller’s network name from the list of WiFi networks on the PC, and using that passphrase for the WiFi password when prompted. Once the PC has successfully joined the WiFi Direct network, ADB can be connected using the Robot Controller’s WiFi Direct IP address (instead of the one obtained from the Android settings menu), which is always 192.168.49.1.

However, this poses a different problem: Now the PC is no longer on the Internet. If while programming, it’s necessary to communicate with team members, use Google to search documentation, or use GitHub to manage code, this becomes very awkward, and would require frequently switching networks, which defeats a lot of the point of this exercise.

More elegant: Add a second WiFi adapter to the PC

A PC is actually quite happy to coexist simultaneously on multiple WiFi (or other) networks, so long as each network has a different IP address scheme. The WiFi Direct network created by the Robot Controller uses 192.168.49.x IP addresses, so as long as the local home/work/school WiFi network uses some other scheme (10.x.y.z or 192.168.0.x are quite typical) then there will be no conflicts.

In order to join the second network, the PC will need an additional WiFi adapter, but fortunately these are quite cheap and very small today: see Appendix: USB WiFi Models for several available models.

After installing the drivers for the new WiFi adapter and plugging it in, simply join the Robot Controller’s WiFi Direct network using the above instructions, but using the new WiFi adapter instead of the computer’s main WiFi adapter. Once connected in this way, the PC should be remain connected to the main WiFi network, and should still have Internet access through that network, while also being able to communicate with the Android device over WiFi Direct.

One possible problem, however, is that the order in which the network devices are connected (or their priority as network adapters) can mean that Internet access may not be available while connected to the Wi-Fi Direct with the second adapter, because Wi-Fi Direct provides an Internet (default) route–even though the device doesn’t itself have Internet access–and the PC may try to use it instead of the other WiFi connection.

This, too, is fixable:

  • On Mac OS X, open the System Preferences and then the Network pane. Click the “gear” icon and select “Set Service Order…” and drag the entries to put “Wi-Fi” above the second Wi-Fi adapter (in the case of the TP-Link adapter, named “802.11n NIC”).
  • On Windows, this problem has not been observed.

Making ADB over TCP/IP easy to use with Android Studio

One additional problem with the above solution is the need to use the adb command – from a command line – to enable TCP/IP and connect to the device. However this is not entirely necessary, either. It can be made to be extremely easy to use in Android Studio!

Add several useful “External Tools” for ADB to Android Studio

Android Studio allows the creation of “External Tools”, which will appear in the main window’s “Tools” menu. These tools can do just about anything, but they can easily be used to run adb commands so that using the command line is no longer required.

In Android Studio, open the main settings panel:

  • On Mac OS, click “Android Studio”, then “Preferences…” (or simply press the hotkey “⌘,”).
  • On Windows, click “File”, then “Settings…”.

In the settings panel:

  1. Expand the “Tools” item
  2. Click “External Tools” to open the External Tools list. The list is normally empty.
  3. For each of the following tools below, click the [+] button, and fill in the provided fields (leaving all others unchanged). Once each tool screen is filled-in, click “OK” to save. (Note: The “Program” field is the same, so the value can be cut and pasted to avoid re-typing.)
  4. Once all tools have been added, click the main settings panel’s “OK” button to save.

“Enable ADB over TCP/IP”

Field Value
Name: Enable ADB over TCP/IP
Program: $ModuleSdkPath$/platform-tools/adb
Parameters: tcpip 5555

“Connect to ADB over WiFi Direct”

Field Value
Name: Connect to ADB over WiFi Direct
Program: $ModuleSdkPath$/platform-tools/adb
Parameters: connect 192.168.49.1:5555

Bonus: To program the device over a non-WiFi Direct network

The following External Tool is not necessary for programming FTC robots over WiFi Direct, but can be added in order to program any Android device via any other WiFi network. It will prompt for the IP address to connect to.

“Connect to ADB over TCP/IP”

Field Value
Name: Connect to ADB over TCP/IP
Program: $ModuleSdkPath$/platform-tools/adb
Parameters: connect $Prompt$:5555

Connect wirelessly to program and debug an FTC robot

Once the above External Tools are added, connecting to an FTC robot wirelessly to program it and debug it is trivial (after having used USB to program the device at least once4). After each reboot of the Android device (and it doesn’t hurt any other time), follow these steps:

  1. Connect the robot’s Android device to the PC via USB.
  2. Ensure that a file (such as an OpMode) is open and the cursor is in that window5.
  3. Click Tools → External Tools → “Enable ADB over TCP/IP” to enable ADB.
  4. Disconnect the USB cable from the Android device and ensure the computer is connected to the WiFi Direct network with its WiFi adapter.
  5. Ensure the “FTC Robot Controller” app is running on the Android device.
  6. Click Tools → External Tools → “Connect to ADB over WiFi Direct” to connect to ADB.

After the above steps, it may be useful to open the Android Monitor and ensure the connected device is selected in the device drop down (there may be a “[DISCONNECTED]” entry as well, from the previous USB connection; it is not the correct one).

Android Studio should work exactly the same as when it’s connected via USB: the “Run” [▶] button should transfer new APKs to the Android device, and Android Monitor will work even while the robot is running.

A bonus: Use Android Monitor logcat in real time!

Since the device can now remain connected via ADB while the robot is running… that also means that Android Monitor is usable while the robot is running. If the Android logging API (android.util.log) is used to log messages in a program, they will appear in the Android Monitor’s logcat in real time!

Appendix: USB WiFi Models

The author has purchased the below WiFi adapters and tested some of them in the course of writing this document. Reports of good or bad results with additional USB WiFi adapters is welcome either in the comments below or by email.

Nano USB WiFi Adapters

These adapters are small enough not to protrude annoyingly from a laptop computer, and should allow use of a laptop sleeve or case without removal of the device.

TP-Link N150 Wireless Nano USB Adapter (TL-WN725N)

Price: ≈$10 (March 2017, Amazon.com).
Works on Mac OS X and Windows. Have had many signal reception issues on MacBook Pro, possibly caused by antenna not protruding far enough from metal casing. Switched to D-Link DWA-131.

Mini USB WiFi Adapters

These adapters are small (similar in size to a USB thumb drive) but will have to be removed before use of a laptop sleeve or case.

D-Link Wireless N USB Wi-Fi Network Adapter (DWA-131)

Price: ≈$25 (March 2017, Amazon.com).
Works on Mac OS X and Windows. Excellent signal reception and no driver issues on Mac OS X. Appears as a wired-Ethernet adapter with a special app (in the status bar) to configure the WiFi network. Exactly the same chipset as TP-Link N150 (clone of the drivers and app).

NETGEAR AC600 Dual Band Wi-Fi USB Mini Adapter (A6100)

Price: ≈$31 (March 2017, Amazon.com).
Windows-only.

Linksys Wireless Mini USB Adapter AC 580 Dual Band (AE6000)

Price: ≈$28 (March 2017, Amazon.com).
Windows-only.

Happy wireless programming!

1 “Command Prompt” / “CMD” in Windows or “Terminal” in Mac OS.

2 An Android device’s WiFi IP address can be found by going to the Global Settings → “About phone” → “Status” and checking “IP address” field.

3 The network always starts with “DIRECT” followed by two random letters/numbers, followed by the device name. The device name is required by the FTC game manual rule <RS01> to match this pattern.

4 The FTC Robot Controller app is responsible for creating the WiFi Direct network, so if the app doesn’t exist on the device, it will not be possible to start it to connect over WiFi Direct. Connect the device over USB and program it that way the first time, start the app as instructed, and then wireless programming should work.

5 If the cursor is not in an Android-related file, running the External Tools from this guide may fail with an error about not finding “/platform-tools/adb” – because the $ModuleSdkPath$ macro used in the External Tool definition will not have been filled with the appropriate Android SDK path. To make the External Tool work with any cursor location, just replace the $ModuleSdkPath$ macro with its actual value, which can be found by clicking “Insert macro…” and selecting $ModuleSdkPath$. The downside of this solution is that if the path changes (for instance due to an upgrade), the External Tool entry may cease to work anymore.

Black History Month

[This was originally posted on Facebook, but has been copied here and backdated appropriately.]

This month – February – is Black History Month.

This month is not about me, but I hope that you will all bear with me for a moment and forgive me as I use the word “I” more than I should:

I was born in Tennessee – the American South – and despite many of my peers being people of color and various races, I was raised as a product of the white-centric American education system. That means, basically, that my understanding of black history amounted to little more than “we used to be mean to black people and call them names [whispering: and hang a few], but we stopped doing that a long time ago and made them EQUAL, and now they just like to do drugs and riot a lot about what happened in the past”.

I accepted this completely wrong “definition” of Black history (and present), not knowing any better, for a long time. Not because I thought it was right, but because it didn’t materially affect me. As an utterly privileged white male, I never really thought much about it. I accepted that it was normal to occasionally hear denigrating comments towards people of any color or of non-Christian religions – it’s the South, after all! I accepted that some of my family just “didn’t like black people”, and that was normal, right? I accepted that it was all just good fun, and everybody jokes, and jokes are harmless, right? I accepted that it was normal to hear people joke about “ebonics” or to mock religious practices or clothing.

I personally didn’t like it, and I attempted not to participate or encourage it, but I accepted it, and I admit that I certainly did participate on occasion.

I now accept that I was wrong, and that I can do better.

I contributed – even if primarily passively – to racism, to discrimination, to hurting people, and I refuse to do that or accept it from anyone else any longer.

I ignored or looked away or walked away far too often, and I refuse to ignore or look away or walk away any longer.

I ignored Black History Month, because I am not black. That was wrong, too.

Black History Month is not about or for black people celebrating black history – having a beer and toasting Dr. King, as I perhaps previously imagined – it’s for everyone (and especially everyone that’s not black). It’s about recognizing the impacts that everyone has had on black history, and especially how those impacts have molded and shaped what it means to be black in America. Many of those impacts have been negative and uncomfortable for white people like myself. Many of those impacts have been positive (and unfortunately often still uncomfortable for white people!).

This month is about recognition – both the joyous and the solemn kind. This month is also about, after achieving some recognition, offering unguarded praise and optimism for black innovation and advances, offering condolences for black sacrifice, shedding tears for black repression and suffering, and offering your heart to accepting and embracing Black History.

Black History Month is not about making blacks equal to whites somehow by giving them a month and marking it on everyone’s calendars. It’s about having the fortitude and compassion and sense to both accept the ugly past, and commit to making blacks and Black Future BETTER than your own. After all, by embracing each other, acknowledging and embracing our differences, and pushing each other higher, nobody actually gets left behind – we all rise up together.

You are black. I see that you are black. I love your blackness. I am sorry for everything. I love you. I will fight for you.

Join me… Invest in Humanity, too

In Invest in Humanity 2016 I introduced my project to “invest” an initial $60,000, by supporting groups/organizations all around the country, with a singular goal: to improve humanity. It’s still going strong, in fact we’ve now given about 75% of the budget—almost $47,000—to 118 different organizations. You can read a bit more and see the current list of organizations and causes we’ve supported at InvestInHumanity2016.com.

Will you join me, and Invest in Humanity, too?

I started this project as an experiment, and with the hope that I could inspire at least a few others to follow me, and invest in humanity along with me. It’s going to take a little bit from a lot of us to make a dent in really improving and furthering humanity. So now I’d like to put out a call to do just that: Will you choose to invest in bettering humanity? I’d love to see people join me at both ends of the scale spectrum:

If you can make one small donation to just one organization which helps/benefits people in other areas or circumstances, every bit helps.

If, however, you have the resources to do something bigger and grander… perhaps even similar to what I’ve been doing, I’d be happy to talk to you about how it’s worked and help you along, or even do much of the work for you. Feel free to reach out to me any time at jeremy@investinhumanity2016.com.

With all of your help, we can and we will build a society that is collectively better than any of us could be individually.

Invest in Humanity 2016

This being Thanksgiving Day, I thought I’d share something I’ve been working on for the past few weeks.

Just after the election, I wrote about the initial constructive steps I decided to take to combat the racism, sexism, misogyny, homophobia, xenophobia, and hate which dominated the 2016 election cycle. Although I initially wrote that post (and on Facebook rather than this blog) and took actions immediately due to my disappointment at the present state of the election, I knew that I wanted to do something bigger. Over the course of a couple of days of thinking it through, I formulated a plan and decided to call it Invest in Humanity 2016.

To that end, I set aside $60,000 (inclusive of my initial donations) to “invest” in causes far and wide which work to advance humanity. However, I also realize that the problems faced by different groups and the challenges known by people of different life experiences are not universal… so I knew I wanted to do something a bit unique to reach people I would not have reached by myself. I recruited several fairly diverse groups of friends (which I called “teams”), with their diverse experiences and gave each team an individual donation budget to manage. Each team has been fully responsible for finding causes they want to support, vetting them, and deciding how to support them and how much support they’d like to give. I’ve taken care of the bookkeeping and of course provided the funds. I’ve provided only very broad guidance rather than any rules or requirements for causes to support.

The teams have been busy! As of right now, we have supported 39 different organizations with a total of $21,850 in donations—but we’re just getting started.

The organizations we’ve supported so far include:

  • ACLU Nationwide
  • Alliance for Multicultural Community Services
  • Amaanah Refugee Services
  • American Humanist Association
  • Border Network for Human Rights
  • Center for Reproductive Rights
  • FairVote
  • Family Promise of Knoxville
  • Food Bank of Northern Nevada
  • Gender Diversity
  • Girls on the Run
  • Houston Food Bank
  • International Refugee Assistance Project
  • Kids In Need of Defense (KIND)
  • Knox Area Rescue Ministries
  • Literacy Advance of Houston
  • Mexican American Legal Defense and Educational Fund
  • NAACP
  • National Immigrant Justice Center
  • National Organization for Women
  • Natural Resources Defense Council
  • Our Center
  • Planned Parenthood
  • RAINN
  • Reno Works c/o Volunteers of America
  • Reproductive Health Access Project
  • Sierra Club, Lone Star Chapter
  • Southern Poverty Law Center
  • The FAYCO Foundation
  • The Love Kitchen
  • The Nature Conservancy
  • The Reno Initiative for Shelter and Equality
  • The Trevor Project
  • The Young Center for Immigrant Children’s Rights
  • Trans LifeLine
  • Transgender Allies Group
  • Transgender Law Center
  • UNR Resettlement and Placement
  • YMCA of Greater Houston

I’ve set up a small (and currently very simple) web site related to this effort at InvestInHumanity2016.com. If you’re interested in investing in humanity as well, please reach out to me. I’d love to hear from you. If you represent a charity or other cause (registered or not) and could use our support, please reach out as well!